[issue27350] Compact and ordered dict

Changes by Jesús Cea Avión : -- nosy: +jcea ___ Python tracker ___ ___ Python-bugs-list mailing

[issue27350] Compact and ordered dict

STINNER Victor added the comment: Serhiy: "Could you compare the performance between the version just before adding new dict implementation and the version just after this?" I'm running benchmarks, I will keep you in touch :-) Since the main issue (implement compact dict) is solved, I close

[issue27350] Compact and ordered dict

Roundup Robot added the comment: New changeset 0773e5cb8608 by Victor Stinner in branch 'default': Issue #27350: Document compact dict memory usage https://hg.python.org/cpython/rev/0773e5cb8608 -- ___ Python tracker

[issue27350] Compact and ordered dict

Changes by Joshua Bronson : -- nosy: +jab ___ Python tracker ___ ___ Python-bugs-list

[issue27350] Compact and ordered dict

INADA Naoki added the comment: 3% slowdown in microbench is not surprising. Compact dict introduces one additional indirection. Instead, I've added freelist for most compact PyDictKeys. So I think overall performance is almost same to before compact dict. --

[issue27350] Compact and ordered dict

Serhiy Storchaka added the comment: There are a lot of other changes in interpreter core between 3.5 and 3.5 (such as new bytecode and optimized function calls). Could you compare the performance between the version just before adding new dict implementation and the version just after this?

[issue27350] Compact and ordered dict

STINNER Victor added the comment: As I expected, a dictionary lookup is a _little bit_ slower (3%) between Python 3.5 and Python 3.6: $ ./python -m perf timeit -s 'd={str(i):i for i in range(100)}' 'd["10"]; d["20"]; d["30"]; d["40"]; d["50"]; d["10"]; d["20"]; d["30"]; d["40"]; d["50"]'

[issue27350] Compact and ordered dict

STINNER Victor added the comment: It seems like the memory usage is between 20% and 25% smaller. Great job! Memory usage, Python 3.5 => Python 3.6 on Linux x86_64: ./python -c 'import sys; print(sys.getsizeof({str(i):i for i in range(10)}))' * 10 items: 480 B => 384 B (-20%) * 100 items: 6240

[issue27350] Compact and ordered dict

STINNER Victor added the comment: > What affect will this have with hash randomization? Hash randomization is still used and useful to avoid the hash DoS. -- ___ Python tracker

[issue27350] Compact and ordered dict

Ethan Furman added the comment: What affect will this have with hash randomization? -- nosy: +ethan.furman ___ Python tracker ___

[issue27350] Compact and ordered dict

STINNER Victor added the comment: > benjamin.peterson set status: open -> closed Please keep it open for the remaining issue: "TODO: The compact dict is not documented in What's New in Python 3.6. It would be nice to run some benchmarks and compare the memory usage to give some

[issue27350] Compact and ordered dict

Changes by Benjamin Peterson : -- resolution: -> fixed status: open -> closed ___ Python tracker ___

[issue27350] Compact and ordered dict

Changes by Stefan Drees : -- nosy: +dilettant ___ Python tracker ___ ___ Python-bugs-list

[issue27350] Compact and ordered dict

STINNER Victor added the comment: For an unknown reason, the code fails on a few buildbots, but not all of them. * PPC64 Fedora 3.x: GNU/Linux ppc64 POWER7 Fedora 20 GCC Compile Farm host gcc110.fsffrance.org * PPC64LE Fedora 3.x: GNU/Linux ppc64le POWER8 Fedora 21 GCC Compile Farm host

[issue27350] Compact and ordered dict

Serhiy Storchaka added the comment: Isn't this premature to commit changes to critical part of Python core without having reliable benchmark results? -- ___ Python tracker

[issue27350] Compact and ordered dict

Roundup Robot added the comment: New changeset 48a1f97d03b4 by Victor Stinner in branch 'default': dk_get_index/dk_set_index uses a type indices variable https://hg.python.org/cpython/rev/48a1f97d03b4 New changeset fc8aaa073eb4 by Victor Stinner in branch 'default': Reindeint DK_xxx macros

[issue27350] Compact and ordered dict

Roundup Robot added the comment: New changeset 9434f511937d by Raymond Hettinger in branch 'default': Issue #27350: Add credits https://hg.python.org/cpython/rev/9434f511937d -- ___ Python tracker

[issue27350] Compact and ordered dict

