Fusion, Fission, Interchange and Tiling

These are not micro-optimizations and they are not about instruction count. Every one of them leaves the arithmetic exactly as it was. What they change is the order of memory accesses, and on a machine where a cache hit is a few cycles and a miss is a few hundred, the order of memory accesses is the program's performance.

Fusion merges two loops over the same range into one. It buys a single traversal instead of two, so a value produced in the first loop is still in cache when the second loop reads it, and it removes one loop's overhead. It costs register pressure — the merged body needs everything both bodies needed live at once — and it can hurt if the two bodies together no longer fit their working set in cache.

Fission (also called distribution) splits one loop into two. It is fusion's inverse and it buys the opposite things: a smaller body with fewer live values, and — most importantly — the ability to vectorize one half when the other half contains something that defeats the vectorizer. Splitting a loop so the vectorizable statements are alone is one of the most common enabling transformations there is.

Interchange swaps the loops in a nest so the innermost one walks memory contiguously. This is the transformation with the largest single effect in the module, because the difference between unit-stride and column-stride access on a row-major array is the difference between one cache miss per cache line and one per element.

Tiling (blocking) restructures a nest so that it works on a block of the data small enough to stay in cache, finishes with it, then moves on. It is the standard technique for matrix multiplication and for any algorithm that revisits data, and it is what turns an operation limited by memory bandwidth into one limited by arithmetic.

A two-dimensional array in C is stored row-major: a[i][j] and a[i][j+1] are adjacent in memory, while a[i][j] and a[i+1][j] are a whole row apart. A loop nest that varies i innermost therefore touches one element from each of many distant locations, and the hardware — which fetches a whole cache line and prefetches sequentially — gets no benefit from either mechanism.

Swapping the loops so j varies innermost makes the access pattern contiguous. Every cache line fetched supplies the next several iterations, the prefetcher recognises the stride, and the same arithmetic completes several times faster with no change in instruction count. This is the clearest available demonstration that instruction count is a poor proxy for time.

Fortran stores column-major, so the correct nesting is the mirror image — which is exactly why the same numerical kernel written from a Fortran textbook and transcribed literally into C is slow, and why this is one of the few optimizations worth knowing by hand.

Matrix multiplication touches every element of both inputs many times. Done naively, by the time the algorithm comes back to a row it walked away from, that row has been evicted, so the total memory traffic is far larger than the data. Tiling fixes this by processing a block at a time: load a tile of each input, do all the arithmetic that involves those tiles, then move on.

The arithmetic is unchanged — the same multiplies and adds in a different order, which for floating point means tiling is a reassociation and technically alters results, one of the reasons high-performance libraries are explicit about their blocking. What changes is that each element is loaded roughly once per tile pass instead of once per use, which converts a memory-bandwidth-bound kernel into a compute-bound one.

The tile size is the parameter, and it is a property of the machine: it should make the working set of the tiles fit comfortably in the target cache level, usually with multiple levels of tiling for multiple levels of cache. This is why hand-tuned BLAS libraries and autotuning frameworks exist, and why a compiler that tiles automatically — which several do, using the polyhedral model — must be told or must guess the cache sizes.

These transformations are well understood and have been implemented for decades, and mainstream compilers still apply them cautiously. The reason is that legality depends on dependence analysis over array subscripts, and dependence analysis over arbitrary subscripts is undecidable in general and expensive in practice. A subscript like a[f(i)] or a[idx[i]] defeats it entirely; a pointer that might alias defeats it before it starts.

This is why Fortran has historically produced faster numerical code than C from the same algorithm: Fortran arrays cannot alias, so the dependence analysis has a chance. It is also why restrict exists and why the polyhedral frameworks — Polly in LLVM, Graphite in GCC — restrict themselves to *affine* loop nests, where subscripts are linear functions of the loop indices and the whole nest can be modelled as a set of integer points with an exact legality test.

The practical consequence for an engineer is that interchange and tiling are among the few loop transformations still worth doing by hand, in the specific case of a numerical kernel over dense arrays. Everything else in this module is better left to the compiler; these two are frequently blocked by information the compiler cannot recover.