I am currently working on a project where I need to implement a cache with limited size.

The most common eviction policy seems to be Least recently used (LRU), that simply discards the least recently used items first.

However, my cache will manage elements that have different size. Therefore, in some cases, the algorithm have to evict several elements in order to store the new one.

Will this make the LRU algorithm less efficient? are there better alternatives in this case?

I wonder if an algorithm that take into account the size of the element to know wich one to delete could be better or not.

This cache will be used for several kinds of elements, and therefore, dosn't follow a clear predictive pattern.


LRU the most efficient ?

The efficiency of LRU depends on the data access patterns. For a file system or for typical paged memory access, LRU turns out to be an excellent choice. But what are the access patterns of your application ?

Other candidate for performance leadership are (the patented) ARC and its variant CAR.

LRU and variable size items ?

LRU was designed for caching items that all have the same size, like fixed-sized memory pages of file systems (it's not the variable size files that are cached, but the underlying file system "blocks" or whatever term is used for fixed size chunks in your favourite OS).

You can use LRU for variable-sized items if your implementation is based on linked-list (and not indexes). But you will face the typical memory management problems of finding contiguous space and manage fragmentation.

For example, if your LRU-item is larger than its replacement, you'll fragment cache memory, with the risk of loosing smaller areas that cannot be reused.

Or if your new item is larger than the LRU-item, there are several possibilities:

  • you look at more recent items until you find one big enough (and what if you find none ?). This seems frightening, but I can reassure you: there is even a Largest-File-First cache policy.
  • you use several neighbour items until you have enough space (but you might also free some very recent ones)
  • you may want to find a sequence of items of the desired size, where the cumulated age is the oldest (but the combinatorials might make it expensive),
  • you fill the gaps and manage the use of fragmented areas (like some variants of sparse arrays). But this means to accept the overhead of combining the fragments when data is used;
  • you may use handles and move blocks corresponding to the handles (or defragment your LRU list, in a similar manner than disks are defragmented).
  • etc...

As you see, there are plenty of possibilities. So you need to first have an understanding of your access patterns, and benchmark the alternatives.

Or are items of different fixed-size ?

Now if your items are of different size, but if this size is not random it's a different story. If the size is selected from a very limited set of p different values (e.g. items of 10, 50 or 100 bytes), then you could consider using LRU by having p LRU data structures, with a an arbitration rule that may reallocate freed LRU space appropriately (e.g. ensuring that one LRU structure does not cause starvation of the others. I imagine that a quota rule could be used for this purpose (e.g. "the LRU structure that has the fewest elements will be served first" or something like this). You'll have to fine-tune with some simulations.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.