Roundup Robot added the comment: New changeset 19902d840448 by Victor Stinner in branch 'default': Split lookdict_unicode_nodummy() assertion to debug https://hg.python.org/cpython/rev/19902d840448 -- ___ Python tracker

[issue27350] Compact and ordered dict

STINNER Victor added the comment: Serhiy Storchaka added the comment: > Did you test the patch with your superstable benchmarking tools Victor? Not yet, as I wrote, we should benchmark the code (CPU and memory) to document the code: See my long comment for more details ;-) --

[issue27350] Compact and ordered dict

Roundup Robot added the comment: New changeset 36545fa93d2b by Victor Stinner in branch 'default': Add assertions to dk_set_index() https://hg.python.org/cpython/rev/36545fa93d2b -- ___ Python tracker

[issue27350] Compact and ordered dict

Serhiy Storchaka added the comment: Did you test the patch with your superstable benchmarking tools Victor? -- ___ Python tracker ___

[issue27350] Compact and ordered dict

STINNER Victor added the comment: Hi INADA Naoki, we discuss a lot about your compact dict change at the current Python core dev sprint. We *all* want your change in Python 3.6! I looked at the code and I found some minor issues, but sadly I'm very busy right now with s many other topics.

[issue27350] Compact and ordered dict

Roundup Robot added the comment: New changeset 0bd618fe0639 by Victor Stinner in branch 'default': Implement compact dict https://hg.python.org/cpython/rev/0bd618fe0639 New changeset 66a539984c9c by Victor Stinner in branch 'default': Add Py_MEMBER_SIZE macro

[issue27350] Compact and ordered dict

INADA Naoki added the comment: Update the patch to use standard int types instead of adding PY_INT16_T ref: https://bugs.python.org/issue17884 -- Added file: http://bugs.python.org/file44418/compact-dict.patch ___ Python tracker

[issue27350] Compact and ordered dict

Changes by INADA Naoki : Added file: http://bugs.python.org/file44395/compact-dict.patch ___ Python tracker ___

[issue27350] Compact and ordered dict

Changes by INADA Naoki : Added file: https://bugs.python.org/file44267/compact-dict.patch ___ Python tracker ___

[issue27350] Compact and ordered dict

Changes by INADA Naoki : Added file: https://bugs.python.org/file44259/compact-dict.patch ___ Python tracker ___

[issue27350] Compact and ordered dict

Changes by Mark Dickinson : -- nosy: -mark.dickinson ___ Python tracker ___ ___

[issue27350] Compact and ordered dict

Changes by INADA Naoki : Added file: http://bugs.python.org/file44194/compact-dict.patch ___ Python tracker ___

[issue27350] Compact and ordered dict

Changes by INADA Naoki : Added file: http://bugs.python.org/file44110/compact-dict.patch ___ Python tracker ___

[issue27350] Compact and ordered dict

Changes by INADA Naoki : Added file: http://bugs.python.org/file44086/compact-dict.patch ___ Python tracker ___

[issue27350] Compact and ordered dict

INADA Naoki added the comment: I see, and I'm sorry about that. -- ___ Python tracker ___ ___

[issue27350] Compact and ordered dict

Raymond Hettinger added the comment: You make need to ask for review help on python-dev. Patches this big take a lot of time and energy to review. Making pings into the blind doesn't help much (most of the patch reviewers are highly time constrained). --

[issue27350] Compact and ordered dict

INADA Naoki added the comment: ping -- ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue27350] Compact and ordered dict

INADA Naoki added the comment: Anyone can review this by Python 3.6a3 ? -- ___ Python tracker ___ ___

[issue27350] Compact and ordered dict

INADA Naoki added the comment: And Python benchmark result is here. https://gist.github.com/methane/e7a2ae389ca13905508905f5fa4ad46c pickup --- ### call_method_slots ### Min: 0.282221 -> 0.266215: 1.06x faster Avg: 0.282379 -> 0.266448: 1.06x faster Significant (t=780.35) Stddev: 0.00015

[issue27350] Compact and ordered dict

INADA Naoki added the comment: Last patch I've posted implements "strict ordering rule" on key sharing dict. * Insertion order should be strictly equal to order in shared key. If insertion position is not equal to ma_used, convert it to combined form. * Deleting from split table is

[issue27350] Compact and ordered dict

Changes by INADA Naoki : Added file: http://bugs.python.org/file43558/compact-dict.patch ___ Python tracker ___

[issue27350] Compact and ordered dict

Changes by INADA Naoki : Added file: http://bugs.python.org/file43542/compact-dict.patch ___ Python tracker ___

