aio-libs / multidict / 37220670984

86%

push

github

Walk a table's entries in one loop per kind (#1676)

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

## What do these changes do?

The linear walks over a table's entries read the kind once and passed it
to every accessor, leaving GCC to split each loop per kind, which #1659
and #1674 showed it does only for some spellings. Each walk now
dispatches on the kind once and runs an `ALWAYS_INLINE` body with the
kind a constant, stepping a pointer by the entry size (`entry_next()`)
instead of multiplying an index. Converted: `md == md`, `update()` /
`extend()` / `merge()` from a multidict of the same class,
`extend(self)`, `to_dict()`, `==` against a mapping, the rebuild of a
table with holes, `tp_traverse` and the C API walk over all items. The
copy and dispose loops, already split per kind, now step a pointer too.

`md_eq()` can see a value's `__eq__` move either table to the full
layout mid-compare; it then carries on from the same positions under the
new kinds. A new test drives that path on both sides and checks the
result against the pure-Python backend.

The probe loops (lookups, deletes, replace, the per-item search in
`update()`) are unchanged: splitting them the same way grew `.text` by
43% on GIL and made CIMultiDict lookups 1-1.6% slower on GIL, since a
probe chain is one or two steps.

Callgrind, base `e81a9413`, Ir per operation, MultiDict / CIMultiDict:

| Operation | GIL | FT |
|---|---|---|
| `md == md` | -41% / -46% | -35% / -47% |
| `merge(md)` | -18% / -16% | -10% / -15% |
| `extend(md)` | -9% / -5% | -9% / -7% |
| `update(md)` | -5% / -5% | -7% / -4% |
| add into a table with holes | -7% / -8% | -5% / -6% |
| GC traverse | -6% / -6% | -3% / -3% |
| `copy()` | -4% / -2% | -3% / -1% |
| `clear()` | -4% / -3% | -3% / -2% |

Nothing regressed by more than 0.8% (FT `update(items)` +0.8%, FT
CIMultiDict constructor +0.6..0.8%). FT `d[key]` -4.5% and FT `items()`
iteration -3% come from code layout, since this change does not touch
those paths. `.t... (continued)

792 of 1584 branches covered (50.0%)

Branch coverage included in aggregate %.

9 of 17 new or added lines in 1 file covered. (52.94%)

9324 of 10184 relevant lines covered (91.56%)

1.83 hits per line