4 ms·

Educated guess: The processor is trying to prefetch instructions. This loop is much tighter than most code that would typically be written, so an incrementing

by maxk42 9y ago

Educated guess: The processor is trying to prefetch instructions. This loop is much tighter than most code that would typically be written, so an incrementing loop causes a branch misprediction. The processor is still loading instructions, so when it goes to find out what to do next, it takes a cache miss and burns some time trying to figure out its next instruction. However, a function call is very slow, however (even to a nop function) and it could delay the processor just long enough for the prefetch to complete.

nkurz 9y ago
You are welcome defend your guess with measurements, but your explanation comes across as "not even wrong". Incrementing the loop does not cause a branch prediction error (why would this happen?), the loop is small enough it comes out of the loop cache (so no cache misses), function calls are not slow (as evidenced by the example). Worse, as far as I can tell, your explanation doesn't actually even explain why adding a call would make the loop run faster.
- titzer 9y ago
  Word. An educated guess would be something more coherent and this was a word salad of architecture jargon.
- maxk42 9y ago
  What I'm saying is it's possible that because the loop is so small the hardware prefetch is not done loading its page of data yet. This causes a cache miss and forces the hardware to think it has to reload the instructions each loop. A tiny delay might slow it down just enough for the prefetch to complete.
  - nkurz 9y ago
    I think the main part that you are missing is that there are two layers of cache below the instruction loading that would also have to be defeated. Modern processors don't actually execute assembly instructions, rather than convert these to micro-ops. There is a tiny "loop cache" that holds the tightest loops like this one, and then a larger "decoded instruction cache" that holds a few functions worth. This means that the second time through a loop you almost never need to reread the binary instructions, and thus in a small loop like this you almost never have the potential for an instruction cache miss. You can check this with 'perf', and you'll see that neither version has any significant number of icache misses. The other part you are probably misconceiving is that the processor doesn't actually proceed linearly through the instructions, but rather decodes them into µops, and then throws them into a "reorder buffer". They then get "issued" to execution ports as soon their input registers are available, then "executed", and then "retired" once it's confirmed that the inputs were indeed correct. The execution is actually happening at many points at once, based on the processors best guess at to what path the execution will take. That is to say, current processors are "speculative", "superscalar", and "out-of-order". The net effect is that they don't really "slow down" in the way that you are picturing. Instead, they usually fail by guessing a wrong path and executing it quickly, and then have to throw away the work if they guessed wrong. The case that you mention isn't exactly impossible, but usually only happens with (extremely rare) self-modifying code.

by maxk42 9y ago

nkurz 9y ago

You are welcome defend your guess with measurements, but your explanation comes across as "not even wrong". Incrementing the loop does not cause a branch prediction error (why would this happen?), the loop is small enough it comes out of the loop cache (so no cache misses), function calls are not slow (as evidenced by the example). Worse, as far as I can tell, your explanation doesn't actually even explain why adding a call would make the loop run faster.

titzer 9y ago
Word. An educated guess would be something more coherent and this was a word salad of architecture jargon.
maxk42 9y ago
What I'm saying is it's possible that because the loop is so small the hardware prefetch is not done loading its page of data yet. This causes a cache miss and forces the hardware to think it has to reload the instructions each loop. A tiny delay might slow it down just enough for the prefetch to complete.
- nkurz 9y ago
  I think the main part that you are missing is that there are two layers of cache below the instruction loading that would also have to be defeated. Modern processors don't actually execute assembly instructions, rather than convert these to micro-ops. There is a tiny "loop cache" that holds the tightest loops like this one, and then a larger "decoded instruction cache" that holds a few functions worth. This means that the second time through a loop you almost never need to reread the binary instructions, and thus in a small loop like this you almost never have the potential for an instruction cache miss. You can check this with 'perf', and you'll see that neither version has any significant number of icache misses. The other part you are probably misconceiving is that the processor doesn't actually proceed linearly through the instructions, but rather decodes them into µops, and then throws them into a "reorder buffer". They then get "issued" to execution ports as soon their input registers are available, then "executed", and then "retired" once it's confirmed that the inputs were indeed correct. The execution is actually happening at many points at once, based on the processors best guess at to what path the execution will take. That is to say, current processors are "speculative", "superscalar", and "out-of-order". The net effect is that they don't really "slow down" in the way that you are picturing. Instead, they usually fail by guessing a wrong path and executing it quickly, and then have to throw away the work if they guessed wrong. The case that you mention isn't exactly impossible, but usually only happens with (extremely rare) self-modifying code.