Back to basics; for-loops, arrays/vectors/lists, and optimization

Question

I was working on some code recently and came across a method that had 3 for-loops that worked on 2 different arrays.

Basically, what was happening was a foreach loop would walk through a vector and convert a DateTime from an object, and then another foreach loop would convert a long value from an object. Each of these loops would store the converted value into lists.

The final loop would go through these two lists and store those values into yet another list because one final conversion needed to be done for the date.

Then after all that is said and done, The final two lists are converted to an array using ToArray().

Ok, bear with me, I'm finally getting to my question.

So, I decided to make a single for loop to replace the first two foreach loops and convert the values in one fell swoop (the third loop is quasi-necessary, although, I'm sure with some working I could also put it into the single loop).

But then I read the article "What your computer does while you wait" by Gustav Duarte and started thinking about memory management and what the data was doing while it's being accessed in the for-loop where two lists are being accessed simultaneously.

So my question is, what is the best approach for something like this? Try to condense the for-loops so it happens in as little loops as possible, causing multiple data access for the different lists. Or, allow the multiple loops and let the system bring in data it's anticipating. These lists and arrays can be potentially large and looping through 3 lists, perhaps 4 depending on how ToArray() is implemented, can get very costy (O(n^3) ??). But from what I understood in said article and from my CS classes, having to fetch data can be expensive too.

Would anyone like to provide any insight? Or have I completely gone off my rocker and need to relearn what I have unlearned?

Thank you

Answer 1

The best approach? Write the most readable code, work out its complexity, and work out if that's actually a problem.

If each of your loops is O(n), then you've still only got an O(n) operation.

Having said that, it does sound like a LINQ approach would be more readable... and quite possibly more efficient as well. Admittedly we haven't seen the code, but I suspect it's the kind of thing which is ideal for LINQ.

Answer 2

Am I understanding you correctly in this?

You have these loops:

for (...){
  // Do A
}

for (...){
  // Do B
}

for (...){
  // Do C
}

And you converted it into

for (...){
  // Do A
  // Do B
}
for (...){
  // Do C
}

and you're wondering which is faster?

If not, some pseudocode would be nice, so we could see what you meant. :) Impossible to say. It could go either way. You're right, fetching data is expensive, but locality is also important. The first version may be better for data locality, but on the other hand, the second has bigger blocks with no branches, allowing more efficient instruction scheduling.

If the extra performance really matters (as Jon Skeet says, it probably doesn't, and you should pick whatever is most readable), you really need to measure both options, to see which is fastest.

My gut feeling says the second, with more work being done between jump instructions, would be more efficient, but it's just a hunch, and it can easily be wrong.

Answer 3

For referemce,

the article is at What your computer does while you wait - Gustav Duarte

Also there's a guide to big-O notation.

---

It's impossible to answer the question without being able to see code/pseudocode. The only reliable answer is "use a profiler". Assuming what your loops are doing is a disservice to you and anyone who reads this question.

Answer 4

... working on one piece of data but with two functions can sometimes make it so that code to act on that data doesn't fit in the processor's low level caches.

for(i=0, i<10, i++ ) {
  myObject object = array[i];
  myObject.functionreallybig1(); // pushes functionreallybig2 out of cache
  myObject.functionreallybig2(); // pushes functionreallybig1 out of cache
}

vs

for(i=0, i<10, i++ ) {
  myObject object = array[i];
  myObject.functionreallybig1(); // this stays in the cache next time through loop
}


for(i=0, i<10, i++ ) {
  myObject object = array[i];
  myObject.functionreallybig2(); // this stays in the cache next time through loop
}

But it was probably a mistake (usually this type of trick is commented)

When data is cycicly loaded and unloaded like this, it is called cache thrashing, btw.

This is a seperate issue from the data these functions are working on, as typically the processor caches that separately.

Answer 5

Aside from cache thrashing on large functions, there may be benefits on tiny functions as well. This applies on any auto-vectorizing compiler (not sure if Java JIT will do this yet, but you can count on it eventually).

Suppose this is your code:

// if this compiles down to a raw memory copy with a bitmask...
Date morningOf(Date d) { return Date(d.year, d.month, d.day, 0, 0, 0); }

Date timestamps[N];
Date mornings[N];

// ... then this can be parallelized using SSE or other SIMD instructions
for (int i = 0; i != N; ++i)
    mornings[i] = morningOf(timestamps[i]);

// ... and this will just run like normal
for (int i = 0; i != N; ++i)
    doOtherCrap(mornings[i]);

For large data sets, splitting the vectorizable code out into a separate loop can be a big win (provided caching doesn't become a problem). If it was all left as a single loop, no vectorization would occur.

This is something that Intel recommends in their C/C++ optimization manual, and it really can make a big difference.

Answer 6

Well, you've got complications if the two vectors are of different sizes. As has already been pointed out, this doesn't increase the overall complexity of the issue, so I'd stick with the simplest code - which is probably 2 loops, rather than 1 loop with complicated test conditions re the two different lengths.

Actually, these length tests could easily make the two loops quicker than a single loop. You might also get better memory fetch performance with 2 loops - i.e. you are looking at contiguous memory - i.e. A[0],A[1],A[2]... B[0],B[1],B[2]..., rather than A[0],B[0],A[1],B[1],A[2],B[2]...

So in every way, I'd go with 2 separate loops ;-p

Answer 7

Thank you every one for the information. Thinking in terms of Big-O and how to optimize has never been my strong point. I believe I am going to put the code back to the way it was, I should have trusted the way it was written before instead of jumping on my novice instincts. Also, in the future I will put more reference so everyone can understand what the heck I'm talking about (clarity is also not a strong point of mine :-/).

Thank you again.