TheDeveloperBlog.com


C# Loop Jamming

Loop jamming combines separate loops. It improves the clarity and performance of some for-loops. We make several passes on the same array. We can apply an optimization technique named loop fusion or jamming to improve this.

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.

Code Complete

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.

Next: You will see that the local variable declaration space in the first loop contains three statements.

And: In the second example, the same result is achieved, but there are three for-loops.

The two loops have the same result. 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.

C# program that demonstrates jammed loops

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


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


Discussion. Loop jamming is a classic optimization technique that actually changes the logic of your loops. At the start, we looked at some problems described with loop jamming in the book Code Complete by Steve McConnell.

Overall: Loop jamming has limited use in most programs. It should be avoided except when it is needed. It makes code harder to read.


Summary. We improved 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 referenced literature.