aio-libs / multidict / 35913838361

87%

push

github

Shrink the walk bitmap's inline buffer (#1543)

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

## What do these changes do?

`bitmap_t` carried a 4 KB inline word buffer. It sits in the caller's
frame, twice over inside `update_marks_t`, and `md_walk()` is always
inlined, so that frame lands in every `getall()`, `popall()`,
`__delitem__()`, `__contains__()` and `to_dict()`. Past about 1 KB it
costs those callers more in the inlining it crowds out than it saves in
allocations.

Nothing else changes. `_bitmap_start()` already falls back to the heap
past the inline capacity, so only the crossover moves, and a table of up
to 8192 entries still gets its bitmap for free.

Instructions per operation on a GIL build, swept at 4096, 2048, 1024 and
512 bytes:

| case | 4096 | 2048 | 1024 | 512 |
| --- | --- | --- | --- | --- |
| `getall()` that hits | 1055 | 1054 | 1026 | 1026 |
| `getall()`, 16384-entry table | 270685 | 270429 | 266973 | 266973 |

Everything else is flat to within 0.1%, and `popall()` over the same
table exactly so. The cliff is between 2048 and 1024. 1024 keeps twice
the inline capacity of 512 for the same result, and 512 is the floor
anyway: below it `BITMAP_INLINE_SUMMARY` rounds down to zero entries and
the struct does not compile.

## Are there changes in behavior for the user?

No. A walk over a table between 8192 and 32768 entries now allocates a
bitmap where it did not before, but only once it has more matches than
the short list holds, and the numbers above cover that case.

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

No, it is one constant.

## Related issue number

None.

## Checklist

- [x] I think the code is well written
- [x] Unit tests for the changes exist — N/A,
`tests/test_update_marks.py` already crosses the inline/heap boundary
and passes at every value swept
- [x] Documentation reflects the changes
- [x] If you provide code modification, please add yourself to
`CONTRIBUTORS.txt` — N/A, no such file in t... (continued)

765 of 1530 branches covered (50.0%)

Branch coverage included in aggregate %.

7290 of 7682 relevant lines covered (94.9%)

1.9 hits per line