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

From: Patrick Steinhardt <ps@pks.im>
Date: Feb 1, 2024, 07:29 UTC
Message-ID: <ZbtIQ3Hk6Mgvkv4j@tanuki>
In-Reply-To: <xmqqmssl44wo.fsf@gitster.g>

On Wed, Jan 31, 2024 at 12:35:51PM -0800, Junio C Hamano wrote:

Show 10 quoted lines

> 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.

Show 7 quoted lines

> > 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.

Show 7 quoted lines

> > 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