LRU implementation in C++ | Hacker News Reader

LRU implementation in C++

bottlenose.demon.co.uk

29 pointsahanjura11 comments

Open articleView on HN

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

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

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

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.

And one in Clojure. :-)

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

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.

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...

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.

How is this notable?

How is your comment worthwhile?

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?

yes it is. it asks a legitimate question.

Reply on news.ycombinator.com