Do the Spidey
Algorithms are quite literally full of loops, repetition constructs meant to recycle code with iterating control variables. In artificial intelligence, machine learning, and computer graphics, these constructs are even more prevalent (if that is even possible!), with matrix operations commonly expressed as nested loops of scalar operations indexed over a matrix's dimensions.
Because of the inherent outsize effect of a loop's body on any algorithm's performance, a multitude of strategies to optimize loop execution time has emerged over the years. Often coupled to the hardware, and always dependent on the programming model and compiler in use, these optimizations are so well understood as to carry their own names.
Loopy
David Spuler's recent works [1][2] feature the taxonomy of loop manipulation strategies that most closely reflects my own thinking. As I read through David's admirable effort to put encyclopedic order to the many code optimization strategies available, I am narrowly focusing this article on loop tuning. I must note that optimization is always to be performed after a code is working correctly and deemed fit for purpose: Sir Tony Hoare's famous quote stating that "premature optimization is the root of all evil" sums up this point of view neatly [3]. The reasons for such a statement are particularly apparent in the many mangling strategies one can choose to apply to loops (Table 1). These strategies have emerged over the decades. The definitions can be very narrow and specific, because many are meant for use by automatic compiler optimizations.
| Table 1: Optimizing Execution Speed | |
| Strategy | Definition |
|---|---|
| Loop fusion | Combining two or more loops into a single body, minimizing test overheads. |
| Loop fission | Splitting a loop's body into multiple loops, each with a simpler body. Often better suited for GPU execution. |
| Loop distribution | Akin to fission, aiming to move a test out of the loop's body. |
| Loop splitting | Cleaving the range of a loop's iterations to separate distinct logic applying to disjoint ranges into two loops. |
| Loop coalescing | Combining two nested loops into a single loop. |
| Loop collapsing | A variant of loop coalescing, wherein the data structure navigated by the loop is also reduced in dimensionality. |
| Loop unrolling | Repeating a loop's body to minimize loop overheads; may couple well with vector operations. |
| Loop peeling | Unrolling a few iterations of the loop's body is useful when special case iterations are present. |
| Tiling or blocking | Operating on subsections of a large multidimensional matrix to increase data locality as its size exceeds a system's cache [4]. |
| Loop reordering | Swapping the order of two sequential loops is not an optimization in itself, but could restructure the code for other approaches. |
| Loop interchange | Swapping inner and outer loops, a typical use is to improve cache data locality [5]. |
| Loop reversal | Running the loop in reverse often produces less optimal code, but might open code to other approaches. |
| Loop perforation | Stochastic non-execution of some loop cycles. Suitable for some algorithms (e.g., neural networks), classified as optimization because it reduces overall cycles. |
| Sentinel | Extending a data structure to eliminate code testing for a special case condition. |
| Code motion | Relocating loop-invariant code outside of the loop's body. |
| Strip mining | Sectioning a loop in slices that can be addressed by an optimized function of a CPU's vector operation. |
| Loop normalization | Equalizing the range of nested loops, which is not itself an optimization but might open other optimization strategies. |
| Loop spreading | Modifying the range of two sequential loops to enable loop fusion of their bodies. A remainder loop might be required. |
| Loop skewing | Altering the respective shape of two loops to make one more accessible to vector instructions or GPUs. |
Most of these modifications force the original problem-solving logic through a grinder, aiming to produce equivalent, faster code designed for a specific computing arrangement -- yet leading to what are inscrutable instructions in the eyes of the original domain experts.
Furthermore, these strategies perform vastly differently depending on the underlying system architecture, ranging from serial CPU logic to CPU instructions operating on multiple data (such as AVX [6]) or a GPU's finer grained parallelism. Many strategies are liable to backfire when switching the underlying choices of hardware, parallelism style, or compiler, forever anchoring the optimized binary to its runtime environment.
Start with Why
Refactoring a loop can take many forms, but the underlying aims are always the same. The original reason to refactor a loop was to reduce the overhead introduced by the loop itself, its plumbing involving cycling jumps and test of termination conditions. Not trivial when repeated tens or even millions of times, these overheads are quite simple to understand in the single-threaded execution environment of a classic processor like the Intel 386 but are easily overshadowed by other optimization choices available in modern multithreaded CPUs with large caches like the Intel Xeon or AMD Epyc.
Despite the hardware's evolution, you still find reason to restructure loops from their original design, aiming to better fit parallelization strategies including multiple execution threads; single instruction, multiple data (SIMD) CPU extensions manipulating data in vectors; or even fine-grained GPU parallelism [6]. Although very different in other respects, all parallelism strategies generally benefit from smaller, simpler loop bodies and the elimination of dependencies between variables. All compute platforms, serial and parallel irrespective, benefit from locality in data access patterns to extract better performance from today's massive on-chip caches (Table 2). The underlying reasons for undertaking loop refactoring include many causes, often orthogonal with each other.
| Table 2: Rationales for Loop Refactoring | |
| Strategy | Definition |
|---|---|
| Loop overheads | Repeating execution of the code required to build a loop (cycling code and test termination conditions). |
| Data locality | Exceeding a cache's range or accessing a matrix outside its natural row-major or column-major order. |
| Chunking | Accessing SIMD CPU primitives operating on vectors of data at a time. |
| Parallelism | Simplifying loop bodies, which are more suitable for GPU massively parallel execution. |
| Data dependency | Structuring loops to eliminate dependencies between variables parallelized to independent execution streams. |
| Compiler optimization | Restructuring code so it may be more efficiently optimized by the compiler itself. |
Loop Unrolling
The original loop unrolling traded increased program code length for reduced use of the jump and test instructions defining a loop. When unrolling a loop, the loop body is repeated a number of times and the loop iteration count is reduced or entirely eliminated, as in this simple case:
for (i=0; i<4; i++) {
c[i] = a[i] + b[i];
}When the number of cycles is known at compile time, a loop can be fully unrolled:
c[0] = a[0] + b[0];
c[1] = a[1] + b[1];
c[2] = a[2] + b[2];
c[3] = a[3] + b[3];However, it remains possible to unroll a loop partially by a factor, even when the execution cycle count is not known up front. This example unrolls by a factor of two, which is the most common case:
for (i=0; i<4; i+=2) {
c[i] = a[i] + b[i];
c[i+1] = a[i+1] + b[i+1];
}A loop's partial unroll typically results in a more complex loop body, enabling and indeed necessitating use of the other strategies listed in Table 1 to simplify the result.
A partial unroll where the number of cycles does not divide evenly by the unroll factor leads to a peculiar C construct known as Duff's device [7], intermingling a switch and a while loop and leveraging the fall-through property of the switch statement in a somewhat appalling construct (Listing 1; "I feel a combination of pride and revulsion at this discovery," is the description Tom Duff himself appended to its announcement [7]).
| Listing 1: Duff's Device for Modulo 8 Loop Unrolling |
|
Duff's device is obsolete today, in the simplest terms because it produces code that optimizing compilers will never be able to manipulate further [8]. It remains an interesting illustration of the mechanism of loop unrolling and the need to address cycle lengths that do not divide evenly by the unroll factor – originating those strategies in Table 1 that address conditionals in complex loop bodies.
Compiler Magic
The magic of loop unrolling is best performed today by the compiler (pragma unroll(4) forces an unroll factor of four). The need to benchmark the resulting code to determine whether the optimization is beneficial results in what must be the ultimate case of "works on my machine" tuning. Oracle has published just such an analysis of Java's behavior as it applies loop unrolling in Java virtual machine (JVM) bytecode [9].
Unrolling Today
A modern programmer may yet choose to unroll to optimize away a conditional or to enable SIMD instruction use. The efficiency of a loop depends on how well the microprocessor can predict the loop control branch. On many processors, only the inner loop is predicted well. Branch prediction faults dwarf other overheads save for cache faults, resulting in the application of strategies like loop interchange to place the higher cycling loop as the inner loop, minimizing prediction misses and resulting in speculative execution resets. Removing conditionals present inside the loop, for example,
for (i = 0; i < 20; i++) {
if (i % 2 == 0) {
even(i);
}
else {
odd(i);
}
count(i);
}might benefit execution time, particularly if the conditionals are difficult for the hardware to predict. The full unrolling removes the conditional inside the loop by trading an additional function call to count():
for (i = 0; i < 20; i += 2) {
even(i);
count(i);
odd(i+1);
count(i+1);
}SIMD instruction nirvana can be even trickier to attain. ARM developer documentation for pragma unroll [10] includes the example matrix multiplication function found in Listing 2; yet, a quick test with Compiler Explorer [11] shows that despite the #pragma directive on line 8, Apple's Clang compiler (20.1.0 for ARM v8, -O3 compiler option) still outputs four separate fused multiply-add (fmadd) CPU instructions (Figure 1) instead of unrolling fourfold into a vectorized instruction.
| Listing 2: Matrix Manipulation Function |
|

