Speed up dict vectorcall creation using keywords

[Marco-Sulla]

BPO	41835
Nosy	@methane, @markshannon, @serhiy-storchaka, @Marco-Sulla
PRs	bpo-41835: Speedup to dict vectorcall with keyword arguments. #22346 bpo-41835: Optimize dict() call with keyword arguments #22909 bpo-41835: Add _PyDict_SetItem_NoDuplicate #23106
Files	pr23106.txt: long result bench_kwcall.py

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2020-11-02.14:13:06.903>
created_at = <Date 2020-09-22.12:56:44.515>
labels = ['interpreter-core', '3.10']
title = 'Speed up dict vectorcall creation using keywords'
updated_at = <Date 2020-11-02.14:13:06.903>
user = 'https://github.com/Marco-Sulla'

bugs.python.org fields:

activity = <Date 2020-11-02.14:13:06.903>
actor = 'methane'
assignee = 'none'
closed = True
closed_date = <Date 2020-11-02.14:13:06.903>
closer = 'methane'
components = ['Interpreter Core']
creation = <Date 2020-09-22.12:56:44.515>
creator = 'Marco Sulla'
dependencies = []
files = ['49560', '49561']
hgrepos = []
issue_num = 41835
keywords = ['patch']
message_count = 25.0
messages = ['377318', '377359', '377397', '379290', '379409', '379435', '379436', '379458', '379475', '379523', '379524', '379525', '379528', '380000', '380033', '380051', '380060', '380066', '380078', '380110', '380127', '380214', '380218', '380219', '380222']
nosy_count = 4.0
nosy_names = ['methane', 'Mark.Shannon', 'serhiy.storchaka', 'Marco Sulla']
pr_nums = ['22346', '22909', '23106']
priority = 'normal'
resolution = 'rejected'
stage = 'resolved'
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue41835'
versions = ['Python 3.10']

[Marco-Sulla]

I've done a PR that speeds up the vectorcall creation of a dict using keyword arguments. The PR in practice creates a insertdict_init(), a specialized version of insertdict. I quote the comment to the function:

Same to insertdict but specialized for inserting without resizing and for dict that are populated in a loop and was empty before (see the empty arg).
Note that resizing must be done before calling this function. If not
possible, use insertdict(). Furthermore, ma_version_tag is left unchanged, you have to change it after calling this function (probably at the end of a loop).

This change speeds up the code up to a 30%. Tested with:

python -m timeit -n 2000 --setup "from uuid import uuid4 ; o =
{str(uuid4()).replace('-', '') : str(uuid4()).replace('-', '') for i
in range(10000)}" "dict(**o)"

[methane]

I have a Linux desktop machine for benchmarking & profiling in my office. But the machine is offline and I am working from home several weeks.
So please wait several weeks until I confirm your branch.

This change speeds up the code up to a 30%. Tested with:

python -m timeit -n 2000 --setup "from uuid import uuid4 ; o =
{str(uuid4()).replace('-', '') : str(uuid4()).replace('-', '') for i
in range(10000)}" "dict(**o)"

dict(**o) is not common use case. Could you provide some other benchmarks?

[Marco-Sulla]

dict(**o) is not common use case. Could you provide some other benchmarks?

You can do

python -m timeit -n 2000000 "dict(key1=1, key2=2, key3=3, key4=4, key5=5, key6=6, key7=7, key8=8, key9=9, key10=10)"

or with pyperf. In this case, since the dict is little, I observed a speedup of 25%.

[Marco-Sulla]

Another bench:

python -m pyperf timeit --rigorous "dict(ihinvdono='doononon', gowwondwon='nwog', bdjbodbob='nidnnpn', nwonwno='vndononon', dooodbob='iohiwipwgpw', doidonooq='ndwnnpnpnp', fndionqinqn='ndjboqoqjb', nonoeoqgoqb='bdboboqbgoqeb', jdnvonvoddo='nvdjnvndvonoq', njnvodnoo='hiehgieba', nvdnvwnnp='wghgihpa', nvfnwnnq='nvdknnnqkm', ndonvnipnq='fndjnaobobvob', fjafosboab='ndjnodvobvojb', nownwnojwjw='nvknnndnow', niownviwnwnwi='nownvwinvwnwnwj')"

Result without pull:
Mean +- std dev: 486 ns +- 8 ns

