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

From: Junio C Hamano <gitster@pobox.com>
Date: Nov 22, 2020, 20:32 UTC
Message-ID: <xmqq7dqdqgji.fsf@gitster.c.googlers.com>
In-Reply-To: <c7db594fae4d0447a55a92e830475d9bc418ae7f.1605123652.git.me@ttaylorr.com>

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

Thanks.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.