classification
Title: Use FASTCALL in dict.update()
Type: enhancement Stage: patch review
Components: Interpreter Core Versions: Python 3.9
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: Nosy List: inada.naoki, jdemeyer, larry, python-dev, rhettinger, vstinner
Priority: normal Keywords: patch

Created on 2017-01-18 17:07 by vstinner, last changed 2019-07-09 10:19 by jdemeyer.

Files
File name Uploaded Description Edit
dict_update_fastcall.patch vstinner, 2017-01-18 17:07
dict_update_fastcall-2.patch vstinner, 2017-01-19 10:03 review
Pull Requests
URL Status Linked Edit
PR 14589 open jdemeyer, 2019-07-04 14:54
Messages (21)
msg285744 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2017-01-18 17:07
Follow-up of the issue #29311 "Argument Clinic: convert dict methods".

The dict.update() method hs a special prototype:

   def update(arg=None **kw): ...

I don't think that Argument Clinic supports it right now, so I propose to first optimize dict_update() to use METH_FASTCALL.

Attached patch is a first step: convert kwnames tuple to a dict.

A second step would be to avoid the temporary dict and update the dict using args + kwnames directly.
msg285745 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2017-01-18 17:10
My patch doesn't use _PyStack_AsDict() since this function currently fails with an assertion error if a key is not exactly a string (PyUnicode_CheckExact). dict_update_common() already checks if all keys are string.
msg285747 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2017-01-18 17:14
See also issue #20291: "Argument Clinic should understand *args and **kwargs parameters".
msg285766 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2017-01-19 01:38
Using FASTCALL for methods accepting **kwargs can't skip creating dict in most cases.  Because they accepts dict.

Even worth, when calling it like `d.update(**config)` (yes, it's abuse of
**, but it can be happen in some C methods), FASTCALL may unpack the passed
dict, and pack it again.

So, when considering METH_FASTCALL, supporting **kwargs is lowest priority.
(Off course, supporting it by AC with METH_KEYWORDS is nice to have)
msg285768 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2017-01-19 06:48
I like the other AC changes to dict in 29311, but this one seems like it shouldn't be done.  There is too much twisting around existing code to force it to use AC and the benefit will be almost nothing.   dict.update() is mainly used with a list of tuples argument or with another mapping.  The O(1) time spent on the method call is inconsequential compared to the O(n) step of looping over all the inputs and putting them in the dict.  Accordingly, I think this method should be skipped, leaving the current clear, stable, fast-enough code in-place.
msg285770 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2017-01-19 10:03
Oops, I forgot a DECREF: fixed in the patch version 2.

--

Oh wait, I misunderstood how dict.update() is called. In fact, they are two bytecodes to call a function with keyword arguments.

(1) Using **kwargs:

>>> def f():
...  d.update(**d2)
... 
>>> dis.dis(f)
  2           0 LOAD_GLOBAL              0 (d)
              2 LOAD_ATTR                1 (update)
              4 BUILD_TUPLE              0
              6 LOAD_GLOBAL              2 (d2)
              8 CALL_FUNCTION_EX         1
             10 POP_TOP
             12 LOAD_CONST               0 (None)
             14 RETURN_VALUE


(2) Using a list of key=value:

>>> def g():
...  d.update(x=1, y=2)
... 
>>> dis.dis(g)
  2           0 LOAD_GLOBAL              0 (d)
              2 LOAD_ATTR                1 (update)
              4 LOAD_CONST               1 (1)
              6 LOAD_CONST               2 (2)
              8 LOAD_CONST               3 (('x', 'y'))
             10 CALL_FUNCTION_KW         2
             12 POP_TOP
             14 LOAD_CONST               0 (None)
             16 RETURN_VALUE


The problem is that the dict.update() method has a single implementation, the C dict_update() function.


For (2), there is a speedup, but it's minor:

$ ./python -m perf timeit -s 'd={"x": 1, "y": 2}' 'd.update(x=1, y=2)' -p10 --compare-to=../default-ref/python 
Median +- std dev: [ref] 185 ns +- 62 ns -> [patched] 177 ns +- 2 ns: 1.05x faster (-5%)


For (1), I expected that **kwargs would be unpacked *before* calling dict.update(), but kwargs is passed unchanged to dict.update() directly! With my patch, CALL_FUNCTION_EX calls PyCFunction_Call() which uses _PyStack_UnpackDict() to create kwnames and then dict_update() rebuilds a new temporary dictionary. It's completely inefficient! As Raymond expected, it's much slower:

