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 no connection to high-level languages.

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 5 repeatedly is much faster than accessing 5 elements further apart.

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

Intermediate Language

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

Speed results. 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 dictates that performance is actually constrained by the farness of elements in physical memory.

Compiler Phases

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

Article. There is another 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.

Gallery of Processor Cache Effects

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.

Related Links