C# Array Optimization

Array optimization. Array element assignments can be optimized.

Typically arrays are initialized in a for-loop. This introduces the loop overhead to the operation. Using constant array element assignment expressions can be faster.

Example. To start, we look at a benchmark that tests operations on a single array. The first, Method1, uses a for-loop over the first twelve elements of the parameter array. It assigns each element to a certain value.

And: Method2 uses twelve assignment statements. It has more source code statements but better performance.

C# program that benchmarks array element assignments

using System;
using System.Diagnostics;

class Program
{
    const int _max = 100000000;
    static void Main()
    {
	int[] array = new int[12];
	Method1(array);
	Method2(array);

	var s1 = Stopwatch.StartNew();
	for (int i = 0; i < _max; i++)
	{
	    Method1(array);
	}
	s1.Stop();
	var s2 = Stopwatch.StartNew();
	for (int i = 0; i < _max; i++)
	{
	    Method2(array);
	}
	s2.Stop();
	Console.WriteLine(((double)(s1.Elapsed.TotalMilliseconds * 1000 * 1000) /
	    _max).ToString("0.00 ns"));
	Console.WriteLine(((double)(s2.Elapsed.TotalMilliseconds * 1000 * 1000) /
	    _max).ToString("0.00 ns"));
	Console.Read();
    }

    static void Method1(int[] array)
    {
	// Initialize each element in for-loop.
	for (int i = 0; i < array.Length; i++)
	{
	    array[i] = 1;
	}
    }

    static void Method2(int[] array)
    {
	// Initialize each element in separate statement with no enclosing loop.
	array[0] = 1;
	array[1] = 1;
	array[2] = 1;
	array[3] = 1;
	array[4] = 1;
	array[5] = 1;
	array[6] = 1;
	array[7] = 1;
	array[8] = 1;
	array[9] = 1;
	array[10] = 1;
	array[11] = 1;
    }
}

Output

11.48 ns
5.43 ns

In this example, the methods Method1 and Method2 both copy a reference (four byte) variable to the formal parameter slot when called (if not inlined). Then, Method1 invokes the for-loop overhead, using an iteration variable.

Each store operation into the array uses an affine expression to compute the physical location of the element. Method1 uses an explicit loop structure. Method2 uses an unrolled or unwound loop structure.

Discussion. You may be wondering why a method with twelve lines of code is more than twice as fast as a method with three lines of code. After all, each method computes the same result in the program.

The reason the longer method is faster is that we are outsmarting the compiler. The C# compiler is unable to determine that a for-loop over twelve elements is slower than twelve explicit assignments.

Note: Please remember that it is more difficult to construct a versatile compiler than write little C# programs.

Summary. We examined an optimization that describes array initialization or assignment procedures. We found that a method that is longer is faster than a method that is shorter, even when both use the same basic assignment instructions.

Review: This basic idea is also detailed in the book Code Complete by Steve McConnell.

Further: This optimization is used in many programs to avoid loop overhead, and is sometimes called loop unrolling.

Loop Unwinding

Related Links