Caching

There are two hard things in computer science: cache invalidation and naming things. 1

1

Phil Karlton, according to Martin Fowler

Few optimization tricks are as general-purpose as the idea of caching. A cache is a resource that has been collected near to where it will be needed. For example, you might have a large storage jar of salt in your pantry, a salt cellar for taking pinches in the kitchen, and a salt shaker at your dining room table. That way you have convenient access in the different situations where you might want it.

Why not just always go to the storage container in the pantry when you need salt? It would be easier in some ways, because you wouldn’t have to keep track of when the salt shaker needed refilling or waste any space in the dining room. It would be inconvenient, however, to have to get up from the table and go to the pantry and open up the big storage container for every pinch of salt you want. Why not keep it at the table, then? Well, you would run out of space at the table using it to store the whole quantity of every resource you might want to use there.

Caching is a space–time tradeoff. By keeping a resource in multiple places, you are using more space, but are prepared to use it faster in the ways you have foreseen. Managing the caches takes some work, but if you have correctly predicted how you will be using them, the benefit easily outweights the cost.

An example in programming is the decision to store a value rather than recomputing it as needed. In C, strings don’t record how long they are; you can call strlen to compute the length of a string, but it does it by counting each letter one-by-one until it reaches the null terminator. Consider the following loop with that in mind.

..code:

int i;
char message[] = "This is a message";

for (i = 0; i < strlen(message); i++)
    printf("%d: %c\n", i, message[i]);

This will print each letter of the message with its index, but a naïve interpretation of this code would call strlen(message) each time it checks the loop condition, making this snippet take \(O(n^2)\) time in the length of the message. Instead, we could cache the length.

..code:

int i;
char message[] = "This is a message";
int len = strlen(message);

for (i = 0; i < len; i++)
    printf("%d: %c\n", i, message[i]);

In this example, the value of strlen(message) is cached in the variable len, which enables the programmer to cheaply access the length of the message without recomputing it, for the lifetime of that cached variable.

But what if the value should be recomputed? When iterating over a string, you might need to recompute its length when the length changes. This is a problem that comes up frequently in the web, when you see an old version of a web page until you tell your browser to ‘refresh’ it.

One of the most important places caching appears in modern computing is invisibly tucked into the memory hierarchy between the CPU and the RAM. This cache is managed entirely by hardware, below the level of even the OS, although some hardware offers configuration settings an OS can change. Part of writing code on a modern computer that has good performance is knowing how the cache will be working on your behalf and playing to its strengths.

…and off-by-one errors 2

2

Leon Bambrick

You have attempted of activities on this page