aio-libs / multidict / 36348057864

86%

push

github

Resize a full table by its live entries, never compact in place (#1615)

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

## What do these changes do?

When an add finds the table full, the C extension compacted it in place
at the same size whenever it held deleted entries. That regains only as
many slots as were deleted, so a table filled exactly to its usable size
and then churned with `del d[oldest]; d.add(new)` was rebuilt on every
add. With 87381 items, 5000 such steps took 4.5 s against 2 ms at 88000
items.

The rebuild is now sized by `GROWTH_RATE` (three times the live entries)
alone, which is the rule CPython and the pure-Python backend already
use; live entries decide whether the table compacts at the same size,
grows or shrinks. `_md_shrink()` and the GIL-only in-place
`_md_shrink_impl()` are removed, and `_md_resize()` is renamed
`_md_rebuild()` as the single rebuild primitive. The pure-Python backend
already behaved this way and is unchanged.

## Are there changes in behavior for the user?

Yes: the delete-then-add churn on a full table is O(1) amortized again,
and a C table shrinks when adds resume after many deletions, matching
the pure-Python backend.

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

No; it removes a code path and the GIL/FT difference in shrinking.

## Related issue number

N/A

## Checklist

- [x] I think the code is well written
- [x] Unit tests for the changes exist
- [ ] Documentation reflects the changes: N/A
- [ ] 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`

Drafted with Claude Opus 5.5 (Claude Code); reviewed by @asvetlov.

<details>
<summary>Agent run details (optional, for reviewers)</summary>

Churn timing (GIL, 5000 `del` + `add` steps, fresh table of n items):

| n | before | after |
|---|---|---|
| ... (continued)

781 of 1562 branches covered (50.0%)

Branch coverage included in aggregate %.

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

8464 of 9033 relevant lines covered (93.7%)

1.87 hits per line