aio-libs / multidict / 37775699769

86%

Build Type

push

github

Committed by web-flow

Commit Message

Yield each key once from keys() and iteration (#1682)

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

## What do these changes do?

`keys()` and iteration over a multidict yield each key once, as spelled
in its first item, which is also the item `d[key]` returns. `items()`,
`values()` and `len(d)` keep every item. `len(d.keys())`, the keys
view's `repr()`, its set operators and its comparisons follow the
deduplicated view, so `dict(md)` and `{k: md.getall(k) for k in md}` now
give one entry per key. This is the outcome agreed in #1654.

Both backends use the same rule. Inserts take only empty slots and
rebuilds reinsert in order, so the first entry of a key on its hash
chain is its first item; the keys iterator yields an entry only if it is
that first one. To keep the common case cheap, each hash table records
whether it may hold a key twice: an insert sets the flag when its probe
passes an entry of the same hash, a rebuild re-checks a set flag, and a
debug build asserts the flag is never clear while two entries share a
hash. While it is clear, keys iteration skips the check, and `getall()`,
`popall()`, `del`, replacing a key, `update()` and `to_dict()` stop at
the first match instead of walking the whole chain. Callers that have
just looked the key up (`setdefault()`, `d[k] = v`, `update()`,
`merge()`), extend from a multidict without repeats, or fill an empty
case-sensitive multidict from a dict or keyword arguments skip the
insert-side check.

Callgrind, instructions per operation vs. master (`MultiDict` /
`CIMultiDict`, C extension):

| Operation | GIL | free-threaded |
|---|---|---|
| `for k in d`, no repeated keys | +4% / +4% | +4% / +4% |
| `for k in d`, every key twice | +5% / +0% | -39% / -41% |
| `getall()` | -14% / -12% | -14% / -14% |
| `d[k] = v`, existing key | -7% / -7% | -7% / -9% |
| `del d[k]` | -8% / -8% | -8% / -8% |
| `update()` | -5% / -5% | -9% / -5% |
| `d[k] = v`, new key | +3% / +3% | +6% / +5% |
| `setdefault()`, new key | +3% /... (continued)

Coverage Stats

830 of 1660 branches covered (50.0%)

Branch coverage included in aggregate %.

351 of 364 new or added lines in 8 files covered. (96.43%)

1 existing line in 1 file now uncovered.

9655 of 10535 relevant lines covered (91.65%)

1.83 hits per line