C# Loop Unwinding

Loop unwinding sometimes improves performance.

It allows you to simplify code and make it more efficient. It reduces the number of iterations in for-loops. You can refactor your C# code with loop unrolling.

Loop unwinding benchmark

Regular loop: 6255 ms
Unrolled ifs: 6179 ms [faster]

Example. First, we change a regular for-loop to an unwound for-loop. Unrolling or unwinding is an optimization you can make to some loops. To make this optimization, you can separate every statement group rather than iterate over each one.

Example loop: C#

class Program
{
    static void Main()
    {
	int[] a = {1, 4, 5, 7};

	for (int i = 0; i < a.Length; i++)
	{
	    if (a[i] == 3)
	    {
		// ...
	    }
	}
    }
}

Example unrolled loop: C#

class Program
{
    static void Main()
    {
	int[] a = {1, 4, 5, 7};

	for (int i = 0; i < a.Length; i += 2)
	{
	    if (a[i] == 3)
	    {
		// ...
	    }
	    if (a[i + 1] == 3)
	    {
		// ...
	    }
	}
    }
}

It is important that you only unwind loops so that the steps in the loops do not exceed the array bounds. The unwound loop above could have two, four, or six elements to loop over, but not three, five, or seven.

Example 2. Loop unwinding can improve the logic of your code. It can improve performance, but more importantly, it can help you clear up confusing parts of your code. When I unrolled the example I had faster and shorter code.

Foreach

And: In the example, I had to test strings. If the string started with one of three acceptable strings, I had to accept it.

StartsWith

Code that tests strings in foreach-loop: C#

string[] a1 = new string[]
{
    "cat/",
    "dog/",
    "man/"
};
string l = "dog/example";

bool ok = false;
foreach (string a in a1)
{
    if (l.StartsWith(a))
    {
	ok = true;
	break;
    }
}

Code that tests strings in unrolled loop: C#

const string aa = "cat/";
const string ab = "dog/";
const string ac = "man/";
string l = "dog/example";

bool ok = false;
if (l.StartsWith(aa) ||
    l.StartsWith(ab) ||
    l.StartsWith(ac))
{
    ok = true;
}

Discussion. You can eliminate loops when the number of iterations is known beforehand. This is usually best with very few iterations—fewer than five. If you have a long loop, then you can unroll four or eight parts.

In the above examples, I received a small speedup. It eliminated the entire loop and made the code shorter. The first code example was tested against the second example, and the unrolled loop was faster.

Benchmark Programs

Note: My understanding is that the processor is better able to predict branches and use pipelining when the statements are unrolled.

Summary. We saw some examples and benchmarks of loops. Sometimes it can be beneficial to unroll or unwind your loops. However, the understanding of computer hardware and processors we gain here is more valuable.

Related Links