A nice refresher on data locality, and coding techniques to improve it for substantial performance gains.

Data Locality

by Bob Nystrom

From the article:

Sure, we can process data faster than ever, but we can’t get that data faster. ...

When I started working on this chapter, I spent some time putting together little game-like programs that would trigger best case and worst case cache usage. I wanted benchmarks that would thrash the cache so I could see first-hand how much bloodshed it causes.

When I got some stuff working, I was surprised. I knew it was a big deal, but there’s nothing quite like seeing it with your own eyes. I wrote two programs that did the exact same computation. The only difference was how many cache misses they caused. The slow one was fifty times slower than the other.