New submission from Dmitry Rubanovich:
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.
----------
components: Interpreter Core
messages: 296072
nosy: Dmitry Rubanovich, inada.naoki, rhettinger, serhiy.storchaka, xiang.zhang
priority: normal
severity: normal
status: open
title: dict: simplify and improve lookup function
type: enhancement
versions: Python 3.7
Added file: http://bugs.python.org/file46953/collisions_count.py
_______________________________________
Python tracker <rep...@bugs.python.org>
<http://bugs.python.org/issue30671>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
