The first type of cache, or rather of eviction policy, that we are going to describe is the LRU (least recently used) cache, purging the cache’s least recently used entry each time.
What do we need to implement this data structure? The operations we want to optimize for are
- Storing an entry given the name of a company (obviously)
- Checking if there is an entry stored for a name
- Retrieving an entry by name
- Getting the number of elements stored
- Getting the oldest entry and purging it from the cache
As we explained in section 7.3, this data structure will only be able to store a certain number of elements at the same time. The actual size of the cache can be decided on creation and, depending on the implementation, can even be changed dynamically. We will denote with n the number of elements that can be stored in the cache. When the cache is already at its full capacity, if we need to add a new entry, we will have to remove one of the existing ones, and in this case we will remove the one that was least recently used (hence the name).
Let’s now reason about which one, among the basic data structures we have seen so far, could guarantee us the best performance. Handling the size of the cache is easy; we can keep a variable for that and update it in constant time, so we won’t mention it any further in this analysis.
Checking if an entry exists is based on finding an entry by name, so only the latter operation needs to be analyzed.
Storing and retrieving entries by name should ring a bell. It’s clearly what an associative array does, so hash tables would be the obvious choice there. Hash tables, however, are not great when it comes to retrieving the minimum (or maximum) element they contain.
In fact, removing the oldest element could take up to linear time and, unless the expected life of the cache is so short that, on average, we are not going to fill it completely, this could slow down every insertion of a new entry.
Using arrays doesn’t seem like a good idea, because they would not speed up any of the operations, or at most just a single one, while requiring all the space for maximum capacity to be allocated from the start.
Linked lists seem promising for keeping the order of insertion, but they wouldn’t be great when it comes to looking up entries.
If you read appendix C, you might remember that there is a data structure offering a compromise between all of these different operations: balanced trees! With a tree, we would be able to guarantee that all of these operations could be performed in logarithmic time in the worst-case scenario.
So, from table 7.1, we could infer that
- The tree would look like the best compromise on the general case.
- The hash table would be the best choice if we know the size of the cache is big enough (and the insertion of new elements infrequent enough) to rarely require removal of the oldest entry.
- The linked list could be a valid option if removing old entries was more important than storing entries or finding cache elements: but in that case, the cache would basically be useless and adding it would provide no benefit.
- In all cases, the memory needed to store n entries is O(n).
Now the question is, can we do any better?
1. Sometimes you have to double down on problems
As you can imagine, if the answer were no, we wouldn’t really be asking the question in the first place.
But how can we do any better? There isn’t any other data structure that allows us to optimize all three main operations at the same time.
And yet . . . . What if I told you that it is possible to design an LRU cache that takes O(1) amortized time[2] for all those operations?
Before you go on and read the solution to the riddle, please try for a couple of minutes to imagine how that could be possible.
Let me give you two hints (spoiler alert: you might want to try designing a solution before reading them):
- You can use as much extra memory as you want (but staying within O(n) should be your target).
- The fact that I mentioned linked lists should ring a bell, and make you think about a specific data structure we saw in appendix C. Nevertheless, we have seen that it’s not enough if you take it alone.
Both hints point to the same idea: a single data structure might not be enough to build the most efficient solution to the problem.
On the one hand, we have data structures that are particularly good for quickly storing and retrieving entries. Hash tables are pretty much impossible to beat if that’s the game.
On the other hand, hash tables are terrible when it comes to maintaining an ordering of things, but we have other structures that handle this very well. Depending on the kind of ordering we would like to keep, we might need trees, or we might be fine with lists. We’ll actually see both cases in the rest of the chapter.
In light of this new hint, pause for another minute and try to imagine how to make this work. Can you come up with an idea of how to combine a hash table and another data structure in order to optimize all operations on a cache?
2. Temporal ordering
It turns out that we have a very simple way to do so. Before delving into this section, you might want to look at appendix C if you can’t exactly remember the running time for operations on arrays and lists, and the difference between singly- and doubly-linked lists.
So, imagine that you only have to keep an ordering on the cache entries, being able to go from the least to the most recently used. Since the order is only based on insertion time, new elements are not changing the order of the older elements; therefore, we don’t need anything fancy: we only need a structure that supports FIFO. We could just use a list or a queue. As you should remember, a linked list is usually the best choice when we don’t know in advance the number of elements we will have to store or the number can change dynamically, while a queue is usually implemented using an array (and so more static in dimension), but optimized for insertion on the head and removal on the tail.
Linked lists can also support fast insertion/removal at their ends. We need, however, a doubly-linked list, as shown in figure 7.5, where we insert elements on the front, and remove from the tail. By always keeping a pointer to the tail and links from each node to its predecessor, we can implement tail removal in O(1) time.
Listing 7.1 shows some pseudo-code implementing an LRU with linked lists.
When static queues are implemented using arrays, we can save some extra memory in comparison to linked lists, which would use it for pointers to other nodes and for the node object itself. This is an implementation detail, though, that depends on the language used and doesn’t change the order of magnitude of the memory used: it’s O(n) in both cases.
So, in the end, how do we choose between lists and queues? Well, we need to reason a bit more about our design. So far, we have only considered the hash table and the linked list separately, but we need to make them work together in synchrony.
We might store very large objects in the cache, and we definitely don’t want to duplicate them in both data structures. One way to avoid duplication is storing the entries only in one of the structures and referencing them from the other one. We could either add the entries to the hash table and store in the other DS the key to the hash table, or vice versa.
Both linked lists and queues could support either way. But we are going to use a linked list instead; the reason will be clear in a few lines.
We also need to decide which data structure should hold the values and which one should be left with the reference. Here, we are arguing that the best choice is having hash table entries store pointers to linked list nodes, and have the latter store the actual values, and the main reason for that is the same as for choosing lists over queues.
This reason stems from a situation we haven’t considered yet.
This cache is called least recently used. It’s not least recently added. This means the ordering is notjust based on the time we first add an element to cache, but on the last time it was accessed (which can be the same, for unlucky entries that are never reused after they have been saved, although it usually shouldn’t be).
So, considering the set method to add a new entry to the cache (implemented in listing 7.2), when we have a cache miss, trying to access an element that is not on the cache, we just add a new entry to the front of our linked list, as shown in figure 7.6.
But when we run into a cache hit, as shown in figure 7.7, accessing an element that is indeed stored on the cache, we need to move an existing list element to the front of the list, and we can only do that efficiently if we can both retrieve in constant(-ish[4]) time a pointer to the linked list node for the existing entry (which could be anywhere in the list, for what we know), and remove an element from the list in constant time (again, we need a doubly-linked list for this; with an array-based implementation of a queue, removal in the middle of the queue takes linear time).
If the cache is full, we need to remove the least-recently-used entry before we can add a new one. In this case, the method to remove the oldest entry, described in listing 7.3 and illustrated in figure 7.8, can access the tail of the linked list in constant time, from which we recover the entry to delete. To locate it on the hash table and delete from it, we will need to hash the entry (or its ID) at an extra cost (potentially non-constant: for strings, it will depend on the length of the string).
There are still a couple of methods in the API that we haven’t discussed yet: get (key) and getSize (). Their implementation, though, is trivial, because they are just wrappers for the homonymous methods in hash tables, at least if we keep values in the hash table directly. If, instead, we keep values in the linked list, and the hash table has pointers to list nodes, then in get we need to resolve this further indirection, as shown in listing 7.4.
3. Performance
So, if you look at all the previous listings, they only contain operations that are either constant-time or amortized constant-time (for the hash table). That gives us the boost in performance that we were looking for!
Table 7.2 shows an updated version of table 7.1, including an entry for the LRU cache.
Source: Rocca Marcello La (2021), Advanced Algorithms and Data Structures, Manning Publications (2021)