classification
Title: Extend the PyDict C API to handle cases where the hash value is known
Type: enhancement Stage: patch review
Components: Interpreter Core Versions: Python 3.5
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: Arfrever, alex, josh.r, pitrou, python-dev, r.david.murray, rhettinger, serhiy.storchaka, terry.reedy
Priority: normal Keywords: patch

Created on 2014-03-30 08:47 by rhettinger, last changed 2014-05-03 23:42 by rhettinger. This issue is now closed.

Files
File name Uploaded Description Edit
known_hash.diff rhettinger, 2014-03-30 08:47 Add two functions to dictobject review
applied_known_hash.diff rhettinger, 2014-03-30 08:47 Sample application to the collections module review
double_counter_hash.py rhettinger, 2014-03-30 09:16 Demonstrate unnecessary double hashing in a counter
Messages (16)
msg215175 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2014-03-30 08:58
Propose adding two functions, PyDict_GetItem_KnownHash() and PyDict_SetItem_KnownHash().

It is reasonably common to make two successive dictionary accesses with the same key.  This results in calling the hash function twice to compute the same result.

For example, the technique can be used to speed-up collections.Counter (see the attached patch to show how).  In that patch, the hash is computed once, then used twice (to retrieve the prior count and to store the new count.

There are many other places in the standard library that could benefit:

    Modules/posixmodule.c 1254
    Modules/pyexpat.c 343 and 1788 and 1798
    Modules/_json.c 628 and 1446 and 1515 and 1697
    Modules/selectmodule.c 465
    Modules/zipmodule.c 137
    Objects/typeobject.c 6678 and 6685
    Objects/unicodeobject.c 14997
    Python/_warnings.c 195
    Python/compile.c 1134
    Python/import.c 1046 and 1066
    Python/symtable 671 and 687 and 1068

A similar technique has been used for years in the Objects/setobject.c internals as a way to eliminate unnecessary calls to PyObject_Hash() during set-to-set and set-to-dict operations.

The benefit is biggest for objects such as tuples or user-defined classes that have to recompute the hash on every call on PyObject_Hash().
msg215180 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2014-03-30 14:18
Is there any benefit in making them public API functions?
msg215186 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2014-03-30 16:23
> Is there any benefit in making them public API functions?

Originally, I was going to suggest them as internal functions, but the variety of use cases in the standard library suggested that third-party C extensions would benefit as well.  

Since this isn't functionality a user can create themselves, a public function is the only way to expose this service.
msg215187 - (view) Author: Alex Gaynor (alex) * (Python committer) Date: 2014-03-30 16:33
Would it be reasonable to develop a Python API for this? If C functions have a need to do this, surely Python code does as well.
msg215192 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2014-03-30 18:23
> Would it be reasonable to develop a Python API for this? 

I suspect that in pure Python, the overhead would exceed the benefit.

Current code:

   d[key] = d[key] + 1

Effort to save a double hash:

   h = hash(key)
   c = d.getitem_known_hash(key, hash)
   d.setitem_known_hash(key, hash, c + 1)

In PyPy, the second code sample might actually be faster that the first, but all the other pythons suffer from interpreter overhead, a double dict lookup for the hash() function, two dict lookups just to find the new methods, allocating a bound method, and forming two argument tuples.

There is also an API design issue.  The pure python core datatype APIs are designed in a way to encourage higher level thinking (that is why we can't directly manage hash table sparsity or list over-allocation for example).

In contrast, the C API is aimed at users who seek additional control and  optimization at a lower level than the core language provides.  We tend to expose a number of tools at the C level that would be inappropriate for higher-level code.
msg215560 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2014-04-04 20:28
While the question is reasonable, I agree with Raymond's answer. As a python programmer, I would not like to see
   d.setitem_known_hash(key, hash, d.getitem_known_hash(key, hash) + 1)

Of course, "d[key] += 1" already solves the double lookup issue at the Python level. Moreover, it abbreviates the form, rather than expanding it, which is appropriate since it abbreviates the computation.

You could optimize get-set even more than the current proposal by saving a reference to the slot corresponding to a key rather than the hash that leads to a slot. Exposing a slot reference probably breaks encapsulation too much. This could be avoided by another alternative: add PyDict_Mod(ify)Item(mapping, key, func). It would combine get and set: find slot, get item, set func(item), and return whatever SetItem does on success/failure.
msg215561 - (view) Author: Alex Gaynor (alex) * (Python committer) Date: 2014-04-04 20:31
d[key] += 1 still does two dict lookups, and invokes the hash function twice:

>>> class X(object):
...   def __hash__(self):
...     print "hashed"
...     return 0
...   def __eq__(self, other):
...     return True
...
>>> d = {X(): 0}
hashed
>>> d[X()]
hashed
0
>>> d[X()] = 3
hashed
>>> d[X()] += 1
hashed
hashed
msg215562 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2014-04-04 20:40
> Of course, "d[key] += 1" already solves the double lookup issue at the
> Python level.

What the hell are you talking about?
msg215570 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2014-04-04 21:56
"What the hell I am talking about" is what the doc says. 'd[key]' is written just once and "is evaluated just once".
https://docs.python.org/3/reference/simple_stmts.html#augmented-assignment-statements

PS: Try being a bit more polite.
msg215573 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2014-04-04 22:18
> PS: Try being a bit more polite.

You could definitely do some research before posting erroneous 
statements (this one isn't difficult to check, as Alex showed). 
Especially when the other posters (Alex and Raymond) are a lot more 
competent than you on the topic at hand.

If you actually try to *reason* about it, there is no other way for:
    x[k] += <some_expr>

to work in the general case than to execute
    x.__setitem__(k, x.__getitem__(k) + <some_expr>)

So, yes, the lookup is done twice, because it currently can't work 
otherwise.
msg215575 - (view) Author: R. David Murray (r.david.murray) * (Python committer) Date: 2014-04-04 22:47
Antoine, being polite never hurts.  Terry is a valuable member of the community and sure, he sometimes makes mistakes (or trusts the docs too much?).  So do the the rest of us.
msg215578 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2014-04-04 23:48
Raymond identified a need and a possible solution. The important part of my post was suggesting another possible solution. Please focus on that.
msg216633 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2014-04-17 01:24
Antoine, do you support adding these as part of the public API?  If not, I can make them private.

I think the functions are broadly useful, but no one has ever asked for this functionality either.
msg216635 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2014-04-17 01:27
I think we can start with making them private. Do you know of any third-party code bases which may be interested in the speedup?
msg217845 - (view) Author: Roundup Robot (python-dev) Date: 2014-05-03 23:32
New changeset 39f475aa0163 by Raymond Hettinger in branch 'default':
Issue 21101:  Internal API for dict getitem and setitem where the hash value is known.
http://hg.python.org/cpython/rev/39f475aa0163
msg217848 - (view) Author: Roundup Robot (python-dev) Date: 2014-05-03 23:41
New changeset 592a57682ced by Raymond Hettinger in branch 'default':
Issue #21101:  Eliminate double hashing in the C code for collections.Counter().
http://hg.python.org/cpython/rev/592a57682ced
History
Date User Action Args
2014-05-03 23:42:02rhettingersetstatus: open -> closed
resolution: fixed
2014-05-03 23:41:26python-devsetmessages: + msg217848
2014-05-03 23:32:20python-devsetnosy: + python-dev
messages: + msg217845
2014-04-17 01:27:51pitrousetmessages: + msg216635
2014-04-17 01:24:04rhettingersetmessages: + msg216633
2014-04-04 23:48:52terry.reedysetmessages: + msg215578
2014-04-04 22:47:28r.david.murraysetnosy: + r.david.murray
messages: + msg215575
2014-04-04 22:18:12pitrousetmessages: + msg215573
2014-04-04 21:56:50terry.reedysetmessages: + msg215570
2014-04-04 20:40:17pitrousetmessages: + msg215562
2014-04-04 20:31:19alexsetmessages: + msg215561
2014-04-04 20:28:58terry.reedysetnosy: + terry.reedy
messages: + msg215560
2014-03-31 21:45:39josh.rsetnosy: + josh.r
2014-03-31 13:58:29Arfreversetnosy: + Arfrever
2014-03-30 18:23:06rhettingersetmessages: + msg215192
2014-03-30 18:01:25rhettingersettitle: Extend the PyDict C API to handle cases where the hash value in known -> Extend the PyDict C API to handle cases where the hash value is known
2014-03-30 16:33:23alexsetnosy: + alex
messages: + msg215187
2014-03-30 16:23:06rhettingersetmessages: + msg215186
2014-03-30 14:18:51pitrousetnosy: + pitrou
messages: + msg215180
2014-03-30 11:48:55serhiy.storchakasetnosy: + serhiy.storchaka
2014-03-30 09:16:51rhettingersetfiles: + double_counter_hash.py
2014-03-30 08:58:29rhettingersetmessages: + msg215175
2014-03-30 08:47:43rhettingersetfiles: + applied_known_hash.diff
2014-03-30 08:47:09rhettingercreate