According the benchmark below,frozendict[key] lookup scales way better with this change: up to33x faster.

Benchmark results:

Benchmark hidden because not significant (1): int keys

Benchmark results compared to the regular build (ref):

Python built in release mode,gcc -O3 (without PGO, LTO, or CPU isolation).

Benchmark run on my Fedora 43 laptop which has 12 threads (6 CPU cores).

The string benchmark has really bad scaling because the strings aren't interned so we have reference count contention, plus some other things means that we also fall back to the locking code path.

Most dicts (and presumably frozendicts) use string literals as keys, which are interned and immortalized and avoid this problem.

You can see this if you update the benchmark:

frozendict_str_keys=frozendict({'0':0,'1':1,'2':2,'3':3,'4':4,'5':5,'6':6,'7':7,'8':8,'9':9})

On my machine, I'm not seeing an improvement with this PR for string literals keys or ints. In fact, it's slightly worse, which is surprising. (Maybe something weird with branch predictor behavior?)

main (671a953)

...........int keys: Mean +- std dev: 6.24 ms +- 0.20 ms...........str keys: Mean +- std dev: 6.52 ms +- 0.24 ms

PR + frozendict_str_keys literals

...........int keys: Mean +- std dev: 6.59 ms +- 0.33 ms...........str keys: Mean +- std dev: 6.74 ms +- 0.26 ms