[Python-Dev] One more dict trick

[M.-A. Lemburg]

Tim Peters wrote:
> 
> If anyone has an app known or suspected to be sensitive to dict timing,
> please try the patch here.  Best I've been able to tell, it's a win.  But
> it's a radical change in approach, so I don't want to rush it.
> 
> This gets rid of the polynomial machinery entirely, along with the branches
> associated with updating the things, and the dictobject struct member
> holding the table's poly.  Instead it relies on that
> 
>     i = (5*i + 1) % n
> 
> is a full-period RNG whenever n is a power of 2 (that's what guarantees it
> will visit every slot), but perturbs that by adding in a few bits from the
> full hash code shifted right each time (that's what guarantees every bit of
> the hash code eventually influences the probe sequence, avoiding simple
> quadratic-time degenerate cases).

Cool idea... rips out all that algebra garble and replaces it with 
random beauty :-)

In any case, this will avoid use the trouble of having to check
those poly numbers every time Intel decides to bump the register
width by another factor of two ;-)

-- 
Marc-Andre Lemburg
CEO eGenix.com Software GmbH
______________________________________________________________________
Company & Consulting:                           http://www.egenix.com/
Python Software:                        http://www.lemburg.com/python/