Why is one loop slower than 2 in C?

http://stackoverflow.com/questions/8547778/why-is-one-loop-so-much-slower-than-two-loops

by rkalla • 15 years ago

191 41 15 years ago

xtacy• 15 years ago

On a related node, this page also has an interesting visualisation of the effects of cache misses on program performance: http://igoro.com/archive/gallery-of-processor-cache-effects

ChuckMcM• 15 years ago

I liked that too. That is the dominant factor here. In the first example the four arrays blow away 4 lines of the cache none of them stay resident, in the second example two of the four arrays stay in cache during the copy. The effects can be quite large.

At Network Appliance there is a guy there who understands cache effects inside and out. File systems it turns our are particularly sensitive to them because 'pointer chasing' (the essence of file system traversal) is often a very cache expensive event.

machrider• 15 years ago

http://en.wikipedia.org/wiki/Locality_of_reference

_delirium• 15 years ago

From the top reply, it looks like it's less locality of reference, and more specific details of the cache indexing; when the arrays are allocated differently so the arrays don't alias each others' cache lines, the one-loop version becomes faster again (for some sizes of arrays).

kia• 15 years ago

In scientific computing it's not unusual to get 2x-3x speedups by doing simple optimizations like this one. For desktop applications it's nothing, but when your simulation is taking a week to complete then 2x-speedup is a huge improvement.

ahelwer• 15 years ago

This was especially the case on the old Pentium 4's. What we used to do was over-allocate the amount of memory needed, then offset the pointer into the allocated memory to avoid cache collisions.

dpe824• 15 years ago

It's not always nothing, particularly when you're dealing with video. :)

blahedo• 15 years ago

tl;dr: At small scales, efficiency is dominated by loop overhead. At larger scales, issues of cache size and bus bandwidth come to dominate. (In particular, if the memory accessed in the single loop doesn't all fit in the cache at once, the two loops might be faster if their respective portions of memory each can fit in the cache.)

kenferry4• 15 years ago

Actually, it turned out to be more interesting than that. False tldr! It had to do with the way the cache is addressed - just shifting one or the other array over in memory so all the parallel indexes weren't at the same offset from the beginning of the cache line would address it.

lbrandy• 15 years ago

The tldr here is that iterating through large arrays simultaneously with identical alignment can be slower than non-simultaneous access because of cache associativity. It's basically hash collisions in the cache due to alignment.

I've actually run into this in the "real world" in image processing applications. Given a "magical" width to an image, a pixel directly above (or below) another pixel can have the same alignment with respect to cpu cache. This can mean that things like (large) 2d convolutions are slower on images of very particular sizes.

tikhonj2• 15 years ago

I recently had a class project where we had similar issues. Being lazy students, we just let it perform slower for matrices of the wrong size; what is a good way to handle this sort of thing?

dpe824• 15 years ago

Usually you just pad the rows a bit.

buff-a• 15 years ago

You pad the rows manually. Then you start loading bigger chunks of data at a time. Then you start issuing prefetch instructions with compiler intrinsics or inline assembly. Then you ask "why am I dealing with this at all?" and use Intel's math libraries. And finally you use Octave or Matlab.

Unless you are a nutter like me, in which case you hand-roll everything in assembly.

tocomment• 15 years ago

Hmm this would be a great interview question when I hire my next round of web developers. Thanks hn!

maximusprime• 15 years ago

I hope you're being sarcastic.

burgerbrain4• 15 years ago

My school taught this sort of thing in the general CS classes, before everyone split off into their own branches. I think this sort of question would be a great thing to ask web developers. They should know it even if they don't always use it.

rkalla2• 15 years ago

It sounds like you want to be hiring ex kernel-hackers as your web dev team :)

rayiner• 15 years ago

Another thing to consider for code like this is that all Intel CPU's since the Core 2 tend to suffer somewhat from loop-unrolling optimizations. They have limited fetch bandwidth and SSE instructions are pretty long. Instead, they've got a loop buffer after the instruction fetch unit (after the decoders in Nehalem), which can feed the decoders much faster than the fetch unit. However the buffer is limited in size, and if unrolling causes the loop to exceed the size of the buffer, it can result in a substantial performance penalty.

