LRU cache reject method

Unfortunately, I once again noticed that almost all my colleagues do not know what LRU is and how to implement a cache of a certain size. So I decided to write a small article where I’ll tell you how to quickly implement the LRU method, and not force colleagues to manually reset the cache where it’s not needed.

We will be caching understand the preservation of the results of calculations in response to some queries. That is, the repeated result of the query is not always re-evaluated, but sometimes it is taken from a table called a cache. It is difficult to overestimate the role of caching in modern systems. In this case, often there is a problem associated with a lack of memory. Indeed, what to do if there are a lot of requests, and there is enough memory only to store a limited number of results? In this case, as a rule, the cash line is as follows. The cache size is fixed, let it be N , and the results are saved only for the N most "popular" queries.

That is, the results of calculations are saved, which will most likely be asked again.
How to determine these "popular" requests? The best known method is LRU , which I will discuss in this article.

LRU (least recently used) is an algorithm that pushes values ​​that have not been requested for the longest. Accordingly, it is necessary to store the time of the last request to the value. And as soon as the number of cached values ​​exceeds N, it is necessary to force out the value that was not requested for the longest.
')
To implement this method, we need two data structures:

1. A hashTable hash table that will store the directly cached values.
2. TimeQueue priority queue . A structure that supports the following operations:
   • Add a pair value and priority timeQueue.Add (val, priority) .
   • Extract (delete and return) the value with the lowest priority timeQueue.extractMinValue () .

Read more about priority queues here.

Suppose that for the initial calculations used the method calculate (x) . We will replace the calculate method with a new calculateWithCache , which replenishes the cache, pushes outdated values ​​and requests the result from calculate , if it does not find it in the cache.

This is how the calculateWithCache algorithm works:

calculateWithCache(key) { curTime = getCurrentTime(); //         if (key in hashTable) { //       key timeQueue.set(key, curTime); return hashTable[key]; } //    result = calculate(key); //     N ,     if (hashTable.length == N) { minKey = timeQueue.extractMinValue(); hashTable.remove(minKey); } //   ,    hashTable.add(key, result); timeQueue.add(key, curTime); return result; } 

That's all. Now instead of having to reset the cache, the user needs to set the cache size. At the same time, setting a reasonable default value is welcome.

If we use the effective implementation of the priority queue, then the overhead projector that requires LRU is O (log N) .

In standard libraries, a priority queue can be implemented, for example, in C ++. But even if it is not implemented, but it is lazy to read, then you can guess how to use a balanced tree to implement the priority queue with the same complexity, though with a slightly larger coefficient.

A question for those who want to think a little. How to achieve a constant overhead projector, considering that the complexity of a hash table operation is a constant?
Tip: you need to remove the priority queue and use the normal queue :)

You can find more sophisticated heuristics that take into account the calculation time for calculate for a given key , or result volume, or something else.
But in most tasks, LRU most adequately determines the most "popular" requests.

Note 1 : You can limit the amount of memory in the cache, not the number of stored values. The algorithm practically does not change, but instead of the length there will be occupied memory + memory for storing the new value.
Note 2 : Specially avoided questions of multithreading, since this is not the topic of this article.

Update (Thanks to ToSHiC22 for the comment) For those interested, a link to a slightly more advanced 2Q implementation