aio-libs / multidict / 37781823661

86%

push

github

Skip repeated probe slots by entry index in getall() (#1752)

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

## What do these changes do?

The probe walk behind `getall()` can reach the same slot twice, so it
kept a list of visited entries that switched to a bitmap past 8 matches
(32 on large tables). That set is not needed. Every entry went into the
first slot of its probe sequence that was empty when it was inserted,
and a slot never becomes empty again; a rebuild reinserts in entry
order, and resume slots only skip slots that are already filled. So the
walk first reaches the entries of one key in increasing entry index, and
a match whose index is not above the previous match is a repeat.
`md_walk_with_hash()` now keeps that one index instead of `md_seen_t`.
This also covers the views' match collector and the C API's foreach-key
walk.

The pure-Python `getall()` and items view `&` now use the same rule
instead of temporarily marking entry hashes. `__setitem__()` still
marks, since it is a writer.

## Are there changes in behavior for the user?

No. `getall()` on a key with many values got faster; see the
measurements below.

## Is it a substantial burden for the maintainers to support this?

No. It removes code; the invariant is documented in `walk.h` and in the
overview comment in `hashtable.h`.

## 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
- [ ] 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`

Instruction counts per `getall(key, None)` call, from callgrind with
`PYTHONHASHSEED=0`, with the driving loop and a no-op arm subtracted.
The base is d970d8cd. "big" is a table with 50,000 other keys; nothing
else changed by more than 2%.

| case | GIL Mu... (continued)

825 of 1650 branches covered (50.0%)

Branch coverage included in aggregate %.

24 of 24 new or added lines in 2 files covered. (100.0%)

9667 of 10547 relevant lines covered (91.66%)

1.83 hits per line