diff options
| author | Tim Peters <tim.peters@gmail.com> | 2001-05-27 07:39:22 (GMT) |
|---|---|---|
| committer | Tim Peters <tim.peters@gmail.com> | 2001-05-27 07:39:22 (GMT) |
| commit | 15d4929ae4ad5206e2f7fa947d632bfba9b8bfd1 (patch) | |
| tree | 97abc7e1d28bcb8da6d31d3578759c70b0e2bf41 /Misc | |
| parent | dac238bd46e95d1736cd6bee11df850a508f433b (diff) | |
| download | cpython-15d4929ae4ad5206e2f7fa947d632bfba9b8bfd1.zip cpython-15d4929ae4ad5206e2f7fa947d632bfba9b8bfd1.tar.gz cpython-15d4929ae4ad5206e2f7fa947d632bfba9b8bfd1.tar.bz2 | |
Implement an old idea of Christian Tismer's: use polynomial division
instead of multiplication to generate the probe sequence. The idea is
recorded in Python-Dev for Dec 2000, but that version is prone to rare
infinite loops.
The value is in getting *all* the bits of the hash code to participate;
and, e.g., this speeds up querying every key in a dict with keys
[i << 16 for i in range(20000)] by a factor of 500. Should be equally
valuable in any bad case where the high-order hash bits were getting
ignored.
Also wrote up some of the motivations behind Python's ever-more-subtle
hash table strategy.
Diffstat (limited to 'Misc')
| -rw-r--r-- | Misc/NEWS | 8 |
1 files changed, 8 insertions, 0 deletions
@@ -116,6 +116,14 @@ Core to crash if the element comparison routines for the dict keys and/or values mutated the dicts. Making the code bulletproof slowed it down. +- Collisions in dicts now use polynomial division instead of multiplication + to generate the probe sequence, following an idea of Christian Tismer's. + This allows all bits of the hash code to come into play. It should have + little or no effect on speed in ordinary cases, but can help dramatically + in bad cases. For example, looking up every key in a dict d with + d.keys() = [i << 16 for i in range(20000)] is approximately 500x faster + now. + Library - calendar.py uses month and day names based on the current locale. |