Idea: more compact, interned string key only dict for namespace.
As my last email, compact ordered dict can't preserve insertion order of key sharing dict (PEP 412). I'm thinking about deprecating key shared dict for now. Instead, my new idea is introducing more compact dict specialized for namespace. If BDFL (or BDFL delegate) likes this idea, I'll take another one week to implement this. Background ---------------- * Most keys of namespace dict are string. * Calculating hash of string is cheap (one memory access, thanks for cache). * And most keys are interned already. Design ---------- Instead of normal PyDictKeyEntry, use PyInternedKeyEntry like this. typedef struct { // no me_hash PyObject *me_key, *me_value; } PyInternedKeyEntry; insertdict() interns key if it's unicode, otherwise it converts dict to normal compact ordered dict. lookdict_interned() compares only pointer (doesn't call unicode_eq()) when searching key is interned. And add new internal API to create interned key only dict. PyDictObject* _PyDict_NewForNamespace(); Memory usage -------------------- on amd64 arch. key-sharing dict: * 96 bytes for ~3 items * 128 bytes for 4~5 items. compact dict: * 224 bytes for ~5 items. (232 bytes when keep supporting key-shared dict) interned key only dict: * 184 bytes for ~5 items Note ------ Interned key only dict is still larger than key-shared dict. But it can be used for more purpose. It can be used for interning string for example. It can be used to kwargs dict when all keys are interned already. If we provide _PyDict_NewForNamespace to extension modules, json decoder can have option to use this, too. -- INADA Naoki <songofacandy@gmail.com>
Hi all, I think we need some more data before going any further reimplementing dicts. What I would like to know is, across a set of Python programs (ideally a representative set), what the proportion of dicts in memory at any one time are: a) instance dicts b) other namespace dicts (classes and modules) c) data dicts with all string keys d) other data dicts e) keyword argument dicts (I'm guessing this is vanishingly small) I would expect that (a) far exceeds (b) and depending on the application also considerably exceeds (c), but I would like some real data. From that we can compute the (approximate) memory costs of the competing designs. As an aside, if anyone is really keen to save memory, then removing the cycle GC header is the thing to do. That uses 24 bytes per object and *half* of all live objects have it. And don't forget that any Python object is really two objects, the object and its dict, so that is 48 extra bytes every time you create a new object. Cheers, Mark. On 22/06/16 10:23, INADA Naoki wrote:
As my last email, compact ordered dict can't preserve insertion order of key sharing dict (PEP 412).
I'm thinking about deprecating key shared dict for now.
Instead, my new idea is introducing more compact dict specialized for namespace.
If BDFL (or BDFL delegate) likes this idea, I'll take another one week to implement this.
Background ----------------
* Most keys of namespace dict are string. * Calculating hash of string is cheap (one memory access, thanks for cache). * And most keys are interned already.
Design ----------
Instead of normal PyDictKeyEntry, use PyInternedKeyEntry like this.
typedef struct { // no me_hash PyObject *me_key, *me_value; } PyInternedKeyEntry;
insertdict() interns key if it's unicode, otherwise it converts dict to normal compact ordered dict.
lookdict_interned() compares only pointer (doesn't call unicode_eq()) when searching key is interned.
And add new internal API to create interned key only dict.
PyDictObject* _PyDict_NewForNamespace();
Memory usage --------------------
on amd64 arch.
key-sharing dict:
* 96 bytes for ~3 items * 128 bytes for 4~5 items.
compact dict:
* 224 bytes for ~5 items.
(232 bytes when keep supporting key-shared dict)
interned key only dict:
* 184 bytes for ~5 items
Note ------
Interned key only dict is still larger than key-shared dict.
But it can be used for more purpose. It can be used for interning string for example. It can be used to kwargs dict when all keys are interned already.
If we provide _PyDict_NewForNamespace to extension modules, json decoder can have option to use this, too.
Hi, Mark. Thank you for reply. On Thu, Jun 23, 2016 at 10:30 AM, Mark Shannon <mark@hotpy.org> wrote:
Hi all,
I think we need some more data before going any further reimplementing dicts.
What I would like to know is, across a set of Python programs (ideally a representative set), what the proportion of dicts in memory at any one time are:
a) instance dicts b) other namespace dicts (classes and modules) c) data dicts with all string keys d) other data dicts e) keyword argument dicts (I'm guessing this is vanishingly small)
I would expect that (a) far exceeds (b) and depending on the application also considerably exceeds (c), but I would like some real data. From that we can compute the (approximate) memory costs of the competing designs.
I think you're right. But, I don't have clear idea about how to do it. Is there existing effort about collecting stats of dict?
As an aside, if anyone is really keen to save memory, then removing the cycle GC header is the thing to do. That uses 24 bytes per object and *half* of all live objects have it. And don't forget that any Python object is really two objects, the object and its dict, so that is 48 extra bytes every time you create a new object.
It's great idea. But I can't do it before Python 3.6. My main concern is not saving memory, ordered dict for **kwargs without significant overhead. If "orderd, except key sharing dict" is acceptable, no problem. Key sharing compact dict is smaller than current key sharing dict of Python 3.5 for most cases. https://docs.google.com/spreadsheets/d/1nN5y6IsiJGdNxD7L7KBXmhdUyXjuRAQR_Wbr... Regards, -- INADA Naoki <songofacandy@gmail.com>
I've checked time and maxrss of sphinx-build. In case of sphinx, ## master $ rm -rf build/ $ /usr/bin/time ~/local/python-master/bin/sphinx-build -b html -d build/doctrees -D latex_paper_size= . build/html -QN 71.76user 0.27system 1:12.06elapsed 99%CPU (0avgtext+0avgdata 176248maxresident)k 80inputs+202888outputs (2major+58234minor)pagefaults 0swaps 71.86user 0.28system 1:12.16elapsed 99%CPU (0avgtext+0avgdata 176312maxresident)k 0inputs+201480outputs (0major+59897minor)pagefaults 0swaps ## compact-dict w/ shared $ rm -rf build/ $ /usr/bin/time ~/local/python-compact/bin/sphinx-build -b html -d build/doctrees -D latex_paper_size= . build/html -QN 72.18user 0.27system 1:12.47elapsed 99%CPU (0avgtext+0avgdata 158104maxresident)k 728inputs+200792outputs (0major+53409minor)pagefaults 0swaps 72.79user 0.30system 1:13.11elapsed 99%CPU (0avgtext+0avgdata 157916maxresident)k 0inputs+200792outputs (0major+54072minor)pagefaults 0swaps ## compact w/o shared key (Only shared key removed. No interned key only dict) $ rm -rf build/ $ /usr/bin/time ~/local/python-intern/bin/sphinx-build -b html -d build/doctrees -D latex_paper_size= . build/html -QN 71.79user 0.34system 1:12.16elapsed 99%CPU (0avgtext+0avgdata 165884maxresident)k 480inputs+200792outputs (0major+56947minor)pagefaults 0swaps 71.84user 0.27system 1:12.13elapsed 99%CPU (0avgtext+0avgdata 166888maxresident)k 640inputs+200792outputs (5major+56834minor)pagefaults 0swaps -- INADA Naoki <songofacandy@gmail.com>
Hi, all. I implemented my new idea. (still wip) https://github.com/methane/cpython/pull/3/files Memory usage when building Python doc with sphinx are: 1) master (shared key) 176MB 2) compact (w/ shared key) 158MB 3) compact (w/o shared key) 166MB 4) compact & interned (new) 160MB Memory usage is close to compact w/ shared key, and more efficient than current. In case of Python benchmark (master vs compact & interned): $ python perf.py -fm ~/local/python-master/bin/python3 ~/local/python-intern/bin/python3 ### 2to3 ### Mem max: 20392.000 -> 16936.000: 1.2041x smaller ### chameleon_v2 ### Mem max: 364604.000 -> 359904.000: 1.0131x smaller ### django_v3 ### Mem max: 26648.000 -> 24948.000: 1.0681x smaller ### fastpickle ### Mem max: 8296.000 -> 8996.000: 1.0844x larger ### fastunpickle ### Mem max: 8332.000 -> 7964.000: 1.0462x smaller ### json_dump_v2 ### Mem max: 10400.000 -> 9972.000: 1.0429x smaller ### json_load ### Mem max: 8088.000 -> 7644.000: 1.0581x smaller ### nbody ### Mem max: 7460.000 -> 7036.000: 1.0603x smaller ### regex_v8 ### Mem max: 12572.000 -> 12520.000: 1.0042x smaller ### tornado_http ### Mem max: 27860.000 -> 26792.000: 1.0399x smaller I'll do more hack in next week to prove my idea. (interned string only vs string only, revive embedded small table or not). If someone interested in, please try my interned-dict branch and report difference of performance and memory usage. https://github.com/methane/cpython/tree/interned-dict (cb0a125c79 passes most tests, except tests using sys.getsizeof()). -- INADA Naoki <songofacandy@gmail.com>
Memory usage --------------------
on amd64 arch.
key-sharing dict:
* 96 bytes for ~3 items * 128 bytes for 4~5 items.
Note: There are another shared key. * 128 bytes for ~3 items * 224 bytes for 4~5 items So, let S = how many instances shares the key, * 90 + (96 / S) bytes for ~3 items * 128 + (224 / S) bytes for 4~5 items
compact dict:
* 224 bytes for ~5 items.
(232 bytes when keep supporting key-shared dict)
interned key only dict:
* 184 bytes for ~5 items
Note ------
Interned key only dict is still larger than key-shared dict.
But it can be used for more purpose. It can be used for interning string for example. It can be used to kwargs dict when all keys are interned already.
If we provide _PyDict_NewForNamespace to extension modules, json decoder can have option to use this, too.
-- INADA Naoki <songofacandy@gmail.com>
-- INADA Naoki <songofacandy@gmail.com>
participants (2)
-
INADA Naoki -
Mark Shannon