GeezerVison is showing github.com — General optimisations for dict lookup/insert performance · Issue #145179 · python/cpython
General optimisations for dict lookup/insert performance #145179DescriptionProposal:
There's room for tiny refactorings in the Objects/dictobject.c that may allow speedups, for example via better CPU cache behavior, compiler hints, cheap checks & fast exits for common cases. In my guess-timation, they may bring about upto 10% overall lookup/insert performance gains. That's more of an un-scientific intuition at best right now, but I'm laying some ideas out here:
-
compare_unicode_unicode(): can benefit from pointer-equality and branch prediction, and reducing unnecessary function calls
-
compare_generic(): can use early rejections on hash-mismatch, avoiding RichCompareBool calls
-
unicodekeys_lookup_unicode(): pointer-equality for the common case can precede do_lookup which today is invoked everytime for all cases
-
find_empty_slot(): early termination / separate path for first iteration can speed up insertions, especially for lightly-populated dicts
-
build_indices_generic / build_indices_unicode (): breaking out the first-probe success case may speed up dict resize operations
I welcome feedback on how to raise this proposal differently, but otherwise I'd like to work on these ideas and quantify them. I feel modern CPUs have deep pipelines and these optimizations may help us avoid some cache-thrashing. These changes are purely performance oriented and don't change functionality / API / ABI and should be thread-safe too.
Has this already been discussed elsewhere?
This is a minor feature, which does not need previous discussion elsewhere
Links to previous discussion of this feature:
No response Activitychanged the title [-]General optimisations for dict lookup/insert[/-] [+]General optimisations for dict lookup/insert performance[/+] on Feb 24, 2026caje731 commented on Feb 24, 2026 Author show commentMore actions Siyet commented on Apr 12, 2026 I analyzed the proposals, looked at related issues/PRs and ran some benchmarks. Here is what I found.
Related issues and PRs
Points 1-3: Lookup path
These optimizations are already present in the current code:
compare_unicode_unicode() already has pointer-equality as the first check (line 1139: ep_key == key), followed by hash comparison + unicode_eq().compare_generic() already has identity check (line 1158: ep->me_key == key) and hash-mismatch early reject (line 1161: ep->me_hash == hash) before RichCompareBool.unicodekeys_lookup_unicode() calls do_lookup() which is Py_ALWAYS_INLINE and already has manual loop unrolling (see Duplicated lookup on unicodekeys_lookup_unicode #104717 above). Adding a pointer-equality check before do_lookup would duplicate the first iteration of the unrolled loop.
Adding __builtin_expect branch hints to compare_unicode_unicode showed mixed results in my testing - slightly faster for hits, but slower for misses (the hint penalizes the miss path).
Points 4-5: Insert/resize path
These are more interesting. I tested extracting an explicit fast path from find_empty_slot() and build_indices_unicode/generic():
// find_empty_slot - before:
Py_ssize_t ix = dictkeys_get_index(keys, i);
for (size_t perturb = hash; is_unusable_slot(ix);) { ... }
// find_empty_slot - after:
Py_ssize_t ix = dictkeys_get_index(keys, i);
if (__builtin_expect(!is_unusable_slot(ix), 1)) {
return i;
}
// slow path with do-whileSimilar pattern for build_indices_* - extract first-probe check with continue before the inner perturb loop.
Non-PGO build results (Ubuntu 24.04, GCC 13.3, x86_64, taskset single core, 100 rounds x 100k iters):
| Benchmark |
Baseline |
Patched |
Change |
| str insert 64 keys |
0.1216s |
0.1141s |
-6.2% |
| str insert 512 keys |
1.1343s |
1.0244s |
-9.7% |
| int insert 512 keys |
0.8794s |
0.8576s |
-2.5% |
| dict.fromkeys(str, 256) |
0.4096s |
0.3776s |
-7.8% |
| dict.fromkeys(int, 256) |
0.3639s |
0.3244s |
-10.9% |
| dict.update 64+64 keys |
0.1106s |
0.1017s |
-8.1% |
| dict.copy 1024 keys |
0.1806s |
0.1768s |
-2.1% |
However, with PGO (--enable-optimizations, full rebuild), the picture changes signficantly:
| Benchmark |
PGO Base |
PGO Patched |
Change |
| str insert 512 keys |
0.8582s |
0.8425s |
-1.8% |
| int insert 512 keys |
0.8766s |
0.8151s |
-7.0% |
| dict.fromkeys(str, 256) |
0.3022s |
0.3057s |
+1.2% |
| dict.fromkeys(int, 256) |
0.3090s |
0.2830s |
-8.4% |
| dict.update 64+64 keys |
0.0984s |
0.0961s |
-2.3% |
PGO largely eliminates the benefit for string key opeartions (which dominate in the PGO training workload). Int key operations still show ~7-8% improvement since PGO covers those paths less thoroughly.
Summary
- Points 1-3 are already implemented in the current codebase. The
do_lookup loop unrolling is intentional (Duplicated lookup on unicodekeys_lookup_unicode #104717). Removing Py_ALWAYS_INLINE from compare functions was a deliberate decision (PR gh-121266: Remove Py_ALWAYS_INLINE in dictobject.c #121493).
- Points 4-5 (
find_empty_slot + build_indices fast paths) show real improvement on insert/resize, especially without PGO.
- Since official CPython releases use PGO and string keys are the most common dict key type, the practical impact on real-world code is narrower than "up to 10%". For int-heavy workloads the improvement is genuine though.
MetadataMetadataDevelopmentNo branches or pull requestsIssue actions
|