Improve the performance of `set_update_internal()`

[thatbirdguythatuknownot]

Use PyObject_LengthHint() to possibly avoid incremental resizing of the table for the general case in set_update_internal().

Linked PRs

• gh-103563: Improve performance of set_update_internal() #103564

[thatbirdguythatuknownot]

I didn't really think much about why the optimization is currently only done for sets/dicts, which is an error on my part. I may change the code later to include a specific downsizing factor like 1/4 or 1/8 to account for the fact that there might be a lot of duplicates. It should provide some reduction of overhead from incremental resizing, which is probably the same reason the same optimization is done for sets/dicts.

…

On Sun, 16 Apr 2023 at 05:05, Stefan Pochmann ***@***.***> wrote: Looks like you copied that optimization and its comment *"Expect that there will be no (or few) overlapping keys"* from the cases where other is a set or a dict. Those don't contain duplicates themselves, so each key occurs at most twice (once in the set to be updated, and once in other). But you're applying it to general iterables, which might very well contain many duplicates, especially since sets are often used for deduplication. Then there'd be *many* "overlapping" keys. Why do you feel that that expectation is warranted for general iterables? — Reply to this email directly, view it on GitHub <#103563 (comment)>, or unsubscribe <https://proxy-ga.blitzz.co/proxy/123456/github.com/notifications/unsubscribe-auth/ASTVXNR7L3VEBU5IIE7W4UDXBMEQTANCNFSM6AAAAAAW7MU2JY> . You are receiving this because you authored the thread.Message ID: ***@***.***>

[thatbirdguythatuknownot]

Results from pyperformance benchmarks (with no reduction/downsizing factor).

Benchmarks with tag 'apps'

2to3: Mean +- std dev: [py311_before] 455 ms +- 7 ms -> [py311_after] 449 ms +- 10 ms: 1.01x faster
chameleon: Mean +- std dev: [py311_before] 12.1 ms +- 0.3 ms -> [py311_after] 11.9 ms +- 0.4 ms: 1.02x faster
docutils: Mean +- std dev: [py311_before] 3.42 sec +- 0.12 sec -> [py311_after] 3.33 sec +- 0.07 sec: 1.03x faster

Benchmark hidden because not significant (2): html5lib, tornado_http

Geometric mean: 1.02x faster

Benchmarks with tag 'math'

float: Mean +- std dev: [py311_before] 136 ms +- 4 ms -> [py311_after] 133 ms +- 5 ms: 1.02x faster
nbody: Mean +- std dev: [py311_before] 179 ms +- 3 ms -> [py311_after] 170 ms +- 2 ms: 1.06x faster

Benchmark hidden because not significant (1): pidigits

Geometric mean: 1.02x faster

Benchmarks with tag 'regex'

regex_compile: Mean +- std dev: [py311_before] 202 ms +- 1 ms -> [py311_after] 203 ms +- 4 ms: 1.01x slower
regex_dna: Mean +- std dev: [py311_before] 187 ms +- 5 ms -> [py311_after] 189 ms +- 4 ms: 1.01x slower
regex_effbot: Mean +- std dev: [py311_before] 3.31 ms +- 0.05 ms -> [py311_after] 3.27 ms +- 0.05 ms: 1.01x faster
regex_v8: Mean +- std dev: [py311_before] 28.2 ms +- 0.4 ms -> [py311_after] 27.6 ms +- 0.3 ms: 1.02x faster

Geometric mean: 1.00x faster

Benchmarks with tag 'serialize'

json_dumps: Mean +- std dev: [py311_before] 13.6 ms +- 0.1 ms -> [py311_after] 13.7 ms +- 0.2 ms: 1.01x slower
json_loads: Mean +- std dev: [py311_before] 38.7 us +- 1.0 us -> [py311_after] 38.3 us +- 0.6 us: 1.01x faster
pickle_dict: Mean +- std dev: [py311_before] 37.0 us +- 0.7 us -> [py311_after] 36.4 us +- 0.8 us: 1.02x faster
pickle_list: Mean +- std dev: [py311_before] 5.95 us +- 0.11 us -> [py311_after] 5.89 us +- 0.06 us: 1.01x faster
pickle_pure_python: Mean +- std dev: [py311_before] 521 us +- 12 us -> [py311_after] 504 us +- 5 us: 1.03x faster
unpickle_list: Mean +- std dev: [py311_before] 5.63 us +- 0.04 us -> [py311_after] 5.50 us +- 0.08 us: 1.02x faster
unpickle_pure_python: Mean +- std dev: [py311_before] 400 us +- 11 us -> [py311_after] 367 us +- 7 us: 1.09x faster
xml_etree_iterparse: Mean +- std dev: [py311_before] 143 ms +- 8 ms -> [py311_after] 137 ms +- 7 ms: 1.05x faster
xml_etree_generate: Mean +- std dev: [py311_before] 140 ms +- 4 ms -> [py311_after] 135 ms +- 4 ms: 1.03x faster
xml_etree_process: Mean +- std dev: [py311_before] 98.1 ms +- 2.7 ms -> [py311_after] 96.1 ms +- 3.1 ms: 1.02x faster

