Repository navigation
Optimising sparse dict copy #161524
Description
Feature or enhancement
Currently when cloning a dict and it's sparse (less than 30% used keys) we fallback to standard un optimised dict_merge even though it would have passed the other optimising enabling checks.
(1) type(mp) doesn't override tp_iter; and
(2) 'mp' is not a split-dict; and
(3) if 'mp' is non-compact ('del' operation does not resize dicts),
do fast-copy only if it has at most 1/3 non-used keys.
A "fast" sparse dict copy would involve allocating a new dict of the source sparse size and then iterating source and copying the key, values where they are set rather than going through the generic insertion code path.
From some benchmarks this can lead up to a 4x speedup, although for more common cases this is at 2x.
| Case | main | main + sparse_copy | Speedup | Peak memory (both builds) |
|---|---|---|---|---|
copy(), compact, 4 keys |
26 ns | 26 ns | 1.0x | - |
copy(), compact, 300 str keys |
350 ns | 353 ns | 1.0x | - |
copy(), sparse, 4 live of 10 |
64 ns | 32 ns | 2.0x | - |
dict(d), sparse, 4 live of 10 |
56 ns | 33 ns | 1.7x | - |
{**d}, sparse, 4 live of 10 |
55 ns | 33 ns | 1.7x | - |
copy(), sparse, 50 live of 1000 |
644 ns | 351 ns | 1.8x | - |
copy(), sparse, 300 live of 1000, str keys |
3.55 µs | 0.85 µs | 4.2x | - |
dict(d), sparse, 300 live of 1000, str keys |
3.53 µs | 0.86 µs | 4.1x | - |
copy(), 300k live of 1M, int keys |
2.5 ms | 1.4 ms | 1.8x | 10.0 MiB |
dict(d), 300k live of 1M, int keys |
2.5 ms | 1.4 ms | 1.8x | 10.0 MiB |
{**d}, 300k live of 1M, int keys |
2.5 ms | 1.4 ms | 1.8x | 10.0 MiB |
copy(), 300k live of 1M, str keys |
5.5 ms | 2.7 ms | 2.0x | 7.3 MiB |
dict(d), 300k live of 1M, str keys |
5.5 ms | 2.6 ms | 2.1x | 7.3 MiB |
{**d}, 300k live of 1M, str keys |
5.6 ms | 2.6 ms | 2.2x | 7.3 MiB |
copy(), 1M emptied to 10, int keys |
248 µs | 246 µs | 1.0x | 0.3 KiB |
copy(), 1M emptied to 10, str keys |
235 µs | 234 µs | 1.0x | 0.2-0.3 KiB |
The downside of this would be more complexity in the copy code and more maintenance. Raising the issue to discuss if optimising this code path would bring a meaningful benefit.
Proof of concept:
Details
/* Like clone_combined_dict_keys(), but skip deleted entries and size the
new table for orig->ma_used items. */
static PyDictKeysObject *
clone_compact_dict_keys(PyDictObject *orig)
{
assert(orig->ma_values == NULL);
if (!PyFrozenDict_Check(orig)) {
ASSERT_DICT_LOCKED(orig);
}
PyDictKeysObject *okeys = orig->ma_keys;
Py_ssize_t n = orig->ma_used;
int unicode = DK_IS_UNICODE(okeys);
PyDictKeysObject *keys = new_keys_object(estimate_log2_keysize(n), unicode);
if (keys == NULL) {
return NULL;
}
if (unicode) {
PyDictUnicodeEntry *ep = DK_UNICODE_ENTRIES(okeys);
PyDictUnicodeEntry *newentries = DK_UNICODE_ENTRIES(keys);
for (Py_ssize_t i = 0; i < n; i++, ep++) {
while (ep->me_value == NULL) {
ep++;
}
newentries[i].me_key = Py_NewRef(ep->me_key);
newentries[i].me_value = Py_NewRef(ep->me_value);
}
build_indices_unicode(keys, newentries, n);
}
else {
PyDictKeyEntry *ep = DK_ENTRIES(okeys);
PyDictKeyEntry *newentries = DK_ENTRIES(keys);
for (Py_ssize_t i = 0; i < n; i++, ep++) {
while (ep->me_value == NULL) {
ep++;
}
newentries[i].me_key = Py_NewRef(ep->me_key);
newentries[i].me_hash = ep->me_hash;
newentries[i].me_value = Py_NewRef(ep->me_value);
}
build_indices_generic(keys, newentries, n);
}
keys->dk_usable -= n;
keys->dk_nentries = n;
return keys;
}
/* dict_dict_merge(), empty target: */
if (mp->ma_values == NULL && other->ma_values == NULL) {
_PyDict_NotifyEvent(PyDict_EVENT_CLONED, mp, (PyObject *)other, NULL);
PyDictKeysObject *keys;
if (other->ma_used == okeys->dk_nentries &&
(DK_LOG_SIZE(okeys) == PyDict_LOG_MINSIZE ||
USABLE_FRACTION(DK_SIZE(okeys)/2) < other->ma_used)) {
keys = clone_combined_dict_keys(other);
}
else {
keys = clone_compact_dict_keys(other);
}
}
/* copy_lock_held_untracked(): */
if (Py_TYPE(mp)->tp_iter == dict_iter) {
assert(mp->ma_values == NULL);
PyDictKeysObject *keys;
if (mp->ma_used >= (mp->ma_keys->dk_nentries * 2) / 3) {
keys = clone_combined_dict_keys(mp);
}
else {
keys = clone_compact_dict_keys(mp);
}
}
Has this already been discussed elsewhere?
No response given
Links to previous discussion of this feature:
No response
Activity
pythongh-161524: Research compact copying for sparse dictionaries
pythongh-161524: Cover sparse dict edge cases and reference lifetimes
pythongh-161524: Add dense and extremely sparse benchmark cases
pythongh-161524: Benchmark non-debug builds against fixed baseline
pythongh-161524: Avoid compact cloning for extremely sparse dicts
pythongh-161524: Benchmark sparse-copy crossover
pythongh-161524: Stress sparse dict copy and allocation failures
pythongh-161524: Cover frozendict construction from sparse tables
pythongh-161524: Add reference leak and ASan checks
pythongh-161524: Benchmark sparse dict copy with PGO and ThinLTO
pythongh-161524: Use GCC for portable PGO/LTO comparison
pythongh-161524: Fetch benchmark baseline and scope optimized CI
pythongh-161524: Lower sparse-copy threshold after benchmark comparison
pythongh-161524: Check sparse dict clone watcher notifications
pythongh-161524: Cover sparse dict clone watcher events
pythongh-161524: Speed up copying sparse dictionaries
dpdani commentedon Nov 9, 2026
I'm quite dubious about this issue because, if I understand correctly, it pertains to a very niche case:
The last time I measured the number of dictionary item deletes on pyperformance, they occurred in a very small amount of 1.2% of the total operations on dicts. While the measurements may be out of date, I don't think new endeavours will find something significantly different. Furthermore, this optimisation requires that the dictionary on which the deletes were performed to be later copied, decreasing the likelihood that this code path is hit even further.
Because of this, I don't believe this change is worth pursuing. That is, I don't see a clear justification for maintaining the extra code and tests.
That being said, if you know of a real workload where this case is hit very frequently, then there may be a justification for the extra cost.
pythongh-161524: Preserve noncompact copy test rationale
pythongh-161524: Speed up copying sparse dictionaries
pythongh-161524: Cover extremely sparse dictionary clone events
pythongh-161524: Speed up copying sparse dictionaries
johng commentedon Nov 10, 2026
Did some more research to re world examples, and unable to justify it
pythongh-161524: Preserve fast-copy rationale for sparse dictionaries
pythongh-161524: Preserve dict clone assertions after dispatch review
pythongh-161524: Simplify sparse dict copy tests