Cache Locality

Modern processors include a small amount of very fast memory called a cache. When the program reads a value, the processor also pulls in a block of other neighboring values. If the other values the program is going to need soon are all in this block, then the read accesses will be fast.

If they are many memory addresses away, the processor must go all the way back to the main memory, and the program becomes slower.

This phenomenon is called cache locality. The simplest thing to do to achieve cache locality is to store data items that you will use sequentially in consecutive memory addresses and then access them in order. The complete program shown in Code 1 fills the data array sequentially and sums the elements of the array sequentially.

#include <iostream>

int main()
{
    int data[1000]{};

    // Increment the value before the expression uses it
    for (int i{0}; i < 1000; ++i)
        data[i] = i;

    int sum{0};

    for (int i{0}; i < 1000; ++i)
        sum += data[i];

    std::cout << sum << '\n';
}

Because the array data is stored in one consecutive region of memory and the loops access it from one end to the other, each cache line fetched from main memory into the cache will likely contain values that are going to be used in future loop iterations.

The program shows excellent spatial locality, and the sum is computed very rapidly.

Compare this with the program shown in Code 2, which steps through memory with a relatively large stride.

#include <iostream>

int main()
{
    int data[1000]{};

    // Stop before the upper boundary is reached
    for (int i{0}; i < 1000; ++i)
        data[i] = i;

    int sum{0};

    for (int i{0}; i < 1000; i += 16)
        sum += data[i];

    std::cout << sum << '\n';
}

Again, the array data is in one consecutive location in memory, but the loops now take a big jump between consecutive memory locations being accessed. Many of the values fetched from memory into the cache are then not used, and the next memory location being accessed will most likely be outside the currently cached line and require a trip back to main memory.

While the total amount of computations in Code 1 and Code 2 are the same, Code 2 is much slower because of higher memory traffic.

In the case of two dimensional arrays, loop order can play an even greater role in cache locality.

Consider a simple two dimensional array stored in row major format, as C++ usually does for built in arrays.

#include <iostream>

int main()
{
    int matrix[100][100]{};

    for (int row{0}; row < 100; ++row)
    {
        for (int col{0}; col < 100; ++col)
            matrix[row][col] = row + col;
    }

    int sum{0};

    for (int row{0}; row < 100; ++row)
    {
        for (int col{0}; col < 100; ++col)
            // Add the value and store the result back in the same variable
            sum += matrix[row][col];
    }

    std::cout << sum << '\n';
}

The code that iterates in a row major order can see extremely good performance. The logic of the access pattern in both loops matches exactly how the elements are stored in memory. When a cache line containing many elements from the current row is fetched into the processor, they are all accessed in subsequent inner loop iterations.

Code 4 is the counterpoint, in which we swap the inner and outer loop.

#include <iostream>

int main()
{
    int matrix[100][100]{};

    for (int row{0}; row < 100; ++row)
    {
        for (int col{0}; col < 100; ++col)
            matrix[row][col] = row + col;
    }

    int sum{0};

    for (int col{0}; col < 100; ++col)
    {
        for (int row{0}; row < 100; ++row)
            sum += matrix[row][col];
    }

    std::cout << sum << '\n';
}

Now, when accessing an element within a row, each access will traverse across the entire memory address range of the row as if stepping by column number across successive rows.

Most of the elements within a cached line will be skipped, and a new cache line will be required virtually every inner loop iteration. Performance of Code 4 is significantly worse than that of Code 3.

A good general rule when both data arrangement and iteration orders are under your control: arrange the data, and order the loops to match the data.

In the extreme, if the arrangement of data cannot be changed, the access patterns should be arranged to match the existing layout as best as possible, often by changing the order of the loops. The resulting improvement in cache locality can often provide a welcome 10x improvement over naive implementations.