GeezerVison is showing github.com — Optimising sparse dict copy · Issue #161524 · python/cpython
Optimising sparse dict copy #161524DescriptionFeature 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
Linked PRs
Activitydpdani commented on Nov 9, 2026 I'm quite dubious about this issue because, if I understand correctly, it pertains to a very niche case:
- create a dictionary and write items into it;
- delete items from the dictionary;
- make a copy of it.
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. johng commented on Nov 10, 2026 ContributorAuthor More actions Did some more research to re world examples, and unable to justify it
MetadataMetadataDevelopmentNo branches or pull requestsIssue actions
|