aio-libs / multidict / 35658110790

87%

push

github

Track duplicate-key walks in a private bitmap instead of marking entry hashes (#1505)

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

## What do these changes do?

Duplicate-key walks in the C extension used to dedupe by OR-ing a high
bit into `entry->hash` and restoring it afterwards (`setitem`,
`update()`, `merge()`, `to_dict()`), or by a linearly scanned visited
list (`getall()` and the views). This replaces both with `bitmap_t`, an
entry-index bitmap private to the call. It keeps a 4 KB inline buffer
(32768 entries) and moves to the heap for bigger tables; nothing is
zeroed or allocated until the first mark. Bitmaps of up to 64 words are
zeroed outright, larger ones lazily through a small summary bitmap.
Words are `size_t`, so 32-bit targets don't emulate 64-bit arithmetic.

`getall()` and the views record their first matches in a short list and
only start the bitmap past it: after 8 matches when the bitmap fits its
inline buffer, after 32 on bigger tables, where it would need a heap
allocation.

`update()` and `merge()` keep two per-batch bitmaps (entries written,
entries half-deleted). The batch's own resizes rebuild them for the new
layout; a mutation from outside the batch (Python code run between
items, another thread) is detected and falls back to the old full-table
sweep. `md_post_update()` visits only the recorded deletions instead of
every slot.

With nothing marking the table, `MD_HASH_MARK` is gone, together with
the masking it forced on lock-free readers, `htkeys_build_indices()` and
the consistency check. The pure-Python backend is unchanged; it keeps
its own hash marks and the observable behaviour is the same.

CodSpeed against master: `getall()` on keys with many values +23 to
+28%, `__setitem__` +10 to +18%, `to_dict()` +11 to +17%, insert +10 to
+11%, the rest unchanged, except `update()` with many duplicate keys,
which is 11% slower (`test_multidict_update_str_with_duplicates`,
`test_cimultidict_update_istr_with_duplicates`). That is... (continued)

762 of 1524 branches covered (50.0%)

Branch coverage included in aggregate %.

98 of 98 new or added lines in 1 file covered. (100.0%)

6714 of 6995 relevant lines covered (95.98%)

1.92 hits per line