[Python-ideas] Fast global cacheless lookup

[Guido van Rossum]

On Nov 24, 2007 6:18 PM, Neil Toronto <ntoronto at cs.byu.edu> wrote:
> Jim Jewett wrote:
> > I think this isn't quite true, because of DUMMY entries.
> >
> > Insert key1.
> > Insert key2 that wants the same slot.
> > Register an observer that cares about key2 but not key1.
> >
> > Delete key1.   The key1 entry is replaced with DUMMY, but the entry
> > for key2 is not affected.
> >
> > Look up key2 (by some other code which hasn't already taken this
> > shortcut) and the lookdict function (as a side effect) moves key2 to
> > the better location that key1 no longer occupies.  As described, I
> > think this breaks your cache.
>
> Good grief old chap, you freaked me out.
>
> Turns out it all still works. Whether the lookdict functions used to
> move entries around I don't know, but now it doesn't. It's probably
> because deletions are so rare compared to other operations that it's not
> worth the extra logic in those tight little loops.

I don't know where Jim gets his information, but I don't recall that
just looking up a key has ever moved entries around. You'd have to
delete and re-add it to get it moved. (Or you'd have to hit the
"rehash everything to a larger hash table" of course.)

-- 
--Guido van Rossum (home page: http://www.python.org/~guido/)