[issue29304] dict: simplify lookup functions

INADA Naoki added the comment: On i386 docker image, pyperformance: ./python -m perf compare_to before.json after.json -G --min-speed=2 Slower (4): - regex_dna: 279 ms +- 1 ms -> 288 ms +- 3 ms: 1.03x slower (+3%) - deltablue: 17.9 ms +- 0.3 ms -> 18.3 ms +- 1.0 ms: 1.03x slower (+3%) -

[issue29304] dict: simplify lookup functions

Raymond Hettinger added the comment: It would have been nice to have timed this on ARM chips or 32-bit builds. I suspect that the previous code was mainly beneficial in register starved environments when it would have saved some memory accesses whenever there were an immediate first hit on a

[issue29304] dict: simplify lookup functions

Antoine Pitrou added the comment: Thank you Inada! -- ___ Python tracker ___ ___ Python-bugs-list mailing

[issue29304] dict: simplify lookup functions

Changes by INADA Naoki : -- resolution: -> fixed stage: -> resolved status: open -> closed ___ Python tracker ___

[issue29304] dict: simplify lookup functions

INADA Naoki added the comment: New changeset 778928b0c7aa438c282727535814d73df850693a by INADA Naoki in branch 'master': bpo-29304: Simplify dict lookup functions (GH-2407) https://github.com/python/cpython/commit/778928b0c7aa438c282727535814d73df850693a --

[issue29304] dict: simplify lookup functions

INADA Naoki added the comment: # microbench https://gist.github.com/methane/db16224a99d12ad4ed170cf3bd45b819 Slower (2): - fromkeys_str: 3.85 us +- 0.07 us -> 4.09 us +- 0.09 us: 1.06x slower (+6%) - fromkeys_int: 4.24 us +- 0.13 us -> 4.48 us +- 0.16 us: 1.06x slower (+6%) Faster (2): -

[issue29304] dict: simplify lookup functions

INADA Naoki added the comment: Finally, I removed `freeslot` and all lookdict*() functions are much simpler in GH-2407. Macro bench doesn't show any significant performance change. I'll try to write micro benchmarks. -- ___ Python tracker

[issue29304] dict: simplify lookup functions

Changes by INADA Naoki : -- pull_requests: +2455 ___ Python tracker ___ ___

[issue29304] dict: simplify lookup functions

INADA Naoki added the comment: Tim Peters: Thanks for your suggestion. But I want to focus on very simple code cleanup without any change to proving algorithm nor memory access pattern in this issue. I'll reply about my thought about reducing collision on the ML. --

[issue29304] dict: simplify lookup functions

INADA Naoki added the comment: Antonie: Thank you for you comment. Actually speaking, size of instructions are reduced on amd64@gcc. lookdict_unicode_nodummy and lookdict_split doesn't have any reason to have duplicated code anymore. I'll do dedupe for them first. lookdict and

[issue29304] dict: simplify lookup functions

Tim Peters added the comment: Oops! I undercounted the shifts in the current scheme: there's an additional shift for "perturb". That doesn't exist in the "double hashing" alternatives. -- ___ Python tracker

[issue29304] dict: simplify lookup functions

Tim Peters added the comment: I suggest reading the thread I started here[1] before pursuing this: it looks very likely that the entire collision resolution scheme should be replaced with one of the "double hashing" ones given there, a bona fide algorithmic improvement for small tables and

[issue29304] dict: simplify lookup functions

Changes by Xavier G. Domingo : -- nosy: +xgdomingo ___ Python tracker ___ ___

[issue29304] dict: simplify lookup functions

Changes by INADA Naoki : -- pull_requests: +2402 ___ Python tracker ___ ___

[issue29304] dict: simplify lookup functions

Antoine Pitrou added the comment: >From a purely human and social perspective, I agree that it's beneficial to >minimize duplicated code. >From a performance perspective, I can see two possible consequences: - either compilers are already smart enough to undo the code duplication, and

[issue29304] dict: simplify lookup functions

INADA Naoki added the comment: New changeset 073ae487b3ff9001c69d530c7555ddaa530dee16 by INADA Naoki in branch 'master': bpo-29304: simplify lookdict_index() function. (GH-2273) https://github.com/python/cpython/commit/073ae487b3ff9001c69d530c7555ddaa530dee16 --

[issue29304] dict: simplify lookup functions

INADA Naoki added the comment: pr-2237 only changes lookdict_index() function. The function is used from only dict_popitem(). So it's not performance critical part. And microbench doesn't show significant performance changes: $ ./python.default -m perf timeit -q -l 2000 -s