C# Reorder If Statements

If statements evaluate sequentially. They can be optimized to improve branch prediction. We can observe a program's runtime and chart its frequent actions. Here we look at an example of reordered if statements, and then benchmark them in the C# language.

Benchmark results for reordering if statements

Unordered if statements: 9100 ms
Optimized order:         4300 ms [faster, see example]

Benchmark

First, here we see an example of how you can speed up if statements. The micro-benchmarking program here aims to show that reordering if statements can make some impact. This is example code and not something that would occur in the real world.

This C# program shows how to reorder if-statements to optimize programs.

Program that tests if statements [C#]

using System;

class Program
{
    static void Main()
    {
	const int m = 10000000; // Number of iterations
	int d = 1;              // Dummy variable
	long t1 = Environment.TickCount;

	for (int a = 0; a < 100; a++)
	{
	    for (int i = 0; i < m; i++)
	    {
#if SLOW
		if (i < 100)
		{
		    d = 1;
		}
		else if (i < 1000)
		{
		    d = 2;
		}
		else if (i > 2000)
		{
		    d = 3;
		}
#else
		if (i > 2000)
		{
		    d = 3;
		}
		else if (i < 100)
		{
		    d = 2;
		}
		else if (i < 1000)
		{
		    d = 1;
		}
#endif
	    }
	}
	long t2 = Environment.TickCount;

	Console.WriteLine("{0},{1}",
	    t2 - t1,
	    d);
	Console.ReadLine();
    }
}

Notes. The code sample runs billions of if checks on the i variable. It is an example of how you can reorder if statements like PGO does automatically.

Overview of reordering. The most popular open-source applications use this technique. You reorder code to put the most likely code first. In C++ using Visual Studio or GCC you can use profile-guided optimization. Software such as Internet Explorer and Firefox have achieved speedups of 10% or more this way.

How important is branch prediction? It is important in some cases. Your processor predicts which paths in your code are likely. However, it has limitations and making those decisions yourself is best.

Is the savings significant?

Yes and no. Most programs have bigger problems than this. I found that the costs for if statements was reduced substantially by reordering to put the most common statement first. Note that the code I benchmarked had a small difference that shouldn't have any significant effect on the results.

Uses

This optimization is usually unneeded because the savings aren't worthwhile unless you are working on something like Google Chrome where tiny performance improvements are needed. It forces us to instrument our apps and look at what happens most often. You can make observations on behavior as the program runs. Then you can make more improvements.

Summary

We saw that you can inspect the behavior of your program and keep tally of what if statements are most frequently used. Profile-guided optimization is great for huge and complex programs. However, it doesn't replace careful observation of paths taken in your program. I have fixed many problems by studying the paths my programs follow most frequently.