Mailman 3 dict changes [was: Ordered storage of keyword arguments] - Python-ideas

newer
Re: [Python-ideas] Possible PEP...

dict changes [was: Ordered storage of keyword arguments]

older
ExternalMemory

Jim Jewett

28 Oct 2010 28 Oct '10

11:44 a.m.

On 10/28/10, Antoine Pitrou wrote:

...

On Thu, 28 Oct 2010 19:58:59 +0200 spir wrote:

...

...
What does the current implementation use as buckets?

...

It uses an open addressing strategy. Each dict entry holds three pointer-sized fields: key object, value object, and cached hash value of the key. (set entries have only two fields, since they don't hold a value object)

Has anyone benchmarked not storing the hash value here? For a string dict, that hash should already be available on the string object itself, so it is redundant. Keeping it obviously improves cache locality, but ... it also makes the dict objects 50% larger, and there is a chance that the strings themselves would already be in cache anyhow. And if strings were reliably interned, the comparison check should normally just be a pointer compare -- possibly fast enough that the "different hash" shortcut doesn't buy anything. [caveats about still needing to go to the slower dict implementation for string subclasses] -jJ

Show replies by date

Raymond Hettinger

28 Oct 28 Oct

12:06 p.m.

On Oct 28, 2010, at 11:44 AM, Jim Jewett wrote:

...

...
It uses an open addressing strategy. Each dict entry holds three pointer-sized fields: key object, value object, and cached hash value of the key. (set entries have only two fields, since they don't hold a value object)

Has anyone benchmarked not storing the hash value here

That would be a small disaster. Either you call PyObject_Hash() for every probe (adding function call overhead for int and str, and adding tons of work for other types) or you can go directly to Py_RichCompareBool() which is never fast. I haven't timed this for dicts, but I did see major speed boosts in the performance of set-to-set operations when the internally stored hash was used instead of calling PyObject_Hash(). Raymond

Antoine Pitrou

3:11 p.m.

Le jeudi 28 octobre 2010 à 14:44 -0400, Jim Jewett a écrit :

...

For a string dict, that hash should already be available on the string object itself, so it is redundant. Keeping it obviously improves cache locality, but ... it also makes the dict objects 50% larger, and there is a chance that the strings themselves would already be in cache anyhow. And if strings were reliably interned, the comparison check should normally just be a pointer compare -- possibly fast enough that the "different hash" shortcut doesn't buy anything. [caveats about still needing to go to the slower dict implementation for string subclasses]

I've thought about that. The main annoyance is to be able to switch transparently between the two implementations. But I think it would be interesting to pursue that effort, since indeed dicts with interned keys are the most common case of dicts in the average Python workload. Saving 1/3 of the memory size on these dicts would be worthwhile IMO. (addressing itself would perhaps be a bit simpler, because of multiplying by 8 or 16 instead of multiplying by 12 or 24. But I doubt the difference would be noticeable) Regartds Antoine.

M.-A. Lemburg

29 Oct 29 Oct

1:51 a.m.

New subject: dict changes [was: Ordered storage of keyword arguments]

Antoine Pitrou wrote:

...

Le jeudi 28 octobre 2010 à 14:44 -0400, Jim Jewett a écrit :

...
For a string dict, that hash should already be available on the string object itself, so it is redundant. Keeping it obviously improves cache locality, but ... it also makes the dict objects 50% larger, and there is a chance that the strings themselves would already be in cache anyhow. And if strings were reliably interned, the comparison check should normally just be a pointer compare -- possibly fast enough that the "different hash" shortcut doesn't buy anything. [caveats about still needing to go to the slower dict implementation for string subclasses]

I've thought about that. The main annoyance is to be able to switch transparently between the two implementations. But I think it would be interesting to pursue that effort, since indeed dicts with interned keys are the most common case of dicts in the average Python workload. Saving 1/3 of the memory size on these dicts would be worthwhile IMO.

Are you sure ? In the age of GB RAM, runtime performance appears to be more important than RAM usage. Moving the hash comparison out of the dict would likely cause (cache) locality to no longer trigger.

...

(addressing itself would perhaps be a bit simpler, because of multiplying by 8 or 16 instead of multiplying by 12 or 24. But I doubt the difference would be noticeable)

-- Marc-Andre Lemburg eGenix.com Professional Python Services directly from the Source (#1, Oct 29 2010)

...

...
...
Python/Zope Consulting and Support ... http://www.egenix.com/ mxODBC.Zope.Database.Adapter ... http://zope.egenix.com/ mxODBC, mxDateTime, mxTextTools ... http://python.egenix.com/

::: Try our new mxODBC.Connect Python Database Interface for free ! :::: eGenix.com Software, Skills and Services GmbH Pastor-Loeh-Str.48 D-40764 Langenfeld, Germany. CEO Dipl.-Math. Marc-Andre Lemburg Registered at Amtsgericht Duesseldorf: HRB 46611 http://www.egenix.com/company/contact/

Antoine Pitrou

2:06 a.m.

New subject: dict changes [was: Ordered storage of keyword arguments]

Le vendredi 29 octobre 2010 à 10:51 +0200, M.-A. Lemburg a écrit :

...

...
I've thought about that. The main annoyance is to be able to switch transparently between the two implementations. But I think it would be interesting to pursue that effort, since indeed dicts with interned keys are the most common case of dicts in the average Python workload. Saving 1/3 of the memory size on these dicts would be worthwhile IMO.

Are you sure ? In the age of GB RAM, runtime performance appears to be more important than RAM usage. Moving the hash comparison out of the dict would likely cause (cache) locality to no longer trigger.

Good point. It probably depends on the collision rate. Also, a string key dict could be optimized for interned strings, in which case the hash comparison is unnecessary. (knowing whether the key is interned could be stored in e.g. the low-order bit of the key pointer) Regards Antoine.

4925

Age (days ago)

4926

Last active (days ago)

List overview

Download

4 comments

4 participants

participants (4)

Antoine Pitrou
Jim Jewett
M.-A. Lemburg
Raymond Hettinger

dict changes [was: Ordered storage of keyword arguments]

Jim Jewett

Raymond Hettinger

Antoine Pitrou

M.-A. Lemburg

Antoine Pitrou

tags

participants (4)