[issue27350] Compact and ordered dict

Changes by INADA Naoki : Added file: http://bugs.python.org/file43520/compact-dict.patch ___ Python tracker ___

[issue27350] Compact and ordered dict

INADA Naoki added the comment: FYI, bench result of USABLE_FRACTION(n) = (n/2): Report on Linux ip-10-0-1-249 3.16.0-4-amd64 #1 SMP Debian 3.16.7-ckt25-1 (2016-03-06) x86_64 Total CPU cores: 2 +--+-++--++ | Benchmark|

[issue27350] Compact and ordered dict

Changes by INADA Naoki : Added file: http://bugs.python.org/file43509/compact-dict.patch ___ Python tracker ___

[issue27350] Compact and ordered dict

INADA Naoki added the comment: Thank you, mark. I've added PY_INT16_T and PY_UINT16_T for windows, too. https://github.com/methane/cpython/pull/1/commits/dfaa44c051b2dbf580701729944cd0fda00cb541 https://github.com/methane/cpython/pull/1/commits/af80dc27dd381af9d211792963a23c5cecfa7009 I'll

[issue27350] Compact and ordered dict

Mark Dickinson added the comment: > That doesn't sound right. It should be available always. To elaborate: assuming not Windows, the configure script has two checks: if AC_CHECK_TYPE(int32_t, ...) succeeds (which should happen whenever int32_t is defined in either stdint.h or inttypes.h), it

[issue27350] Compact and ordered dict

Mark Dickinson added the comment: > I found PY_INT32_T in pyport.h. It seems only available when stdint.h is > available. That doesn't sound right. It should be available always. -- nosy: +mark.dickinson ___ Python tracker

[issue27350] Compact and ordered dict

INADA Naoki added the comment: As I posted to python-dev ML, this compact ordered dict doesn't keep insertion order for key-shared dict. >>> class A: ... ... ... >>> a = A() >>> b = A() >>> a.a = 1 >>> a.b = 2 >>> b.b = 3 >>> b.a = 4 >>> a.__dict__.items() dict_items([('a', 1), ('b', 2)])

[issue27350] Compact and ordered dict

Changes by INADA Naoki : Added file: http://bugs.python.org/file43484/compact-dict.patch ___ Python tracker ___

[issue27350] Compact and ordered dict

Changes by INADA Naoki : Added file: http://bugs.python.org/file43480/compact-dict.patch ___ Python tracker ___

[issue27350] Compact and ordered dict

Changes by INADA Naoki : Added file: http://bugs.python.org/file43472/compact-dict.patch ___ Python tracker ___

[issue27350] Compact and ordered dict

INADA Naoki added the comment: Make sense! I did it. -- Added file: http://bugs.python.org/file43467/compact-dict.patch ___ Python tracker ___

[issue27350] Compact and ordered dict

Serhiy Storchaka added the comment: When stdint.h is not available you can define PY_INT32_T externally. E.g. CFLAGS="-DPY_INT32_T=__int32". -- ___ Python tracker

[issue27350] Compact and ordered dict

Changes by INADA Naoki : Added file: http://bugs.python.org/file43465/compact-dict.patch ___ Python tracker ___

[issue27350] Compact and ordered dict

INADA Naoki added the comment: >> How to support sizeof(Py_ssize_t) == 4? >#if SIZEOF_VOID_P == 4 Thanks! >> Can I use int8_t, int16_t and int32_t > You can use PY_INT32_T for 32-bit signed integers, short for 16-bit signed > integers (if SIZEOF_SHORT == 2) and signed char for 8-bit signed

[issue27350] Compact and ordered dict

Serhiy Storchaka added the comment: > How to support sizeof(Py_ssize_t) == 4? #if SIZEOF_VOID_P == 4 > Can I use int8_t, int16_t and int32_t You can use PY_INT32_T for 32-bit signed integers, short for 16-bit signed integers (if SIZEOF_SHORT == 2) and signed char for 8-bit signed integers.

[issue27350] Compact and ordered dict

Changes by INADA Naoki : -- type: -> resource usage ___ Python tracker ___ ___

[issue27350] Compact and ordered dict

New submission from INADA Naoki: I've implemented compact ordered dictionary, introduced in PyPy blog [1]. To finish my work, I really need core developer's help. Please see TODO comment in the patch. [1]: https://morepypy.blogspot.jp/2015/01/faster-more-memory-efficient-and-more.html See