gh-158898: Optimize dict insertion and deletion by avoiding a second probe by hetaozdh · Pull Request #158899 · python/cpython

hetaozdh · 2026-10-06T07:41:24Z

This is based on @eendebakpt's dict-insert-single-probe-v7 prototype. I rebased and reshaped it on top of main and finished the remaining pieces. Thanks to Pieter for the prototype and for the measurements that started this.

The problem

do_lookup() walks the index table's probe sequence to find a key. After that walk, the insert and delete paths walked the same sequence a second time: find_empty_slot() to find a slot for a new key, and lookdict_index() to find the slot that refers to a deleted entry. The lookup only returned the entry index, so the slot in the index table had to be recomputed.

The change

do_lookup() now takes an optional Py_ssize_t *hashpos and reports the slot its probe ends on:

if the key is found, the slot that refers to its entry, i.e. what lookdict_index() computes;
if the key is not found, the slot where the key would be inserted: the first dummy slot in the GIL build, or the first empty slot in the free-threaded build. do_lookup() keeps track of the first dummy slot as freeslot for the GIL build.

dict_lookup_pos() is the writer-side entry point: it reports hashpos for the case described below and sets it to -1 otherwise. insertdict(), dict_setdefault_ref_lock_held(), _PyDict_DelItem_KnownHash_LockHeld() and _PyDict_Pop_KnownHash() use it and pass hashpos to insert_combined_dict() / delitem_common(), which then reuse it instead of probing again. Readers pass NULL.

insert_combined_dict() invalidates hashpos before resizing, and debug builds assert that a reused hashpos matches a second probe.

Passing NULL on the reader paths lets the compiler eliminate the slot-tracking bookkeeping, so ordinary lookups do not pay for this optimization.

Why only exact `str` keys

Reusing hashpos is only valid if the index table cannot change between the lookup and the write. This is guaranteed for exact str keys because the comparison cannot invoke arbitrary Python code.

For an exact str key in a combined all-unicode table (DICT_KEYS_UNICODE; the dict switches to DICT_KEYS_GENERAL on the first non-str key), the key comparison is pointer equality, cached hash comparison and unicode_eq() (a raw string-data comparison). None of that can run Python code, so the dict cannot be mutated, resized or cleared while the probe is running.

PyUnicode_CheckExact is required because subclasses may override comparison behavior and can therefore execute Python code. The table kind also guarantees that the stored keys are exact str.

For every other key, compare_generic() / compare_unicode_generic() call PyObject_RichCompareBool(), so __eq__ can insert into, delete from, clear() or resize the same dict in the middle of the probe. A hashpos observed before that is no longer valid, so those keys keep probing again after the lookup.

Two implementation notes. The slot-reporting probe is a separate function (unicodekeys_lookup_unicode_pos()) and find_empty_slot() is not force-inlined, so insertdict() and pop() do not grow; the reader functions unicodekeys_lookup_unicode() and unicodekeys_lookup_unicode_threadsafe() generate the same code as before.

Split (shared) keys tables are handled as well: delitem_common() only computes hashpos for combined tables (deleting from a split table never touches the index table), and insert_split_key() reuses the slot from the lookup it already performs while holding the keys mutex.

Affected operations

del d[k], d.pop(k), d[k] = v for absent and existing string keys, d.setdefault(k, v), dict.fromkeys(), dict comprehensions and d.update() (they go through the same insert path), plus new attribute insertion through split-key dictionaries.

Lookups (d[k], k in d, d.get()), iteration and resizing (dictresize() / build_indices_*()) are unchanged. int, mixed and otherwise generic keys keep the previous two-probe behaviour.

Benchmarks

Method: branch vs main (85c03d4). Every metric runs in its own process, 11 alternating repetitions, median reported.

Objects/dictobject.c is compiled with -O3 -DNDEBUG and linked into an otherwise --with-pydebug --disable-gil build, so the dict code is optimized like a release build while the surrounding interpreter is still a debug build. This is not a PGO build.

k in d is included as a control whose code is identical to main; it measured +0.4%, which is worth keeping in mind for the smaller numbers below.

Unicode keys (exact `str`, combined all-unicode table)

operation	main	branch	change
`del d[k]`	46.8 ns	41.1 ns	−12.2%
`del d[k]`, many dummy slots	47.7 ns	41.7 ns	−12.5%
`d.pop(k)`	62.1 ns	58.3 ns	−6.2%
`d[k] = v`, existing key	57.6 ns	51.2 ns	−11.3%
`d[k] = v`, absent key	66.3 ns	61.3 ns	−7.4%
`d.setdefault(k, v)`, absent	89.3 ns	84.1 ns	−5.9%
`d.setdefault(k, v)`, present	70.5 ns	70.7 ns	+0.2%
`dict.fromkeys()`	41.4 ns/key	37.6 ns/key	−9.2%
dict comprehension	65.8 ns/key	59.7 ns/key	−9.3%
`k in d` (control, unchanged code)	43.7 ns	43.9 ns	+0.4%

int keys (GENERAL table)

operation	main	branch	change
`del d[k]`	35.4 ns	35.4 ns	+0.1%
`d.pop(k)`	51.6 ns	52.3 ns	+1.4%
`d[k] = v`, existing key	45.1 ns	45.7 ns	+1.4%
`d[k] = v`, absent key	56.4 ns	56.1 ns	−0.6%
`d.setdefault(k, v)`, absent	79.1 ns	75.6 ns	−4.4%
`dict.fromkeys()`	25.4 ns/key	24.6 ns/key	−3.0%
dict comprehension	47.8 ns	47.3 ns	−1.1%
`k in d` (control)	31.1 ns	31.1 ns	0.0%

