Chapter 4
Cache Is King

In the previous chapter, I introduced randomized algorithms and explained how randomization can boost the efficiency of all sorts of applications. In this chapter, you’ll discover how randomization can also boost the speed of a process known as caching.

Caching is built into the hardware of virtually all computers and affects the speed of the code you write. At the same time, you can create software that performs additional layers of caching as well.

But whether you write your own caching code or leverage the caching built into your computer, understanding caching—and how randomization can play a role in it—will allow you to take your code’s speed to the next level.

In addition, caching is another key piece of the puzzle of why two algorithms can have different actual-time speeds even though they execute the same number of steps. Understanding the related concept of spatial locality can help you design faster algorithms even when Big O analysis tells you that you can’t beat the speed of the algorithm you already have.

So, without further ado, let’s dig into caching.