Repository navigation
gh-158898: Optimize dict insertion and deletion by avoiding a second probe - #158899
hetaozdh wants to merge 6 commits into
Conversation
Sorry, something went wrong.
… 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).
|
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? |
Sorry, something went wrong.
|
@methane I think you are right. I ran pyperformance, but it did not show any significant improvement. I think this is because dictionary insertion and deletion are not particularly hot operations in representative workloads. |
Sorry, something went wrong.
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:
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)
int keys (GENERAL table)
mixed str + int keys (GENERAL table)
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
--with-pydebug --disable-gil build, with the new debug assert enabled.
collisions, instance attributes / split keys, deletion, popitem(),
clear()) gives identical results.
unicodekeys_lookup_unicode() and
unicodekeys_lookup_unicode_threadsafe() is identical.