joe_the_user• 15 years ago

So with this level of complexity and opaqueness for a simple routine, does it ever get any better?

If your algorithm has ten intertwined loops, does one have any hope of systematically optimizing performance or would you be reduced to "intuition" and easter-egging. (http://www.catb.org/jargon/html/E/Easter-egging.html)

What about "cache oblivious" algorithms? http://en.wikipedia.org/wiki/Cache-oblivious_algorithm

kenferry4• 15 years ago

What I would like to see is support in performance tools, like Instruments on Mac/iOS, for understanding and visualizing the effects of memory latency on your code. Sampling tools have been an incredible step forward for understanding why your code takes a long time, but I haven't seen anything remotely easy to use that helps understand memory latency. Considering how much slower our computers are at memory vs everything else, this could make a big difference!

nitrogen• 15 years ago

Have you tried Valgrind's Cachegrind (http://valgrind.org/docs/manual/cg-manual.html) and found it inadequate?

minimax• 15 years ago

Have you looked at Shark? It can show you where your program most frequently encounters L2 cache misses (or really any event your cpu has a hardware performance counter to track). Intel VTune and the "perf" tool from the Linux kernel also perform similarly.

ww520• 15 years ago

Without looking at the answers, let me guess. It has to do with fitting more data in L1/L2 cache and filling up the CPU's speculative execution pipeline with the simpler code.

kenferry4• 15 years ago

Nope! Man, there are a lot of people in the comments who didn't read it.

rkalla2• 15 years ago

wait, I thought that was the reason? (the L1-cache misses)

CamperBob• 15 years ago

Cache associativity isn't necessarily the only problem. Also possibly relevant, from http://drdobbs.com/184405848 (Mike Abrash):

"The other cause of erratic performance—and by far the worst—was 64K aliasing. On most Pentium 4s, if two data items in the L1 cache are at the same address modulo 64K, then a massive slowdown often occurs. Intel's documentation explains this by saying that the instruction that accesses the second piece of 64K-aliasing data has to wait until the first piece is written from the cache, which is to say until the first instruction is completely finished. As you might expect, this can wreak havoc with out-of-order processing. It was 64K aliasing that caused the aforementioned four-times slowdown in our large-triangle drawing benchmark.

"The truly insidious thing about 64K aliasing is that it is very hard to reliably eliminate it. Sure, it helps to avoid obvious problems. For example, pixel buffers and 32-bit z buffers are accessed at the same intrabuffer offsets for any given pixel, so if they encounter 64K aliasing at all, it will happen constantly; to avoid this, Pixomatic makes sure the two buffers never start at the same address modulo 64K (and also not at the same address modulo 4K, to avoid cache contention). But time after time, we've tweaked our data to get rid of 64K aliasing, only to have it pop up again a few days later after more changes were made. About all you can do is run VTune periodically to see if the number of 64K-aliasing events has spiked and, if it has, start backing out changes to figure out what variables or buffers need to be tweaked so they're not 64K aligned.

"On newer Pentium 4s, 64K aliasing changes to 1M aliasing, and in the most recent versions to 4M aliasing, which should reduce the problem considerably. Older Pentium 4s that have 64K aliasing also have 1M aliasing, which introduces an additional penalty on top of the cost of 64K aliasing, so beware of 1M aliasing even more than 64K.

"By the way, on Pentium 4s that have 1M aliasing but not 64K aliasing, the aliasing event counter still fires on 64K-aliasing events, even though they don't affect performance on those chips, so VTune will report incorrect results in such cases. On newer P4s that only have 4M aliasing, VTune will correctly report only 4M-aliasing events."

Mordor• 15 years ago

Why didn't the compiler split them between two cores/cpu's - would this have been quicker?

Why is one loop slower than 2 in C?

Related Stories