C# Loop Jamming

Loop jamming combines separate loops. It may improve the clarity and performance of some for-loops in C# programs. You are making several passes on the same array, and can apply an optimization technique named loop fusion or jamming to improve this.

This C# benchmark article demonstrates the loop jamming optimization.

Example

Here we see an interesting optimization where several loops are combined into one loop. Usually, this approach works best on for loops, where the loop indices are constrained in the iteration statement. You will see that the local variable declaration space in the first loop contains three statements. In the second example, the same result is achieved, but there are three for loops.

Program that demonstrates jammed loops [C#]

using System;

class Program
{
    const int max = 10;

    static void Main()
    {
	//
	// Initialize array in jammed loop.
	//
	int[] array = new int[10];
	for (int i = 0; i < max; i++)
	{
	    array[0] = i;
	    array[1] = i;
	    array[2] = i;
	}
	//
	// End jammed loop.
	//
	foreach (int value in array)
	{
	    Console.WriteLine(value);
	}

	//
	// Initialize array in separate loops.
	//
	array = new int[10];
	for (int i = 0; i < max; i++)
	{
	    array[0] = i;
	}
	for (int i = 0; i < max; i++)
	{
	    array[1] = i;
	}
	for (int i = 0; i < max; i++)
	{
	    array[2] = i;
	}
	//
	// End separate loops.
	//
	foreach (int value in array)
	{
	    Console.WriteLine(value);
	}
    }
}

Output

9
9
9
0
0
0
0
0
0
0

9
9
9
0
0
0
0
0
0
0

Description. The output section of the example shows that the two loops result in the exact same output in the array. Note that these array assignments in the loop bodies cannot be easily optimized out by the compiler, because each iteration is different, and each statement is separate.

Benchmark

The benchmark here tests the block of code in the jammed section of the above example to the block of code in the 'separate' loop section. The next block shows the characteristics of the benchmark, including the bounds and layout.

Benchmark details

Loop maximum:                         10000000
Method calls to loop:                 100
Total array assignments in each test: 10000000 * 100 * 3
Jammed loop result:                   1274 ms [33.23% faster]
Separate three loops result:          1908 ms

Research

Loop jamming is a classic optimization technique that actually changes the logic of your loops. Next, we look at some problems described with loop jamming in the book Code Complete by Steve McConnell. "Loop jamming has two main hazards. First, the indexes for the two parts that have been jammed might change so they're no longer compatible. Second, you might not be able to combine the loops easily." (Page 618)

Note: I recommend Code Complete to all dedicated programmers.

Summary

Here we saw how you can improve your loops with a classic optimization technique. This can rarely improve the performance of character intensive or byte intensive operations. We looked at a benchmark and finally referenced the leading programming literature on this topic.