Do not track immutable tuples in PyTuple_Pack

[sergey-miryanov]

Feature or enhancement

Proposal:

When we use PyTuple_Pack all objects already well constructed. If we know that they immutable we can skip tracking it in GC, because GC will untrack them eventually.

I have a PR ready and benchmark results:

Geometric mean: 1.01x faster (Win11 x64, 11th Gen Intel(R) Core(TM) i5-11600K @ 3.90GHz, 48d0d0d)

All benchmarks:

+--------------------------+----------+------------------------+
| Benchmark                | main     | tuples                 |
+==========================+==========+========================+
| async_generators         | 435 ms   | 430 ms: 1.01x faster   |
+--------------------------+----------+------------------------+
| asyncio_tcp              | 750 ms   | 756 ms: 1.01x slower   |
+--------------------------+----------+------------------------+
| asyncio_tcp_ssl          | 1.91 sec | 1.92 sec: 1.01x slower |
+--------------------------+----------+------------------------+
| comprehensions           | 22.1 us  | 21.8 us: 1.01x faster  |
+--------------------------+----------+------------------------+
| bench_mp_pool            | 104 ms   | 103 ms: 1.01x faster   |
+--------------------------+----------+------------------------+
| bench_thread_pool        | 1.29 ms  | 1.27 ms: 1.01x faster  |
+--------------------------+----------+------------------------+
| coroutines               | 28.2 ms  | 27.7 ms: 1.02x faster  |
+--------------------------+----------+------------------------+
| coverage                 | 88.5 ms  | 86.3 ms: 1.02x faster  |
+--------------------------+----------+------------------------+
| crypto_pyaes             | 90.1 ms  | 86.7 ms: 1.04x faster  |
+--------------------------+----------+------------------------+
| deepcopy                 | 310 us   | 307 us: 1.01x faster   |
+--------------------------+----------+------------------------+
| deepcopy_memo            | 36.4 us  | 36.1 us: 1.01x faster  |
+--------------------------+----------+------------------------+
| deltablue                | 5.19 ms  | 4.85 ms: 1.07x faster  |
+--------------------------+----------+------------------------+
| django_template          | 45.5 ms  | 45.8 ms: 1.01x slower  |
+--------------------------+----------+------------------------+
| docutils                 | 2.47 sec | 2.45 sec: 1.01x faster |
+--------------------------+----------+------------------------+
| dulwich_log              | 86.2 ms  | 86.9 ms: 1.01x slower  |
+--------------------------+----------+------------------------+
| fannkuch                 | 449 ms   | 441 ms: 1.02x faster   |
+--------------------------+----------+------------------------+
| float                    | 85.3 ms  | 82.5 ms: 1.03x faster  |
+--------------------------+----------+------------------------+
| create_gc_cycles         | 1.17 ms  | 1.17 ms: 1.01x faster  |
+--------------------------+----------+------------------------+
| gc_traversal             | 2.97 ms  | 2.88 ms: 1.03x faster  |
+--------------------------+----------+------------------------+
| generators               | 43.0 ms  | 41.6 ms: 1.03x faster  |
+--------------------------+----------+------------------------+
| genshi_text              | 28.9 ms  | 28.7 ms: 1.01x faster  |
+--------------------------+----------+------------------------+
| go                       | 160 ms   | 153 ms: 1.04x faster   |
+--------------------------+----------+------------------------+
| hexiom                   | 8.39 ms  | 8.13 ms: 1.03x faster  |
+--------------------------+----------+------------------------+
| json_dumps               | 8.62 ms  | 8.69 ms: 1.01x slower  |
+--------------------------+----------+------------------------+
| logging_format           | 12.5 us  | 12.2 us: 1.02x faster  |
+--------------------------+----------+------------------------+
| logging_silent           | 139 ns   | 140 ns: 1.01x slower   |
+--------------------------+----------+------------------------+
| logging_simple           | 11.3 us  | 11.1 us: 1.01x faster  |
+--------------------------+----------+------------------------+
| mako                     | 14.2 ms  | 14.4 ms: 1.01x slower  |
+--------------------------+----------+------------------------+
| mdp                      | 1.47 sec | 1.50 sec: 1.02x slower |
+--------------------------+----------+------------------------+
| meteor_contest           | 104 ms   | 102 ms: 1.02x faster   |
+--------------------------+----------+------------------------+
| nbody                    | 114 ms   | 113 ms: 1.01x faster   |
+--------------------------+----------+------------------------+
| pickle_pure_python       | 439 us   | 436 us: 1.01x faster   |
+--------------------------+----------+------------------------+
| pprint_safe_repr         | 953 ms   | 916 ms: 1.04x faster   |
+--------------------------+----------+------------------------+
| pprint_pformat           | 1.95 sec | 1.88 sec: 1.04x faster |
+--------------------------+----------+------------------------+
| pyflate                  | 506 ms   | 492 ms: 1.03x faster   |
+--------------------------+----------+------------------------+
| python_startup           | 28.5 ms  | 27.4 ms: 1.04x faster  |
+--------------------------+----------+------------------------+
| python_startup_no_site   | 23.2 ms  | 22.2 ms: 1.05x faster  |
+--------------------------+----------+------------------------+
| raytrace                 | 361 ms   | 345 ms: 1.05x faster   |
+--------------------------+----------+------------------------+
| regex_compile            | 146 ms   | 146 ms: 1.01x faster   |
+--------------------------+----------+------------------------+
| regex_effbot             | 2.03 ms  | 2.02 ms: 1.01x faster  |
+--------------------------+----------+------------------------+
| regex_v8                 | 23.9 ms  | 22.7 ms: 1.06x faster  |
+--------------------------+----------+------------------------+
| richards                 | 66.1 ms  | 59.9 ms: 1.10x faster  |
+--------------------------+----------+------------------------+
| richards_super           | 71.6 ms  | 68.7 ms: 1.04x faster  |
+--------------------------+----------+------------------------+
| scimark_fft              | 300 ms   | 294 ms: 1.02x faster   |
+--------------------------+----------+------------------------+
| scimark_lu               | 135 ms   | 131 ms: 1.03x faster   |
+--------------------------+----------+------------------------+
| scimark_monte_carlo      | 83.3 ms  | 82.4 ms: 1.01x faster  |
+--------------------------+----------+------------------------+
| scimark_sor              | 157 ms   | 150 ms: 1.05x faster   |
+--------------------------+----------+------------------------+
| scimark_sparse_mat_mult  | 4.27 ms  | 4.35 ms: 1.02x slower  |
+--------------------------+----------+------------------------+
| spectral_norm            | 122 ms   | 118 ms: 1.03x faster   |
+--------------------------+----------+------------------------+
| sqlglot_optimize         | 60.7 ms  | 60.9 ms: 1.00x slower  |
+--------------------------+----------+------------------------+
| sympy_expand             | 501 ms   | 503 ms: 1.00x slower   |
+--------------------------+----------+------------------------+
| sympy_sum                | 143 ms   | 144 ms: 1.01x slower   |
+--------------------------+----------+------------------------+
| sympy_str                | 287 ms   | 292 ms: 1.02x slower   |
+--------------------------+----------+------------------------+
| telco                    | 7.26 ms  | 7.33 ms: 1.01x slower  |
+--------------------------+----------+------------------------+
| tomli_loads              | 2.23 sec | 2.25 sec: 1.01x slower |
+--------------------------+----------+------------------------+
| typing_runtime_protocols | 189 us   | 185 us: 1.02x faster   |
+--------------------------+----------+------------------------+
| unpack_sequence          | 65.4 ns  | 68.7 ns: 1.05x slower  |
+--------------------------+----------+------------------------+
| unpickle                 | 13.9 us  | 14.1 us: 1.01x slower  |
+--------------------------+----------+------------------------+
| unpickle_pure_python     | 303 us   | 300 us: 1.01x faster   |
+--------------------------+----------+------------------------+
| xml_etree_parse          | 130 ms   | 130 ms: 1.01x slower   |
+--------------------------+----------+------------------------+
| xml_etree_iterparse      | 107 ms   | 108 ms: 1.01x slower   |
+--------------------------+----------+------------------------+
| xml_etree_process        | 79.2 ms  | 78.6 ms: 1.01x faster  |
+--------------------------+----------+------------------------+
| Geometric mean           | (ref)    | 1.01x faster           |
+--------------------------+----------+------------------------+

