patchcommit-reach: simplify cleanup of remaining bitmaps in ahead_behind()
6 messages between Mar 18, 2026 and Mar 20, 2026, from René Scharfe, Jeff King, Junio C Hamano, Derrick Stolee.
Plain Markdown or JSON for tools and agents. Diffs are folded; open one to read it.
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(-)
Show changes to commit-reach.c +6 −5
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()
On 3/18/26 1:45 PM, René Scharfe wrote:
Show 5 quoted lines
> 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.
Show 31 quoted lines
> 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()
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(-)
Show changes to commit-reach.c +2 −4
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()
On Wed, Mar 18, 2026 at 05:09:37PM +0100, René Scharfe wrote:
Show 10 quoted lines
> > - 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.
Show 6 quoted lines
> 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()
René Scharfe <l.s.r@web.de> writes:
Show 8 quoted lines
> 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.
Show 18 quoted lines
>
> 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()
On 3/19/2026 1:44 PM, Junio C Hamano wrote:
Show 5 quoted lines
> 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.
Show 6 quoted lines
>> - 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
René Scharfe