Result with pull:
Mean +- std dev: 328 ns +- 4 ns

I compiled both with optimizations and lto.

Some arch info:

python -VV
Python 3.10.0a1+ (heads/master-dirty:dde91b1953, Oct 22 2020, 14:00:51)
[GCC 10.1.1 20200718]

uname -a
Linux buzz 4.15.0-118-generic #119-Ubuntu SMP Tue Sep 8 12:30:01 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 18.04.5 LTS

[methane]

Ok. Performance improvement comes from:

a. Presizing
b. Bypassing some checks in PyDict_SetItem
c. Avoiding duplication check.

(b) is relatively small so I tried to focus on (a) and (b). See #67098.

In case of simple keyword arguments, it is 10% faster than #66542:

$ ./python -m pyperf timeit --compare-to ./python-speedup_kw "dict(ihinvdono='doononon', gowwondwon='nwog', bdjbodbob='nidnnpn', nwonwno='vndononon', dooodbob='iohiwipwgpw', doidonooq='ndwnnpnpnp', fndionqinqn='ndjboqoqjb', nonoeoqgoqb='bdboboqbgoqeb', jdnvonvoddo='nvdjnvndvonoq', njnvodnoo='hiehgieba', nvdnvwnnp='wghgihpa', nvfnwnnq='nvdknnnqkm', ndonvnipnq='fndjnaobobvob', fjafosboab='ndjnodvobvojb', nownwnojwjw='nvknnndnow', niownviwnwnwi='nownvwinvwnwnwj')"
python-speedup_kw: ..................... 357 ns +- 10 ns
python: ..................... 323 ns +- 4 ns

Mean +- std dev: [python-speedup_kw] 357 ns +- 10 ns -> [python] 323 ns +- 4 ns: 1.11x faster (-10%)

In case of dict(d, key=val) case, it is 8% slower than #66542, but still 8% faster than master.

$ ./python -m pyperf timeit --compare-to ./python-speedup_kw -s 'd={"foo":"bar"}' "dict(d, ihinvdono='doononon', gowwondwon='nwog', bdjbodbob='nidnnpn', nwonwno='vndononon', dooodbob='iohiwipwgpw', doidonooq='ndwnnpnpnp', fndionqinqn='ndjboqoqjb', nonoeoqgoqb='bdboboqbgoqeb', jdnvonvoddo='nvdjnvndvonoq', njnvodnoo='hiehgieba', nvdnvwnnp='wghgihpa', nvfnwnnq='nvdknnnqkm', ndonvnipnq='fndjnaobobvob', fjafosboab='ndjnodvobvojb', nownwnojwjw='nvknnndnow', niownviwnwnwi='nownvwinvwnwnwj')"
python-speedup_kw: ..................... 505 ns +- 15 ns
python: ..................... 546 ns +- 17 ns

Mean +- std dev: [python-speedup_kw] 505 ns +- 15 ns -> [python] 546 ns +- 17 ns: 1.08x slower (+8%)

$ ./python -m pyperf timeit --compare-to ./python-master -s 'd={"foo":"bar"}' "dict(d, ihinvdono='doononon', gowwondwon='nwog', bdjbodbob='nidnnpn', nwonwno='vndononon', dooodbob='iohiwipwgpw', doidonooq='ndwnnpnpnp', fndionqinqn='ndjboqoqjb', nonoeoqgoqb='bdboboqbgoqeb', jdnvonvoddo='nvdjnvndvonoq', njnvodnoo='hiehgieba', nvdnvwnnp='wghgihpa', nvfnwnnq='nvdknnnqkm', ndonvnipnq='fndjnaobobvob', fjafosboab='ndjnodvobvojb', nownwnojwjw='nvknnndnow', niownviwnwnwi='nownvwinvwnwnwj')"
python-master: ..................... 598 ns +- 10 ns
python: ..................... 549 ns +- 19 ns

Mean +- std dev: [python-master] 598 ns +- 10 ns -> [python] 549 ns +- 19 ns: 1.09x faster (-8%)

Additionally, I expect we can reuse this new code to optimize BUILD_CONST_KEY_MAP.

[methane]

@marco Sulla Please take a look at #67098. It is simplified version of your PR. And I wrote another optimization based on it bpo-42126.

[markshannon]

Could we get a pyperformance benchmark run on this please?

