Implementing LRU cache in PHP
“Least Recently Used” is a practical caching technique that holds frequently accessed data and discards unused items.
The LRU cache is a Cache replacement policy, one of many, which:
are optimizing instructions, or algorithms, that a computer program or a hardware-maintained structure can utilize in order to manage a cache of information stored on the computer. Caching improves performance by keeping recent or often-used data items in memory locations that are faster or computationally cheaper to access than normal memory stores. When the cache is full, the algorithm must choose which items to discard to make room for the new ones
The definition
It’s a cache strategy that holds items of a finite amount. When the cache is full and you try to insert another cache item, it should remove the “least used cache” item to make room for the newcomer.
LRU cache use-case
LRU cache algorithm increases code execution efficiency by caching frequently used data. The cache size limit reduces memory usage to a sensible amount. This strategy is useful for long-running processes handling large quantities of data.
How the LRU cache works
Imagine an empty cache for five numbers. Initially, it is empty:
As we insert new numbers they are appended to the cache. When we insert 4 the cache looks like follows:
Then we insert 8. This element is not yet in the cache so it goes to the front:
Then, we subsequently insert 15, then 16 and 23. Number 4 becomes the “least used element”.
This is the time when things start to get interesting. We would like to add another number to the list 42. Since only five numbers are allowed, we remove the “least used number” and prepend the number to the list. The new “least used number” is 8:
Now we would like to request number 8 from the cache. The number is in the list so it is pushed to the front of the list. The new “least used number” is 15:
PHP implementation
We should begin with an interface. It will be annotated with generics to:
- properly resolve variable types in PHPStorm
- allow strict code validation for tools like Psalm/PHPStan
The interface
The implementation
Example usage
Any doubts? Thoughts? Please leave me a comment on what you think. Let’s together make our code beautiful. Subscribe to my publications for more articles like this to become a better developer.
Was this story of any value to you? Please support my work by leaving a 👏 clap as a token of appreciation. Did you know that you can clap more than once? 🥰 Thank You.