When, if ever, is loop unrolling still useful?

by

Loop unrolling makes sense if you can break dependency chains. This gives a out of order or super-scalar CPU the possibility to schedule things better and thus run faster.

A simple example:

for (int i=0; i<n; i++)
{
  sum += data[i];
}

Here the dependency chain of the arguments is very short. If you get a stall because you have a cache-miss on the data-array the cpu cannot do anything but to wait.

On the other hand this code:

for (int i=0; i<n-3; i+=4)  // note the n-3 bound for starting i + 0..3
{
  sum1 += data[i+0];
  sum2 += data[i+1];
  sum3 += data[i+2];
  sum4 += data[i+3];
}
sum = sum1 + sum2 + sum3 + sum4;
// if n%4 != 0, handle final 0..3 elements with a rolled up loop or whatever

could run faster. If you get a cache miss or other stall in one calculation there are still three other dependency chains that don’t depend on the stall. A out of order CPU can execute these in parallel.

(See Why does mulss take only 3 cycles on Haswell, different from Agner’s instruction tables? (Unrolling FP loops with multiple accumulators) for an in-depth look at how register-renaming helps CPUs find that parallelism, and an in depth look at the details for FP dot-product on modern x86-64 CPUs with their throughput vs. latency characteristics for pipelined floating-point SIMD FMA ALUs. Hiding latency of FP addition or FMA is a major benefit to multiple accumulators, since latencies are longer than integer but SIMD throughput is often similar.)

More Related Contents:

  1. Performance optimization strategies of last resort [closed]
  2. What is the best way to set a register to zero in x86 assembly: xor, mov or and?
  3. Why are loops always compiled into “do…while” style (tail jump)?
  4. What methods can be used to efficiently extend instruction length on modern x86?
  5. Can modern x86 implementations store-forward from more than one prior store?
  6. How can the rep stosb instruction execute faster than the equivalent loop?
  7. One could use a profiler, but why not just halt the program? [closed]
  8. INC instruction vs ADD 1: Does it matter?
  9. Google app script timeout ~ 5 minutes?
  10. Google app script timeout ~ 5 minutes?
  11. Why does breaking the “output dependency” of LZCNT matter?
  12. Is there a penalty when base+offset is in a different page than the base?
  13. Branch alignment for loops involving micro-coded instructions on Intel SnB-family CPUs
  14. Which Intel microarchitecture introduced the ADC reg,0 single-uop special case?
  15. What is the fastest way to get the value of π?
  16. What is the most ridiculous pessimization you’ve seen? [closed]
  17. What are the major performance hitters in AS3 aside from rendering vectors?
  18. Assembly – How to score a CPU instruction by latency and throughput
  19. Why should recursion be preferred over iteration?
  20. Unexpectedly poor and weirdly bimodal performance for store loop on Intel Skylake
  21. Why is vectorization, faster in general, than loops?
  22. Why are compilers so stupid?
  23. How to find pair with kth largest sum?
  24. Modern x86 cost model
  25. Why do these goroutines not scale their performance from more concurrent executions?
  26. Fastest way to strip all non-printable characters from a Java String
  27. Cycles/cost for L1 Cache hit vs. Register on x86?
  28. Best Practices for Multiple OnEdit Functions
  29. Memory Allocation/Deallocation Bottleneck?
  30. Relative performance of x86 inc vs. add instruction

Leave a Comment