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

[Patrick Steinhardt <ps@pks.im>]

[-- Attachment #1: Type: text/plain, Size: 3127 bytes --]

On Wed, Jan 31, 2024 at 12:35:51PM -0800, Junio C Hamano wrote:
> Patrick Steinhardt <ps@pks.im> writes:
> 
> > patterns in the reftable library. For In most cases, we end up only having a
> > 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
> > paths. 
> 
> You need to know not just that you very often initially have only
> one but you rarely grow it beyond 3, or something like that to
> explain "significantly overallocates", though.

True.

> > This effect is indeed measurable:
> 
> And measuring is very good, but I somehow expected that you would
> measure not the time (if you often under-allocate and end up
> reallocating too many times, it might consume more time, though) but
> the peak memory usage.  I cannot quite tell what to think of that 2%
> time difference.

Very good point indeed. I don't think peak memory usage is really all
that helpful either because the problem is not that we are allocating
arrays that we keep around all the time, but many small arrays which are
short lived. So what is telling is the total number of bytes we end up
allocating:

    Before change:

        HEAP SUMMARY:
            in use at exit: 671,983 bytes in 152 blocks
          total heap usage: 3,843,446 allocs, 3,843,294 frees, 223,761,402 bytes allocated

    Growth factor (alloc * 2 + 1):

        HEAP SUMMARY:
            in use at exit: 671,983 bytes in 152 blocks
          total heap usage: 3,843,446 allocs, 3,843,294 frees, 223,761,410 bytes allocated

    Growth factor (alloc + 16) * 2 / 3:

        HEAP SUMMARY:
            in use at exit: 671,983 bytes in 152 blocks
          total heap usage: 3,833,673 allocs, 3,833,521 frees, 4,728,251,742 bytes allocated

Allocating 21 times as many bytes with our default growth factor should
be a much more compelling argument why we don't actually want to use it
compared to the 2% speedup.

It's somewhat amazing though that this huge difference only makes for a
2% speedup.

> > Convert the reftable library to use these new macros.
> 
> In any case, the conversion shortens the code and is a good thing.
> I wish we had a way to tell these macros that we are actually using
> the same single allocator (which we are doing in our code when
> linking the reftable thing to us anyway), which would have made this
> even simpler because you did not have to introduce separate macros..

Yeah, I wasn't a huge fan of this, either. I initially just wanted to
reuse our usual macros, but when I noticed the resulting difference in
allocated bytes I already had two arguments against this: the fact that
we have pluggable allocators in the reftable library and the growth
factor. While we could make our macros more flexible so that they can
accommodate for both, I don't think that the result would be pretty.

So at that point I decided to just duplicate the code. It still ends up
removing a lot of code duplication in the reftable library itself, so I
don't think it is too bad.

Patrick

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]