{"thread":{"id":"65290","subject":"[PATCH] commit-reach: simplify cleanup of remaining bitmaps in ahead_behind()","startedAt":"2026-03-18T12:45:20Z","lastAt":"2026-03-20T16:35:42Z","messageCount":6,"participants":["René Scharfe","Jeff King","Junio C Hamano","Derrick Stolee"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"539285","messageId":"06000e28-c1b1-472f-bd6b-367b6c8d208d@web.de","threadId":"65290","inReplyTo":null,"subject":"[PATCH] commit-reach: simplify cleanup of remaining bitmaps in ahead_behind()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-03-18T12:45:15Z","receivedAt":"2026-03-18T12:45:20Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Use the deep clear function of the bit_arrays commit slab to free\nbitmaps of commits we didn't traverse. We don't care about their order\nanymore at this point, so we can bypass the prio_queue and its heap\nrebalancing logic. Note that bitmap_free() handles NULL pointers, so we\ndon't have to check.\n\nSigned-off-by: René Scharfe \n---\n commit-reach.c | 11 ++++++-----\n 1 file changed, 6 insertions(+), 5 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 9604bbdcce..a4fc41ff40 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -1047,6 +1047,11 @@ static void free_bit_array(struct commit *c)\n \t*bitmap = NULL;\n }\n \n+static void free_bitmap_pointer(struct bitmap **bitmap)\n+{\n+\tbitmap_free(*bitmap);\n+}\n+\n void ahead_behind(struct repository *r,\n \t\t struct commit **commits, size_t commits_nr,\n \t\t struct ahead_behind_count *counts, size_t counts_nr)\n@@ -1117,11 +1122,7 @@ void ahead_behind(struct repository *r,\n \n \t/* STALE is used here, PARENT2 is used by insert_no_dup(). */\n \trepo_clear_commit_marks(r, PARENT2 | STALE);\n-\twhile (prio_queue_peek(&queue)) {\n-\t\tstruct commit *c = prio_queue_get(&queue);\n-\t\tfree_bit_array(c);\n-\t}\n-\tclear_bit_arrays(&bit_arrays);\n+\tdeep_clear_bit_arrays(&bit_arrays, free_bitmap_pointer);\n \tclear_prio_queue(&queue);\n }\n \n-- \n2.53.0\n"},{"id":"539293","messageId":"c01eb1e3-d839-4cf6-ba47-5a9edd336ae3@web.de","threadId":"65290","inReplyTo":"06000e28-c1b1-472f-bd6b-367b6c8d208d@web.de","subject":"Re: [PATCH] commit-reach: simplify cleanup of remaining bitmaps in ahead_behind()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-03-18T16:09:37Z","receivedAt":"2026-03-18T16:09:43Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 3/18/26 1:45 PM, René Scharfe wrote:\n> Use the deep clear function of the bit_arrays commit slab to free\n> bitmaps of commits we didn't traverse. We don't care about their order\n> anymore at this point, so we can bypass the prio_queue and its heap\n> rebalancing logic. Note that bitmap_free() handles NULL pointers, so we\n> don't have to check.\n\nThat's nice and all, but it's also slower:\n\nBenchmark 1: ./git_main for-each-ref --format='%(objectname) %(ahead-behind:main)'\n Time (mean ± σ): 1.228 s ± 0.001 s [User: 1.188 s, System: 0.039 s]\n Range (min … max): 1.226 s … 1.231 s 10 runs\n\nBenchmark 2: ./git_deep_clear for-each-ref --format='%(objectname) %(ahead-behind:main)'\n Time (mean ± σ): 1.354 s ± 0.002 s [User: 1.313 s, System: 0.039 s]\n Range (min … max): 1.351 s … 1.356 s 10 runs\n\nSummary\n ./git_main for-each-ref --format='%(objectname) %(ahead-behind:main)' ran\n 1.10 ± 0.00 times faster than ./git_deep_clear for-each-ref --format='%(objectname) %(ahead-behind:main)'\n\nPlease don't apply this patch -- I should have measured first.\n\n> Signed-off-by: René Scharfe \n> ---\n> commit-reach.c | 11 ++++++-----\n> 1 file changed, 6 insertions(+), 5 deletions(-)\n> \n> diff --git a/commit-reach.c b/commit-reach.c\n> index 9604bbdcce..a4fc41ff40 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -1047,6 +1047,11 @@ static void free_bit_array(struct commit *c)\n> \t*bitmap = NULL;\n> }\n> \n> +static void free_bitmap_pointer(struct bitmap **bitmap)\n> +{\n> +\tbitmap_free(*bitmap);\n> +}\n> +\n> void ahead_behind(struct repository *r,\n> \t\t struct commit **commits, size_t commits_nr,\n> \t\t struct ahead_behind_count *counts, size_t counts_nr)\n> @@ -1117,11 +1122,7 @@ void ahead_behind(struct repository *r,\n> \n> \t/* STALE is used here, PARENT2 is used by insert_no_dup(). */\n> \trepo_clear_commit_marks(r, PARENT2 | STALE);\n> -\twhile (prio_queue_peek(&queue)) {\n> -\t\tstruct commit *c = prio_queue_get(&queue);\n> -\t\tfree_bit_array(c);\n> -\t}\n> -\tclear_bit_arrays(&bit_arrays);\n> +\tdeep_clear_bit_arrays(&bit_arrays, free_bitmap_pointer);\n\nThe prio_queue contains just a few unvisited entries at this point (or\nperhaps even none), while deep_clear_*() will visit all commits that\never had a bitmap, even if their bitmap pointer is NULL now.\n\nWe could still access them in array order, which must be cheaper:\n\n\tfor (size_t i = 0; i < queue.nr; i++)\n\t\tfree_bit_array(queue.array[i].data);\n\nPerformance is the same for my local Git repo clone, though.\n\n> \tclear_prio_queue(&queue);\n> }\n> \n\n"},{"id":"539399","messageId":"21adf042-2bd1-4022-8822-9ed4985122a4@web.de","threadId":"65290","inReplyTo":"06000e28-c1b1-472f-bd6b-367b6c8d208d@web.de","subject":"[PATCH v2] commit-reach: simplify cleanup of remaining bitmaps in ahead_behind()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-03-19T16:24:40Z","receivedAt":"2026-03-19T16:24:51Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Don't bother extracting the last few remaining prio_queue items in\norder when we only want to free their associated bitmaps; just iterate\nover the item array.\n\nSigned-off-by: René Scharfe \n---\n commit-reach.c | 6 ++----\n 1 file changed, 2 insertions(+), 4 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 9604bbdcce..d3a9b3ed6f 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -1117,10 +1117,8 @@ void ahead_behind(struct repository *r,\n \n \t/* STALE is used here, PARENT2 is used by insert_no_dup(). */\n \trepo_clear_commit_marks(r, PARENT2 | STALE);\n-\twhile (prio_queue_peek(&queue)) {\n-\t\tstruct commit *c = prio_queue_get(&queue);\n-\t\tfree_bit_array(c);\n-\t}\n+\tfor (size_t i = 0; i < queue.nr; i++)\n+\t\tfree_bit_array(queue.array[i].data);\n \tclear_bit_arrays(&bit_arrays);\n \tclear_prio_queue(&queue);\n }\n-- \n2.53.0\n"},{"id":"539407","messageId":"20260319165747.GA3615867@coredump.intra.peff.net","threadId":"65290","inReplyTo":"c01eb1e3-d839-4cf6-ba47-5a9edd336ae3@web.de","subject":"Re: [PATCH] commit-reach: simplify cleanup of remaining bitmaps in ahead_behind()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-03-19T16:57:47Z","receivedAt":"2026-03-19T16:57:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Mar 18, 2026 at 05:09:37PM +0100, René Scharfe wrote:\n\n> > -\twhile (prio_queue_peek(&queue)) {\n> > -\t\tstruct commit *c = prio_queue_get(&queue);\n> > -\t\tfree_bit_array(c);\n> > -\t}\n> > -\tclear_bit_arrays(&bit_arrays);\n> > +\tdeep_clear_bit_arrays(&bit_arrays, free_bitmap_pointer);\n> \n> The prio_queue contains just a few unvisited entries at this point (or\n> perhaps even none), while deep_clear_*() will visit all commits that\n> ever had a bitmap, even if their bitmap pointer is NULL now.\n\nIt is potentially even worse than that. A commit-slab must over-allocate\nbecause it provides a pseudo-array over _all_ commits in the program. So\nif the commit with index 123 gets a bitmap, then we will allocate a\npointer for the whole chunk, even if 124, 125, etc, never got one.\n\nLooking at ahead_behind(), though, I think it's probably pretty dense.\nWe'll be creating new commits from parent pointers and then immediately\nqueuing them. So the index values we allocate should have high locality.\n\nBut it might be something interesting to double-check.\n\n> We could still access them in array order, which must be cheaper:\n> \n> \tfor (size_t i = 0; i < queue.nr; i++)\n> \t\tfree_bit_array(queue.array[i].data);\n> \n> Performance is the same for my local Git repo clone, though.\n\nYeah, I agree that is a reasonable simplification.\n\n-Peff\n"},{"id":"539411","messageId":"xmqqjyv7lnmz.fsf@gitster.g","threadId":"65290","inReplyTo":"21adf042-2bd1-4022-8822-9ed4985122a4@web.de","subject":"Re: [PATCH v2] commit-reach: simplify cleanup of remaining bitmaps in ahead_behind()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-03-19T17:44:52Z","receivedAt":"2026-03-19T17:44:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> Don't bother extracting the last few remaining prio_queue items in\n> order when we only want to free their associated bitmaps; just iterate\n> over the item array.\n>\n> Signed-off-by: René Scharfe \n> ---\n> commit-reach.c | 6 ++----\n> 1 file changed, 2 insertions(+), 4 deletions(-)\n\nQuite obvious and straightforward. Will queue. Thanks.\n\n>\n> diff --git a/commit-reach.c b/commit-reach.c\n> index 9604bbdcce..d3a9b3ed6f 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -1117,10 +1117,8 @@ void ahead_behind(struct repository *r,\n> \n> \t/* STALE is used here, PARENT2 is used by insert_no_dup(). */\n> \trepo_clear_commit_marks(r, PARENT2 | STALE);\n> -\twhile (prio_queue_peek(&queue)) {\n> -\t\tstruct commit *c = prio_queue_get(&queue);\n> -\t\tfree_bit_array(c);\n> -\t}\n> +\tfor (size_t i = 0; i < queue.nr; i++)\n> +\t\tfree_bit_array(queue.array[i].data);\n> \tclear_bit_arrays(&bit_arrays);\n> \tclear_prio_queue(&queue);\n> }\n"},{"id":"539566","messageId":"ac4df3ef-1704-4a1b-a47c-6fe96ae1c01f@gmail.com","threadId":"65290","inReplyTo":"xmqqjyv7lnmz.fsf@gitster.g","subject":"Re: [PATCH v2] commit-reach: simplify cleanup of remaining bitmaps in ahead_behind()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-03-20T16:35:40Z","receivedAt":"2026-03-20T16:35:42Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/19/2026 1:44 PM, Junio C Hamano wrote:\n> René Scharfe writes:\n> \n>> Don't bother extracting the last few remaining prio_queue items in\n>> order when we only want to free their associated bitmaps; just iterate\n>> over the item array.\n\n> Quite obvious and straightforward. Will queue. Thanks.\n\n>> -\twhile (prio_queue_peek(&queue)) {\n>> -\t\tstruct commit *c = prio_queue_get(&queue);\n>> -\t\tfree_bit_array(c);\n>> -\t}\n>> +\tfor (size_t i = 0; i < queue.nr; i++)\n>> +\t\tfree_bit_array(queue.array[i].data);\n\nI like this cleanup quite a bit, thanks! I appreciate your\nself-review on the performance side, too. Thinking out loud\nlike that can help other (e.g. me) avoid similar mistakes in\nthe future.\n\nThanks,\n-Stolee\n"}]}