Thread: Locality of program

In what context did you encounter the phrase "locality of program"?

Normally in the context of programming, locality refers to variables in use being close to each other in memory.

Locality is important especially for caching. When I run a program, and I decide to use variable x, the processor does not just fetch variable x from memory, but also everything that is around variable x in memory, and it puts it in the processor cache. It does this because it assumes that much of what we do with variable x will involve variables found very close to x in memory, and in fact if we do something like this:

Code:

void myfunc ( void )
{
        int x = 0;
        int y = 5;
        int z = 10;
}

Chances are they will will be located near each other in memory. One of the classic examples of locality and caching is looping through a matrix. Of course, when you iterate through a matrix the ideal way to do it (under normal circumstances) is in row-major order because elements in the same row of the matrix should be near each other in memory, while elements in different rows are probably much farther apart:

Code:

void myfunc ( void )
{
        int mat[5][5];

        for ( int y = 0; y < 5; y++ )
                for ( int x = 0; x < 5; x++ )
                        mat[y][x] = something;
}

This causes more cache hits/less cache misses.

This is how I usually understand locality in a programming context...I don't know if it has any other meaning in the programming world.