Benchmark hidden because not significant (20): 2to3, chaos, deepcopy_reduce, genshi_xml, html5lib, json_loads, nqueens, pathlib, pickle, pickle_dict, pickle_list, pidigits, regex_dna, sqlglot_normalize, sqlglot_parse, sqlglot_transpile, sqlite_synth, sympy_integrate, unpickle_list, xml_etree_generate

It doesn't hurt performance, but can decrease number of objects in GC to check and untrack.

Has this already been discussed elsewhere?

This is a minor feature, which does not need previous discussion elsewhere

Links to previous discussion of this feature:

No response

Linked PRs

• GH-139389: Do not track immutable tuples in PyTuple_Pack #139390

[picnixz]

1.01 faster is not a realistic improvement IMO. In general, we want > 10% improvements. We should also have benchmarks on Linux machines with clang/gcc instead (and be sure that it's also using PGO+LTO).

It doesn't hurt performance, but can decrease number of objects in GC to check and untrack.

But is it really important if it doesn't change the performance? by how much are we changing the number of items to track? is it a lot? if not, I don't think it's necessary.

[sergey-miryanov]

But is it really important if it doesn't change the performance? by how much are we changing the number of items to track? is it a lot? if not, I don't think it's necessary.

I will try to calculate and compare.

We should also have benchmarks on Linux machines with clang/gcc instead (and be sure that it's also using PGO+LTO).

Unfortunately, I don't have such machine :(

[picnixz]

Also, could we have some micro-benchmark as well to check by how much PyTuple_Pack itself is affected? TiA.

[sergey-miryanov]

Also, could we have some micro-benchmark as well to check by how much PyTuple_Pack itself is affected? TiA.

Got it.

[Fidget-Spinner]

1.01 faster is not a realistic improvement IMO. In general, we want > 10% improvements. We should also have benchmarks on Linux machines with clang/gcc instead (and be sure that it's also using PGO+LTO).

1.01x faster is the geometric mean, not a single benchmark. It is completely realistic for pyperformance. For context, one good specialization in the specializing interpreter gives 2-3% geomean on pyperformance. 10% is very unrealistic. The entire specializing interpreter gave a 25% speedup in its first iteration.

Edit: I removed NOT in call caps and replaced it with not, because I didn't want to seem shouty. Sorry if I did sound like it unintentionally, meant to use bold not caps!

[picnixz]

1.01x faster is the geometric mean, NOT a single benchmark

Yes, but Victor usually asks for 10% improvements even for the geometric mean.

For context, one good specialization in the specializing interpreter gives 2-3% geomean on pyperformance

Ok, then in this case I'm fine with lowering the threshold. However, should we also consider losing 1% as important? For instance, unpacking sequences becomes 5% slower and unpickling became 1% slower as well, though other benchmarks seem fine.

I would still be interested in micro-benchmarks though.

[Fidget-Spinner]

1.01x faster is the geometric mean, NOT a single benchmark

Yes, but Victor usually asks for 10% improvements even for the geometric mean.

No my understanding is that he asks for 10% of geometric mean of microbenchmarks, which makes perfect sense. 10% on pyperformance geometric mean is different than 10% of microbenchmark geometric mean.

[picnixz]

Sorry I wasn't clear here. I wanted to explain why I thought that the 10% threshold should have applied, but I wasn't aware that we only reached 1-2% max improvements on macro benchmarks in general. So if you're ok with a 1% improvements overall but with some specific tasks being slower, then I'm also ok.

[Fidget-Spinner]

Sorry I wasn't clear here. I wanted to explain why I thought that the 10% threshold should have applied, but I wasn't aware that we only reached 1-2% max improvements on macro benchmarks in general. So if you're ok with a 1% improvements overall but with some specific tasks being slower, then I'm also ok.

To be fair, I'm not too sure 1% is a good threshold on normal pyperformance nowadays too. Some benchmarks are noisy and 1% is within the range of noise for some systems.

[serhiy-storchaka]

1% is within the noise range. I expect the difference (in one direction or another) to be several orders of magnitude smaller. Tuples creation is a small part of any code, and PyTuple_Pack() is a tiny part of it. The GC will untrack such tuples first time it encounter them, so roughly the same code will be executed in any case.

If there is a noticeable difference, there should be a microbenchmark that shows a significant (tens of percent) difference. Then you should show that such a case can actually happen in non-trivial amount of user code.

[sergey-miryanov]

There are numbers of how reduced count of untracked tuples in untrack_tuples:

cnt_main is for 48d0d0d
cnt_pack is for fbb7342
cnt_all is for 04f0f66

pack_ratio = 100.0 * (cnt_main - cnt_pack) / cnt_main
pack_all = 100.0 * (cnt_main - cnt_all) / cnt_main

Most of the work done in the generation 1, for pack it is about 1% reduce count, for all it varies from 5% to 8%.

Numbers are from pyperfomance benchmarks. Instrumentation for main made like this - https://github.com/python/cpython/pull/139390/files#diff-1c580282bd10a8157cc81dd4a4658d4bb47f75ea476cd433bc7435913b33eb77R137

gen	cnt_main	cnt_pack	cnt_all	pack_ratio	all_ratio
2	3	3	3	0.0	0.0
2	8	8	6	0.0	25.0
2	8	8	4	0.0	50.0
2	19	19	18	0.0	5.3
2	20	20	20	0.0	0.0
2	34	34	19	0.0	44.1
2	38	38	35	0.0	7.9
2	40	40	19	0.0	52.5
2	44	44	19	0.0	56.8
2	45	45	19	0.0	57.8
2	47	47	19	0.0	59.6
2	48	48	19	0.0	60.4
2	49	49	19	0.0	61.2
2	50	50	19	0.0	62.0
2	51	51	19	0.0	62.7
2	55	55	19	0.0	65.5
2	56	56	19	0.0	66.1
2	71	71	19	0.0	73.2
2	110	109	76	0.9	30.9
2	379	371	355	2.1	6.3
2	409	401	386	2.0	5.6
2	410	402	386	2.0	5.9
2	482	473	429	1.9	11.0
2	512	503	460	1.8	10.2
2	569	560	538	1.6	5.4
2	687	682	659	0.7	4.1
1	9587	9370	8943	2.3	6.7
1	9628	9411	9008	2.3	6.4
1	14911	14643	14075	1.8	5.6
1	18010	17699	17070	1.7	5.2
1	18775	18453	17799	1.7	5.2
1	23765	23417	22527	1.5	5.2
1	23896	23520	22464	1.6	6.0
1	24868	24484	18262	1.5	26.6
1	35545	35037	33672	1.4	5.3
1	43140	42566	40637	1.3	5.8
1	43198	42624	40673	1.3	5.8
1	43218	42644	40674	1.3	5.9
1	43219	42645	40674	1.3	5.9
1	43221	42647	40674	1.3	5.9
1	43223	42649	40674	1.3	5.9
1	43228	42654	40674	1.3	5.9
1	43233	42659	40674	1.3	5.9
1	43240	42666	40675	1.3	5.9
1	43243	42669	40674	1.3	5.9
1	43255	42681	40674	1.3	6.0
1	43256	42682	40675	1.3	6.0
1	43257	42683	40675	1.3	6.0
1	43276	42702	40676	1.3	6.0
1	43315	42741	40676	1.3	6.1
1	43340	42766	40766	1.3	5.9
1	47530	46954	43982	1.2	7.5
1	47573	46954	43982	1.3	7.5
1	48431	47855	44454	1.2	8.2