mixed `str` + `int` keys (GENERAL table)

operation	main	branch	change
`del d[k]`	46.4 ns	45.7 ns	−1.5%
`d.pop(k)`	60.4 ns	61.1 ns	+1.2%
`d[k] = v`, existing key	62.0 ns	64.2 ns	+3.4%
`d[k] = v`, absent key	76.0 ns	76.1 ns	+0.1%
`d.setdefault(k, v)`, absent	101.5 ns	100.8 ns	−0.7%
`dict.fromkeys()`	38.2 ns/key	37.7 ns/key	−1.5%
`k in d` (control)	37.8 ns	37.5 ns	−0.8%

The string-key insert/delete paths are consistently faster in this build. The int and mixed paths change little overall, with individual results of a few percent in both directions; they still probe twice and only see the extra hashpos argument and the dispatch in dict_lookup_pos().

These numbers are not enough to judge the impact on real workloads. The next step is to measure the effect on PGO builds with realistic workloads.

Tests

test_dict, test_dictviews, test_dictcomps: pass (171 tests) on a
--with-pydebug --disable-gil build, with the new debug assert enabled.
test_capi.test_watchers: pass (60 tests).
A randomized differential test against main (str/int/mixed keys, hash
collisions, instance attributes / split keys, deletion, popitem(),
clear()) gives identical results.
Compared with main, the generated -O3 assembly for
unicodekeys_lookup_unicode() and
unicodekeys_lookup_unicode_threadsafe() is identical.

Issue: Optimize dict insertion and deletion by avoiding a second probe #158898

… key Inserting a str key probed the index table twice: once in the lookup to see whether the key is present, again in find_empty_slot() to find the slot for it. Deleting one probed again in lookdict_index(). do_lookup() can now report the slot its probe ends on: the slot of the entry if the key is found, otherwise the slot find_empty_slot() would return. Only exact str keys in all-unicode tables use it, because that comparison cannot run Python code and mutate the dict during the probe. Readers pass NULL and generate the same code as before. The writer-side probe is a separate function and find_empty_slot() stays out of line, so keys that cannot use it (int, mixed) do not slow down.

Entries whose value is NULL are never reached through the index table and every scan of the entry array skips them, so their hash is never read. Drop the stores in delitem_common() and popitem().

_PyDict_Pop_KnownHash() returns the value, so it had to incref it before delitem_common() dropped the entry's reference. Transfer that reference instead; the two callers that discard the value decref it.

The probe made _PyDict_Pop_KnownHash() big enough that inlining it into dict.pop() is left to the compiler's size thresholds. Move the body to a static always-inline helper and keep the exported function as a wrapper, so the hot caller inlines it either way.

A split table shares its keys with every instance of a type, so deleting never touches the index table and never needs the slot lookdict_index() computes. Move that lookup into the combined branch of delitem_common(). insert_split_key() already looks the key up under the keys mutex, so the slot that lookup reports is still the one find_empty_slot() would return. Reuse it: one index table traversal less per new shared key (three to two in the free-threaded build, two to one otherwise).

methane · 2026-10-06T08:24:40Z

Even a performance improvement of more than 10% in a microbenchmark does not necessarily translate into a meaningful speedup in real-world applications.

This PR adds extra code to a highly performance-critical part of Python, so we need to consider not only maintainability, but also test whether the accumulated small overhead on ordinary namespace lookups has any negative impact.

For that reason, I'm -1 on this change for now. If you believe this change provides a meaningful performance benefit, could you run pyperformance on a physical machine and see whether it shows any measurable difference?

eendebakpt and others added 6 commits October 6, 2026 02:01

Do not overwrite the hash of a deleted dict entry

398d2fe

Entries whose value is NULL are never reached through the index table and every scan of the entry array skips them, so their hash is never read. Drop the stores in delitem_common() and popitem().

Let delitem_common() transfer the value reference to its caller

ae05c80

_PyDict_Pop_KnownHash() returns the value, so it had to incref it before delitem_common() dropped the entry's reference. Transfer that reference instead; the two callers that discard the value decref it.

pythongh-158898: Add a NEWS entry

9a16aba

hetaozdh requested review from markshannon and methane as code owners October 6, 2026 07:41

bedevere-app Bot added the awaiting review label Oct 6, 2026

hetaozdh changed the title ~~Optimize dict insertion and deletion by avoiding a second probe~~ gh-158898: Optimize dict insertion and deletion by avoiding a second probe Oct 6, 2026

bedevere-app Bot added the type-feature A feature request or enhancement label Oct 6, 2026

bedevere-app Bot mentioned this pull request Oct 6, 2026

Optimize dict insertion and deletion by avoiding a second probe #158898

Open

Navigation Menu

Uh oh!

gh-158898: Optimize dict insertion and deletion by avoiding a second probe - #158899

gh-158898: Optimize dict insertion and deletion by avoiding a second probe#158899
hetaozdh wants to merge 6 commits into
python:mainfrom
hetaozdh:dict-single-probe

hetaozdh commented Oct 6, 2026 •

edited by bedevere-app Bot

Loading

Uh oh!

methane commented Oct 6, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Uh oh!

Conversation

hetaozdh commented Oct 6, 2026 • edited by bedevere-app Bot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

The problem

The change

Why only exact str keys

Affected operations

Benchmarks

Unicode keys (exact str, combined all-unicode table)

int keys (GENERAL table)

mixed str + int keys (GENERAL table)

Tests

Uh oh!

methane commented Oct 6, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

hetaozdh commented Oct 6, 2026 •

edited by bedevere-app Bot

Loading

Why only exact `str` keys

Unicode keys (exact `str`, combined all-unicode table)

mixed `str` + `int` keys (GENERAL table)