aio-libs / multidict / 36010336083

87%

push

github

Drop the trailing tombstones when popitem() removes the last entry (#1568)

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

## What do these changes do?

`popitem()` in the C extension finds the last live entry by walking
back from `nentries` over the tombstones that earlier deletes left
behind, but never shortened `nentries` afterwards, so each call walked
every entry the previous calls had already removed and popping a
mapping empty cost quadratic time. `md_pop_item()` now sets `nentries`
to the popped entry's position, dropping it and the tombstones after
it, which is what CPython's `dict.popitem()` does and what the
pure-Python implementation already did with `del entries[pos:]`.

The trim is done before the delete releases its references: a `__del__`
on the popped key can re-enter the mapping (on the free-threaded build
by suspending the critical section) and an `add()` from there must land
at the trimmed position, not past it. A test covers that with a `str`
subclass key whose finalizer adds to the mapping, which on a
`CIMultiDict` is released inside `popitem()` because the returned key
is a fresh `istr`.

Instruction counts per `popitem()` on a 200-item mapping,
`benchmarks/callgrind_driver.py`, CPython 3.14.7, `PYTHONHASHSEED=0`:

| `d.popitem()` | before | after | | `dict` |
| --- | ---: | ---: | ---: | ---: |
| `MultiDict`, GIL | 1,092 | 497 | -54% | 447 |
| `CIMultiDict`, GIL | 2,387 | 1,792 | -25% | |
| `MultiDict`, free-threaded | 1,245 | 650 | -48% | 482 |
| `CIMultiDict`, free-threaded | 2,582 | 1,987 | -23% | |

What is left on `CIMultiDict` is the `istr` built for the returned key.

Wall clock, `benchmarks/benchmark.py` pinned to a P-core on an idle
machine, median ns per `popitem()`:

| `d.popitem()` | before | after | | `dict` |
| --- | ---: | ---: | ---: | ---: |
| `MultiDict`, GIL | 89.0 | 46.6 | -48% | 48.0 |
| `CIMultiDict`, GIL | 217.7 | 168.8 | -22% | |
| `MultiDict`, free-threaded | 125.1 | 80.7 | -35% | 54.8 |
| `CIMultiDict`, fr... (continued)

775 of 1550 branches covered (50.0%)

Branch coverage included in aggregate %.

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

7637 of 8046 relevant lines covered (94.92%)

1.9 hits per line