Subject: Re: [PATCH] commit-reach: simplify cleanup of remaining bitmaps in ahead_behind()

From: René Scharfe <[email-masked]>
Date: Wed, 18 Mar 2026 17:09:37 +0100

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 <[email-masked]>
> ---
>  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);
>  }
>