What is the difference between LRU and LFU

Let’s consider a constant stream of cache requests with a cache capacity of 3, see below:

A, B, C, A, A, A, A, A, A, A, A, A, A, A, B, C, D

If we just consider a Least Recently Used (LRU) cache with a HashMap + doubly linked list implementation with O(1) eviction time and O(1) load time, we would have the following elements cached while processing the caching requests as mentioned above.

[A]
[A, B]
[A, B, C]
[B, C, A] <- a stream of As keeps A at the head of the list.
[C, A, B]
[A, B, C]
[B, C, D] <- here, we evict A, we can do better!

When you look at this example, you can easily see that we can do better – given the higher expected chance of requesting an A in the future, we should not evict it even if it was least recently used.

A - 12
B - 2
C - 2
D - 1

Least Frequently Used (LFU) cache takes advantage of this information by keeping track of how many times the cache request has been used in its eviction algorithm.

Related Posts:

  1. Memcached vs. Redis?
  2. What is the “Endurance Cache” feature in my WordPress website?
  3. Conflict Miss v/s Compulsory Miss
  4. What is the advantage of caching an entire line instead of a single byte or word at a time?
  5. calculate the effective access time
  6. What is __pycache__?
  7. What is __pycache__?
  8. Write-back vs Write-Through caching?
  9. Why does cache use Most Recently Used (MRU) algorithm as evict policy?
  10. Read whole ASCII file into C++ std::string
  11. How to clear gradle cache?
  12. Laravel 5 Clear Views Cache
  13. Clear the cache in JavaScript
  14. How to implement a most-recently-used cache
  15. How can I cache image files locally with PhoneGap / Cordova?
  16. W3 Total Cache WordPress plugin disturbing my page layout

Leave a Comment