Mailing List Archive: Python: Bugs

[issue13903] New shared-keys dictionary implementation

1 2

View All

Index | Next | Previous | View Threaded

report at bugs

Jan 29, 2012, 6:26 AM

Post #1 of 35 (80 views)
Permalink

[issue13903] New shared-keys dictionary implementation

New submission from Mark Shannon :

The proposed dictionary implementation allows sharing of keys & hashes between dictionaries. This leads to substantial memory savings for object-oriented programs. For non-OO programs the impact is negligible.

----------
components: Interpreter Core
hgrepos: 109
messages: 152229
nosy: Mark.Shannon
priority: normal
severity: normal
status: open
title: New shared-keys dictionary implementation
type: performance
versions: Python 3.4

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Jan 29, 2012, 6:42 AM

Post #2 of 35 (76 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Changes by Georg Brandl <georg [at] python>:

----------
keywords: +patch
Added file: http://bugs.python.org/file24357/061f8573af54.diff

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Jan 29, 2012, 9:06 AM

Post #3 of 35 (73 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Changes by Mark Shannon :

Added file: http://bugs.python.org/file24360/6a21f3b35e20.diff

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Jan 29, 2012, 9:10 AM

Post #4 of 35 (73 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Changes by Georg Brandl <georg [at] python>:

Removed file: http://bugs.python.org/file24357/061f8573af54.diff

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Jan 29, 2012, 9:55 AM

Post #5 of 35 (73 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Changes by Antoine Pitrou <pitrou [at] free>:

----------
nosy: +benjamin.peterson, pitrou
stage: -> patch review
versions: +Python 3.3 -Python 3.4

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Jan 29, 2012, 10:43 AM

Post #6 of 35 (73 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Terry J. Reedy <tjreedy [at] udel> added the comment:

In the initial comment, 'Dummy' to 'Deleted' here but only here:
- Holds an active (key, value) pair. Active can transition to Dummy
+ Holds an active (key, value) pair. Active can transition to Deleted

Im Lib/test/test_pprint.py
def test_set_reprs(self): ...
# Consequently, this test is fragile and ...
+ # XXX So why include this "test" in the first place?
Raymond, I believe you added this 44927 and revised for 3.x in 45067.
I imagine it will also be a problem with randomized hashes. Should it be removed or somehow revised?

----------
nosy: +terry.reedy

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Jan 29, 2012, 11:06 AM

Post #7 of 35 (73 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Changes by Giampaolo Rodola' <g.rodola [at] gmail>:

----------
nosy: +giampaolo.rodola

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Jan 29, 2012, 11:57 AM

Post #8 of 35 (73 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Changes by Philip Jenvey <pjenvey [at] underboss>:

----------
nosy: +pjenvey

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Jan 29, 2012, 3:04 PM

Post #9 of 35 (66 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Changes by Gregory P. Smith <greg [at] krypto>:

----------
nosy: +gregory.p.smith

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Jan 29, 2012, 4:05 PM

Post #10 of 35 (66 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

STINNER Victor <victor.stinner [at] haypocalc> added the comment:

I see two unrelated parts in your patch:
- change dictionary structure in memory
- change many constants linked to optimization: PyDICT_MAXFREELIST: 80->40, 2/3->5/8, etc.

You may open a new issue for the second part, except if I am wrong and you need to change constants for the first part?

