aio-libs / multidict / 35963992961

87%

push

github

Pool small hash tables in the module state (#1539)

<!-- Thank you for your contribution! -->

## What do these changes do?

`htkeys_new()` and `htkeys_free()` carried a standing TODO to do what
CPython does for `PyDictKeysObject`. They now check a bounded
per-size-class pool held in the module state, which every multidict
reaches through its cached `state` pointer. A miss allocates and a full
pool frees, so the ordinary path is unchanged.

Size classes `log2_size` 3 to 8, at depths 32, 32, 32, 16, 8 and 4:
about 109 KB per interpreter with every pool full. The ladder stops
where a 100-item constructor pre-sizes to, since past that the
allocation is a small part of filling the table.

Nothing is pooled on a free-threaded build, and that was the measurement
that decided the design. A shared pool needs an atomic exchange to pop
and another to push; on x86 an exchange is a locked operation whatever
memory order it asks for, which came to a flat ~41 cycles per round trip
against mimalloc's 30-52, so it lost below a 1456-byte block. mimalloc
already gives every thread its own freelist. On a GIL build the same
pool is ~10 cycles against pymalloc's 26-55 and libc `malloc`'s 117-158.
Instruction counts said the opposite, 22 against 108-312, which is the
blind spot: callgrind cannot see what a locked exchange costs.

The pools live in the module state rather than at file scope because
under a per-interpreter GIL a block has to be freed by the interpreter
that allocated it. They hold no reference, so `module_traverse()` needs
no change; `module_clear()` drains them.

`MULTIDICT_NO_FREELIST=1` builds without them. A pooled block never
reaches `free()`, so AddressSanitizer can neither poison it nor report a
use-after-free on it, and an ASan run now wants a second pass with that
set. AGENTS.md says so.

## Are there changes in behavior for the user?

No. Faster construction and teardown, nothing observable otherwise.

## Is it a substantial burden for the maintain... (continued)

767 of 1534 branches covered (50.0%)

Branch coverage included in aggregate %.

67 of 72 new or added lines in 2 files covered. (93.06%)

7361 of 7759 relevant lines covered (94.87%)

1.9 hits per line