Message296070
lookdict_index() (and the rest of the files in dictobject.c) are using unnecessarily complicated perturb mechanism. And, in fact, it's slower than the simpler case.
Instead of this:
for (size_t perturb = hash;;) {
perturb >>= PERTURB_SHIFT;
i = mask & ((i << 2) + i + perturb + 1);
....
it should do this:
for (size_t perturb = hash;;) {
i = mask & ((i << 1) + perturb + 1);
perturb >>= PERTURB_SHIFT;
....
This would not only save an instruction (a minor issue), but it would also reduce collisions.
I've attached a file which calculates frequencies of collisions for demonstration purposes. It shows that the calculation, as it stands right now, does not create a 1-1 mapping even on the 1st iteration through the loop. Moving PERTURB_SHIFT to the line before the calculation does reduce the density of the collision space. But using the calculation, which I proposed, eliminates collisions on the 1st iteration completely and reduces it on most subsequent iterations. |
|
Date |
User |
Action |
Args |
2017-06-15 06:57:07 | Dmitry Rubanovich | set | recipients:
+ Dmitry Rubanovich, rhettinger, methane, serhiy.storchaka, xiang.zhang |
2017-06-15 06:57:07 | Dmitry Rubanovich | set | messageid: <1497509827.72.0.705182775146.issue29304@psf.upfronthosting.co.za> |
2017-06-15 06:57:07 | Dmitry Rubanovich | link | issue29304 messages |
2017-06-15 06:57:07 | Dmitry Rubanovich | create | |
|