Writing Cache-Friendly Code
Let’s get to the fun stuff. While it seems that we’ve merely had a leisurely tour through some of our computer’s hardware, these concepts can directly impact the way we should write code.
Following is some code that computes the sum of integers contained within a two-dimensional array. For simplicity, let’s assume that the array is square, meaning that the rows and columns have equal lengths. I’m going to present two versions. Here’s Version One:
| | def compute_sum(array): |
| | size = len(array) |
| | sum = 0 |
| | |
| | for row_index in range(size): |
| | for column_index in range(size): |
| | sum += array[row_index][column_index] |
| | |
| | return sum |
It’s pretty straightforward. We iterate over each row, and within each row, we iterate over each column, adding up the numbers as we go.
Now, here’s Version Two, which is only subtly different:
| | def compute_sum(array): |
| | size = len(array) |
| | sum = 0 |
| | |
| | for column_index in range(size): |
| | for row_index in range(size): |
| | sum += array[row_index][column_index] |
| | |
| | return sum |
It’s almost identical to Version One except that now we’re going in column order first, meaning that our outer loop iterates over the column indexes and the inner loop iterates over the row indexes.
Both versions get the job done, but let’s visualize the difference between these two versions.
In Version One, the following diagram depicts the order we’d process, say, an array of size 3. In the diagram, I placed little numbers in circles to indicate the order in which we iterate over each integer. (I also made all of the array integers 9 so we don’t get distracted with all the different numbers floating around.)
And here’s the order of Version Two:
Believe it or not, there’s a significant efficiency difference between these two versions since iterating by row first is faster than iterating by column first. The reason for this is the caching concepts we’ve just discussed.
We saw that if code sets or accesses a variable, that variable will be cached inside the CPU register or the like. But here’s something important: if you access an item from an array such as array[0], the computer doesn’t only cache array[0]. Depending on the array’s size, the computer may cache the entire array, or at least a good chunk of it.
This makes sense because we often iterate over arrays. And if we start a loop by accessing array[0], it’s clear that we’re about to also access array[1] and array[2] soon. So the computer, smartly, caches a large chunk of the array so that we can access those later indexes super quickly.
So in Version One, our inner loop first accesses array[row_index][column_index], which initially is array[0][0]. Because the computer accessed the first inner array, the computer “smartly” caches that entire array. In the following diagram, I used rectangles to indicate what is currently cached:
Now, this is great since next we’ll be accessing array[0][1] and array[0][2]. Because the entire array[0] is cached, the computer can grab all of these values almost instantaneously:
However, in Version Two, where we go in column order first, here’s what happens. In this version, we also start at array[0][0], so the entire array[0] is cached like before:
But here’s the snag. We next access array[1][0], which is not inside the cache:
As such, the computer doesn’t benefit from the cache speed when reading array[1][0]. Once we do access array[1][0], though, the computer now caches the entire array[1]:
Next, the computer looks up array[2][0]. Man, this isn’t in the cache either!
As “smart” as the computer is, it can’t always predict your next move. Its array-caching system is ideal if we follow the rows first, but backfires when we go by columns first.
