C# Locality of Reference

Locality of reference refers to memory locations. It tells us that elements nearer in memory are faster to access. This is a low-level consideration. It has nothing to do with high-level languages such as C#. Instead it simply reflects the influence of the hardware on performance.

This C# performance article demonstrates locality of reference.

Example

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. Therefore, in an array with 100,000 elements, accessing the first five elements repeatedly is much faster than accessing five elements with many elements in between them.

At the high-level of the C# language, the instruction count is equivalent, but below this abstraction the physical aspects of the hardware come into play.

Program that benchmarks locality of reference [C#]

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

What we see. As indicated, the tight loop in Method1 that accesses five adjacent elements in the integer array is much faster than the tight loop in Method2 that accesses five spaced-out elements.

In compiler theory, this relates to the memory hierarchy and the principle of locality of reference—specifically, spatial locality, which dictates that performance is actually constrained by the farness of elements in physical memory. The farther away an element is, the longer it may take to access it.

Article

There is another interesting article on this topic, which deals with how processor caches can affect spatial locality. Igor Ostrovsky describes and tests processor caches in the C# language. His article is more detailed and complete than this one and highly recommended.

Summary

Even in high-level languages, locality of reference comes into play and influences or even greatly determines performance levels. This means, then, that at all levels of computer programming locality of elements in memory can be thought of as a performance determinant.