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

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

[René Scharfe]

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.

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);
 	clear_prio_queue(&queue);
 }
 
-- 
2.53.0

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

[René Scharfe]

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);
>  }
>  

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

[René Scharfe]

Don't bother extracting the last few remaining prio_queue items in
order when we only want to free their associated bitmaps; just iterate
over the item array.

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 commit-reach.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

diff --git a/commit-reach.c b/commit-reach.c
index 9604bbdcce..d3a9b3ed6f 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -1117,10 +1117,8 @@ 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);
-	}
+	for (size_t i = 0; i < queue.nr; i++)
+		free_bit_array(queue.array[i].data);
 	clear_bit_arrays(&bit_arrays);
 	clear_prio_queue(&queue);
 }
-- 
2.53.0

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

[Jeff King]

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

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

[Junio C Hamano]

René Scharfe <l.s.r@web.de> writes:

> Don't bother extracting the last few remaining prio_queue items in
> order when we only want to free their associated bitmaps; just iterate
> over the item array.
>
> Signed-off-by: René Scharfe <l.s.r@web.de>
> ---
>  commit-reach.c | 6 ++----
>  1 file changed, 2 insertions(+), 4 deletions(-)

Quite obvious and straightforward.  Will queue.  Thanks.

>
> diff --git a/commit-reach.c b/commit-reach.c
> index 9604bbdcce..d3a9b3ed6f 100644
> --- a/commit-reach.c
> +++ b/commit-reach.c
> @@ -1117,10 +1117,8 @@ 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);
> -	}
> +	for (size_t i = 0; i < queue.nr; i++)
> +		free_bit_array(queue.array[i].data);
>  	clear_bit_arrays(&bit_arrays);
>  	clear_prio_queue(&queue);
>  }

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

[Derrick Stolee]

On 3/19/2026 1:44 PM, Junio C Hamano wrote:
> René Scharfe <l.s.r@web.de> writes:
> 
>> Don't bother extracting the last few remaining prio_queue items in
>> order when we only want to free their associated bitmaps; just iterate
>> over the item array.

> Quite obvious and straightforward.  Will queue.  Thanks.

>> -	while (prio_queue_peek(&queue)) {
>> -		struct commit *c = prio_queue_get(&queue);
>> -		free_bit_array(c);
>> -	}
>> +	for (size_t i = 0; i < queue.nr; i++)
>> +		free_bit_array(queue.array[i].data);

I like this cleanup quite a bit, thanks! I appreciate your
self-review on the performance side, too. Thinking out loud
like that can help other (e.g. me) avoid similar mistakes in
the future.

Thanks,
-Stolee