Loop unrolling is one of those compiler tricks that feels like it should not work, but it does :) It is also super easy to implement.
The idea is simple: instead of iterating one element at a time, the compiler (or you, manually) writes the loop to process multiple elements per iteration. A loop that runs 1000 times becomes one that runs 250 times but does 4x the work per pass.
- sum += arr[i]
- sum += (arr[i] + arr[i+1] + arr[i+2] + arr[i+3])
Why does this help? Modern CPUs are deeply pipelined. The branch check at the end of every iteration - “are we done yet?” - is small, but it adds up. Fewer branches mean fewer pipeline stalls and more room for instruction-level parallelism.
Another improvement is memory prefetching. When you process four elements per iteration, the CPU has a cleaner, more predictable access pattern. Prefetchers love this and will load upcoming cache lines well before you need them.
The trade-off is code size and readability. Unrolling a loop 4x means 4x the instructions in the binary. This might blow the instruction cache, which can actually make things slower. Most compilers use heuristics to find the sweet spot.
If you want to, you can write this by hand. But in most cases, you should let the compiler do it for you. GCC and Clang will often do it automatically with -O2 or -O3, and they may even leverage SIMD instructions to squeeze out more throughput.
By the way, you can code every single thing I mentioned in under 15 minutes and see it for yourself.
Anyway, it’s Friday, so give it a shot. It will be fun!