Message195520
Serhiy, I've posted a patch so you can examine the effects in detail.
For something like set(range(n)), I would expect no change because the dataset is collision free due to Tim's design where hash(someint)==someint. That said, I'm trying to optimize the general case and don't really if rare cases are modestly slowed.
The new code only kicks in when there is a collision. The logic for the initial probe is unchanged. The idea is to pickup some of the cache locality benefits of collision resolution by separate chaining, but not incurring the 100% malloc typically associated with chaining.
When adjacent entries are in the same cache-line, the cost of the extra adjacent probe is much cheaper (nearly zero) than a probe somewhere else in memory. |
|
Date |
User |
Action |
Args |
2013-08-17 21:11:13 | rhettinger | set | recipients:
+ rhettinger, vstinner, christian.heimes, serhiy.storchaka |
2013-08-17 21:11:13 | rhettinger | set | messageid: <1376773873.26.0.896329041842.issue18771@psf.upfronthosting.co.za> |
2013-08-17 21:11:13 | rhettinger | link | issue18771 messages |
2013-08-17 21:11:12 | rhettinger | create | |
|