4 ms·

LRU implementation in C++

29 points by ahanjura 15y ago

abcd_f 15y ago
How is this notable?
- jcapote 15y ago
  How is your comment worthwhile?
  - abcd_f 15y 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 15y ago
    yes it is. it asks a legitimate question.
tlack 15y ago
For comparison's sake, here's a simple LRU in Erlang: http://erlangquicktips.heroku.com/2008/10/05/an-erlang-lru-module/ http://erlangquicktips.heroku.com/2008/10/05/an-erlang-lru-m...
- rudiger 15y ago
  In Java, LinkedHashMap[1] is well-suited to building LRU caches. [1] http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashMap.html http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHas...
  - Someone 15y 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 15y ago
  And one in Clojure. :-) https://github.com/clojure/core.cache/blob/master/src/main/clojure/clojure/core/cache.clj#L151 https://github.com/clojure/core.cache/blob/master/src/main/c...
jsaxton86 15y ago
This algorithm is arguably already patented: http://www.patentstorm.us/patents/5893120.html 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&subj=news&tag=2547-1_3-0-20 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.
bborud 15y 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.
albertzeyer 15y ago
Here is another simple implementation in C++: https://github.com/albertz/grub-fuse/blob/master/include/cache.h https://github.com/albertz/grub-fuse/blob/master/include/cac... Usage example: https://github.com/albertz/grub-fuse/blob/master/grub-core/fs/reiserfs_key_cache.cpp https://github.com/albertz/grub-fuse/blob/master/grub-core/f...

29 points by ahanjura 15y ago

abcd_f 15y ago

How is this notable?

jcapote 15y ago
How is your comment worthwhile?
- abcd_f 15y 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 15y ago
  yes it is. it asks a legitimate question.

tlack 15y ago

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

rudiger 15y ago
In Java, LinkedHashMap[1] is well-suited to building LRU caches. [1] http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashMap.html http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHas...
- Someone 15y 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 15y ago
And one in Clojure. :-) https://github.com/clojure/core.cache/blob/master/src/main/clojure/clojure/core/cache.clj#L151 https://github.com/clojure/core.cache/blob/master/src/main/c...

jsaxton86 15y ago

This algorithm is arguably already patented: http://www.patentstorm.us/patents/5893120.html 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&subj=news&tag=2547-1_3-0-20 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.

bborud 15y 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.

albertzeyer 15y ago

Here is another simple implementation in C++: https://github.com/albertz/grub-fuse/blob/master/include/cache.h https://github.com/albertz/grub-fuse/blob/master/include/cac... Usage example: https://github.com/albertz/grub-fuse/blob/master/grub-core/fs/reiserfs_key_cache.cpp https://github.com/albertz/grub-fuse/blob/master/grub-core/f...