Re: [PATCH 1/9] reftable: introduce macros to grow arrays

[Eric Sunshine <sunshine@sunshineco.com>]

On Wed, Jan 31, 2024 at 3:01 AM Patrick Steinhardt <ps@pks.im> wrote:
> Throughout the reftable library we have many cases where we need to grow
> arrays. In order to avoid too many reallocations, we roughly double the
> capacity of the array on each iteration. The resulting code pattern is
> thus duplicated across many sites.
>
> We have similar patterns in our main codebase, which is why we have
> eventually introduced an `ALLOC_GROW()` macro to abstract it away and
> avoid some code duplication. We cannot easily reuse this macro here
> though because `ALLOC_GROW()` uses `REALLOC_ARRAY()`, which in turn will
> call realloc(3P) to grow the array. The reftable code is structured as a
> library though (even if the boundaries are fuzzy), and one property this
> brings with it is that it is possible to plug in your own allocators. So
> instead of using realloc(3P), we need to use `reftable_realloc()` that
> knows to use the user-provided implementation.
>
> So let's introduce two new macros `REFTABLE_REALLOC_ARRAY()` and
> `REFTABLE_ALLOC_GROW()` that mirror what we do in our main codebase,
> with two modifications:
>
>   - They use `reftable_realloc()`, as explained above.
>
>   - They use a different growth factor of `2 * cap + 1` instead of `(cap
>     + 16) * 3 / 2`.
>
> The second change is because we know a bit more about the allocation
> patterns in the reftable library. For In most cases, we end up only having a

s/For In/In/

> single item in the array, so the initial capacity that our global growth
> factor uses (which is 24), significantly overallocates in a lot of code

Perhaps? s/overallocates/over-allocates/

> paths. This effect is indeed measurable:
>   [...]
>
> Convert the reftable library to use these new macros.
>
> Signed-off-by: Patrick Steinhardt <ps@pks.im>

(Neither above comment is worth a reroll.)