Skip to content

Commit b37f07c

Browse files
authored
Allocate deferred decrefs in fixed-size blocks (#1501)
<!-- Thank you for your contribution! --> ## What do these changes do? Replaces the storage of `md_deferred_decref_t` (free-threaded build only) with a chain of fixed-size blocks. Each block holds 511 object pointers (4 KiB with the pointer) plus a `next` pointer. The first block is inline in the struct and is always the tail of the chain; when it fills, a heap block is prepended, so every block behind the current one is full and `md_deferred_decref_release()` needs no per-block counts. This drops the old 8-slot inline array and its doubling `PyMem_Realloc`/`memcpy` growth path. The GIL build and the pure-Python implementation do not use this structure and are unaffected. ## Are there changes in behavior for the user? No. ## Is it a substantial burden for the maintainers to support this? No; the init/push/release API is unchanged and the implementation is shorter than the previous one. ## 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 (N/A, internal only) - [ ] 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); reviewed by @asvetlov. <details> <summary>Agent run details (optional, for reviewers)</summary> New test `test_replace_many_duplicates_releases_all` replaces 3000 duplicates via `__setitem__` and `update()` (about 9000 deferred decrefs, many heap blocks) and checks via weakrefs that every old value is released. Temporarily breaking the release walk to skip full blocks makes it fail on the C extension. - 3.14t, `MULTIDICT_DEBUG_BUILD=1`: 2066 passed, 18 skipped - 3.14t, debug + `MULTIDICT_ASAN_BUILD=1` (`-k "not test_leak"`, no `PYTHONMALLOC=malloc` since free-threaded CPython rejects it): 2055 passed, no sanitizer reports - 3.13 C extension: 2063 passed; `--no-c-extensions`: 1039 passed - `make doc-spelling`, pre-commit: pass - Benchmarks not compared locally. </details>
1 parent 563f667 commit b37f07c

3 files changed

Lines changed: 64 additions & 31 deletions

File tree

‎CHANGES/1501.misc.rst‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
Changed the free-threaded build's deferred decref buffer, used by
2+
``update()`` and ``__setitem__()``, to a chain of fixed-size blocks
3+
with a large inline first block instead of a small inline array that
4+
was reallocated on growth -- by :user:`asvetlov`.

‎multidict/_multilib/hashtable.h‎

Lines changed: 34 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -1015,47 +1015,43 @@ md_add(MultiDictObject* md, PyObject* key, PyObject* value)
10151015
buffer, and only releasing it once the caller has left its critical
10161016
section, means nothing can suspend the critical section while it's
10171017
held, so no other thread can ever observe an in-progress mutation.
1018-
Sized like md_readonly_finder_t's visited buffer, for the same
1019-
reason: the common case (0-1 replaced entries per call) fits inline,
1020-
pathological cases spill to the allocator. */
1021-
#define MD_DEFERRED_DECREF_INLINE 8
1018+
Storage is a list of fixed-size blocks, newest first: the inline
1019+
block (4 KiB on the stack) is always the last one and covers any
1020+
realistic call; each overflow prepends a heap block, so every block
1021+
past `current` is full. Self-referential: never copy after init. */
1022+
#define MD_DEFERRED_DECREF_BLOCK 511
1023+
1024+
typedef struct _md_deferred_decref_block {
1025+
PyObject* items[MD_DEFERRED_DECREF_BLOCK];
1026+
struct _md_deferred_decref_block* next;
1027+
} md_deferred_decref_block_t;
10221028

10231029
typedef struct _md_deferred_decref {
1024-
PyObject* inline_buf[MD_DEFERRED_DECREF_INLINE];
1025-
PyObject** buf;
1030+
md_deferred_decref_block_t* current;
10261031
Py_ssize_t count;
1027-
Py_ssize_t capacity;
1032+
md_deferred_decref_block_t inline_block;
10281033
} md_deferred_decref_t;
10291034

10301035
static inline void
10311036
md_deferred_decref_init(md_deferred_decref_t* defer)
10321037
{
1033-
defer->buf = defer->inline_buf;
1038+
defer->inline_block.next = NULL;
1039+
defer->current = &defer->inline_block;
10341040
defer->count = 0;
1035-
defer->capacity = MD_DEFERRED_DECREF_INLINE;
10361041
}
10371042

10381043
HT_COLD static int
10391044
_md_deferred_decref_grow(md_deferred_decref_t* defer)
10401045
{
1041-
Py_ssize_t new_capacity = defer->capacity * 2;
1042-
size_t new_size = (size_t)new_capacity * sizeof(PyObject*);
1043-
PyObject** new_buf;
1044-
if (defer->buf == defer->inline_buf) {
1045-
new_buf = PyMem_Malloc(new_size);
1046-
if (new_buf != NULL) {
1047-
memcpy(
1048-
new_buf, defer->buf, (size_t)defer->count * sizeof(PyObject*));
1049-
}
1050-
} else {
1051-
new_buf = PyMem_Realloc(defer->buf, new_size);
1052-
}
1053-
if (new_buf == NULL) {
1046+
md_deferred_decref_block_t* block =
1047+
PyMem_Malloc(sizeof(md_deferred_decref_block_t));
1048+
if (block == NULL) {
10541049
PyErr_NoMemory();
10551050
return -1;
10561051
}
1057-
defer->buf = new_buf;
1058-
defer->capacity = new_capacity;
1052+
block->next = defer->current;
1053+
defer->current = block;
1054+
defer->count = 0;
10591055
return 0;
10601056
}
10611057

@@ -1073,24 +1069,31 @@ md_deferred_decref_push(md_deferred_decref_t* defer, PyObject* obj)
10731069
if (obj == NULL) {
10741070
return 0;
10751071
}
1076-
if (HT_UNLIKELY(defer->count == defer->capacity)) {
1072+
if (HT_UNLIKELY(defer->count == MD_DEFERRED_DECREF_BLOCK)) {
10771073
if (_md_deferred_decref_grow(defer) < 0) {
10781074
Py_DECREF(obj);
10791075
return -1;
10801076
}
10811077
}
1082-
defer->buf[defer->count++] = obj;
1078+
defer->current->items[defer->count++] = obj;
10831079
return 0;
10841080
}
10851081

10861082
static inline void
10871083
md_deferred_decref_release(md_deferred_decref_t* defer)
10881084
{
1089-
for (Py_ssize_t i = 0; i < defer->count; i++) {
1090-
Py_DECREF(defer->buf[i]);
1091-
}
1092-
if (defer->buf != defer->inline_buf) {
1093-
PyMem_Free(defer->buf);
1085+
md_deferred_decref_block_t* block = defer->current;
1086+
Py_ssize_t n = defer->count;
1087+
while (block != NULL) {
1088+
for (Py_ssize_t i = 0; i < n; i++) {
1089+
Py_DECREF(block->items[i]);
1090+
}
1091+
md_deferred_decref_block_t* next = block->next;
1092+
if (block != &defer->inline_block) {
1093+
PyMem_Free(block);
1094+
}
1095+
block = next;
1096+
n = MD_DEFERRED_DECREF_BLOCK;
10941097
}
10951098
}
10961099
#endif

‎tests/test_multidict.py‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2321,6 +2321,32 @@ def update_worker(n: int) -> None:
23212321
assert len(d.getall("k")) == 1
23222322

23232323

2324+
@pytest.mark.parametrize("op", ["setitem", "update"])
2325+
def test_replace_many_duplicates_releases_all(
2326+
case_sensitive_multidict_class: type[MultiDict[object]], op: str
2327+
) -> None:
2328+
"""Enough replaced duplicates to overflow the free-threaded build's
2329+
deferred-decref buffer into several heap blocks; every old value
2330+
must still be released."""
2331+
2332+
class Tracked:
2333+
pass
2334+
2335+
values = [Tracked() for _ in range(3000)]
2336+
refs = [weakref.ref(v) for v in values]
2337+
d = case_sensitive_multidict_class([("k", v) for v in values])
2338+
del values
2339+
2340+
if op == "setitem":
2341+
d["k"] = "v"
2342+
else:
2343+
d.update(k="v")
2344+
2345+
assert list(d.items()) == [("k", "v")]
2346+
gc.collect()
2347+
assert all(r() is None for r in refs)
2348+
2349+
23242350
@pytest.mark.c_extension
23252351
def test_to_dict_vs_lock_free_reads_thread_safety() -> None:
23262352
"""Concurrent to_dict() alongside lock-free contains()/get() on the

0 commit comments

Comments
 (0)