Benchmark hidden because not significant (3): pickle, unpickle, xml_etree_parse

Geometric mean: 1.02x faster

Benchmarks with tag 'startup'

python_startup: Mean +- std dev: [py311_before] 33.3 ms +- 3.4 ms -> [py311_after] 32.2 ms +- 2.8 ms: 1.04x faster

Benchmark hidden because not significant (1): python_startup_no_site

Geometric mean: 1.01x faster

Benchmarks with tag 'template'

django_template: Mean +- std dev: [py311_before] 58.8 ms +- 1.3 ms -> [py311_after] 56.0 ms +- 0.5 ms: 1.05x faster
genshi_xml: Mean +- std dev: [py311_before] 82.5 ms +- 2.1 ms -> [py311_after] 81.2 ms +- 2.5 ms: 1.02x faster
mako: Mean +- std dev: [py311_before] 18.5 ms +- 0.6 ms -> [py311_after] 18.0 ms +- 0.5 ms: 1.03x faster

Benchmark hidden because not significant (1): genshi_text

Geometric mean: 1.02x faster

All benchmarks

2to3: Mean +- std dev: [py311_before] 455 ms +- 7 ms -> [py311_after] 449 ms +- 10 ms: 1.01x faster
async_generators: Mean +- std dev: [py311_before] 546 ms +- 14 ms -> [py311_after] 536 ms +- 11 ms: 1.02x faster
async_tree_cpu_io_mixed: Mean +- std dev: [py311_before] 1.08 sec +- 0.05 sec -> [py311_after] 1.04 sec +- 0.05 sec: 1.04x faster
chameleon: Mean +- std dev: [py311_before] 12.1 ms +- 0.3 ms -> [py311_after] 11.9 ms +- 0.4 ms: 1.02x faster
bench_mp_pool: Mean +- std dev: [py311_before] 155 ms +- 8 ms -> [py311_after] 150 ms +- 4 ms: 1.04x faster
bench_thread_pool: Mean +- std dev: [py311_before] 1.64 ms +- 0.18 ms -> [py311_after] 1.57 ms +- 0.08 ms: 1.04x faster
coroutines: Mean +- std dev: [py311_before] 35.8 ms +- 0.3 ms -> [py311_after] 36.3 ms +- 0.2 ms: 1.01x slower
coverage: Mean +- std dev: [py311_before] 1.03 sec +- 0.02 sec -> [py311_after] 1.05 sec +- 0.01 sec: 1.01x slower
crypto_pyaes: Mean +- std dev: [py311_before] 116 ms +- 2 ms -> [py311_after] 114 ms +- 1 ms: 1.02x faster
deepcopy: Mean +- std dev: [py311_before] 574 us +- 11 us -> [py311_after] 553 us +- 4 us: 1.04x faster
deepcopy_reduce: Mean +- std dev: [py311_before] 4.99 us +- 0.08 us -> [py311_after] 4.77 us +- 0.05 us: 1.05x faster
deepcopy_memo: Mean +- std dev: [py311_before] 63.2 us +- 0.7 us -> [py311_after] 61.2 us +- 1.1 us: 1.03x faster
deltablue: Mean +- std dev: [py311_before] 7.17 ms +- 0.20 ms -> [py311_after] 6.71 ms +- 0.13 ms: 1.07x faster
django_template: Mean +- std dev: [py311_before] 58.8 ms +- 1.3 ms -> [py311_after] 56.0 ms +- 0.5 ms: 1.05x faster
docutils: Mean +- std dev: [py311_before] 3.42 sec +- 0.12 sec -> [py311_after] 3.33 sec +- 0.07 sec: 1.03x faster
fannkuch: Mean +- std dev: [py311_before] 600 ms +- 8 ms -> [py311_after] 578 ms +- 5 ms: 1.04x faster
float: Mean +- std dev: [py311_before] 136 ms +- 4 ms -> [py311_after] 133 ms +- 5 ms: 1.02x faster
generators: Mean +- std dev: [py311_before] 56.2 ms +- 1.1 ms -> [py311_after] 55.3 ms +- 0.9 ms: 1.02x faster
genshi_xml: Mean +- std dev: [py311_before] 82.5 ms +- 2.1 ms -> [py311_after] 81.2 ms +- 2.5 ms: 1.02x faster
hexiom: Mean +- std dev: [py311_before] 11.3 ms +- 0.1 ms -> [py311_after] 11.4 ms +- 0.1 ms: 1.01x slower
json_dumps: Mean +- std dev: [py311_before] 13.6 ms +- 0.1 ms -> [py311_after] 13.7 ms +- 0.2 ms: 1.01x slower
json_loads: Mean +- std dev: [py311_before] 38.7 us +- 1.0 us -> [py311_after] 38.3 us +- 0.6 us: 1.01x faster
logging_format: Mean +- std dev: [py311_before] 19.4 us +- 0.5 us -> [py311_after] 18.5 us +- 0.2 us: 1.05x faster
logging_silent: Mean +- std dev: [py311_before] 185 ns +- 3 ns -> [py311_after] 175 ns +- 2 ns: 1.06x faster
logging_simple: Mean +- std dev: [py311_before] 17.9 us +- 0.5 us -> [py311_after] 16.9 us +- 0.1 us: 1.06x faster
mako: Mean +- std dev: [py311_before] 18.5 ms +- 0.6 ms -> [py311_after] 18.0 ms +- 0.5 ms: 1.03x faster
meteor_contest: Mean +- std dev: [py311_before] 137 ms +- 2 ms -> [py311_after] 134 ms +- 3 ms: 1.02x faster
nbody: Mean +- std dev: [py311_before] 179 ms +- 3 ms -> [py311_after] 170 ms +- 2 ms: 1.06x faster
nqueens: Mean +- std dev: [py311_before] 137 ms +- 2 ms -> [py311_after] 129 ms +- 1 ms: 1.06x faster
pathlib: Mean +- std dev: [py311_before] 245 ms +- 6 ms -> [py311_after] 212 ms +- 3 ms: 1.16x faster
pickle_dict: Mean +- std dev: [py311_before] 37.0 us +- 0.7 us -> [py311_after] 36.4 us +- 0.8 us: 1.02x faster
pickle_list: Mean +- std dev: [py311_before] 5.95 us +- 0.11 us -> [py311_after] 5.89 us +- 0.06 us: 1.01x faster
pickle_pure_python: Mean +- std dev: [py311_before] 521 us +- 12 us -> [py311_after] 504 us +- 5 us: 1.03x faster
pprint_safe_repr: Mean +- std dev: [py311_before] 1.18 sec +- 0.02 sec -> [py311_after] 1.14 sec +- 0.02 sec: 1.03x faster
pprint_pformat: Mean +- std dev: [py311_before] 2.47 sec +- 0.04 sec -> [py311_after] 2.41 sec +- 0.05 sec: 1.02x faster
pyflate: Mean +- std dev: [py311_before] 769 ms +- 17 ms -> [py311_after] 748 ms +- 32 ms: 1.03x faster
python_startup: Mean +- std dev: [py311_before] 33.3 ms +- 3.4 ms -> [py311_after] 32.2 ms +- 2.8 ms: 1.04x faster
regex_compile: Mean +- std dev: [py311_before] 202 ms +- 1 ms -> [py311_after] 203 ms +- 4 ms: 1.01x slower
regex_dna: Mean +- std dev: [py311_before] 187 ms +- 5 ms -> [py311_after] 189 ms +- 4 ms: 1.01x slower
regex_effbot: Mean +- std dev: [py311_before] 3.31 ms +- 0.05 ms -> [py311_after] 3.27 ms +- 0.05 ms: 1.01x faster
regex_v8: Mean +- std dev: [py311_before] 28.2 ms +- 0.4 ms -> [py311_after] 27.6 ms +- 0.3 ms: 1.02x faster
richards: Mean +- std dev: [py311_before] 85.1 ms +- 1.1 ms -> [py311_after] 83.9 ms +- 1.8 ms: 1.01x faster
scimark_fft: Mean +- std dev: [py311_before] 476 ms +- 7 ms -> [py311_after] 464 ms +- 7 ms: 1.03x faster
scimark_lu: Mean +- std dev: [py311_before] 166 ms +- 3 ms -> [py311_after] 162 ms +- 3 ms: 1.03x faster
scimark_monte_carlo: Mean +- std dev: [py311_before] 117 ms +- 2 ms -> [py311_after] 118 ms +- 2 ms: 1.01x slower
scimark_sor: Mean +- std dev: [py311_before] 219 ms +- 4 ms -> [py311_after] 214 ms +- 3 ms: 1.02x faster
scimark_sparse_mat_mult: Mean +- std dev: [py311_before] 5.92 ms +- 0.08 ms -> [py311_after] 5.88 ms +- 0.10 ms: 1.01x faster
spectral_norm: Mean +- std dev: [py311_before] 175 ms +- 2 ms -> [py311_after] 169 ms +- 3 ms: 1.04x faster
sqlglot_transpile: Mean +- std dev: [py311_before] 2.59 ms +- 0.05 ms -> [py311_after] 2.49 ms +- 0.07 ms: 1.04x faster
sqlglot_optimize: Mean +- std dev: [py311_before] 78.7 ms +- 0.9 ms -> [py311_after] 75.9 ms +- 1.1 ms: 1.04x faster
sqlglot_normalize: Mean +- std dev: [py311_before] 169 ms +- 2 ms -> [py311_after] 159 ms +- 2 ms: 1.06x faster
sqlite_synth: Mean +- std dev: [py311_before] 3.87 us +- 0.07 us -> [py311_after] 3.80 us +- 0.04 us: 1.02x faster
sympy_expand: Mean +- std dev: [py311_before] 660 ms +- 5 ms -> [py311_after] 666 ms +- 12 ms: 1.01x slower
sympy_integrate: Mean +- std dev: [py311_before] 28.2 ms +- 1.0 ms -> [py311_after] 27.6 ms +- 0.7 ms: 1.02x faster
sympy_sum: Mean +- std dev: [py311_before] 239 ms +- 9 ms -> [py311_after] 233 ms +- 7 ms: 1.03x faster
sympy_str: Mean +- std dev: [py311_before] 414 ms +- 9 ms -> [py311_after] 408 ms +- 11 ms: 1.01x faster
telco: Mean +- std dev: [py311_before] 9.44 ms +- 0.13 ms -> [py311_after] 9.02 ms +- 0.22 ms: 1.05x faster
unpack_sequence: Mean +- std dev: [py311_before] 76.3 ns +- 1.2 ns -> [py311_after] 80.3 ns +- 1.2 ns: 1.05x slower
unpickle_list: Mean +- std dev: [py311_before] 5.63 us +- 0.04 us -> [py311_after] 5.50 us +- 0.08 us: 1.02x faster
unpickle_pure_python: Mean +- std dev: [py311_before] 400 us +- 11 us -> [py311_after] 367 us +- 7 us: 1.09x faster
xml_etree_iterparse: Mean +- std dev: [py311_before] 143 ms +- 8 ms -> [py311_after] 137 ms +- 7 ms: 1.05x faster
xml_etree_generate: Mean +- std dev: [py311_before] 140 ms +- 4 ms -> [py311_after] 135 ms +- 4 ms: 1.03x faster
xml_etree_process: Mean +- std dev: [py311_before] 98.1 ms +- 2.7 ms -> [py311_after] 96.1 ms +- 3.1 ms: 1.02x faster

Benchmark hidden because not significant (16): async_tree_none, async_tree_io, async_tree_memoization, chaos, genshi_text, go, html5lib, mdp, pickle, pidigits, python_startup_no_site, raytrace, sqlglot_parse, tornado_http, unpickle, xml_etree_parse

Geometric mean: 1.02x faster

[mdboom]

I ran this branch on the Faster CPython team's benchmarking infrastructure, and it came back as 1.00x faster. The 2% faster that @thatbirdguythatuknownot is within the noise we usually see. So this confirms that the change is "at least harmless, probably helpful".

[thatbirdguythatuknownot]

I'm probably going to also benchmark and compare different reduction factors if I have the time.

[arhadthedev]

Closing after #103564 (comment).