Pseudo LRU tree algorithm.

views:

337

answers:

+1 Q:

Pseudo LRU tree algorithm.

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.

+1 A:

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 2010-05-03 19:42:52

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 2010-05-03 20:20:24

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 2010-05-03 22:15:09

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 2010-05-04 01:35:34

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 2010-05-04 03:03:09

Yes, but that is not safe for concurrent reads.

patros 2010-05-04 05:27:45

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 2010-05-04 06:04:52

Good point. However, concurrent move-to-front LRU approximations abound. Try this: http://www.codeproject.com/KB/recipes/LRUCache.aspx

Keith Randall 2010-05-04 06:22:26

ansaurus

tags:

views:

answers:

Pseudo LRU tree algorithm.

related questions