View Full Version : Locality of program

05-15-2009, 12:54 AM
I don't understand what locality of program means.

I searched in the oxford dicitonary and got this result:
AskOxford: locality (http://www.askoxford.com/concise_oed/locality?view=uk)

noun (pl. localities) 1 an area or neighbourhood. 2 the position or site of something.

Can someone explain this to me?


05-15-2009, 01:05 AM
In what context did you encounter the phrase "locality of program"?

05-15-2009, 02:02 AM
I got it:

Most programs display a high degree of locality: the same set of pages,the current working set, is being referenced repeatedly.

05-15-2009, 06:27 PM
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:

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:

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.