4

I have been trying to find a good case in which LFU is better than LRU but I am not sure for that.

What I have managed to do (but not sure if it is a good example) is the case when you have a cache with capacity 3 and the cache requests are 4 (like A B C D) but C and D are requested more often.

So if the request stream was A B C D C A D B D C A B A C D LRU will produce 10 faults but LFU will produce 9 faults.

Is this an accepted case??

Argiris
  • 179
  • 1
  • 13
  • 2
    LRU is more efficient for small caches but scales poorly to larger ones. In those, the typical Zipf workload of a cache dominates so LFU often has a higher hit rate at a lower capacity. LRU is also problematic in scans (e.g. databases) and is often bypassed. Modern policies combine the two to find a more ideal balance. – Ben Manes Jun 05 '17 at 16:38

2 Answers2

1

You may find this helpful. LRU is quite staright forward.

Your mobile keyboard uses LFU. When you type some letters you can see few suggested words at the top of the keyboard matching with the letters you have typed. At the begining when the keyboard app's cache is empty, it may show you these 4 words ( Lets assume, you typed letters "STA". Suggested words may pop like ex. start, stand, statue, staff). The idea here is that, based on the words you use, it will ignore the LRU word in the suggestions after a certain time. You may not see the word "staff" in the suggesions later on if you haven't used it.

If you have a case where you know that the data is pretty repetative, surely go for LFU to avoid cache miss. It seems that these both are independent quite clearly and have isolative significance. It depends on the use case of where you want to use any of these.

Ankush Rathi
  • 612
  • 1
  • 6
  • 26
1

It may happen that some data was popular in the past and currently becomes temporarily irrelevant, but then it will likely be accessed again in the near future.

Think about an online retailer store. Let's say some of their best selling items are camera, phone etc.If Valentine's day is around the corner, people are going to order gifts for Valentine's day. So if you implemented LRU cache, Least Recently Used cache, it will purge your best selling items from the cache.

enter image description here

While LRU policy never guarantees that best-selling items will stay in the cache, the higher frequency with which they are accessed makes it more likely that they will stay in the cache (because it is likely they will go to the head of the queue before being purged). During a peak, if the number of items that suddenly become popular is large enough, they could fill the cache and force the usual items to be purged. This would be a temporary side effect that will regress after the peak. In some situations, this could also be desirable, because items popular during a peak should be accessed faster than the regular best-selling ones.

Yilmaz
  • 1
  • 7
  • 79
  • 120