General optimisations for dict lookup/insert performance #145179

Activity

1. caje731

   added

   type-featureA feature request or enhancementA feature request or enhancement

   on Feb 24, 2026
2. caje731

   changed the title [-]General optimisations for dict lookup/insert[/-] [+]General optimisations for dict lookup/insert performance[/+] on Feb 24, 2026
3. caje731 commented on Feb 24, 2026

   

   caje731

   on Feb 24, 2026 · Hidden as resolved

   Author

   show commentMore actions
4. sergey-miryanov

   added

   interpreter-core(Objects, Python, Grammar, and Parser dirs)(Objects, Python, Grammar, and Parser dirs)

   performancePerformance or resource usagePerformance or resource usage

   on Feb 24, 2026
5. Siyet commented on Apr 12, 2026

   

   Siyet

   on Apr 12, 2026

   More actions

   I analyzed the proposals, looked at related issues/PRs and ran some benchmarks. Here is what I found.

   Related issues and PRs

   • Duplicated lookup on unicodekeys_lookup_unicode #104717 / PR gh-104717: Remove duplicated lookup from unicodekeys_lookup_unicode #104716 - @corona10 asked whether the duplication in unicodekeys_lookup_unicode was a bug. @methane confirmed: it is intentional manual loop unrolling on the hottest path in dictobject.c. PR was closed without merging.
   • PR gh-121266: Remove Py_ALWAYS_INLINE in dictobject.c #121493 - @vstinner removed Py_ALWAYS_INLINE from compare_unicode_generic(), compare_unicode_unicode(), compare_generic() - exactly the functions proposed for optimization here. Reason: these are callbacks for do_lookup, inlining is useless with indirect calls.
   • JIT optimize dict access with consts with known hash #146558 / PR gh-146558: optimize dict access with objects with known hash #146559 (merged) - @kumaraditya303 added JIT optimization for dict access with precomputed hashes for const keys. Speedup of +14-75% with JIT. This shows that the main lookup path gains are now coming through JIT rather than dictobject.c itself.
   • Unexplained performance slowdown on both official 3.13.6 and 3.14 regarding hash collisions - reproduced on dict[int, int] and set[int], cannot be reproduced when building Python locally #137636 - an apparent 5x dict lookup regression that turned out to be a difference between PGO and non-PGO builds. Confirms that PGO critically affects dict performance and benchmarks without PGO can be misleading.

   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-while

   Similar 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.