Virtual locality of reference

Quite a lot of programmers consider the advantages of locality of reference; if they put all the data they work with in about the same space the processor will be able to retreive them more easily, for the processor caches regions of memory in the Lx caches.

Quite a lot of memory managers even move objects for you in the same place which seem to depend on each other. This doesn’t only decrease fragmentation, for they would be freed in the same timespan, but also increase performance due to locality of reference.

Although the advantage of locality of reference isn’t as big as most people presume in some situations due to virtual memory.

The address space a process sees is a virtual address space, it is mapped in place by the OS. This means that 0x1234 can contain an image for one process and a normal integer for another process. This enables two processes to be loaded, virtually, in the same place.

One implication this has on locality of reference is that a seamingly contiguous piece of memory can in physically be distributed over quite a big span of real physical memory. One part of your list could be at 0x1300, the other at 0x30240.

If your program wants to enumerate through that list it`ll have to query the RAM for the second part, which it wouldn’t have to if it would be contiguous in the physical memory, for then it would most likely be in complete in the L2 cache.

The physical memory is mapped page by page into the virtual memory space. Usually pages are 2KB. Each page is always contiguous in physical memory for it can’t be split up by mapping. Therefore locality of reference always works within a page.

It doesn’t mean that if you are working with more than a page of memory it will be all fragmented. The OS usually does a good job at keeping pages contiguous in physical memory when it is contiguous in virtual memory.

Although when a computer is under some load and it’ll have to use each bit of memory and swap in and out memory it will likely be a lot more fragmented.

I don’t want people to be ignorant about the advantage of locality of reference when dealing with more than a page of memory. I want people that trade of literally everything for their holy locality of reference to see that it’s just a nice extra, but that it just doesn’t always work due to fragmentation of the physical memory.

Side notes
Virtual memory is a bit more complicated than I explained, read about it on wikipedia.
Processors will try to keep virtual memory address space in mind to avoid this issue, although it’s limited.