[Python-Dev] One more dict trick (original) (raw)

M.-A. Lemburg mal@lemburg.com
Thu, 31 May 2001 09:33:36 +0200

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/