aio-libs / multidict / 37799616380

86%

push

github

Move to_dict() into to_dict.h and mark only later duplicates (#1756)

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

## What do these changes do?

Moves `to_dict()` out of `hashtable.h` into its own
`_multilib/to_dict.h`, and trims its use of the `collected` bitmap.

The outer loop only starts a chain walk at the first entry of a key, and
equal keys are first reached along the chain in increasing entry index
(the invariant #1752 relies on), so the walk's first match is that entry
itself. Only the later matches need a mark for the outer loop to skip. A
repeated probe slot is now caught by `index <= last`, as in
`md_walk_with_hash()`, instead of `bitmap_test_and_set()`. The loop over
a table without repeated keys is split per entry kind, instead of
choosing the entry layout on every entry.

Dropping the bitmap altogether, by testing each entry for being the
first of its key the way `keys()` does, was measured too and is slower
on every table with repeated keys (GIL +3..+31%, FT +3..+24%): every
later duplicate then pays a probe and a string compare where the bitmap
pays one bit test. Iterating `keys()` and calling `getall()` per key
would add a separate first-key walk and rehash every key on top of that.

The pure-Python backend is unaffected; its `to_dict()` groups through a
dict keyed by identity.

## Are there changes in behavior for the user?

No.

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

No.

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

Instructions per `to_dict()` call, from callgrind with
`PYTHONHASHSEED=0`, bracketed around the calls and differenced between
10 an... (continued)

832 of 1664 branches covered (50.0%)

Branch coverage included in aggregate %.

9706 of 10588 relevant lines covered (91.67%)

1.83 hits per line