Expiring cached data?

[ajb at spamcop.net]

G'day all.

Tom Pledger wrote:

> How about adapting splay trees so that their pointers become weak
> after a certain depth?  The advantage for caching is that the more
> frequently used elements move closer to the root, so you wouldn't have
> to add much code for tracking recent use, just a depth threshold.

Nice idea, but I think it wouldn't be generally useful.  Splay trees
optimise themselves for static frequency distributions.  Caches, on
the other hand, are generally used more for changing working sets (i.e.
dynamic frequency distributions).  It seems to me that splay trees are
therefore not necessarily a good fit.

Cheers,
Andrew Bromage