From: Jeff King <peff@peff•net>
To: "René Scharfe" <l.s.r@web•de>
Cc: Git List <git@vger•kernel.org>, Patrick Steinhardt <ps@pks•im>,
Derrick Stolee <stolee@gmail•com>
Subject: Re: [PATCH] commit-reach: simplify cleanup of remaining bitmaps in ahead_behind()
Date: Thu, 19 Mar 2026 12:57:47 -0400 [thread overview]
Message-ID: <20260319165747.GA3615867@coredump.intra.peff.net> (raw)
In-Reply-To: <c01eb1e3-d839-4cf6-ba47-5a9edd336ae3@web.de>
On Wed, Mar 18, 2026 at 05:09:37PM +0100, René Scharfe wrote:
> > - while (prio_queue_peek(&queue)) {
> > - struct commit *c = prio_queue_get(&queue);
> > - free_bit_array(c);
> > - }
> > - clear_bit_arrays(&bit_arrays);
> > + deep_clear_bit_arrays(&bit_arrays, free_bitmap_pointer);
>
> The prio_queue contains just a few unvisited entries at this point (or
> perhaps even none), while deep_clear_*() will visit all commits that
> ever had a bitmap, even if their bitmap pointer is NULL now.
It is potentially even worse than that. A commit-slab must over-allocate
because it provides a pseudo-array over _all_ commits in the program. So
if the commit with index 123 gets a bitmap, then we will allocate a
pointer for the whole chunk, even if 124, 125, etc, never got one.
Looking at ahead_behind(), though, I think it's probably pretty dense.
We'll be creating new commits from parent pointers and then immediately
queuing them. So the index values we allocate should have high locality.
But it might be something interesting to double-check.
> We could still access them in array order, which must be cheaper:
>
> for (size_t i = 0; i < queue.nr; i++)
> free_bit_array(queue.array[i].data);
>
> Performance is the same for my local Git repo clone, though.
Yeah, I agree that is a reasonable simplification.
-Peff
next prev parent reply other threads:[~2026-03-19 16:57 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-03-18 12:45 [PATCH] commit-reach: simplify cleanup of remaining bitmaps in ahead_behind() René Scharfe
2026-03-18 16:09 ` René Scharfe
2026-03-19 16:57 ` Jeff King [this message]
2026-03-19 16:24 ` [PATCH v2] " René Scharfe
2026-03-19 17:44 ` Junio C Hamano
2026-03-20 16:35 ` Derrick Stolee
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20260319165747.GA3615867@coredump.intra.peff.net \
--to=peff@peff$(echo .)net \
--cc=git@vger$(echo .)kernel.org \
--cc=l.s.r@web$(echo .)de \
--cc=ps@pks$(echo .)im \
--cc=stolee@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox