Skip to content

Commit 45552bd

Browse files
authored
Fold the hash chain walk into _md_update() (#1757)
<!-- Thank you for your contribution! --> ## What do these changes do? `_md_update_replace()`, the walk of the hash chain for each `update()` item, was a separate out-of-line function. The call, with eight arguments and the callee-saved register spills around it, cost about 25 instructions per item. Its loops now live in `_md_update()` itself, which goes on to add the key when the walk does not find it. `merge()` and `extend()` do not use this path. The pure-Python backend has no equivalent call and is unchanged. ## Are there changes in behavior for the user? No. ## Is it a substantial burden for the maintainers to support this? No; one function fewer. ## Related issue number Follow-up to #1755. ## Checklist - [x] I think the code is well written - [ ] Unit tests for the changes exist N/A, no behaviour change; covered by the existing update() tests - [x] Documentation reflects the changes - [ ] If you provide code modification, please add yourself to `CONTRIBUTORS.txt` N/A - [x] Add a new news fragment into the `CHANGES/` folder - [x] `make doc-spelling` passes and any new technical words are added to `docs/spelling_wordlist.txt` Drafted with Claude Code (Claude Opus 5.5); reviewed by @asvetlov. <details> <summary>Agent run details (optional, for reviewers)</summary> Callgrind, `PYTHONHASHSEED=0`, per call with a 100-item argument (N=120 minus N=20 runs), base cfd8ea2, CPython 3.14.7 and 3.14.7t: | case | GIL md / ci | FT md / ci | | --- | --- | --- | | update(dict), keys present | -10.2% / -9.3% | -8.0% / -7.0% | | update(list), keys present | -9.1% / -8.5% | -6.5% / -5.8% | | update(dict) into an empty multidict | -8.7% / -7.1% | -6.6% / -5.1% | | update(dict), new keys into 100 | -7.9% / -6.9% | -6.0% / -4.9% | | update(list) with duplicate keys | -6.9% / -6.2% | -5.1% / -4.3% | | update(multidict) | -2.9..-4.3% | -1.8..-4.0% | | merge(...) | 0.0% (-2.0% from a multidict) | 0.0..-0.4% | Also tried, and rejected: skipping the per-batch `updated` bitmap when the source cannot repeat a key (a same-class multidict without duplicates, no keywords). That made `update(multidict)` 2-5% cheaper, but every other source paid 1-4% more for the flag test. Tests: full suite passes on the C extension (3.14.7 GIL, 3.14.7t FT, 3.10.17) and on pure Python (`MULTIDICT_NO_EXTENSIONS=1 pytest --no-c-extensions` from a clean tree copy). `tools/check_inlining.py` passes on 3.14.7 and 3.14.7t. `make doc-spelling` passes. </details>
1 parent 84c5412 commit 45552bd

2 files changed

Lines changed: 28 additions & 37 deletions

File tree

‎CHANGES/1757.misc.rst‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
Merged the C extension's walk of the hash chain for each
2+
:meth:`~multidict.MultiDict.update` item into its caller, which saved a
3+
function call per item: an update needed 3% to 10% fewer instructions
4+
-- by :user:`asvetlov`.

‎multidict/_multilib/bulk_update.h‎

Lines changed: 24 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -74,14 +74,21 @@ _md_update_matched(MultiDictObject* md, uint8_t kind, entry_t* entry,
7474
return push_ret;
7575
}
7676

77-
/* _md_update()'s walk of the hash chain: 1 if the key was there, 0 if
78-
not, 2 if not but this batch has added it already, -1 on error. One
79-
loop per kind. */
80-
static inline int
81-
_md_update_replace(MultiDictObject* md, Py_hash_t hash, PyObject* identity,
82-
PyObject* key, PyObject* value, reflist_t* defer,
83-
update_marks_t* marks)
77+
/* Nothing here runs Python code or suspends the critical section: the
78+
* replaced key and value go to `defer`. One loop per kind. */
79+
static int
80+
_md_update(MultiDictObject* md, Py_hash_t hash, PyObject* identity,
81+
PyObject* key, PyObject* value, reflist_t* defer,
82+
update_marks_t* marks, bool fits)
8483
{
84+
assert(fits == md_key_fits(md, key, identity));
85+
if (kind_is_compact(md->keys->kind) && UNLIKELY(!fits) &&
86+
md_to_anystr(md) < 0) {
87+
return -1;
88+
}
89+
if (update_marks_sync(marks, md) < 0) {
90+
return -1;
91+
}
8592
bool ci = md->is_ci;
8693
bool found = false;
8794
bool added = false;
@@ -171,37 +178,17 @@ _md_update_replace(MultiDictObject* md, Py_hash_t hash, PyObject* identity,
171178
}
172179
}
173180
}
174-
return found ? 1 : added ? 2 : 0;
175-
}
176-
177-
/* Nothing here runs Python code or suspends the critical section: the
178-
* replaced key and value go to `defer`. */
179-
static int
180-
_md_update(MultiDictObject* md, Py_hash_t hash, PyObject* identity,
181-
PyObject* key, PyObject* value, reflist_t* defer,
182-
update_marks_t* marks, bool fits)
183-
{
184-
assert(fits == md_key_fits(md, key, identity));
185-
if (kind_is_compact(md->keys->kind) && UNLIKELY(!fits) &&
186-
md_to_anystr(md) < 0) {
187-
return -1;
188-
}
189-
if (update_marks_sync(marks, md) < 0) {
190-
return -1;
191-
}
192-
int found =
193-
_md_update_replace(md, hash, identity, key, value, defer, marks);
194-
if (found == 0 || found == 2) {
195-
return md_add_for_upd(md,
196-
hash,
197-
identity,
198-
key,
199-
value,
200-
marks,
201-
fits,
202-
found == 2 ? MD_SLOT_CHECK : MD_SLOT_FIND);
181+
if (found) {
182+
return 0;
203183
}
204-
return found < 0 ? -1 : 0;
184+
return md_add_for_upd(md,
185+
hash,
186+
identity,
187+
key,
188+
value,
189+
marks,
190+
fits,
191+
added ? MD_SLOT_CHECK : MD_SLOT_FIND);
205192
}
206193

207194
/* Whether md has `identity` from before the batch: the insert's `slot`

0 commit comments

Comments
 (0)