[Marco-Sulla]

@methane: well, to be honest, I don't see much difference between the two pulls. The major difference is that you merged insertdict_init in dict_merge_init.

But I kept insertdict_init separate on purpose, because this function can be used in other future dedicated function on creation time only. Furthermore it's more simple to maintain, since it's quite identical to insertdict.

[Marco-Sulla]

@Mark.Shannon I tried to run pyperformance, but wheel does not work for Python 3.10. I get the error:

AssertionError: would build wheel with unsupported tag ('cp310', 'cp310', 'linux_x86_64')

[methane]

@Mark.Shannon I had seen some speedup on tornado benchmark when I didn't use PGO+LTO. but it was noise.

Now I use PGO+LTO. master vs PR-22909:

$ ./python -m pyperf compare_to master-opt.json speedup_kw-opt.json -G --min-speed=1
Slower (11):
- spectral_norm: 147 ms +- 1 ms -> 153 ms +- 2 ms: 1.04x slower (+4%)
- pickle_dict: 28.6 us +- 0.1 us -> 29.5 us +- 0.6 us: 1.03x slower (+3%)
- regex_compile: 199 ms +- 1 ms -> 204 ms +- 4 ms: 1.03x slower (+3%)
- chameleon: 9.75 ms +- 0.10 ms -> 9.99 ms +- 0.09 ms: 1.02x slower (+2%)
- logging_format: 10.9 us +- 0.2 us -> 11.1 us +- 0.2 us: 1.02x slower (+2%)
- sqlite_synth: 3.29 us +- 0.05 us -> 3.36 us +- 0.05 us: 1.02x slower (+2%)
- regex_v8: 26.1 ms +- 0.1 ms -> 26.5 ms +- 0.3 ms: 1.02x slower (+2%)
- json_dumps: 14.6 ms +- 0.1 ms -> 14.8 ms +- 0.1 ms: 1.02x slower (+2%)
- logging_simple: 9.88 us +- 0.18 us -> 10.0 us +- 0.2 us: 1.02x slower (+2%)
- nqueens: 105 ms +- 1 ms -> 107 ms +- 2 ms: 1.01x slower (+1%)
- raytrace: 511 ms +- 5 ms -> 517 ms +- 6 ms: 1.01x slower (+1%)

Faster (10):

• regex_dna: 233 ms +- 1 ms -> 229 ms +- 1 ms: 1.02x faster (-2%)
• unpickle: 14.7 us +- 0.1 us -> 14.5 us +- 0.2 us: 1.02x faster (-1%)
• deltablue: 8.17 ms +- 0.29 ms -> 8.06 ms +- 0.17 ms: 1.01x faster (-1%)
• mako: 16.8 ms +- 0.2 ms -> 16.6 ms +- 0.1 ms: 1.01x faster (-1%)
• xml_etree_iterparse: 117 ms +- 1 ms -> 116 ms +- 1 ms: 1.01x faster (-1%)
• scimark_monte_carlo: 117 ms +- 2 ms -> 115 ms +- 1 ms: 1.01x faster (-1%)
• xml_etree_parse: 164 ms +- 3 ms -> 162 ms +- 1 ms: 1.01x faster (-1%)
• unpack_sequence: 62.7 ns +- 0.7 ns -> 62.0 ns +- 0.7 ns: 1.01x faster (-1%)
• regex_effbot: 3.43 ms +- 0.01 ms -> 3.39 ms +- 0.02 ms: 1.01x faster (-1%)
• scimark_fft: 405 ms +- 4 ms -> 401 ms +- 1 ms: 1.01x faster (-1%)

Benchmark hidden because not significant (39)

[methane]

@marco Sulla

@methane: well, to be honest, I don't see much difference between the two pulls. The major difference is that you merged insertdict_init in dict_merge_init.

Not only it but also some simplification which make 10% faster than #66542.

But I kept insertdict_init separate on purpose, because this function can be used in other future dedicated function on creation time only.

Where do you expect to use it? Would you implement some more optimization based on your PR to demonstrate your idea?

I confirmed that #67098 can be used to optimize BUILD_CONST_KEY_MAP (GH-22911). That's why I merged two functions.

AssertionError: would build wheel with unsupported tag ('cp310', 'cp310', 'linux_x86_64')

Try pip install pyperformance==1.0.0.