LRU implementation in C++

LRU implementation in C++(bottlenose.demon.co.uk)

29 points by ahanjura 14 years ago | 11 comments

tlack 14 years ago |

For comparison's sake, here's a simple LRU in Erlang: http://erlangquicktips.heroku.com/2008/10/05/an-erlang-lru-m...

rudiger 14 years ago | |

In Java, LinkedHashMap[1] is well-suited to building LRU caches.

[1] http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHas...

Someone 14 years ago | | |

However, one should be aware of that "Note that insertion order is not affected if a key is re-inserted into the map".

Because of that, a timestamps update must do:

  Cache.remove(key);
  Cache.put(key,value);

Only doing the latter will not move the item to its correct location.

Also, I am too lazy to chrck it, but I do not think this will have the same big-O as the C++ code.

fogus 14 years ago | |

And one in Clojure. :-)

https://github.com/clojure/core.cache/blob/master/src/main/c...

jsaxton86 14 years ago |

This algorithm is arguably already patented: http://www.patentstorm.us/patents/5893120.html

In fact, you may remember that Google was sued over this last year: http://news.cnet.com/8301-13577_3-20056192-36.html?part=rss&...

Granted, using a timestamp to expire hash table entries is probably different enough from using a timestamp to evict cache entries where I would hope this wouldn't hold up in court, but IANAL and I could be totally wrong here. Another possibility is that there could be a totally different patent that already covers this algorithm.

albertzeyer 14 years ago |

Here is another simple implementation in C++: https://github.com/albertz/grub-fuse/blob/master/include/cac...

Usage example: https://github.com/albertz/grub-fuse/blob/master/grub-core/f...

bborud 14 years ago |

If this article shows anything it is that C++ never really "grew up". Even in Java, implementing an LRU cache is such a trivial thing to do because most people actually use, and build on, the standard library.

abcd_f 14 years ago |

How is this notable?

jcapote 14 years ago | |

How is your comment worthwhile?

abcd_f 14 years ago | | |

In a condensed form of a rhetorical question it states that LRU cache containers are fairly trivial and they are routinely implemented as a part of larger projects. It typically takes under an hour to do and it comes out lighter and more legible if one does not depend on boost.

So, how is this notable? Is it L2-cache friendly? Is it optimized not to fragment heap? Perhaps it's lockfree?

bborud 14 years ago | | |

yes it is. it asks a legitimate question.