haypo@smithers$ ./python -m perf timeit -s 'd={"x": 1, "y": 2}; d2=dict(d)' 'd.update(**d2)' -p10 --compare-to=../default-ref/python
Median +- std dev: [ref] 114 ns +- 1 ns -> [patched] 232 ns +- 21 ns: 2.04x slower (+104%)


I expect that (1) dict.update(**kwargs) is more common than (2) dict.update(x=1, y=2). Moreover, the speedup for (2) is low (5%), so I prefer to reject this issue.

--

Naoki: "So, when considering METH_FASTCALL, supporting **kwargs is lowest priority. (Off course, supporting it by AC with METH_KEYWORDS is nice to have)"

Hum, dict.update() is the first function that I found that really wants a Python dict at the end.

For dict1.update(**dict2), METH_VARARGS|METH_KEYWORDS is already optimal.

So I don't think that it's worth it to micro-optimize the way to pass positional arguments. The common case is to call dict1.update(dict2) which requires to build a temporary tuple of 1 item. PyTuple_New() uses a free list for such small tuple, so it should be fast enough.

I found a few functions which pass through keyword arguments, but they are "proxy". I'm converting all METH_VARARGS|METH_KEYWORDS to METH_FASTCALL, so most functions will expects a kwnames tuple at the end of the call for keyword arguments. In this case, using METH_FASTCALL for the proxy is optimum for func(x=1, y=2) (CALL_FUNCTION_KW), but slower for func(**kwargs) (CALL_FUNCTION_EX).

With METH_FASTCALL, CALL_FUNCTION_EX requires to unpack the dictionary if I understood correctly.
msg285774 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2017-01-19 11:34
When analyzing how FASTCALL handles "func(**kwargs)" calls for Python functions, I identified a missed optimization. I created the issue #29318: "Optimize _PyFunction_FastCallDict() for **kwargs".
msg285778 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2017-01-19 11:45
New changeset e371686229e7 by Victor Stinner in branch 'default':
Add a note explaining why dict_update() doesn't use METH_FASTCALL
https://hg.python.org/cpython/rev/e371686229e7
msg347262 - (view) Author: Jeroen Demeyer (jdemeyer) * (Python triager) Date: 2019-07-04 09:55
For the benefit of PR 37207, I would like to re-open this discussion. It may have been rejected for the wrong reasons. Victor's patch was quite inefficient, but that's to be expected: msg285744 mentions a two-step process, but during the discussion the second steps seems to have been forgotten.
msg347271 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-07-04 11:07
How can we avoid unpacking dict in case of d1.update(**d2)?
msg347274 - (view) Author: Jeroen Demeyer (jdemeyer) * (Python triager) Date: 2019-07-04 11:35
> How can we avoid unpacking dict in case of d1.update(**d2)?

We cannot. However, how common is that call? One could argue that we should optimize for the more common case of d1.update(d2).
msg347275 - (view) Author: Jeroen Demeyer (jdemeyer) * (Python triager) Date: 2019-07-04 11:37
Above, I meant #37207 or PR 13930.
msg347276 - (view) Author: Jeroen Demeyer (jdemeyer) * (Python triager) Date: 2019-07-04 11:48
> How can we avoid unpacking dict in case of d1.update(**d2)?

The unpacking is only a problem if you insist on using PyDict_Merge(). It would be perfectly possible to implement dict merging from a tuple+vector instead of from a dict. In that case, there shouldn't be a performance penalty.
msg347277 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-07-04 11:55
> The unpacking is only a problem if you insist on using PyDict_Merge(). It would be perfectly possible to implement dict merging from a tuple+vector instead of from a dict. In that case, there shouldn't be a performance penalty.

Really?

```
class K:
    def __eq__(self, other):
        return True
    def __hash__(self):
        time.sleep(10)
        return 42

d1 = {"foo": 1, "bar": 2, "baz": 3, K(): 4}
d2 = dict(**d1)
```

