aio-libs / multidict / 36705619278

86%

push

github

Store a MultiDict of exact str keys in a compact table (#1644)

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

## What do these changes do?

A hash table now has a kind, stored in the padding of its header.
`KIND_STR` stores only the key and the value, 16 bytes per entry instead
of 32: every key is an exact `str` that is its own identity, and the
hash is the one the `str` caches. A case-sensitive `MultiDict` starts in
`KIND_STR`; the first key that is not its own identity (an `istr`, a
`str` subclass) moves the table to `KIND_ANYSTR`, the full layout,
keeping every entry at its index, so iterators and an in-flight
`update()`'s marks stay valid. `clear()` lets the table start compact
again. A `CIMultiDict` stays `KIND_ANYSTR`, since reading a key swaps
the stored `str` for its `istr`.

In `KIND_STR` the key slot doubles as the identity, the field a
lock-free reader checks first, so on FT it is written only by
`publish_identity()` and cleared only by `reset_identity()`, and a
lock-free reader takes the hash from the key object, treating an emptied
slot as a mismatch. The pools are keyed by kind as well as size.

Keeping `CIMultiDict` flat took the second commit: its tables are always
`KIND_ANYSTR`, so its `add()`, `setdefault()` and item assignment, and
the bulk updates when `md->is_ci`, pass that as a compile-time constant
and every test on the kind folds away. `CIMultiDict` gets its own method
table through a shared `MULTIDICT_METHODS(P)` macro and its own
`mp_ass_subscript`. The bulk updates have one out-of-line copy per
operation and kind; one copy with both kinds inlined made the
constructor 16 to 21% slower. `_md_parse_item()` and
`md_add_with_hash_steal_refs()` are pinned inline, with
`tools/check_inlining.py` rules.

Callgrind, Ir per operation against master, 200 `str` keys:

| operation | GIL `MultiDict` | FT `MultiDict` | GIL `CIMultiDict` | FT
`CIMultiDict` |
| --- | ---: | ---: | ---: | ---: |
| `d.copy()` | -59.2% | -55.9% | flat | flat |
| `d... (continued)

789 of 1578 branches covered (50.0%)

Branch coverage included in aggregate %.

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

8990 of 9719 relevant lines covered (92.5%)

1.85 hits per line