Expiring cached data?

[Tom Pledger]

ajb at spamcop.net writes:
 | 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.

Hi.

It sounds like the term "splay tree" means different things to
different people.  I was thinking in particular of one which, whenever
it finds a key it was looking for, does some rotation so that the
key's node's depth is reduced.

e.g. finding g in this initial tree    causes this rotation

                  d                              d
                 / \                            / \
               T1   h                         T1   h
                   / \                            / \
  weak            f   T2                         g   T2
  pointer ------ / \ -------------------------- / \ -------
  threshold    T3   g                          f   T5
                   / \                        / \
                 T4   T5                    T3   T4

This is admittedly a side effect on the cache lookup, but we'd be in
the IO monad anyway if we're using weak pointers.

- Tom