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

[Raymond Hettinger]

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