(I don't understand why you changed constants and how you chose new values.)

----------
nosy: +haypo

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Jan 29, 2012, 4:42 PM

Post #11 of 35 (63 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Changes by John O'Connor <tehjcon [at] gmail>:

----------
nosy: +jcon

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Jan 30, 2012, 12:22 PM

Post #12 of 35 (63 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Raymond Hettinger <raymond.hettinger [at] gmail> added the comment:

This would likely require a PEP before having a chance of being considered for inclusion.

----------
nosy: +rhettinger

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Jan 30, 2012, 1:26 PM

Post #13 of 35 (63 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Mark Shannon added the comment:

Does this really need a PEP?
There is no new language feature and no change to any API.
It is just saving some memory.

The only possible issue is changing dict repr() ordering,
but issue 13703 will do that anyway.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Jan 30, 2012, 6:10 PM

Post #14 of 35 (63 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Changes by Raymond Hettinger <raymond.hettinger [at] gmail>:

----------
assignee: -> rhettinger

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Jan 30, 2012, 6:17 PM

Post #15 of 35 (63 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Raymond Hettinger <raymond.hettinger [at] gmail> added the comment:

Changing dictionaries is a big deal. You're changing many pieces at once (not a good idea) including changing tunable parameters that are well-studied (I spent a month testing whether 5/8 was better idea that 2/3 for resizing or when the ideal small dict size was 4, 8, or 16). You're changing the meaning of the fields in dictobject.h which will likely break any code that relied on those.

The ideas may be good ones but they warrant a good deal of thought. Dicts weren't just slapped together -- the current code is the product to two decades of tweaking by engineers who devoted significant time to the task. It would be easy to unknowingly undo some of their work.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Jan 31, 2012, 2:38 AM

Post #16 of 35 (55 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Mark Shannon added the comment:

Raymond Hettinger wrote:
> Raymond Hettinger <raymond.hettinger [at] gmail> added the comment:
>
> Changing dictionaries is a big deal. You're changing many pieces at once (not a good idea) including changing tunable parameters that are well-studied (I spent a month testing whether 5/8 was better idea that 2/3 for resizing or when the ideal small dict size was 4, 8, or 16). You're changing the meaning of the fields in dictobject.h which will likely break any code that relied on those.
>
> The ideas may be good ones but they warrant a good deal of thought. Dicts weren't just slapped together -- the current code is the product to two decades of tweaking by engineers who devoted significant time to the task. It would be easy to unknowingly undo some of their work.
>

OK.
I'll write a PEP.

By the way, I'm trying not changing the tunable parameters for the
unshared-keys case, just the shared-keys case. Of course, they do
interact with each other.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Jan 31, 2012, 4:55 AM

Post #17 of 35 (55 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Antoine Pitrou <pitrou [at] free> added the comment:

As Victor I think the tunables could be changed separately, unless they truely get in the way of the shared-keys optimization.

By the way, there will need a "protection" for the case where instances are used as bags of key/value pairs (dict-alikes with attribute access). Perhaps bound the size of the keys array to 100 entries and then switch into unshared mode.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Jan 31, 2012, 5:54 AM

Post #18 of 35 (55 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Changes by Jesús Cea Avión <jcea [at] jcea>:

----------
nosy: +jcea

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Jan 31, 2012, 4:09 PM

Post #19 of 35 (55 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Gregory P. Smith <greg [at] krypto> added the comment:

FYI - I strongly support this type of work to reduce memory use of the Python interpreter! :)

Also, yes, constant changing should be separate from this change but are worth occasionally re-measuring and justifying as common computer architectures have changed since the original decisions were made.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Feb 6, 2012, 8:42 AM

Post #20 of 35 (50 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Changes by Mark Shannon :

----------
hgrepos: -109

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Feb 8, 2012, 5:43 AM

Post #21 of 35 (48 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Changes by Mark Shannon :

----------
hgrepos: +112

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Feb 8, 2012, 5:44 AM

Post #22 of 35 (48 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Changes by Mark Shannon :

Added file: http://bugs.python.org/file24453/a9138aba7896.diff

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Feb 8, 2012, 5:48 AM

Post #23 of 35 (48 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Changes by Mark Shannon :

Removed file: http://bugs.python.org/file24360/6a21f3b35e20.diff

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Feb 8, 2012, 6:00 AM

Post #24 of 35 (48 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Changes by Mark Shannon :

Removed file: http://bugs.python.org/file24453/a9138aba7896.diff

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Feb 8, 2012, 6:20 AM

Post #25 of 35 (48 views)
Permalink

[issue13903] New shared-keys dictionary implementation [In reply to]

Changes by Mark Shannon :

Added file: http://bugs.python.org/file24454/1f703b2607af.diff

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue13903>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

1 2

View All

Index | Next | Previous | View Threaded

Interested in having your list archived? Contact Gossamer Threads