Feature or enhancement
Proposal
Inserting a str key probes the dict index table twice: the lookup decides
whether the key is present, then find_empty_slot() walks the same probe
sequence to find the slot to insert into. Deleting probes twice as well
(lookup + lookdict_index()).
I'd like the first probe to report the slot it ends on, so the
insert/delete path can reuse it:
- on a hit: the slot that refers to the entry (what lookdict_index()
returns);
- on a miss: the slot find_empty_slot() would return (the first dummy
in the GIL build, the empty slot in the free-threaded build).
Scope
Only exact str keys in all-unicode tables can use it. That comparison
(pointer equality, cached hash, memcmp) cannot execute Python code, therefore
the dict cannot be resized or mutated while the probe is running. For
other keys __eq__ can run arbitrary code and invalidate the slot, so
they keep today's two-probe behaviour. Readers pass a NULL slot and
generate the same code as before.
Numbers
Prototype, Objects/dictobject.c only. Per-metric subprocesses, medians
of 11 runs. the dict code built with -O3 -DNDEBUG, otherwise a
free-threaded debug build.
| operation |
before |
after |
| del d[k], str |
47.7 ns |
41.4 ns (−13%) |
| del d[k], str, many dummies |
48.6 ns |
43.0 ns (−12%) |
| d.pop(k), str |
65.0 ns |
59.9 ns (−7.7%) |
| dict.fromkeys, str |
42.5 ns |
38.1 ns (−10%) |
| dict comprehension, str |
66.5 ns |
60.9 ns (−8.4%) |
| d[k] = v, existing str key |
60.0 ns |
54.2 ns (−9.6%) |
| k in d, str (control) |
43.6 ns |
44.4 ns (+1.9%) |
| del / pop / d[k] = v, int |
36.1 / 52.4 / 46.5 |
36.3 / 53.0 / 46.8 (≤1.2%) |
The reader path is instruction-for-instruction identical to main at -O3.
test_dict, test_dictviews, test_dictcomps and
test_capi.test_watchers pass on a free-threaded debug build.
Status
This is @eendebakpt's dict-insert-single-probe-v7 branch, rebased and
reshaped (thanks!).
Has this already been discussed elsewhere?
I have already discussed this feature proposal on Discourse
Links to previous discussion of this feature:
https://discuss.python.org/t/optimization-for-insertdict/109348
Linked PRs
Feature or enhancement
Proposal
Inserting a str key probes the dict index table twice: the lookup decides
whether the key is present, then find_empty_slot() walks the same probe
sequence to find the slot to insert into. Deleting probes twice as well
(lookup + lookdict_index()).
I'd like the first probe to report the slot it ends on, so the
insert/delete path can reuse it:
returns);
in the GIL build, the empty slot in the free-threaded build).
Scope
Only exact str keys in all-unicode tables can use it. That comparison
(pointer equality, cached hash, memcmp) cannot execute Python code, therefore
the dict cannot be resized or mutated while the probe is running. For
other keys __eq__ can run arbitrary code and invalidate the slot, so
they keep today's two-probe behaviour. Readers pass a NULL slot and
generate the same code as before.
Numbers
Prototype, Objects/dictobject.c only. Per-metric subprocesses, medians
of 11 runs. the dict code built with -O3 -DNDEBUG, otherwise a
free-threaded debug build.
The reader path is instruction-for-instruction identical to main at -O3.
test_dict, test_dictviews, test_dictcomps and
test_capi.test_watchers pass on a free-threaded debug build.
Status
This is @eendebakpt's dict-insert-single-probe-v7 branch, rebased and
reshaped (thanks!).
Has this already been discussed elsewhere?
I have already discussed this feature proposal on Discourse
Links to previous discussion of this feature:
https://discuss.python.org/t/optimization-for-insertdict/109348
Linked PRs