[issue29304] dict: simplify lookup function

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

[issue29304] dict: simplify lookup function

Serhiy Storchaka added the comment: Dmitry, please open a new issue for your proposition. It changes visible behavior, while Inada's patch doesn't do this. -- ___ Python tracker

[issue29304] dict: simplify lookup function

Dmitry Rubanovich added the comment: 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 =

[issue29304] dict: simplify lookup function

INADA Naoki added the comment: dict-refactoring-3.patch: $ ../python.default -m perf compare_to default.json patched2.json -G --min-speed=2 Slower (7): - scimark_lu: 422 ms +- 35 ms -> 442 ms +- 11 ms: 1.05x slower (+5%) - logging_silent: 736 ns +- 7 ns -> 761 ns +- 21 ns: 1.03x slower (+3%) -

[issue29304] dict: simplify lookup function

INADA Naoki added the comment: > I think the patch should not be pushed without such analysis. Perhaps > Raymond will found a time to do this. Ok, I won't push until expert's LGTM. > One possible optimization is removing freeslot completely. because: > > * freeslot is used only when

[issue29304] dict: simplify lookup function

Serhiy Storchaka added the comment: I agreed that the duplication was made for reasons, but these reasons can be not valid or less weighty now, after a number of changes made last years like shared keys or compact dicts. An overhead of additional levels of indirection and complex code of

[issue29304] dict: simplify lookup function

INADA Naoki added the comment: BTW, perturb shift uses (i << 2) + i, instead of i*5. I feel it doesn't make sense in 21th century. I'll change it too. -- ___ Python tracker

[issue29304] dict: simplify lookup function

INADA Naoki added the comment: Digging history, duplicated code is introduced here. (1997-01-17) https://github.com/python/cpython/commit/99304174680d4c724476dad300ae7fc638842bf0#diff-2131209d0deb0e50c93a88ec6c7b0d52 /* Optimizations based on observations by Jyrki Alakuijala

[issue29304] dict: simplify lookup function

INADA Naoki added the comment: I've attached wrong file. This patch is first version I wanted to post. It dedupe all five functions. -- Added file: http://bugs.python.org/file46325/dict-refactor.patch ___ Python tracker

[issue29304] dict: simplify lookup function

Changes by INADA Naoki : Removed file: http://bugs.python.org/file46324/dictlook-refactoring.patch ___ Python tracker ___

[issue29304] dict: simplify lookup function

INADA Naoki added the comment: Raymond, I understand your worries. I won't commit this until I do more precise survey. But why I trying this is not only I find duplicated code. I think benefit of this technique is reduced by historical reason. In Python 2.7, there are only two lookup

[issue29304] dict: simplify lookup function

Raymond Hettinger added the comment: I worry you guys are rapidly sloshing around and churning code that was developed slowly and methodically over many years. A lot of people have looked at an tweaked the dictionary code, but now it seems like there is a rewrite-everything festival. When

[issue29304] dict: simplify lookup function

Xiang Zhang added the comment: Ahh, I got the same idea before. But then I persuaded myself that the first "lookup()" was deliberately extracted from the loop since it's highly possible there is no collision and you can hit the result (empty or not) the first time. -- nosy:

[issue29304] dict: simplify lookup function

New submission from INADA Naoki: All lookdict* functions are implemented like pseudo language: ``` lookup() if not collision: return result while True: perturb_shift() lookup() if not collision: return result ``` This patch changes it as: ``` while True: lookup()