aio-libs / multidict / 38229350857

86%

push

github

Keep md_is_first_key()'s probe state out of memory on a first-slot hit (#1775)

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

## What do these changes do?

`md_is_first_key()` passed the address of its `htkeysiter_t` to the cold
`_md_is_first_key_probe()`, so the `len(md.keys())` loop and the keys
iterator stored the whole iterator to the stack for every entry,
although most entries match in their first slot. The first slot is now
read into a local, and the probe builds its iterator from that index
only when it runs. The C extension only; the pure-Python backend has no
equivalent.

Specialising the loop on `ci` by hand was considered first and dropped:
GCC already unswitches it at `-O3` on both builds.

Callgrind, Ir per op, base to this branch:

| operation | GIL MD | GIL CI | FT MD | FT CI |
|---|---|---|---|---|
| `iter_keys_dup` | -5.3% | -6.1% | -6.2% | -6.4% |
| `len(keys())`, 200 entries, half duplicates | -3.6% | -6.7% | -4.0% |
-4.1% |
| `len(keys())`, 200 entries, one duplicate | -11.1% | -13.4% | -10.6% |
-10.8% |
| `getitem_hit` | **+2.5%** | 0 | 0 | 0 |
| `contains_hit` | **+2.2%** | 0 | 0 | 0 |

The `getitem_hit` and `contains_hit` regression on the GIL build is
collateral: it sits entirely in `_md_get_one_locked.isra.0` (+4.25 Ir
per lookup), which does not reach the changed code. GCC reordered its
index width branches, so the 16-bit index read costs an extra compare
and jump. The out-of-line call graph is unchanged and
`tools/check_inlining.py` passes. This must be resolved before the PR
leaves draft.

## 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 (existing keys() duplicate tests
cover the path; no behaviour change)
- [x] Documentation reflects the changes (N/A, no user-facing API
change)
- [ ] If you provide code modification, please add y... (continued)

832 of 1664 branches covered (50.0%)

Branch coverage included in aggregate %.

9778 of 10667 relevant lines covered (91.67%)

1.83 hits per line