1

A lot of descriptions of Pseudo LRU algorithms involve using a binary search tree, and setting flags to "point away" from the node you're searching for every time you access the tree.

This leads to a reasonable approximation of LRU. However, it seems from the descriptions that all of the nodes deemed LRU would be leaf nodes. Is there a pseudo-LRU algorithm that deals with a static tree that will still perform reasonably well, while determining that non-leaf nodes are suitable LRU candidates?

edit: I've already implemented an LRU using hashmaps and linkedlists. I'm interested in seeing the performance implications of using a pseudo lru tree (especially on concurrent reads). That is why I specifically asked about pseudo lru tree algorithms, but I should have made that clearer.

patros
  • 7,719
  • 3
  • 28
  • 37
  • Perhaps this will convince you to use hashtable+linkedlist: http://stackoverflow.com/questions/2504178/lru-cache-design/2504317#2504317 –  May 22 '10 at 13:55

2 Answers2

1

You can always push your internal node down to the leaf using rotates ala red-black trees.

Keeping the tree balanced while doing that might be tough. But you do have a choice of which subtree to push down, so maybe not impossible...

Keith Randall
  • 22,985
  • 2
  • 35
  • 54
  • I'm trying to keep the tree structure static to allow concurrent reads, as well as for performance reasons. (I realize there will be race conditions on the flags, but I don't care since it's only pseudo LRU anyways. ) – patros May 03 '10 at 20:20
  • How do you keep the tree static? The node you're removing and the node you're adding don't have the same key, so they go in different parts of the tree. Do you mean "static during a cache hit" so you can use a read lock for lookup? – Keith Randall May 03 '10 at 22:15
  • The keys stay the same. I map my data to an arbitrary index (0 to (2^depth)-1). When I "remove" something I just add that node of the tree to a list of available nodes. When I add, I don't add a node I simply overwrite the data held by the node. This keeps the tree structure static, but the data is still mutable. – patros May 04 '10 at 01:35
  • Then you don't need a tree at all. Just use a doubly-linked list with move-to-front and you can do LRU exactly. – Keith Randall May 04 '10 at 03:03
  • Then use my ConcurrentLinkedHashMap (google code) for a true LRU that has the performance of ConcurrentHashMap. Feel free to email me if you want to discuss it / your approach in detail. – Ben Manes May 04 '10 at 06:04
  • Good point. However, concurrent move-to-front LRU approximations abound. Try this: http://www.codeproject.com/KB/recipes/LRUCache.aspx – Keith Randall May 04 '10 at 06:22
0

According to the benchmark numbers presented here Study of Different Cache Line Replacement Algorithms in Embedded Systems, pseudo-LRU's (PLRUm,PLRUt, MPLRU) appear as the best candidates for implementation.

Sidharth N. Kashyap
  • 299
  • 2
  • 6