Home

Search

C# Sentinel Optimization

Use a sentinel value to improve loops. A sentinel helps avoid branches.

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

In this example, we have 2 conditions that must be satisfied for the loop to continue. We require the number of elements encountered must be less than N, and the elements must be greater than zero. In Example 1, we specify these 2 conditions as if-statements.
And: In Example 2 we force the search to end at the maximum number of elements by changing the data after the last valid element.
If
Then: We can use a single check for each element to ensure validity. Example2 has only one if-statement.
C# program that uses sentinel 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

Discussion. Most of the uses of sentinels would come in complex searching algorithms. Because of their complexity, they are not easy to demonstrate. And examples are not widely applicable.
Tip: 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. The cost of changing the data must be weighed against the performance gain. Because of this, sentinels are best suited for long-running loops.

Home
© 2007-2020 Sam Allen. Every person is special and unique. Send bug reports to info@dotnetperls.com.