C# Sentinel Element

Sentinels can simplify loops. How can you optimize a loop with two conditions by using a sentinel value in the data? With the C# programming language, we make a loop with two conditions only have one by using a sentinel element in the data array.

This C# performance article shows how to use a sentinel value to improve loops.

Examples

In this example, we have two conditions that must be satisfied for the loop to continue: the number of elements encountered must be less than N, and the elements must be greater than zero. In Example1, we specify these two conditions as if-statements. In Example 2, meanwhile, we force the search to stop at the maximum number of elements by changing the data after the last valid element. We can then use a single check for each element to ensure validity.

Notice: There are two if-statements in Example1's inner loop, but only one in Example2's inner loop.

Program that uses sentinel [C#]

using System;

class Program
{
    static void Main()
    {
	Console.WriteLine(Example1(5));
	Console.WriteLine(Example2(5));
    }

    static int Example1(int n)
    {
	// Count number of elements greater than zero in first N elements.
	int[] array = { 1, 1, 2, 2, 3, 3, 4, 4, 5, 5 };

	// Loop.
	int position = 0;
	int count = 0;
	while (true)
	{
	    if (position >= n)
	    {
		break;
	    }
	    if (array[position] <= 0)
	    {
		break;
	    }
	    count++;
	    position++;
	}
	return count;
    }

    static int Example2(int n)
    {
	// Count number of elements greater than zero in first N elements.
	int[] array = { 1, 1, 2, 2, 3, 3, 4, 4, 5, 5 };

	// Assign a sentinel.
	array[n] = 0;

	// Loop.
	int position = 0;
	int count = 0;
	while (true)
	{
	    if (array[position] <= 0)
	    {
		break;
	    }
	    count++;
	    position++;
	}
	return count;
    }
}

Output

5
5

Bad example

The difficulty with demonstrating sentinel code is that most of the uses of sentinels would come in complex searching algorithms. Because of their complexity, they are not easy to demonstrate and not widely applicable. However, the core concept here is durable: you can mutate the data source to reduce the number of logical checks in an inner loop, improving performance by reducing branches.

Summary

Sentinels can be used in arrays to make search loops less complicated and faster to execute. The cost of changing the data must be weighed again the performance gain in the inner loop. Because of this consideration, sentinels are best suited for very long-running loops, such as those that are executed thousands of times.