Vertexbuffer.com

There is a classic book on optimization written in 1996. The book was revolutionary because it pointed out that optimization is not just a left brained process. Although the book is over a decade old, there are still many portions of the book that are true today. It’s view on memory is not one of them.

Ten years ago, it was likely that our application could not process arithmetic and logic fast enough to contend with the speed of memory. This is no longer the case. Now a single compulsorily cache miss can take as much time as hundreds of arithmetic operations. If your application is CPU bound, and it uses a reasonable amount of memory, then you are likely memory bound.

Cache misses play the most major role in memory issues on the CPU, but before we can discuss how to solve cache misses, we need to understand what cache misses are. Let’s use an example from my college days:

Beer Me!

My roommates and I enjoyed watching hockey games in our living room. Unfortunately, the fridge was very far away from our couch. In order to get to the fridge, we had to walk though a narrow hallway to get to the kitchen.
Sometimes when you would go to the fridge, someone would already be in the hallway, and since only one person could use the hallway at a time, you had to wait to get to the kitchen. This meant you were missing more of the game.

After missing several goals, we decided that we should get a little cooler and keep it by the couch. That way when we needed a beer, we could simply reach down and grab it. Sometimes, we would reach for a beer and the cooler would be empty (a compulsorily beer miss). We then had to go back to the fridge, but this time, we grabbed several beers and filled up the cooler.
If you haven’t figured it out yet, this somewhat uninteresting story of beer relates to the way cache works. The cooler, is similar to L1, L2, and L3 cache. The hallway, is analogous to the front side bus. The fridge is system memory. By having the cooler nearby, we were able to save a trip down the slow hallway that everyone shared. The front side bus is also shared by other devices, so having the cache nearby, saves us from missing too much of the game.

So how do we save ourselves from causing cache misses? Let’s take a look at a popular method for increasing cache performance.