GeezerVison

Keep the existing path for very sparse tables (fewer than approximately 1/64 live entries), where scanning tombstones is less beneficial.

Could you benchmark the case where can_clone_sparse_dict() always returns true and compare the results?

I'm interested in whether this branch is really necessary. If the performance is comparable, there's no need to keep the existing code path. If there's a significant difference, I'd also like to reconsider the similar code in dictresize().

Update (2026-11-10): The results below were for the earlier for-loop implementation. After methane's suggestion, I tested a while loop that stops after the live entries, removed the 1/64 cutoff, and updated the PR. The new PGO/LTO comparison and conclusions are in this follow-up.

I tried making can_clone_sparse_dict() always return true and compared it with the current 1/64 threshold. The regular-build benchmark shows a clear regression for very sparse tables.

Some dict.copy() results (ns/op, averages of two measurement passes, lower is better):

The difference is small for less sparse cases, but the fallback is noticeably faster once almost all entries have been deleted. Both implementations passed the targeted dict tests, watcher tests, and the sparse-dict stress checks.

I used the same Ubuntu 24.04 runner for each comparison, with measurements in A–B–B–A order. The benchmark and workflow are available here: https://github.com/localzet/cpython/actions/runs/42595205328

The GCC PGO/LTO comparison has now completed, and it gave a different result. For example, with str keys and 1/100,000 live entries, the threshold build measured 50.1 μs/op while always-clone measured 32.9 μs/op. With int keys and 1,600/100,000 live entries, however, the threshold build measured 49.6 μs/op versus 70.0 μs/op for always-clone, even though both variants should take the clone path at that density. These differences indicate build/code-generation or measurement effects, so I don't think this experiment alone establishes the optimal cutoff. I'll leave the code unchanged while investigating with more controlled measurements.

The two configurations and raw logs are in the same workflow run linked above. I'll examine dictresize() separately, since its resize path has different constraints.

When the number of live entries is extremely small, performance is dominated by the code that skips empty entries. The loop in _PyDict_Next() is written as follows:

On the other hand, this PR uses the following code:

for (Py_ssize_t i = 0; i < oldkeys->dk_nentries; i++) {
    if (src[i].me_value != NULL) {

If we changed the for loop condition to n < used and skipped empty entries in an inner loop using while (src[i].me_value == NULL) i++;, couldn't we achieve the same performance as _PyDict_Next()?

You're using Codex, right? Codex is good at investigating this kind of low-level implementation detail, so please have it thoroughly investigate whether we really need to introduce another copy path just for this.

Thanks for the suggestion. The inner while made a significant difference.

I compared three variants: the original for loop with the 1/64 cutoff, while with that cutoff, and while without it. Both the regular build and GCC PGO/LTO runs favor the last variant in the very sparse cases. For example, with PGO/LTO, dict.copy() went from 68.2 μs to 37.0 μs for 1,000 string keys out of 100,000, and from 79.7 μs to 38.8 μs for integer keys. At 1/100,000 live entries, the improvements were 51.0 → 34.5 μs (str) and 63.3 → 38.0 μs (int). A denser 30,000/100,000 str case was slightly slower (233.6 → 240.9 μs).

Stopping after ma_used entries also avoids scanning trailing deleted entries. I measured deletions from the front, back, middle, and random positions, as well as both key types.

I've updated this PR to use the inner while and removed can_clone_sparse_dict() and the extra fallback. The new version passed debug, free-threaded, reference-leak, and ASan tests, plus additional patterned and randomized stress checks.

Benchmarks: https://github.com/localzet/cpython/actions/runs/42801499895 and https://github.com/localzet/cpython/actions/runs/42803337022
Verification: https://github.com/localzet/cpython/actions/runs/42806793734

And yes, Codex helped prepare the benchmark variants and tests. I reviewed the changes and checked the results before updating the PR.

I looked for standard-library paths where deletions can leave a sparse dict that is subsequently copied:

• linecache.checkcache(None) snapshots cache.copy().keys(), while stale cache entries are removed with cache.pop().
• weakref.WeakValueDictionary.copy() snapshots self.data.copy(), while weakref callbacks remove dead entries from that underlying dict.

I added a standalone benchmark on a separate fork branch (no change to this PR) that exercises these existing methods after constructing dictionaries with many deleted entries. I compared the PR base (4575fb9) with the current implementation (eea9266) in regular GCC builds on the same Ubuntu runner, in A–B–B–A order. The numbers below are averages of the two pass medians, in µs/op:

In both standard-library examples, the underlying dict.copy() itself improves more than the full method, as expected. The smaller full-method differences, especially in WeakValueDictionary.copy(), need more repetitions before drawing strong conclusions. Dense-dict timings were broadly comparable in this run.

These are constructed cache states, not measurements of how frequently real applications enter them. They establish concrete call sites where this path is possible, but do not by themselves settle the concern about the maintenance cost of the extra C code.

Benchmark script · raw workflow results

I ran a follow-up GCC PGO/LTO comparison and instrumented a few official pyperformance workloads to get a better sense of how frequently the new path is used.

With PGO/LTO, the speedups in constructed sparse cases are still clear (mean of two medians per variant, same runner, A–B–B–A):

PGO/LTO workflow

I also added temporary counters to a separate research build of the base commit. They record (a) calls reaching copy_lock_held_untracked() and (b) opportunities to clone a non-empty combined source directly into an empty combined destination in dict_dict_merge(). The two groups can overlap and should not be added together.

In four completed pyperformance workloads (logging, json_dumps, sqlalchemy_declarative, xml_etree), I observed 0 sparse sources among 289,175 direct-copy calls and 0 among 896,558 merge-clone candidates. The django_template benchmark could not run on this development interpreter because it encountered a missing distutils module, so I excluded it. The counts also include benchmark setup and worker initialization; they are not a general frequency estimate for Python applications.

Instrumented pyperformance run

So the speedup is reproducible when a dict is sparse, but I still don't have evidence that this is common in representative workloads. I understand the concern about adding code to a rarely used path. I'll leave the PR unchanged rather than expand it further without a stronger use case.

• Please compare the performance against main, rather than against an earlier version of this PR.
• The test coverage is excessive. Please keep only the tests necessary for future maintenance.

Thanks! I've reduced the tests in 3595cf8 to the existing test_copy_noncompact() and test_clone() cases, covering both key layouts, insertion order, cached hashes and the clone event.

For the new comparison, both builds use the same main commit (020c5f3), with the PR applied to only one of them. I'm measuring dict.copy() and dict(d) across dense and sparse tables, including different deletion patterns, in regular and GCC PGO/LTO builds.

The run is here: https://github.com/localzet/cpython/actions/runs/43236839567