public inbox for git@vger.kernel.org 
 help / color / mirror / Atom feed

From: "René Scharfe" <l.s.r@web•de>
To: Git List <git@vger•kernel.org>
Cc: Patrick Steinhardt <ps@pks•im>, Derrick Stolee <stolee@gmail•com>
Subject: Re: [PATCH] commit-reach: simplify cleanup of remaining bitmaps in ahead_behind()
Date: Wed, 18 Mar 2026 17:09:37 +0100	[thread overview]
Message-ID: <c01eb1e3-d839-4cf6-ba47-5a9edd336ae3@web.de> (raw)
In-Reply-To: <06000e28-c1b1-472f-bd6b-367b6c8d208d@web.de>

On 3/18/26 1:45 PM, René Scharfe wrote:
> Use the deep clear function of the bit_arrays commit slab to free
> bitmaps of commits we didn't traverse.  We don't care about their order
> anymore at this point, so we can bypass the prio_queue and its heap
> rebalancing logic.  Note that bitmap_free() handles NULL pointers, so we
> don't have to check.

That's nice and all, but it's also slower:

Benchmark 1: ./git_main for-each-ref --format='%(objectname) %(ahead-behind:main)'
  Time (mean ± σ):      1.228 s ±  0.001 s    [User: 1.188 s, System: 0.039 s]
  Range (min … max):    1.226 s …  1.231 s    10 runs

Benchmark 2: ./git_deep_clear for-each-ref --format='%(objectname) %(ahead-behind:main)'
  Time (mean ± σ):      1.354 s ±  0.002 s    [User: 1.313 s, System: 0.039 s]
  Range (min … max):    1.351 s …  1.356 s    10 runs

Summary
  ./git_main for-each-ref --format='%(objectname) %(ahead-behind:main)' ran
    1.10 ± 0.00 times faster than ./git_deep_clear for-each-ref --format='%(objectname) %(ahead-behind:main)'

Please don't apply this patch -- I should have measured first.

> Signed-off-by: René Scharfe <l.s.r@web•de>
> ---
>  commit-reach.c | 11 ++++++-----
>  1 file changed, 6 insertions(+), 5 deletions(-)
> 
> diff --git a/commit-reach.c b/commit-reach.c
> index 9604bbdcce..a4fc41ff40 100644
> --- a/commit-reach.c
> +++ b/commit-reach.c
> @@ -1047,6 +1047,11 @@ static void free_bit_array(struct commit *c)
>  	*bitmap = NULL;
>  }
>  
> +static void free_bitmap_pointer(struct bitmap **bitmap)
> +{
> +	bitmap_free(*bitmap);
> +}
> +
>  void ahead_behind(struct repository *r,
>  		  struct commit **commits, size_t commits_nr,
>  		  struct ahead_behind_count *counts, size_t counts_nr)
> @@ -1117,11 +1122,7 @@ void ahead_behind(struct repository *r,
>  
>  	/* STALE is used here, PARENT2 is used by insert_no_dup(). */
>  	repo_clear_commit_marks(r, PARENT2 | STALE);
> -	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.

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.

>  	clear_prio_queue(&queue);
>  }
>  

next prev parent reply	other threads:[~2026-03-18 16:09 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 [this message]
2026-03-19 16:57   ` Jeff King
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=c01eb1e3-d839-4cf6-ba47-5a9edd336ae3@web.de \
    --to=l.s.r@web$(echo .)de \
    --cc=git@vger$(echo .)kernel.org \
    --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

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox