Skip to content

Commit cfd8ea2

Browse files
authored
Reserve room for update() and merge() only when keys are added (#1755)
<!-- Thank you for your contribution! --> ## What do these changes do? `update()` and `merge()` reserved room for every item of their argument before the batch, so an update of keys already present rebuilt the table on every call, about 15% of its cost. Like `dict.update()`, they now grow up front only a table that could not hold the argument even empty, or one with holes from deletions (a rebuild inside the batch would have to keep them). Otherwise the first added key makes room for the whole batch: `update_marks_t.reserve` carries the size, and the add path tests `usable <= reserve`, which folds the pending check into the existing full-table test. A rebuild during a batch now takes the compacting path when the table has no holes, since compaction then keeps every index. The pure-Python backend got the same sizing, so `sys.getsizeof()` still agrees between the two. ## Are there changes in behavior for the user? No, apart from a smaller table after an update of keys that were already present. ## Is it a substantial burden for the maintainers to support this? No; it is a sizing rule in `md_reserve_batch()` plus one field in `update_marks_t`. ## Related issue number N/A ## Checklist - [x] I think the code is well written - [x] Unit tests for the changes exist - [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 fb828e3, CPython 3.14.7 and 3.14.7t: | case | GIL md / ci | FT md / ci | | --- | --- | --- | | update(dict), keys present | -16.6% / -21.4% | -15.6% / -21.2% | | update(list), keys present | -15.2% / -19.9% | -13.1% / -18.1% | | update(multidict), keys present | -17.8% / -25.0% | -15.3% / -23.1% | | merge(dict), keys present | -23.6% / -28.1% | -24.8% / -29.4% | | update/merge into an empty multidict | +0.2..+0.4% | +0.3% | | update/merge of 100 new keys into 100 | +0.1..+0.6% | +0.5..+0.6% | | update with duplicate keys | +0.4..+0.9% | +0.6..+0.7% | The adding paths pay about 1 instruction per add for the folded reserve check. Tests: full suite passes on the C extension (3.14.7 GIL, 3.14.7t FT, 3.10.17, 3.14.7t debug build) and on pure Python (`MULTIDICT_NO_EXTENSIONS=1 pytest --no-c-extensions` from a clean tree copy). `test_update_of_present_keys_keeps_the_table` fails on the base. `tools/check_inlining.py` passes on 3.14.7 and 3.14.7t. `make doc-spelling` passes. </details>
1 parent fb828e3 commit cfd8ea2

7 files changed

Lines changed: 120 additions & 23 deletions

File tree

‎CHANGES/1755.misc.rst‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
Stopped :meth:`~multidict.MultiDict.update` and
2+
:meth:`~multidict.MultiDict.merge` from growing the table up front when it
3+
could hold the argument even empty, as :meth:`dict.update` does; the first
4+
added key makes the room instead. An update of keys already present needed
5+
13% to 29% fewer instructions -- by :user:`asvetlov`.

‎multidict/_multidict.c‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -649,17 +649,17 @@ _multidict_bulk_locked(MultiDictObject* self, UpdateOp op, bool reinit,
649649
int ret;
650650
bool from_self = source == BULK_FROM_SEQ && other != NULL;
651651
if (op != Extend) {
652-
ret = md_reserve_batch(self, size, kwds != NULL);
653-
update_marks_init(marks, self);
652+
ret = md_reserve_batch(self, size, kwds != NULL, true);
653+
update_marks_init(marks, self, size);
654654
md_watch_record_simple(self, MultiDict_EVENT_BATCH_BEGIN);
655655
} else {
656656
md_watch_record_simple(self, MultiDict_EVENT_BATCH_BEGIN);
657657
if (!reinit) {
658-
ret = md_reserve_batch(self, size, kwds != NULL);
658+
ret = md_reserve_batch(self, size, kwds != NULL, false);
659659
} else if (from_self) {
660660
// re-init from itself: md_init() would drop the source
661661
assert(kwds != NULL);
662-
ret = md_reserve_batch(self, PyDict_GET_SIZE(kwds), true);
662+
ret = md_reserve_batch(self, PyDict_GET_SIZE(kwds), true, false);
663663
} else {
664664
ret = md_init(
665665
self,

‎multidict/_multidict_py.py‎

Lines changed: 21 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1390,7 +1390,7 @@ def popitem(self) -> tuple[str, _V]:
13901390
def update(self, arg: MDArg[_V] = None, /, **kwargs: _V) -> None:
13911391
"""Update the dictionary, overwriting existing keys."""
13921392
it = self._parse_args(arg, kwargs)
1393-
self._reserve(cast(int, next(it)))
1393+
reserve = self._reserve_batch(cast(int, next(it)))
13941394
# The entries this call wrote and those it doomed, by id(): kept
13951395
# out of the table, they survive whatever runs between items. They
13961396
# and `replaced` also hold the dropped pairs until the call ends.
@@ -1399,7 +1399,7 @@ def update(self, arg: MDArg[_V] = None, /, **kwargs: _V) -> None:
13991399
replaced: list[tuple[str, _V]] = []
14001400
try:
14011401
self._update_items(
1402-
cast(Iterator[_Entry[_V]], it), updated, deleted, replaced
1402+
cast(Iterator[_Entry[_V]], it), updated, deleted, replaced, reserve
14031403
)
14041404
finally:
14051405
self._post_update(deleted)
@@ -1410,6 +1410,7 @@ def _update_items(
14101410
updated: dict[int, _Entry[_V]],
14111411
deleted: dict[int, tuple[_Entry[_V], _V]],
14121412
replaced: list[tuple[str, _V]],
1413+
reserve: int,
14131414
) -> None:
14141415
for entry in items:
14151416
found = False
@@ -1431,6 +1432,9 @@ def _update_items(
14311432
# with what it holds now: a write since is kept
14321433
deleted[eid] = (e, e.value)
14331434
if not found:
1435+
if reserve:
1436+
self._reserve(reserve)
1437+
reserve = 0
14341438
self._add_with_hash(entry)
14351439
updated[id(entry)] = entry
14361440

@@ -1456,13 +1460,13 @@ def _post_update(self, deleted: dict[int, tuple[_Entry[_V], _V]]) -> None:
14561460
def merge(self, arg: MDArg[_V] = None, /, **kwargs: _V) -> None:
14571461
"""Merge into the dictionary, adding non-existing keys."""
14581462
it = self._parse_args(arg, kwargs)
1459-
self._reserve(cast(int, next(it)))
1463+
reserve = self._reserve_batch(cast(int, next(it)))
14601464
try:
1461-
self._merge_items(cast(Iterator[_Entry[_V]], it))
1465+
self._merge_items(cast(Iterator[_Entry[_V]], it), reserve)
14621466
finally:
14631467
self._incr_version()
14641468

1465-
def _merge_items(self, items: Iterator[_Entry[_V]]) -> None:
1469+
def _merge_items(self, items: Iterator[_Entry[_V]], reserve: int) -> None:
14661470
# See update()
14671471
added: dict[int, _Entry[_V]] = {}
14681472
for entry in items:
@@ -1471,6 +1475,9 @@ def _merge_items(self, items: Iterator[_Entry[_V]]) -> None:
14711475
if e.identity == identity and id(e) not in added:
14721476
break
14731477
else:
1478+
if reserve:
1479+
self._reserve(reserve)
1480+
reserve = 0
14741481
self._add_with_hash(entry)
14751482
added[id(entry)] = entry
14761483

@@ -1490,6 +1497,15 @@ def _reserve(self, extra: int) -> None:
14901497
if self._keys.usable < extra:
14911498
self._resize(estimate_log2_keysize(self._used + extra))
14921499

1500+
def _reserve_batch(self, extra: int) -> int:
1501+
# update() and merge() often find their keys there already: see
1502+
# md_reserve_batch(). Returns the room their first add makes.
1503+
keys = self._keys
1504+
n = len(keys.entries)
1505+
if n != self._used or n + keys.usable < extra:
1506+
self._reserve(extra)
1507+
return extra
1508+
14931509
def _resize(self, log2_newsize: int) -> None:
14941510
oldkeys = self._keys
14951511
newentries = self._used

‎multidict/_multilib/bulk_update.h‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -521,7 +521,8 @@ md_update_from_ht(MultiDictObject* md, MultiDictObject* other, UpdateOp op,
521521
// callers handle md itself: md_extend_self(), or a no-op
522522
assert(md != other);
523523

524-
if (md_reserve(md, other->used) < 0) {
524+
// update() and merge() reserved as md_reserve_batch() does for them
525+
if (op == Extend && md_reserve(md, other->used) < 0) {
525526
return -1;
526527
}
527528

‎multidict/_multilib/hashtable.h‎

Lines changed: 38 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -567,7 +567,8 @@ _md_publish_compacted(MultiDictObject* md, htkeys_t* oldkeys,
567567
static int
568568
_md_rebuild(MultiDictObject* md, uint8_t log2_newsize)
569569
{
570-
if (UNLIKELY(md->batches != 0)) {
570+
// without holes, compacting keeps every index anyway
571+
if (UNLIKELY(md->batches != 0) && md->keys->nentries != md->used) {
571572
return _md_rebuild_keeping_indices(md, log2_newsize);
572573
}
573574
if (!htkeys_size_fits(log2_newsize)) {
@@ -669,16 +670,27 @@ _md_rebuild_to_anystr(MultiDictObject* md, uint8_t log2_newsize)
669670
/* md_reserve() for extend(), update() or merge(), before their batch
670671
starts. Keyword names are plain str, which never fit a CIMultiDict's
671672
compact table, so with any the table is moved while it grows; moved
672-
later, it cost update(istr_items, **kwargs) a second copy, 18%. */
673+
later, it cost update(istr_items, **kwargs) a second copy, 18%.
674+
675+
update() and merge() often find their keys there already, so, like
676+
dict.update(), they grow only a table that could not hold `extra_size`
677+
entries even empty. Any other growth waits for the batch's first add,
678+
which then makes room for them all, unless deletions left holes: those
679+
the batch would have to keep. */
673680
static int
674-
md_reserve_batch(MultiDictObject* md, Py_ssize_t extra_size, bool kwargs)
681+
md_reserve_batch(MultiDictObject* md, Py_ssize_t extra_size, bool kwargs,
682+
bool overlap)
675683
{
676684
if (UNLIKELY(kwargs) && md->is_ci && kind_is_compact(md->keys->kind) &&
677685
md->used > 0 && md->batches == 0 &&
678686
extra_size <= (PY_SSIZE_T_MAX - 1) / 3 - md->used) {
679687
return _md_rebuild_to_anystr(
680688
md, estimate_log2_keysize(extra_size + md->used));
681689
}
690+
if (overlap && md->keys->nentries == md->used &&
691+
md->keys->nentries + md->keys->usable >= extra_size) {
692+
return 0;
693+
}
682694
return md_reserve(md, extra_size);
683695
}
684696

@@ -1140,21 +1152,37 @@ md_add_with_hash(MultiDictObject* md, Py_hash_t hash, PyObject* identity,
11401152
return 0;
11411153
}
11421154

1155+
/* Room for a batch's add: on the first add that is short of the room
1156+
update_marks_init() asked for, all of it. */
1157+
static int
1158+
_md_grow_for_upd(MultiDictObject* md, update_marks_t* marks)
1159+
{
1160+
Py_ssize_t extra = marks->reserve;
1161+
marks->reserve = 0;
1162+
if (extra > 0 && md_reserve(md, extra) < 0) {
1163+
return -1;
1164+
}
1165+
// md_reserve() ignores an extra too large to be real
1166+
htkeys_t* keys = md->keys;
1167+
if ((keys->usable <= 0 || keys == &empty_htkeys) &&
1168+
_md_resize_for_add(md) < 0) {
1169+
return -1;
1170+
}
1171+
return update_marks_sync(marks, md);
1172+
}
1173+
11431174
static int
11441175
_md_add_for_upd_steal_refs(MultiDictObject* md, Py_hash_t hash,
11451176
PyObject* identity, PyObject* key, PyObject* value,
11461177
update_marks_t* marks, bool fits, Py_ssize_t slot)
11471178
{
11481179
htkeys_t* keys = md->keys;
1149-
if (keys->usable <= 0 || keys == &empty_htkeys) {
1150-
/* Need to resize. */
1151-
if (_md_resize_for_add(md) < 0) {
1152-
return -1;
1153-
}
1154-
keys = md->keys; // updated by resizing
1155-
if (update_marks_sync(marks, md) < 0) {
1180+
// a reserve still pending is no more than the room left
1181+
if (keys->usable <= marks->reserve || keys == &empty_htkeys) {
1182+
if (_md_grow_for_upd(md, marks) < 0) {
11561183
return -1;
11571184
}
1185+
keys = md->keys;
11581186
}
11591187
if (bitmap_set(&marks->updated, keys->nentries) < 0) {
11601188
return -1;

‎multidict/_multilib/update_marks.h‎

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -53,6 +53,7 @@ typedef struct _update_marks {
5353
doomed_entry_t* doomed;
5454
Py_ssize_t ndoomed;
5555
Py_ssize_t doomed_capacity;
56+
Py_ssize_t reserve; // room the first add makes; see md_reserve_batch()
5657
uint32_t layout_gen;
5758
} update_marks_t;
5859

@@ -62,17 +63,18 @@ _md_entries_capacity(const htkeys_t* keys)
6263
return keys->nentries + keys->usable;
6364
}
6465

65-
/* Starts a batch; the caller holds md's critical section until the
66-
matching update_marks_end(). */
66+
/* Starts a batch of `size` items; the caller holds md's critical section
67+
until the matching update_marks_end(). */
6768
static void
68-
update_marks_init(update_marks_t* marks, MultiDictObject* md)
69+
update_marks_init(update_marks_t* marks, MultiDictObject* md, Py_ssize_t size)
6970
{
7071
Py_ssize_t capacity = _md_entries_capacity(md->keys);
7172
bitmap_init(&marks->updated, md->keys, capacity);
7273
bitmap_init(&marks->deleted, md->keys, capacity);
7374
marks->doomed = NULL;
7475
marks->ndoomed = 0;
7576
marks->doomed_capacity = 0;
77+
marks->reserve = size;
7678
marks->layout_gen = md->layout_gen;
7779
assert(md->batches < UINT16_MAX);
7880
md->batches++;

‎tests/test_update.py‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -330,6 +330,51 @@ def test_update_marks_outgrow_the_table(
330330
assert list(d.items()) == [("a", 1), ("a", 2)] + items[1:-1]
331331

332332

333+
_SOURCES: dict[str, Callable[[list[tuple[str, int]]], object]] = {
334+
"dict": dict,
335+
"list": list,
336+
"md": MultiDict,
337+
}
338+
339+
340+
@pytest.mark.skipif(
341+
sys.implementation.name == "pypy",
342+
reason="getsizeof() is not implemented on PyPy",
343+
)
344+
@pytest.mark.parametrize("op", ["update", "merge"])
345+
@pytest.mark.parametrize("source", list(_SOURCES))
346+
def test_update_of_present_keys_keeps_the_table(
347+
any_multidict_class: _MD_Classes, op: str, source: str
348+
) -> None:
349+
# As in dict.update(), a table that could hold the argument even empty
350+
# does not grow up front: its keys may all be there already.
351+
old = [(f"k{i}", i) for i in range(100)]
352+
new = [(f"k{i}", -i) for i in range(100)]
353+
d = any_multidict_class(old)
354+
size = sys.getsizeof(d)
355+
getattr(d, op)(_SOURCES[source](new))
356+
assert sys.getsizeof(d) == size
357+
assert list(d.items()) == (new if op == "update" else old)
358+
359+
360+
@pytest.mark.skipif(
361+
sys.implementation.name == "pypy",
362+
reason="getsizeof() is not implemented on PyPy",
363+
)
364+
@pytest.mark.parametrize("op", ["update", "merge"])
365+
@pytest.mark.parametrize("source", list(_SOURCES))
366+
def test_update_of_new_keys_makes_room_for_all(
367+
any_multidict_class: _MD_Classes, op: str, source: str
368+
) -> None:
369+
# The first add makes the room the up-front check left out.
370+
old = [(f"k{i}", i) for i in range(100)]
371+
new = [("k0", 0)] + [(f"n{i}", i) for i in range(99)]
372+
d = any_multidict_class(old)
373+
getattr(d, op)(_SOURCES[source](new))
374+
assert list(d.items()) == old + new[1:]
375+
assert sys.getsizeof(d) == sys.getsizeof(any_multidict_class(old + new[1:]))
376+
377+
333378
@pytest.mark.parametrize("nested", ["update", "setitem", "merge", "read"])
334379
def test_update_keeps_what_code_between_items_wrote(
335380
any_multidict_class: type[MultiDict[object]], nested: str

0 commit comments

Comments
 (0)