Spatial Locality

Computer scientists like to refer to this idea as either spatial locality or locality of reference. That is, code is faster if it keeps accessing data that is near other data that was accessed recently. So, if our code accessed array[0], it’s great if the next data the computer grabs is array[1] or array[2]. Because array[1] and array[2] are near array[0], they’re likely already in the cache.

Understanding the computer’s caching hardware allows us to avoid these pitfalls and write faster code. In this case, the difference is significant. When I benchmark summing a two-dimensional array of size 10,000, Version One takes about 9 seconds, while Version Two takes roughly 18 seconds. Leveraging spatial locality, in this case, makes our software twice as fast!

Arrays vs. Linked Lists

Another practical application of memory caching comes into play when iterating over arrays and linked lists. Although iterating over each data structure takes O(N) time, it’s way faster to iterate over an array than a linked list. This, again, is because of spatial locality. Specifically, when we access array[0], the next chunk of the array is loaded into the cache for quick access.

With a linked list, though, the nodes are not necessarily near each other in memory. Therefore, when we access the list’s first node, the other nodes do not get cached. The computer has to laboriously jump around from memory cell to memory cell to access each node. Accordingly, iterating over a linked list is generally slower than iterating over an array.

Mergesort vs. Quicksort

Ah, you thought we were done talking about Mergesort, weren’t you? Surprise! Back in , I explained that even though both Mergesort and Quicksort, in the world of Big O notation, are O(N log N), Quicksort is usually faster than Mergesort in the real world.

Back then, we offered up one potential reason for why this might be so. But now we have another possible reason: Quicksort is better than Mergesort in terms of spatial locality.

As different computers utilize caches in different ways, it’s not always easy to definitively explain why one algorithm works better with a cache than another. However, here’s a general idea: because Quicksort sorts an array in place, the algorithm repeatedly accesses the same array. So, once this array is in the cache, Quicksort can always access each element of the array extremely quickly. Mergesort, on the other hand, is always creating new arrays. Because Mergesort has to juggle data from a number of different arrays, not all the data that we need at the moment is in the cache.