General optimisations for dict lookup/insert performance

[caje731]

Proposal:

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

[caje731]

Could someone help me set the right tags/labels here? For lack of permissions I can't do so myself. Thanks!

[Siyet]

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.