← All writings // #0005

Exploring Loop Fission vs. Loop Fusion in Rust

PerformaceFissionFusionLoop

When I was playing LeetCode a long time ago, I found someone who posted an interesting discussion. He gave us a tip to separate a single loop to process an algorithm into separated loops to make it faster. At first, I thought he was joking since it logically doesn't make sense. 

However, when I dug more into it, I found that the technique of splitting one loop into multiple loops is called loop fission. It is the counterpart of loop fusion, where we combine multiple calculations into one single loop whenever it is possible. Surprisingly, loop fission can sometimes perform better than loop fusion.

I wanted to understand why, so I conducted three simple experiments using Rust.

Experiment Setup

To perform this experiment, I used Rust and measured execution time for these two approaches:

  • Loop Fusion: Performs all calculations inside a single loop.
  • Loop Fission: Separates or distributes the calculations into multiple loops. 

Both approaches use the same experiment variables, such as input data, and perform the same calculations. To verify the result, a checksum will be checked at the end of each test.

Each experiment uses six input sizes, starting from 10,000 to 100 million elements. The test will be run seven times and use the median execution time.

Case A: Simple Calculations

In this case, we will perform two independent simple calculations on a u64 vector:

  1. Calculate the sum of consecutive indices.
  2. Multiply each element by its previous element.

Results (median of seven runs):

Surprisingly, I did not expect the results to be quite close, while fission is faster in five out of six tests. I initially thought fusion would be faster because it processes the data in a single pass.

Nevertheless, this experiment shows that reducing the number of iterations does not always improve performance.

Case B: Memory Pressure (Random Access)

For the second experiment, we will see how memory access affects performance.

There will be three u64 vectors: one input vector and two output vectors. Both calculations access the input using pseudo-random indices.

Results (median of seven runs):

This time, the results are opposite from the previous one. Fusion performs better in most cases, especially for larger input sizes, with fission becoming approximately 13–28% slower.

To investigate why, I examined the 10-million-element test using Cachegrid:

From the data, we can see fission produces more instructions executed and almost twice as many cache misses compared to fusion. This might be one of the reasons why fission is slower.

One possible explanation is temporal locality. When fusion performs calculations within its loop iteration, it accesses the same input locations close together in time. This gives the processor a better opportunity to reuse recently accessed cache lines. Meanwhile, fission performs the second calculation in a separate pass, making those cache lines less likely to remain available.

This experiment demonstrates that loop fusion can be beneficial when calculations reuse the same data.

Case C: Complex Calculations (36-Term Polynomial)

For the final experiment, let's do complex calculations.

Each iteration calculates two independent 36-term polynomials using f64 values. Fusion performs both calculations in the same loop, while fission separates them into two loops.

Results (median of seven runs):

This is interesting. Fission is consistently faster by around 9-13% across all sizes. 

To understand why, I asked the coding agent to examine the generated assembly and used Valgrind to compare instruction counts and cache behavior.

The Valgrind test used a smaller dataset of 100,000 elements, which fits comfortably within the CPU's last-level cache. This helps isolate CPU execution from memory pressure.

The results showed:

The fused version executes approximately 1.4 million more instructions, while both versions have virtually identical cache misses.

The generated assembly showed that the fused loop requires additional instructions to load constant values. Separating the calculations allows the compiler to generate more efficient instructions.

This suggests that the performance difference is not caused by memory access, but by the additional instruction overhead in the fused version.

Final Thoughts 

The biggest lesson for me is that fewer loops do not automatically mean better performance. Memory access, cache behavior, register usage, and compiler optimizations can all influence the final result.

These experiments are only a small exploration using specific workloads and hardware. They don't establish that one technique is always better than the other.

My takeaway: Don't optimize code based on how it looks. Write clear code first, measure its performance, and investigate the bottleneck before deciding whether loop fusion or loop fission makes more sense. Understanding trade-offs is important.

Source code: https://github.com/aodihis/loop-research