Re: [PATCH 07/23] ewah: make bitmap growth less aggressive

From: Taylor Blau <me@ttaylorr.com>
Date: Nov 23, 2020, 16:49 UTC
Message-ID: <X7voLUlevHygqFg/@nand.local>
In-Reply-To: <xmqq7dqdqgji.fsf@gitster.c.googlers.com>

On Sun, Nov 22, 2020 at 12:32:01PM -0800, Junio C Hamano wrote:

Show 10 quoted lines

> Taylor Blau <me@ttaylorr.com> writes:
>
> >  - a geometric increase in existing size; we'll switch to 3/2 instead of
> >    2 here. That's less aggressive and may help avoid fragmenting memory
> >    (N + 3N/2 > 9N/4, so old chunks can be reused as we scale up).
>
> I am sure this is something obvious to bitmap folks, but where does
> 9N/4 come from (I get that the left-hand-side of the comparison is
> the memory necessary to hold both the old and the new copy while
> reallocating the words[] array)?

I thought that I was in the group of "bitmap folks", but since it's not obvious to me either, I guess I'll have to hand in my bitmap folks membership card ;).

Peff: where does 9N/4 come from? On a similar note: we could certainly
use ALLOC_GROW here, too, but it would change the behavior slightly (by
using alloc_nr()'s "add-16-first" behavior). Maybe we should be using
it, but I'll defer to your judgement.

> Thanks.

Thanks, Taylor