C# Locality of Reference

This C# performance article demonstrates locality of reference. It provides a benchmark.
Locality of reference. This refers to memory locations. It tells us that elements nearer in memory are faster to access. This is a low-level consideration. It has no connection to high-level languages.
In computer hardware, memory is often referred to as RAM (random access memory), but this is actually a misnomer. Random access memory is not random. Its performance is constrained by the physical nearness of elements.

Version 1: This code accesses the first 5 elements in the int array many times. It does nothing important with the values.

Version 2: This version of the code accesses 5 elements in the same int array, but the indexes of those elements are more spread out (further apart).

Int Array

Result: In an array with 100,000 elements, accessing the first 5 repeatedly is faster than accessing 5 elements further apart.


Info: At the high level of the .NET Framework, the instruction count is equivalent. But the physical aspects of the hardware come into play.

C# program that benchmarks locality of reference using System; using System.Diagnostics; class Program { static void Method1(int[] array) { // Assign elements near in physical location. for (int i = 0; i < 10; i++) { array[0] = 1; array[1] = 1; array[2] = 1; array[3] = 1; array[4] = 1; } } static void Method2(int[] array) { // Assign elements spread out in location. for (int i = 0; i < 10; i++) { array[0] = 1; array[10000] = 1; array[20000] = 1; array[30000] = 1; array[40000] = 1; } } const int _max = 10000000; const int _size = 100000; static void Main() { int[] array = new int[_size]; Method1(array); Method2(array); array = new int[_size]; GC.Collect(); var s1 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { Method1(array); } s1.Stop(); array = new int[_size]; GC.Collect(); 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(); } } Output 20.99 ns 23.65 ns
In compiler theory, this relates to the memory hierarchy and the principle of locality of reference. Specifically, spatial locality dictates that performance is actually constrained by the farness of elements in physical memory.

Note: In spatial locality, the farther away an element is, the longer it may take to access it.

Summary. We tested locality of reference in the .NET Framework. Even in high-level languages, locality of reference comes into play. This influences or even greatly determines performance levels.

Thus: At all levels of computer programming, locality of elements in memory can be thought of as a performance determinant.

© 2007-2019 Sam Allen. Every person is special and unique. Send bug reports to info@dotnetperls.com.
Dot Net Perls