C# Reorder If-Statements

If-statements sequentially evaluate.

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.

Optimizations

Example. First, 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—not something that would occur in the real world.

Here: The code sample runs billions of if-checks on the i variable. It shows how to reorder if-statements.

Benchmark

C# program that tests if-statements

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();
    }
}

Results

Unordered if-statements: 9100 ms
Optimized order:         4300 ms

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.

Note: 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.

Discussion. Most programs have bigger problems than this. The costs for if-statements was reduced by reordering to put the most common statement first. Note that the code I benchmarked had a small difference. This had no effect on the results.

This optimization is usually unneeded. The savings aren't worthwhile unless you are working on something where tiny performance improvements are needed. It forces us to instrument our apps and look at what happens most often.

Tip: You can make observations on behavior as the program runs. Then you can make more improvements.

Vowel

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. This analysis can fix many problems.

Related Links