[Ecls-list] Hopefully some innovation..

[Brian Spilsbury]

On Jan 12, 2008 6:46 PM, Juan Jose Garcia-Ripoll
<jjgarcia at users.sourceforge.net> wrote:
> On Jan 8, 2008 6:40 AM, Brian Spilsbury <brian.spilsbury at gmail.com> wrote:
> > Here we view the hash-table as a kind of list, which we can sweep around
> > with the clock hand. So the hand starts at the first entry, then moves to the
> > second -- the hand doesn't care about the keys.
>
> The problem I find is that the hash is actually not ordered while the
> motion of the clock has a precise sense and most of the time you end
> up deleting quite recent entries when there are older ones that should
> have been expired.

Since you insert items pre-marked, this problem doesn't occur -- the hand
needs to touch the object twice without a hit.

This means that for an object to be a candidate for deletion it must
have survived
one pass, and given that this is a one bit approximation to LRU, that's as old
as you can measurably get.