I think `dict(**d1)` doesn't call K.__hash__() in this example, because hash value is cached in d1.
msg347278 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-07-04 11:56
- d2 = dict(**d1)
+ d2 = {"fizz": "buzz"}
+ d2.update(**d1)
msg347279 - (view) Author: Jeroen Demeyer (jdemeyer) * (Python triager) Date: 2019-07-04 12:22
You are correct that PyDict_Merge() does not need to recompute the hashes of the keys. However, your example doesn't work because you need string keys for **kwargs. The "str" class caches its hash, so you would need a dict with a "str" subclass as keys to hit that problem.

I think that calling d.update(**kw) with kw having str-subclass keys should be very rare. I'm not sure that we should care about that.
msg347280 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-07-04 12:34
OK, `d1.update(**d2)` is not useful in practice.  Practical usages of dict.update() are:

* d.update(d2)
* d.update([(k1,k2),...])
* d.update(k1=v1, k2=v2, ...)
* d.update(**d2, **d3, **d4)  # little abuse, but possible.

In all of them, kwdict is not used at all or can't avoid unpacking the kwdict.
msg347286 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2019-07-04 16:13
Changing dict.update() calling convention may save a few nanoseconds on d1.update(d2) call, but it will make d1.update(**d2) way slower with a complexity of O(n): d2 must be converted to 2 lists (kwnames and args) and then a new dict should be created.

I don't see the point of micro-optimizing d1.update(d2), if d1.update(**d2) would become way slower.
msg347506 - (view) Author: Jeroen Demeyer (jdemeyer) * (Python triager) Date: 2019-07-08 19:08
> d2 must be converted to 2 lists (kwnames and args) and then a new dict should be created.

The last part is not necessarily true. You could do the update directly, without having that intermediate dict.
msg347515 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-07-09 02:46
> Changing dict.update() calling convention may save a few nanoseconds on d1.update(d2) call, but it will make d1.update(**d2) way slower with a complexity of O(n): d2 must be converted to 2 lists (kwnames and args) and then a new dict should be created.

But who/why use d1.update(**d2)?
In case of dict(), dict(d1, **d2) was idiom to merge two dicts.
But I don't know any practical usage of d1.update(**d2).  d1.update(d2) should be preferred.
msg347539 - (view) Author: Jeroen Demeyer (jdemeyer) * (Python triager) Date: 2019-07-09 10:19
> but it will make d1.update(**d2) slower with a complexity of O(n): d2 must be converted to 2 lists

This part is still true and it causes a slow-down of about 23% for dict.update(**d), see benchmarks at https://github.com/python/cpython/pull/14589#issuecomment-509356084
History
Date User Action Args
2019-07-09 10:19:34jdemeyersetmessages: + msg347539
2019-07-09 02:46:32inada.naokisetmessages: + msg347515
2019-07-08 19:08:05jdemeyersetmessages: + msg347506
2019-07-04 16:13:14vstinnersetmessages: + msg347286
2019-07-04 14:54:52jdemeyersetstage: patch review
pull_requests: + pull_request14407
2019-07-04 12:34:42inada.naokisetstatus: closed -> open
versions: + Python 3.9, - Python 3.7
messages: + msg347280

components: + Interpreter Core, - Argument Clinic
resolution: rejected ->
2019-07-04 12:22:14jdemeyersetmessages: + msg347279
2019-07-04 11:56:28inada.naokisetmessages: + msg347278
2019-07-04 11:55:14inada.naokisetmessages: + msg347277
2019-07-04 11:48:02jdemeyersetmessages: + msg347276
2019-07-04 11:37:51jdemeyersetmessages: + msg347275
2019-07-04 11:35:52jdemeyersetmessages: + msg347274
2019-07-04 11:07:56inada.naokisetmessages: + msg347271
2019-07-04 09:55:51jdemeyersetnosy: + jdemeyer
messages: + msg347262
2017-01-19 11:45:26python-devsetnosy: + python-dev
messages: + msg285778
2017-01-19 11:34:29vstinnersetresolution: rejected
messages: + msg285774
2017-01-19 10:03:50vstinnersetstatus: open -> closed
files: + dict_update_fastcall-2.patch
messages: + msg285770
2017-01-19 06:48:40rhettingersetnosy: + rhettinger
messages: + msg285768
2017-01-19 01:38:56inada.naokisetmessages: + msg285766
2017-01-18 17:14:13vstinnersetmessages: + msg285747
2017-01-18 17:13:27vstinnersetnosy: + larry
components: + Argument Clinic
2017-01-18 17:10:15vstinnersetmessages: + msg285745
2017-01-18 17:07:42vstinnercreate