Apple's compiler is very strict about floating point reordering guarantees, and although some switches can force better results, I was not able to obtain a four-way unroll. GCC (15.1.0 for ARM v8, -O3 compiler option) was significantly more aggressive – and effective. The resulting code uses a single vector multiply-accumulate (vmla) SIMD instruction to achieve the inner loop's addition (Figure 2), vectorizing the loop as intended.

The highly tuned Assembler subroutines so crucial to the demoscene art [12] and interactive shoot-em-up videogames of the 1990s were handcrafted by iconic programmers such as Doom's John Carmack [13] or Quake's Michael Abrash [14]. These industry giants would literally count instruction cycles in search of faster frame-drawing code, ever searching for a faster refresh rate.
With the advent of processors with multiple execution pipelines [15], multilevel data caches, and speculative execution [16], cycle counting has become impossible in most practical cases, its effect in any event secondary to optimizations designed to avoid cache faults or branch mis-prediction. Stalling an instruction pipeline or causing data to be retrieved directly from RAM affects the execution speed of modern processors many orders of magnitude more than instruction cycle counts ever could. Now, Moore then ever, the compiler knows best.
[2] Spuler, David. Efficient Modern C++ Data Structures: Container and Algorithm Optimizations, book 3 of 7 in Advanced C++ Programming. Aussie AI Labs Pty Ltd, 2025
[3] Hyde, Randall. The fallacy of premature optimization. Ubiquity, 2009;10(3):5 pp, https://ubiquity.acm.org/article.cfm?id=1513451
[4] "Go testing frameworks" by Federico Lucifredi, ADMIN, issue 82, 2024, pg. 94, https://www.admin-magazine.com/Archive/2024/82/Go-testing-frameworks
[5] "Thrashing the data cache for fun and profit" by Federico Lucifredi, ADMIN, issue 54, 2019, pg. 95, https://www.admin-magazine.com/Archive/2019/54/Thrashing-the-data-cache-for-fun-and-profit
[6] Advanced Vector Extensions, https://en.wikipedia.org/wiki/Advanced_Vector_Extensions
[7] Explanation of Duff's Device by Tom Duff: https://www.lysator.liu.se/c/duffs-device.html
[8] "Duff's device in 2021" by Chloé Lourseyre, Belay the C++, https://belaycpp.com/2021/11/18/duffs-device-in-2021/
[9] "Loop Unrolling" by Chris Newland and Ben Evans, Java Magazine, May 15, 2019, https://blogs.oracle.com/javamagazine/post/loop-unrolling
[10] #pragma unroll [(n)], documentation, arm Developer: https://developer.arm.com/documentation/dui0491/i/Compiler-specific-Features/-pragma-unroll---n--
[11] Compiler Explorer: https://godbolt.org
[12] Future Crew. Second Reality. YouTube video, 1993: https://www.youtube.com/watch?v=iw17c70uJes&pp=0gcJCfwAo7VqN5tD
[13] Development of Doom: https://en.wikipedia.org/wiki/Development_of_Doom
[14] Abrash, Michael. Zen of Code Optimization: The Ultimate Guide to Writing Software That Pushes PCs to the Limit. Coriolis Group, 1994
[15] Instruction pipelining: https://en.wikipedia.org/wiki/Instruction_pipelining
[16] Branch prediction: https://en.wikipedia.org/wiki/Branch_predictor