{"thread":{"id":"65684","subject":"[PATCH 0/3] commit-reach: replace queue_has_nonstale with a counter","startedAt":"2026-05-24T17:42:23Z","lastAt":"2026-05-26T06:57:25Z","messageCount":26,"participants":["Kristofer Karlsson via GitGitGadget","Junio C Hamano","Derrick Stolee","Jeff King","Kristofer Karlsson"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"544005","messageId":"pull.2124.git.1779644541.gitgitgadget@gmail.com","threadId":"65684","inReplyTo":null,"subject":"[PATCH 0/3] commit-reach: replace queue_has_nonstale with a counter","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-24T17:42:17Z","receivedAt":"2026-05-24T17:42:23Z","isPatch":true,"body":"paint_down_to_common() and ahead_behind() terminate when every commit in\ntheir priority queue is STALE. The current check, queue_has_nonstale(), does\nan O(n) linear scan of the queue on every iteration, costing O(n*m) total\nwhere n is the queue size and m is the number of commits processed. This\nseries replaces that scan with an O(1) counter.\n\nPerformance measurements with git merge-base --all and git for-each-ref\n--format='%(ahead-behind:...)':\n\ngit.git (merge-base)\n Baseline Dedup Dedup+Ctr\nseen..next, 33 merge bases: 157ms 165ms 143ms\nseen..master, 1 base: 47ms 40ms 44ms\nmaster..next, 1 base: 62ms 60ms 63ms\n\n(seen=fe056fe1, next=c82f1880, master=6a4418c3)\n\nLarge monorepo, 2.4M commits (merge-base)\n Baseline Dedup+Ctr\ncomponent import, wide frontier (1): 8083ms 3778ms\ncomponent import, wide frontier (2): 5664ms 4207ms\ncomponent import, wide frontier (3): 4558ms 1796ms\n\nLarge monorepo, 2.4M commits (ahead-behind)\n Baseline Dedup+Ctr\ncomponent import, wide frontier (1): 8216ms 4145ms\ncomponent import, wide frontier (2): 6107ms 4528ms\ncomponent import, wide frontier (3): 4725ms 1999ms\n\nLinear history (merge-base), no regression:\nmaster vs HEAD~10000: 4410ms 4180ms\nmaster vs HEAD~50000: 4412ms 4494ms\n\n\nThe improvement depends on how wide the frontier gets during the walk.\nComponent imports in the monorepo create wide frontiers where the queue\ngrows large, making the O(n) scan expensive -- up to 2.5x speedup for\nmerge-base and 2.4x for ahead-behind. Linear history and simple merges show\nno regression.\n\nWith a very narrow frontier the counter approach adds a small constant\noverhead per iteration (maintaining the counter and the ENQUEUED flag)\ncompared to the old scan which would return almost immediately. Both are\nO(1) and cheap in that scenario, so it should not matter in practice -- the\nbenchmark numbers above confirm this.\n\nKristofer Karlsson (3):\n commit-reach: deduplicate queue entries in paint_down_to_common\n commit-reach: optimize queue scan in paint_down_to_common\n commit-reach: optimize queue scan in ahead_behind\n\n commit-reach.c | 58 ++++++++++++++++++++++++++++++++++++--------------\n object.h | 2 +-\n 2 files changed, 43 insertions(+), 17 deletions(-)\n\n\nbase-commit: 6a4418c36d6bad69a599044b3cf49dcbd049cb45\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2124%2Fspkrka%2Fqueue-has-nonstale-v3-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2124/spkrka/queue-has-nonstale-v3-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/2124\n-- \ngitgitgadget\n"},{"id":"544006","messageId":"1d3751569ba3a5f0c353fb468578d6c5bcd0b738.1779644541.git.gitgitgadget@gmail.com","threadId":"65684","inReplyTo":"pull.2124.git.1779644541.gitgitgadget@gmail.com","subject":"[PATCH 1/3] commit-reach: deduplicate queue entries in paint_down_to_common","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-24T17:42:18Z","receivedAt":"2026-05-24T17:42:25Z","isPatch":true,"body":"From: Kristofer Karlsson \n\npaint_down_to_common() can enqueue the same commit multiple times\nwhen it is reached through different parents with different flag\ncombinations. Add an ENQUEUED flag to track whether a commit is\ncurrently in the priority queue, and skip it if already present.\n\nThis change is performance-neutral on its own: the O(n)\nqueue_has_nonstale() scan still dominates the per-iteration cost.\nHowever, the deduplication guarantee (each commit appears in the\nqueue at most once) is a prerequisite for the next commit, which\nreplaces that scan with an O(1) nonstale counter.\n\nSigned-off-by: Kristofer Karlsson \n---\n commit-reach.c | 19 +++++++++++++++----\n object.h | 2 +-\n 2 files changed, 16 insertions(+), 5 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex d3a9b3ed6f..c16d4b061c 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -17,8 +17,9 @@\n #define PARENT2\t\t(1u<<17)\n #define STALE\t\t(1u<<18)\n #define RESULT\t\t(1u<<19)\n+#define ENQUEUED\t(1u<<20)\n \n-static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);\n+static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT | ENQUEUED);\n \n static int compare_commits_by_gen(const void *_a, const void *_b)\n {\n@@ -39,6 +40,14 @@ static int compare_commits_by_gen(const void *_a, const void *_b)\n \treturn 0;\n }\n \n+static void maybe_enqueue(struct prio_queue *queue, struct commit *c)\n+{\n+\tif (c->object.flags & ENQUEUED)\n+\t\treturn;\n+\tc->object.flags |= ENQUEUED;\n+\tprio_queue_put(queue, c);\n+}\n+\n static int queue_has_nonstale(struct prio_queue *queue)\n {\n \tfor (size_t i = 0; i < queue->nr; i++) {\n@@ -70,11 +79,11 @@ static int paint_down_to_common(struct repository *r,\n \t\tcommit_list_append(one, result);\n \t\treturn 0;\n \t}\n-\tprio_queue_put(&queue, one);\n+\tmaybe_enqueue(&queue, one);\n \n \tfor (i = 0; i < n; i++) {\n \t\ttwos[i]->object.flags |= PARENT2;\n-\t\tprio_queue_put(&queue, twos[i]);\n+\t\tmaybe_enqueue(&queue, twos[i]);\n \t}\n \n \twhile (queue_has_nonstale(&queue)) {\n@@ -83,6 +92,8 @@ static int paint_down_to_common(struct repository *r,\n \t\tint flags;\n \t\ttimestamp_t generation = commit_graph_generation(commit);\n \n+\t\tcommit->object.flags &= ~ENQUEUED;\n+\n \t\tif (min_generation && generation > last_gen)\n \t\t\tBUG(\"bad generation skip %\"PRItime\" > %\"PRItime\" at %s\",\n \t\t\t generation, last_gen,\n@@ -124,7 +135,7 @@ static int paint_down_to_common(struct repository *r,\n \t\t\t\t\t oid_to_hex(&p->object.oid));\n \t\t\t}\n \t\t\tp->object.flags |= flags;\n-\t\t\tprio_queue_put(&queue, p);\n+\t\t\tmaybe_enqueue(&queue, p);\n \t\t}\n \t}\n \ndiff --git a/object.h b/object.h\nindex d814647ebe..05cbf728e9 100644\n--- a/object.h\n+++ b/object.h\n@@ -74,7 +74,7 @@ void object_array_init(struct object_array *array);\n * bundle.c: 16\n * http-push.c: 11-----14\n * commit-graph.c: 15\n- * commit-reach.c: 16-----19\n+ * commit-reach.c: 16-------20\n * builtin/last-modified.c: 1617\n * sha1-name.c: 20\n * list-objects-filter.c: 21\n-- \ngitgitgadget\n\n"},{"id":"544007","messageId":"4742f5e634b55820f3b5a626ec97e24617fdae3d.1779644541.git.gitgitgadget@gmail.com","threadId":"65684","inReplyTo":"pull.2124.git.1779644541.gitgitgadget@gmail.com","subject":"[PATCH 2/3] commit-reach: optimize queue scan in paint_down_to_common","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-24T17:42:19Z","receivedAt":"2026-05-24T17:42:28Z","isPatch":true,"body":"From: Kristofer Karlsson \n\npaint_down_to_common() terminates when every commit remaining in its\npriority queue is STALE. This was checked by queue_has_nonstale(),\nwhich performed an O(n) linear scan of the entire queue on every\niteration, resulting in O(n*m) total overhead where n is the queue\nsize and m is the number of commits processed.\n\nReplace this with an O(1) nonstale_count that tracks the number of\nnon-stale commits currently in the queue. The counter is incremented\nby maybe_enqueue() and decremented on dequeue and by mark_stale()\nwhen a commit transitions to STALE while still in the queue. Since\neach commit appears at most once (guaranteed by the ENQUEUED flag\nfrom the previous commit), the counter is exact.\n\nahead_behind() also uses queue_has_nonstale() and will be converted\nin the next commit.\n\nSigned-off-by: Kristofer Karlsson \n---\n commit-reach.c | 28 +++++++++++++++++++++++-----\n 1 file changed, 23 insertions(+), 5 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex c16d4b061c..356ff52d08 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -40,12 +40,25 @@ static int compare_commits_by_gen(const void *_a, const void *_b)\n \treturn 0;\n }\n \n-static void maybe_enqueue(struct prio_queue *queue, struct commit *c)\n+static void maybe_enqueue(struct prio_queue *queue, struct commit *c,\n+\t\t\t int *nonstale_count)\n {\n \tif (c->object.flags & ENQUEUED)\n \t\treturn;\n \tc->object.flags |= ENQUEUED;\n \tprio_queue_put(queue, c);\n+\tif (!(c->object.flags & STALE))\n+\t\t(*nonstale_count)++;\n+}\n+\n+static void mark_stale(struct commit *c, unsigned queued_flag,\n+\t\t int *nonstale_count)\n+{\n+\tif (!(c->object.flags & STALE)) {\n+\t\tif (c->object.flags & queued_flag)\n+\t\t\t(*nonstale_count)--;\n+\t\tc->object.flags |= STALE;\n+\t}\n }\n \n static int queue_has_nonstale(struct prio_queue *queue)\n@@ -68,6 +81,7 @@ static int paint_down_to_common(struct repository *r,\n {\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n \tint i;\n+\tint nonstale_count = 0;\n \ttimestamp_t last_gen = GENERATION_NUMBER_INFINITY;\n \tstruct commit_list **tail = result;\n \n@@ -79,20 +93,22 @@ static int paint_down_to_common(struct repository *r,\n \t\tcommit_list_append(one, result);\n \t\treturn 0;\n \t}\n-\tmaybe_enqueue(&queue, one);\n+\tmaybe_enqueue(&queue, one, &nonstale_count);\n \n \tfor (i = 0; i < n; i++) {\n \t\ttwos[i]->object.flags |= PARENT2;\n-\t\tmaybe_enqueue(&queue, twos[i]);\n+\t\tmaybe_enqueue(&queue, twos[i], &nonstale_count);\n \t}\n \n-\twhile (queue_has_nonstale(&queue)) {\n+\twhile (nonstale_count > 0) {\n \t\tstruct commit *commit = prio_queue_get(&queue);\n \t\tstruct commit_list *parents;\n \t\tint flags;\n \t\ttimestamp_t generation = commit_graph_generation(commit);\n \n \t\tcommit->object.flags &= ~ENQUEUED;\n+\t\tif (!(commit->object.flags & STALE))\n+\t\t\tnonstale_count--;\n \n \t\tif (min_generation && generation > last_gen)\n \t\t\tBUG(\"bad generation skip %\"PRItime\" > %\"PRItime\" at %s\",\n@@ -134,8 +150,10 @@ static int paint_down_to_common(struct repository *r,\n \t\t\t\treturn error(_(\"could not parse commit %s\"),\n \t\t\t\t\t oid_to_hex(&p->object.oid));\n \t\t\t}\n+\t\t\tif (flags & STALE)\n+\t\t\t\tmark_stale(p, ENQUEUED, &nonstale_count);\n \t\t\tp->object.flags |= flags;\n-\t\t\tmaybe_enqueue(&queue, p);\n+\t\t\tmaybe_enqueue(&queue, p, &nonstale_count);\n \t\t}\n \t}\n \n-- \ngitgitgadget\n\n"},{"id":"544008","messageId":"711a0e2235103489f17ff867439e007abd0e4291.1779644541.git.gitgitgadget@gmail.com","threadId":"65684","inReplyTo":"pull.2124.git.1779644541.gitgitgadget@gmail.com","subject":"[PATCH 3/3] commit-reach: optimize queue scan in ahead_behind","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-24T17:42:20Z","receivedAt":"2026-05-24T17:42:29Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nApply the same nonstale_count optimization from the previous commit\nto ahead_behind(). This replaces the remaining caller of the O(n)\nqueue_has_nonstale() scan with an O(1) counter check, allowing\nqueue_has_nonstale() to be removed.\n\nahead_behind() already deduplicates queue entries using the PARENT2\nflag (via insert_no_dup), so the counter is maintained through\ninsert_no_dup() and mark_stale() using PARENT2 as the queued_flag.\n\nSigned-off-by: Kristofer Karlsson \n---\n commit-reach.c | 27 ++++++++++++---------------\n 1 file changed, 12 insertions(+), 15 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 356ff52d08..41deb8fc78 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -61,16 +61,6 @@ static void mark_stale(struct commit *c, unsigned queued_flag,\n \t}\n }\n \n-static int queue_has_nonstale(struct prio_queue *queue)\n-{\n-\tfor (size_t i = 0; i < queue->nr; i++) {\n-\t\tstruct commit *commit = queue->array[i].data;\n-\t\tif (!(commit->object.flags & STALE))\n-\t\t\treturn 1;\n-\t}\n-\treturn 0;\n-}\n-\n /* all input commits in one and twos[] must have been parsed! */\n static int paint_down_to_common(struct repository *r,\n \t\t\t\tstruct commit *one, int n,\n@@ -1051,12 +1041,15 @@ struct commit_list *get_reachable_subset(struct commit **from, size_t nr_from,\n define_commit_slab(bit_arrays, struct bitmap *);\n static struct bit_arrays bit_arrays;\n \n-static void insert_no_dup(struct prio_queue *queue, struct commit *c)\n+static void insert_no_dup(struct prio_queue *queue, struct commit *c,\n+\t\t\t int *nonstale_count)\n {\n \tif (c->object.flags & PARENT2)\n \t\treturn;\n \tprio_queue_put(queue, c);\n \tc->object.flags |= PARENT2;\n+\tif (!(c->object.flags & STALE))\n+\t\t(*nonstale_count)++;\n }\n \n static struct bitmap *get_bit_array(struct commit *c, int width)\n@@ -1082,6 +1075,7 @@ void ahead_behind(struct repository *r,\n {\n \tstruct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };\n \tsize_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);\n+\tint nonstale_count = 0;\n \n \tif (!commits_nr || !counts_nr)\n \t\treturn;\n@@ -1100,14 +1094,17 @@ void ahead_behind(struct repository *r,\n \t\tstruct bitmap *bitmap = get_bit_array(c, width);\n \n \t\tbitmap_set(bitmap, i);\n-\t\tinsert_no_dup(&queue, c);\n+\t\tinsert_no_dup(&queue, c, &nonstale_count);\n \t}\n \n-\twhile (queue_has_nonstale(&queue)) {\n+\twhile (nonstale_count > 0) {\n \t\tstruct commit *c = prio_queue_get(&queue);\n \t\tstruct commit_list *p;\n \t\tstruct bitmap *bitmap_c = get_bit_array(c, width);\n \n+\t\tif (!(c->object.flags & STALE))\n+\t\t\tnonstale_count--;\n+\n \t\tfor (size_t i = 0; i < counts_nr; i++) {\n \t\t\tint reach_from_tip = !!bitmap_get(bitmap_c, counts[i].tip_index);\n \t\t\tint reach_from_base = !!bitmap_get(bitmap_c, counts[i].base_index);\n@@ -1136,9 +1133,9 @@ void ahead_behind(struct repository *r,\n \t\t\t * queue is STALE.\n \t\t\t */\n \t\t\tif (bitmap_popcount(bitmap_p) == commits_nr)\n-\t\t\t\tp->item->object.flags |= STALE;\n+\t\t\t\tmark_stale(p->item, PARENT2, &nonstale_count);\n \n-\t\t\tinsert_no_dup(&queue, p->item);\n+\t\t\tinsert_no_dup(&queue, p->item, &nonstale_count);\n \t\t}\n \n \t\tfree_bit_array(c);\n-- \ngitgitgadget\n"},{"id":"544015","messageId":"xmqqpl2kgyvy.fsf@gitster.g","threadId":"65684","inReplyTo":"1d3751569ba3a5f0c353fb468578d6c5bcd0b738.1779644541.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/3] commit-reach: deduplicate queue entries in paint_down_to_common","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-05-24T23:40:17Z","receivedAt":"2026-05-24T23:40:19Z","isPatch":true,"body":"\"Kristofer Karlsson via GitGitGadget\" \nwrites:\n\n> diff --git a/commit-reach.c b/commit-reach.c\n> index d3a9b3ed6f..c16d4b061c 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -17,8 +17,9 @@\n> #define PARENT2\t\t(1u<<17)\n> #define STALE\t\t(1u<<18)\n> #define RESULT\t\t(1u<<19)\n> +#define ENQUEUED\t(1u<<20)\n> \n> -static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);\n> +static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT | ENQUEUED);\n> ...\n> diff --git a/object.h b/object.h\n> index d814647ebe..05cbf728e9 100644\n> --- a/object.h\n> +++ b/object.h\n> @@ -74,7 +74,7 @@ void object_array_init(struct object_array *array);\n> * bundle.c: 16\n> * http-push.c: 11-----14\n> * commit-graph.c: 15\n> - * commit-reach.c: 16-----19\n> + * commit-reach.c: 16-------20\n> * builtin/last-modified.c: 1617\n> * sha1-name.c: 20\n> * list-objects-filter.c: 21\n\nNot directly the fault of this series, but we'd need to audit and\nupdate this table of bit assignment to match more recent reality.\n\nFor example, there no longer exists sha1-name.c but the table claims\nthat bit 20 is in use for its own purpose, and it being stale makes\nit harder to audit and ensure that this new use would not crash with\nthese existing uses (note. there are other uses of bit 20 in other\nsubsystems).\n\nFWIW, object-name.c, which was formerly known as sha1-name.c, uses\nthe bit 20 as ONELINE_SEEN bit, which is used to turn textual object\nnames like :/string (i.e., commit with that string in its message)\ninto raw object name, and bit 20 is cleared from all the objects\ninvolved in the search before the helper function returns.\nPresumably, once commit-reach.c starts queueing commits and reuses\nthis bit for its own purpose, we will never try to parse a textual\ncommit object name to clobber what we thought is ENQUEUED bit,\nbreaking the code introduced here, so we are probably safe against\nits use.\n\nI didn't check all other uses of bit 20, though.\n\n"},{"id":"544020","messageId":"ca39c8ca-ca4c-4954-a1ab-633bfa55f64b@gmail.com","threadId":"65684","inReplyTo":"xmqqpl2kgyvy.fsf@gitster.g","subject":"Re: [PATCH 1/3] commit-reach: deduplicate queue entries in paint_down_to_common","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-05-25T01:43:06Z","receivedAt":"2026-05-25T01:43:09Z","isPatch":true,"body":"On 5/24/26 7:40 PM, Junio C Hamano wrote:\n> \"Kristofer Karlsson via GitGitGadget\" \n> writes:\n> \n>> diff --git a/commit-reach.c b/commit-reach.c\n>> index d3a9b3ed6f..c16d4b061c 100644\n>> --- a/commit-reach.c\n>> +++ b/commit-reach.c\n>> @@ -17,8 +17,9 @@\n>> #define PARENT2\t\t(1u<<17)\n>> #define STALE\t\t(1u<<18)\n>> #define RESULT\t\t(1u<<19)\n>> +#define ENQUEUED\t(1u<<20)\n>> \n>> -static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);\n>> +static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT | ENQUEUED);\n>> ...\n>> diff --git a/object.h b/object.h\n>> index d814647ebe..05cbf728e9 100644\n>> --- a/object.h\n>> +++ b/object.h\n>> @@ -74,7 +74,7 @@ void object_array_init(struct object_array *array);\n>> * bundle.c: 16\n>> * http-push.c: 11-----14\n>> * commit-graph.c: 15\n>> - * commit-reach.c: 16-----19\n>> + * commit-reach.c: 16-------20\n>> * builtin/last-modified.c: 1617\n>> * sha1-name.c: 20\n>> * list-objects-filter.c: 21\n> \n> Not directly the fault of this series, but we'd need to audit and\n> update this table of bit assignment to match more recent reality.\n> \n> For example, there no longer exists sha1-name.c but the table claims\n> that bit 20 is in use for its own purpose, and it being stale makes\n> it harder to audit and ensure that this new use would not crash with\n> these existing uses (note. there are other uses of bit 20 in other\n> subsystems).\n\nIt would be worth adding an update patch before this patch, that\nonly makes these adjustments\n\n> FWIW, object-name.c, which was formerly known as sha1-name.c, uses\n> the bit 20 as ONELINE_SEEN bit, which is used to turn textual object\n> names like :/string (i.e., commit with that string in its message)\n> into raw object name, and bit 20 is cleared from all the objects\n> involved in the search before the helper function returns.\n\nThis appears to me like the only interaction that _could_ have\noverlap with paint_down_to_common().\n\n> Presumably, once commit-reach.c starts queueing commits and reuses\n> this bit for its own purpose, we will never try to parse a textual\n> commit object name to clobber what we thought is ENQUEUED bit,\n> breaking the code introduced here, so we are probably safe against\n> its use.\n> \n> I didn't check all other uses of bit 20, though.\n\nFLAG_LINK in builtin/index-pack.c and FLAG_OPEN in\nbuiltin/unpack-objects.c both seem to be completely independent from\nthis use in commit-reach.c.\n\nThanks,\n-Stolee\n\n\n\n"},{"id":"544021","messageId":"42aef000-7952-482d-8532-2287cf32b275@gmail.com","threadId":"65684","inReplyTo":"4742f5e634b55820f3b5a626ec97e24617fdae3d.1779644541.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 2/3] commit-reach: optimize queue scan in paint_down_to_common","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-05-25T01:59:53Z","receivedAt":"2026-05-25T01:59:57Z","isPatch":true,"body":"On 5/24/26 1:42 PM, Kristofer Karlsson via GitGitGadget wrote:\n> From: Kristofer Karlsson \n> \n> paint_down_to_common() terminates when every commit remaining in its\n> priority queue is STALE. This was checked by queue_has_nonstale(),\n> which performed an O(n) linear scan of the entire queue on every\n> iteration, resulting in O(n*m) total overhead where n is the queue\n> size and m is the number of commits processed.\n> \n> Replace this with an O(1) nonstale_count that tracks the number of\n> non-stale commits currently in the queue. The counter is incremented\n> by maybe_enqueue() and decremented on dequeue and by mark_stale()\n> when a commit transitions to STALE while still in the queue. Since\n> each commit appears at most once (guaranteed by the ENQUEUED flag\n> from the previous commit), the counter is exact.\n\nThis idea has a lot of merit, but I'm a bit concerned about the\norganization of data. My ideas of how to improve things may also\nimpact patch 1's use of ENQUEUED.\n\n> -static void maybe_enqueue(struct prio_queue *queue, struct commit *c)\n> +static void maybe_enqueue(struct prio_queue *queue, struct commit *c,\n> +\t\t\t int *nonstale_count)\n> {\n> \tif (c->object.flags & ENQUEUED)\n> \t\treturn;\n> \tc->object.flags |= ENQUEUED;\n> \tprio_queue_put(queue, c);\n> +\tif (!(c->object.flags & STALE))\n> +\t\t(*nonstale_count)++;\n> +}\n> +\n> +static void mark_stale(struct commit *c, unsigned queued_flag,\n> +\t\t int *nonstale_count)\n> +{\n> +\tif (!(c->object.flags & STALE)) {\n> +\t\tif (c->object.flags & queued_flag)\n> +\t\t\t(*nonstale_count)--;\n> +\t\tc->object.flags |= STALE;\n> +\t}\n> }\n\nThese two methods have some concerns on my end:\n\n1. We need to store the nonstale count somewhere other than the\n priority queue, even though it's necessarily representing a\n subset of the commits within the queue.\n\n2. mark_stale() needs a queued_flag. (I need to check to see if\n this is indeed changing in multiple callers or should always\n be ENQUEUED).\n\n> static int queue_has_nonstale(struct prio_queue *queue)\n> @@ -68,6 +81,7 @@ static int paint_down_to_common(struct repository *r,\n> {\n> \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n> \tint i;\n> +\tint nonstale_count = 0;\n\nMy preference would be to create a new struct that contains a\nprio_queue as a member _and_ a nonstale_count. It could initialize\nwith compare_commits_by_gen_then_commit_date by default.\n\nThe important thing is that consumers of such a \"stale-tracking\"\nqueue would not be setting the STALE or ENQUEUED bits themselves,\nbut instead the queue would be responsible for that.\n\nThis could allow us to simplify callers by always assuming we can\n\"add\" an element to the queue and the queue will use its ENQUEUED\nbit to prevent duplicates from reaching its internal prio_queue.\n\nSuch a data structure could be private to commit-reach.c for now,\nsince all the methods that would use it seem to be colocated there.\n\nThis is a big ask, but I'm interested to see if such an approach\nwould simplify things here.\n\nHere's a potential breakdown of how to build such a thing in\n\"small\" patches:\n\n1. Create the data structure and update paint_down_to_common and\n ahead_behind to use that structure, but still use the existing\n prio_queue methods on its internal member.\n\n2. Add the ENQUEUED bit and methods on the new struct that add\n that bit as it adds commits to the inner prio_queue. It would\n also ignore commits that already have that bit. (Should it\n also remove the bit as commits are removed from the queue?)\n\n3. Now add the nonstale_count (or stale count?) to the struct and\n have it control the STALE bit modifications, with increasing\n the stale count when ENQUEUED is live, and decreasing the stale\n count as such a STALE object is dequeued.\n\nI like the idea of this being encapsulated within the struct and\nits helper methods. But the proof will be in the implementation.\n\nThanks,\n-Stolee\n\n"},{"id":"544033","messageId":"20260525064755.GA2737798@coredump.intra.peff.net","threadId":"65684","inReplyTo":"pull.2124.git.1779644541.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/3] commit-reach: replace queue_has_nonstale with a counter","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-25T06:47:55Z","receivedAt":"2026-05-25T06:48:03Z","isPatch":true,"body":"On Sun, May 24, 2026 at 05:42:17PM +0000, Kristofer Karlsson via GitGitGadget wrote:\n\n> paint_down_to_common() and ahead_behind() terminate when every commit in\n> their priority queue is STALE. The current check, queue_has_nonstale(), does\n> an O(n) linear scan of the queue on every iteration, costing O(n*m) total\n> where n is the queue size and m is the number of commits processed. This\n> series replaces that scan with an O(1) counter.\n\nWe faced a similar problem in limit_list() but solved it a bit\ndifferently (mostly because I was worried about keeping the counter up\nto date in all cases).\n\nIt's described in more detail in b6e8a3b540 (limit_list: avoid quadratic\nbehavior from still_interesting, 2015-04-17), but the general idea is to\njust cache the interesting element we found, and invalidate the cache\nwhen it gets removed from the queue or gets marked UNINTERESTING.\n\nThe equivalent code for the STALE flag here is something like this:\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex d3a9b3ed6f..d1621be89f 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -39,12 +39,25 @@ static int compare_commits_by_gen(const void *_a, const void *_b)\n \treturn 0;\n }\n \n-static int queue_has_nonstale(struct prio_queue *queue)\n+static int queue_has_nonstale(struct prio_queue *queue,\n+\t\t\t struct commit **nonstale_cache)\n {\n+\tif (*nonstale_cache) {\n+\t\tstruct commit *commit = *nonstale_cache;\n+\t\tif (!(commit->object.flags & STALE))\n+\t\t\treturn 1;\n+\t}\n+\n+\t/*\n+\t * This might also benefit from looking back-to-front, since\n+\t * earlier commits are more likely to get popped sooner.\n+\t */\n \tfor (size_t i = 0; i < queue->nr; i++) {\n \t\tstruct commit *commit = queue->array[i].data;\n-\t\tif (!(commit->object.flags & STALE))\n+\t\tif (!(commit->object.flags & STALE)) {\n+\t\t\t*nonstale_cache = commit;\n \t\t\treturn 1;\n+\t\t}\n \t}\n \treturn 0;\n }\n@@ -61,6 +74,7 @@ static int paint_down_to_common(struct repository *r,\n \tint i;\n \ttimestamp_t last_gen = GENERATION_NUMBER_INFINITY;\n \tstruct commit_list **tail = result;\n+\tstruct commit *nonstale_cache = NULL;\n \n \tif (!min_generation && !corrected_commit_dates_enabled(r))\n \t\tqueue.compare = compare_commits_by_commit_date;\n@@ -77,12 +91,15 @@ static int paint_down_to_common(struct repository *r,\n \t\tprio_queue_put(&queue, twos[i]);\n \t}\n \n-\twhile (queue_has_nonstale(&queue)) {\n+\twhile (queue_has_nonstale(&queue, &nonstale_cache)) {\n \t\tstruct commit *commit = prio_queue_get(&queue);\n \t\tstruct commit_list *parents;\n \t\tint flags;\n \t\ttimestamp_t generation = commit_graph_generation(commit);\n \n+\t\tif (nonstale_cache == commit)\n+\t\t\tnonstale_cache = NULL;\n+\n \t\tif (min_generation && generation > last_gen)\n \t\t\tBUG(\"bad generation skip %\"PRItime\" > %\"PRItime\" at %s\",\n \t\t\t generation, last_gen,\n@@ -1053,6 +1070,7 @@ void ahead_behind(struct repository *r,\n {\n \tstruct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };\n \tsize_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);\n+\tstruct commit *nonstale_cache = NULL;\n \n \tif (!commits_nr || !counts_nr)\n \t\treturn;\n@@ -1074,11 +1092,14 @@ void ahead_behind(struct repository *r,\n \t\tinsert_no_dup(&queue, c);\n \t}\n \n-\twhile (queue_has_nonstale(&queue)) {\n+\twhile (queue_has_nonstale(&queue, &nonstale_cache)) {\n \t\tstruct commit *c = prio_queue_get(&queue);\n \t\tstruct commit_list *p;\n \t\tstruct bitmap *bitmap_c = get_bit_array(c, width);\n \n+\t\tif (c == nonstale_cache)\n+\t\t\tnonstale_cache = NULL;\n+\n \t\tfor (size_t i = 0; i < counts_nr; i++) {\n \t\t\tint reach_from_tip = !!bitmap_get(bitmap_c, counts[i].tip_index);\n \t\t\tint reach_from_base = !!bitmap_get(bitmap_c, counts[i].base_index);\n\n\nI don't have a repo handy which reproduces the problem, so I can't see\nif it improves things. But if it's easy to do, can you report on the\ntiming change with your monorepo?\n\nI do think what I've shown here is a bit hacky (just like the\nlimit_list() one), as we are relying on heuristics about the order in\nwhich items are taken from the queue. So even if it performs well, we\nmay still prefer the counter version for being truly O(1). But having\ntiming numbers would be useful for comparing the two approaches.\n\n-Peff\n"},{"id":"544034","messageId":"CAL71e4NxpbM8QZYhVA_SSC4vDmAFv-Kpe6qDcurefgPkSSdSnQ@mail.gmail.com","threadId":"65684","inReplyTo":"ca39c8ca-ca4c-4954-a1ab-633bfa55f64b@gmail.com","subject":"Re: [PATCH 1/3] commit-reach: deduplicate queue entries in paint_down_to_common","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-05-25T06:50:11Z","receivedAt":"2026-05-25T06:50:26Z","isPatch":true,"body":"I ran an audit of the flag allocation table and found three stale entries:\n\n1. sha1-name.c was renamed to object-name.c.\n2. builtin/show-branch.c uses bits 0 and 2-28, not 0-26.\n3. negotiator/skipping.c is missing — it uses bits 2-5 like\nnegotiator/default.c, with ADVERTISED on bit 3 instead of\nCOMMON_REF.\n\nI have a fixup commit ready - mini-preview below. I can submit\nit on top of this patchset or create a separate patch if you prefer that?\n\n+ * negotiator/skipping.c: 2--5\n- * sha1-name.c: 20\n+ * object-name.c: 20\n- * builtin/show-branch.c: 0-------------------------------------------26\n+ * builtin/show-branch.c: 0-----------------------------------------------28\n\nWhile doing the audit I noticed that reasoning about flag safety is\ncurrently entirely manual. Would there be interest in something more\nsystematic (e.g. runtime registration/assertion, dynamic allocation or static\nanalysis of flag usage)? I have some local work on that already, but I was\nnot sure if this was something worth spending time on or not.\n\n- Kristofer\n\n\nOn Mon, 25 May 2026 at 03:43, Derrick Stolee wrote:\n>\n> On 5/24/26 7:40 PM, Junio C Hamano wrote:\n> > \"Kristofer Karlsson via GitGitGadget\" \n> > writes:\n> >\n> >> diff --git a/commit-reach.c b/commit-reach.c\n> >> index d3a9b3ed6f..c16d4b061c 100644\n> >> --- a/commit-reach.c\n> >> +++ b/commit-reach.c\n> >> @@ -17,8 +17,9 @@\n> >> #define PARENT2 (1u<<17)\n> >> #define STALE (1u<<18)\n> >> #define RESULT (1u<<19)\n> >> +#define ENQUEUED (1u<<20)\n> >>\n> >> -static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);\n> >> +static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT | ENQUEUED);\n> >> ...\n> >> diff --git a/object.h b/object.h\n> >> index d814647ebe..05cbf728e9 100644\n> >> --- a/object.h\n> >> +++ b/object.h\n> >> @@ -74,7 +74,7 @@ void object_array_init(struct object_array *array);\n> >> * bundle.c: 16\n> >> * http-push.c: 11-----14\n> >> * commit-graph.c: 15\n> >> - * commit-reach.c: 16-----19\n> >> + * commit-reach.c: 16-------20\n> >> * builtin/last-modified.c: 1617\n> >> * sha1-name.c: 20\n> >> * list-objects-filter.c: 21\n> >\n> > Not directly the fault of this series, but we'd need to audit and\n> > update this table of bit assignment to match more recent reality.\n> >\n> > For example, there no longer exists sha1-name.c but the table claims\n> > that bit 20 is in use for its own purpose, and it being stale makes\n> > it harder to audit and ensure that this new use would not crash with\n> > these existing uses (note. there are other uses of bit 20 in other\n> > subsystems).\n>\n> It would be worth adding an update patch before this patch, that\n> only makes these adjustments\n>\n> > FWIW, object-name.c, which was formerly known as sha1-name.c, uses\n> > the bit 20 as ONELINE_SEEN bit, which is used to turn textual object\n> > names like :/string (i.e., commit with that string in its message)\n> > into raw object name, and bit 20 is cleared from all the objects\n> > involved in the search before the helper function returns.\n>\n> This appears to me like the only interaction that _could_ have\n> overlap with paint_down_to_common().\n>\n> > Presumably, once commit-reach.c starts queueing commits and reuses\n> > this bit for its own purpose, we will never try to parse a textual\n> > commit object name to clobber what we thought is ENQUEUED bit,\n> > breaking the code introduced here, so we are probably safe against\n> > its use.\n> >\n> > I didn't check all other uses of bit 20, though.\n>\n> FLAG_LINK in builtin/index-pack.c and FLAG_OPEN in\n> builtin/unpack-objects.c both seem to be completely independent from\n> this use in commit-reach.c.\n>\n> Thanks,\n> -Stolee\n>\n>\n>\n"},{"id":"544036","messageId":"20260525070114.GB2737798@coredump.intra.peff.net","threadId":"65684","inReplyTo":"1d3751569ba3a5f0c353fb468578d6c5bcd0b738.1779644541.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/3] commit-reach: deduplicate queue entries in paint_down_to_common","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-25T07:01:14Z","receivedAt":"2026-05-25T07:01:17Z","isPatch":true,"body":"On Sun, May 24, 2026 at 05:42:18PM +0000, Kristofer Karlsson via GitGitGadget wrote:\n\n> +static void maybe_enqueue(struct prio_queue *queue, struct commit *c)\n> +{\n> +\tif (c->object.flags & ENQUEUED)\n> +\t\treturn;\n> +\tc->object.flags |= ENQUEUED;\n> +\tprio_queue_put(queue, c);\n> +}\n\nOK, so we mark each commit with ENQUEUED when we queue it, and then...\n\n> @@ -83,6 +92,8 @@ static int paint_down_to_common(struct repository *r,\n> \t\tint flags;\n> \t\ttimestamp_t generation = commit_graph_generation(commit);\n> \n> +\t\tcommit->object.flags &= ~ENQUEUED;\n> +\n\n...clear that when we pop it. But the loop may terminate early before\npopping everything, and we get to this cleanup code at the end:\n\n\tclear_prio_queue(&queue);\n\nWhen we drop all of those queue elements, they'll all be left with the\nENQUEUED flag set. Should we clear those?\n\nThe ahead_behind() variant doesn't have the same problem, because it\nuses PARENT2 to check for queueing, and then does:\n\n\t/* STALE is used here, PARENT2 is used by insert_no_dup(). */\n\trepo_clear_commit_marks(r, PARENT2 | STALE);\n\nSo it's cleaning up both flags, whereas paint_down_to_common() is\nalready leaving the STALE flag set. I'm not sure how much that matters\n(or if it is even an intentional thing communicated to the caller). But\nnow we'd be adding ENQUEUED.\n\n-Peff\n"},{"id":"544037","messageId":"20260525071150.GC2737798@coredump.intra.peff.net","threadId":"65684","inReplyTo":"711a0e2235103489f17ff867439e007abd0e4291.1779644541.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 3/3] commit-reach: optimize queue scan in ahead_behind","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-25T07:11:50Z","receivedAt":"2026-05-25T07:11:51Z","isPatch":true,"body":"On Sun, May 24, 2026 at 05:42:20PM +0000, Kristofer Karlsson via GitGitGadget wrote:\n\n> ahead_behind() already deduplicates queue entries using the PARENT2\n> flag (via insert_no_dup), so the counter is maintained through\n> insert_no_dup() and mark_stale() using PARENT2 as the queued_flag.\n\nThat makes sense, but it does raise one question: since we do not clear\nthe PARENT2 flag upon popping, is it possible to consider a commit a\nsecond time, after it has been popped?\n\nI suspect the answer is \"yes\", if you have commits with out-of-order\ndates (so we visit X, which has PARENT2 set, and then later visit its\ndescendant, and try to add X again as a parent).\n\nI guess your counter does not make anything worse, though, because the\nsame PARENT2 flag that prevents us from incrementing the counter also\nprevents us from actually adding it to the queue again.\n\nAnd I think the current code is OK because we do not care about\nde-duping the queue, but about not double-counting commits in the global\nspace. So PARENT2 effectively acts as a \"seen\" flag here.\n\n-Peff\n"},{"id":"544038","messageId":"20260525071545.GD2737798@coredump.intra.peff.net","threadId":"65684","inReplyTo":"20260525070114.GB2737798@coredump.intra.peff.net","subject":"Re: [PATCH 1/3] commit-reach: deduplicate queue entries in paint_down_to_common","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-25T07:15:45Z","receivedAt":"2026-05-25T07:15:47Z","isPatch":true,"body":"On Mon, May 25, 2026 at 03:01:14AM -0400, Jeff King wrote:\n\n> When we drop all of those queue elements, they'll all be left with the\n> ENQUEUED flag set. Should we clear those?\n> \n> The ahead_behind() variant doesn't have the same problem, because it\n> uses PARENT2 to check for queueing, and then does:\n> \n> \t/* STALE is used here, PARENT2 is used by insert_no_dup(). */\n> \trepo_clear_commit_marks(r, PARENT2 | STALE);\n> \n> So it's cleaning up both flags, whereas paint_down_to_common() is\n> already leaving the STALE flag set. I'm not sure how much that matters\n> (or if it is even an intentional thing communicated to the caller). But\n> now we'd be adding ENQUEUED.\n\nAh, hmm. We do clear flags in the callers using clear_commit_marks(),\nwhich walks down parent pointers until nobody has a flag we care about\n(from all_flags). I'm not 100% sure that ENQUEUED flags will always be\ncaught that way, but I think the reasoning is roughly: every thing we\nqueue will either have PARENT1 or PARENT2 set, so we'll keep walking and\nclearing flags until we stop seeing those.\n\n-Peff\n"},{"id":"544039","messageId":"xmqqse7gez5l.fsf@gitster.g","threadId":"65684","inReplyTo":"CAL71e4NxpbM8QZYhVA_SSC4vDmAFv-Kpe6qDcurefgPkSSdSnQ@mail.gmail.com","subject":"Re: [PATCH 1/3] commit-reach: deduplicate queue entries in paint_down_to_common","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-05-25T07:17:26Z","receivedAt":"2026-05-25T07:17:29Z","isPatch":true,"body":"Kristofer Karlsson writes:\n\n> While doing the audit I noticed that reasoning about flag safety is\n> currently entirely manual. Would there be interest in something more\n> systematic (e.g. runtime registration/assertion, dynamic allocation or static\n> analysis of flag usage)? I have some local work on that already, but I was\n> not sure if this was something worth spending time on or not.\n\nIf there weren't existing code that are so tied to their current\nuses of fixed flag bits and assumption that nobody else uses these\nbits outside their intended use, I'd love to have any of these.\nUncolliding and unbounded number of usable bits per object that are\n*fast* to access would be good (and commit-slab was an attempt to\nintroduce a framework that can be used as the basis for such a\nsystem). Independent of that, if we can statically analyze the uses\nof these bits to prove that the same flag bits are never used at the\nsame time for colliding purposes, that would really be valuable.\n"},{"id":"544042","messageId":"CAL71e4ODJeCJctKg=3o9PKD6Rw3_xHnrjc+zT_MYFc=CdNc59A@mail.gmail.com","threadId":"65684","inReplyTo":"xmqqse7gez5l.fsf@gitster.g","subject":"Re: [PATCH 1/3] commit-reach: deduplicate queue entries in paint_down_to_common","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-05-25T07:53:09Z","receivedAt":"2026-05-25T07:53:22Z","isPatch":true,"body":"Good catch Jeff! I think it's possible that I missed the flag cleanup case\nhere, but it's also possible that I got lucky and it worked anyway.\nThat said, I think the observation in the other email thread/commit is key\nhere. I will reply back in that one, but it seems like this can all be\nsimplified using Jeff's idea with an amortized O(1) solution by caching a\nknown non-stale entry in the queue, and thus becomes obsolete. I will post\na new patchset when the discussion slows down.\n\nAs for general flag management, I will spend some more time thinking about it.\nI don't fully trust static code analysis to work, but some cheap assertion\nbased model might give a nice trade-off.\n\nThanks for all the feedback!\n- Kristofer\n\nOn Mon, 25 May 2026 at 09:17, Junio C Hamano wrote:\n>\n> Kristofer Karlsson writes:\n>\n> > While doing the audit I noticed that reasoning about flag safety is\n> > currently entirely manual. Would there be interest in something more\n> > systematic (e.g. runtime registration/assertion, dynamic allocation or static\n> > analysis of flag usage)? I have some local work on that already, but I was\n> > not sure if this was something worth spending time on or not.\n>\n> If there weren't existing code that are so tied to their current\n> uses of fixed flag bits and assumption that nobody else uses these\n> bits outside their intended use, I'd love to have any of these.\n> Uncolliding and unbounded number of usable bits per object that are\n> *fast* to access would be good (and commit-slab was an attempt to\n> introduce a framework that can be used as the basis for such a\n> system). Independent of that, if we can statically analyze the uses\n> of these bits to prove that the same flag bits are never used at the\n> same time for colliding purposes, that would really be valuable.\n"},{"id":"544043","messageId":"CAL71e4MOH2iPve19dKixLHSgpC3ZAZz59zLWEWRoxW1a7vhMwg@mail.gmail.com","threadId":"65684","inReplyTo":"20260525064755.GA2737798@coredump.intra.peff.net","subject":"Re: [PATCH 0/3] commit-reach: replace queue_has_nonstale with a counter","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-05-25T07:59:59Z","receivedAt":"2026-05-25T08:00:12Z","isPatch":true,"body":"That's an excellent approach! Much cleaner in general.\n\nI benchmarked it against the counter on a monorepo with wide-frontier DAGs\n(2.4M commits, component import merges). Using merge-base --all to bypass\nthe early-exit optimization from kk/paint-down-to-common-optim:\n\n Baseline Cache Counter\n import(A) 8079ms 3686ms 3723ms\n import(B) 5498ms 3993ms 4038ms\n import(C) 4350ms 1748ms 1766ms\n\nThe cache performs on par with the counter - within noise on all three\ncases. No new flags needed, much simpler diff.\nThe amortized O(1) is just as good as true O(1) in practice, and it avoids\nthe ENQUEUED flag and counter bookkeeping entirely.\n\nI went with back-to-front scanning as you suggested, and also clear\nthe cache when the cached entry goes stale. Applied to both\npaint_down_to_common and ahead_behind.\n\nI can rewrite the patchset with this approach and add you as co-author or\nsuggested-by? Or I think I can wait for you to push it yourself.\nYou did all the work here, and just didn't have enough data points to\nmotivate it?\n\n- Kristofer\n\nOn Mon, 25 May 2026 at 08:47, Jeff King wrote:\n>\n> On Sun, May 24, 2026 at 05:42:17PM +0000, Kristofer Karlsson via GitGitGadget wrote:\n>\n> > paint_down_to_common() and ahead_behind() terminate when every commit in\n> > their priority queue is STALE. The current check, queue_has_nonstale(), does\n> > an O(n) linear scan of the queue on every iteration, costing O(n*m) total\n> > where n is the queue size and m is the number of commits processed. This\n> > series replaces that scan with an O(1) counter.\n>\n> We faced a similar problem in limit_list() but solved it a bit\n> differently (mostly because I was worried about keeping the counter up\n> to date in all cases).\n>\n> It's described in more detail in b6e8a3b540 (limit_list: avoid quadratic\n> behavior from still_interesting, 2015-04-17), but the general idea is to\n> just cache the interesting element we found, and invalidate the cache\n> when it gets removed from the queue or gets marked UNINTERESTING.\n>\n> The equivalent code for the STALE flag here is something like this:\n>\n> diff --git a/commit-reach.c b/commit-reach.c\n> index d3a9b3ed6f..d1621be89f 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -39,12 +39,25 @@ static int compare_commits_by_gen(const void *_a, const void *_b)\n> return 0;\n> }\n>\n> -static int queue_has_nonstale(struct prio_queue *queue)\n> +static int queue_has_nonstale(struct prio_queue *queue,\n> + struct commit **nonstale_cache)\n> {\n> + if (*nonstale_cache) {\n> + struct commit *commit = *nonstale_cache;\n> + if (!(commit->object.flags & STALE))\n> + return 1;\n> + }\n> +\n> + /*\n> + * This might also benefit from looking back-to-front, since\n> + * earlier commits are more likely to get popped sooner.\n> + */\n> for (size_t i = 0; i < queue->nr; i++) {\n> struct commit *commit = queue->array[i].data;\n> - if (!(commit->object.flags & STALE))\n> + if (!(commit->object.flags & STALE)) {\n> + *nonstale_cache = commit;\n> return 1;\n> + }\n> }\n> return 0;\n> }\n> @@ -61,6 +74,7 @@ static int paint_down_to_common(struct repository *r,\n> int i;\n> timestamp_t last_gen = GENERATION_NUMBER_INFINITY;\n> struct commit_list **tail = result;\n> + struct commit *nonstale_cache = NULL;\n>\n> if (!min_generation && !corrected_commit_dates_enabled(r))\n> queue.compare = compare_commits_by_commit_date;\n> @@ -77,12 +91,15 @@ static int paint_down_to_common(struct repository *r,\n> prio_queue_put(&queue, twos[i]);\n> }\n>\n> - while (queue_has_nonstale(&queue)) {\n> + while (queue_has_nonstale(&queue, &nonstale_cache)) {\n> struct commit *commit = prio_queue_get(&queue);\n> struct commit_list *parents;\n> int flags;\n> timestamp_t generation = commit_graph_generation(commit);\n>\n> + if (nonstale_cache == commit)\n> + nonstale_cache = NULL;\n> +\n> if (min_generation && generation > last_gen)\n> BUG(\"bad generation skip %\"PRItime\" > %\"PRItime\" at %s\",\n> generation, last_gen,\n> @@ -1053,6 +1070,7 @@ void ahead_behind(struct repository *r,\n> {\n> struct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };\n> size_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);\n> + struct commit *nonstale_cache = NULL;\n>\n> if (!commits_nr || !counts_nr)\n> return;\n> @@ -1074,11 +1092,14 @@ void ahead_behind(struct repository *r,\n> insert_no_dup(&queue, c);\n> }\n>\n> - while (queue_has_nonstale(&queue)) {\n> + while (queue_has_nonstale(&queue, &nonstale_cache)) {\n> struct commit *c = prio_queue_get(&queue);\n> struct commit_list *p;\n> struct bitmap *bitmap_c = get_bit_array(c, width);\n>\n> + if (c == nonstale_cache)\n> + nonstale_cache = NULL;\n> +\n> for (size_t i = 0; i < counts_nr; i++) {\n> int reach_from_tip = !!bitmap_get(bitmap_c, counts[i].tip_index);\n> int reach_from_base = !!bitmap_get(bitmap_c, counts[i].base_index);\n>\n>\n> I don't have a repo handy which reproduces the problem, so I can't see\n> if it improves things. But if it's easy to do, can you report on the\n> timing change with your monorepo?\n>\n> I do think what I've shown here is a bit hacky (just like the\n> limit_list() one), as we are relying on heuristics about the order in\n> which items are taken from the queue. So even if it performs well, we\n> may still prefer the counter version for being truly O(1). But having\n> timing numbers would be useful for comparing the two approaches.\n>\n> -Peff\n"},{"id":"544045","messageId":"xmqqfr3fg9z6.fsf@gitster.g","threadId":"65684","inReplyTo":"CAL71e4MOH2iPve19dKixLHSgpC3ZAZz59zLWEWRoxW1a7vhMwg@mail.gmail.com","subject":"Re: [PATCH 0/3] commit-reach: replace queue_has_nonstale with a counter","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-05-25T08:38:21Z","receivedAt":"2026-05-25T08:38:23Z","isPatch":true,"body":"Kristofer Karlsson writes:\n\n> That's an excellent approach! Much cleaner in general.\n>\n> I benchmarked it against the counter on a monorepo with wide-frontier DAGs\n> (2.4M commits, component import merges). Using merge-base --all to bypass\n> the early-exit optimization from kk/paint-down-to-common-optim:\n>\n> Baseline Cache Counter\n> import(A) 8079ms 3686ms 3723ms\n> import(B) 5498ms 3993ms 4038ms\n> import(C) 4350ms 1748ms 1766ms\n>\n> The cache performs on par with the counter - within noise on all three\n> cases. No new flags needed, much simpler diff.\n> The amortized O(1) is just as good as true O(1) in practice, and it avoids\n> the ENQUEUED flag and counter bookkeeping entirely.\n\nNice.\n\n> I went with back-to-front scanning as you suggested, and also clear\n> the cache when the cached entry goes stale. Applied to both\n> paint_down_to_common and ahead_behind.\n>\n> I can rewrite the patchset with this approach and add you as co-author or\n> suggested-by? Or I think I can wait for you to push it yourself.\n> You did all the work here, and just didn't have enough data points to\n> motivate it?\n\nI can take from either of you two ;-). Thanks for working so well\ntogether, as always.\n"},{"id":"544046","messageId":"CAL71e4PKL9e9empOBppF-RxufaQK95DJh0icAmtfd4cnGUN-Wg@mail.gmail.com","threadId":"65684","inReplyTo":"42aef000-7952-482d-8532-2287cf32b275@gmail.com","subject":"Re: [PATCH 2/3] commit-reach: optimize queue scan in paint_down_to_common","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-05-25T08:54:12Z","receivedAt":"2026-05-25T08:54:24Z","isPatch":true,"body":"I have been thinking a bit about encapsulation too - the problem is twofold:\n1. ENQUEUED is a tag on the commit object but it represents membership\n inside the queue and so we already have an implicit assumption that it only\n matches one queue (at a time).\n2. The counter is touched on enqueue/dequeue BUT also when mutating objects -\n that last part is tricky to encapsulate as a part of the queue.\n\nThat said, I think if we go in the direction of Jeff's idea with an amortized\nO(1) staleness check, this becomes simpler - and we can perhaps do something\nto structure _that_ code instead. Something like this perhaps:\n\nstruct stale_prio_queue {\n prio_queue pq;\n commit *nonstale_cache;\n}\n\nand add the corresponding wrapper functions.\n\nI think the encapsulation idea becomes even stronger with that approach than\nwith the counter based approach.\n\n\n- Kristofer\n\nOn Mon, 25 May 2026 at 03:59, Derrick Stolee wrote:\n>\n> On 5/24/26 1:42 PM, Kristofer Karlsson via GitGitGadget wrote:\n> > From: Kristofer Karlsson \n> >\n> > paint_down_to_common() terminates when every commit remaining in its\n> > priority queue is STALE. This was checked by queue_has_nonstale(),\n> > which performed an O(n) linear scan of the entire queue on every\n> > iteration, resulting in O(n*m) total overhead where n is the queue\n> > size and m is the number of commits processed.\n> >\n> > Replace this with an O(1) nonstale_count that tracks the number of\n> > non-stale commits currently in the queue. The counter is incremented\n> > by maybe_enqueue() and decremented on dequeue and by mark_stale()\n> > when a commit transitions to STALE while still in the queue. Since\n> > each commit appears at most once (guaranteed by the ENQUEUED flag\n> > from the previous commit), the counter is exact.\n>\n> This idea has a lot of merit, but I'm a bit concerned about the\n> organization of data. My ideas of how to improve things may also\n> impact patch 1's use of ENQUEUED.\n>\n> > -static void maybe_enqueue(struct prio_queue *queue, struct commit *c)\n> > +static void maybe_enqueue(struct prio_queue *queue, struct commit *c,\n> > + int *nonstale_count)\n> > {\n> > if (c->object.flags & ENQUEUED)\n> > return;\n> > c->object.flags |= ENQUEUED;\n> > prio_queue_put(queue, c);\n> > + if (!(c->object.flags & STALE))\n> > + (*nonstale_count)++;\n> > +}\n> > +\n> > +static void mark_stale(struct commit *c, unsigned queued_flag,\n> > + int *nonstale_count)\n> > +{\n> > + if (!(c->object.flags & STALE)) {\n> > + if (c->object.flags & queued_flag)\n> > + (*nonstale_count)--;\n> > + c->object.flags |= STALE;\n> > + }\n> > }\n>\n> These two methods have some concerns on my end:\n>\n> 1. We need to store the nonstale count somewhere other than the\n> priority queue, even though it's necessarily representing a\n> subset of the commits within the queue.\n>\n> 2. mark_stale() needs a queued_flag. (I need to check to see if\n> this is indeed changing in multiple callers or should always\n> be ENQUEUED).\n>\n> > static int queue_has_nonstale(struct prio_queue *queue)\n> > @@ -68,6 +81,7 @@ static int paint_down_to_common(struct repository *r,\n> > {\n> > struct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n> > int i;\n> > + int nonstale_count = 0;\n>\n> My preference would be to create a new struct that contains a\n> prio_queue as a member _and_ a nonstale_count. It could initialize\n> with compare_commits_by_gen_then_commit_date by default.\n>\n> The important thing is that consumers of such a \"stale-tracking\"\n> queue would not be setting the STALE or ENQUEUED bits themselves,\n> but instead the queue would be responsible for that.\n>\n> This could allow us to simplify callers by always assuming we can\n> \"add\" an element to the queue and the queue will use its ENQUEUED\n> bit to prevent duplicates from reaching its internal prio_queue.\n>\n> Such a data structure could be private to commit-reach.c for now,\n> since all the methods that would use it seem to be colocated there.\n>\n> This is a big ask, but I'm interested to see if such an approach\n> would simplify things here.\n>\n> Here's a potential breakdown of how to build such a thing in\n> \"small\" patches:\n>\n> 1. Create the data structure and update paint_down_to_common and\n> ahead_behind to use that structure, but still use the existing\n> prio_queue methods on its internal member.\n>\n> 2. Add the ENQUEUED bit and methods on the new struct that add\n> that bit as it adds commits to the inner prio_queue. It would\n> also ignore commits that already have that bit. (Should it\n> also remove the bit as commits are removed from the queue?)\n>\n> 3. Now add the nonstale_count (or stale count?) to the struct and\n> have it control the STALE bit modifications, with increasing\n> the stale count when ENQUEUED is live, and decreasing the stale\n> count as such a STALE object is dequeued.\n>\n> I like the idea of this being encapsulated within the struct and\n> its helper methods. But the proof will be in the implementation.\n>\n> Thanks,\n> -Stolee\n>\n"},{"id":"544050","messageId":"20260525095506.GA3868724@coredump.intra.peff.net","threadId":"65684","inReplyTo":"CAL71e4MOH2iPve19dKixLHSgpC3ZAZz59zLWEWRoxW1a7vhMwg@mail.gmail.com","subject":"Re: [PATCH 0/3] commit-reach: replace queue_has_nonstale with a counter","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-25T09:55:06Z","receivedAt":"2026-05-25T09:55:08Z","isPatch":true,"body":"On Mon, May 25, 2026 at 09:59:59AM +0200, Kristofer Karlsson wrote:\n\n> That's an excellent approach! Much cleaner in general.\n> \n> I benchmarked it against the counter on a monorepo with wide-frontier DAGs\n> (2.4M commits, component import merges). Using merge-base --all to bypass\n> the early-exit optimization from kk/paint-down-to-common-optim:\n> \n> Baseline Cache Counter\n> import(A) 8079ms 3686ms 3723ms\n> import(B) 5498ms 3993ms 4038ms\n> import(C) 4350ms 1748ms 1766ms\n> \n> The cache performs on par with the counter - within noise on all three\n> cases. No new flags needed, much simpler diff.\n> The amortized O(1) is just as good as true O(1) in practice, and it avoids\n> the ENQUEUED flag and counter bookkeeping entirely.\n\nI'm not sure if it's technically amortized O(1), as I think in the worst\ncase we are still quadratic. That would happen if we've cached some\nnon-stale X, then pop it and put on some new commit Y. And then the next\nround we have no cache (X was popped), but have to walk the whole queue\nto find Y.\n\nSo I think it's more of a \"heuristically O(1)\" or something.\n\n> I went with back-to-front scanning as you suggested\n\nOut of curiosity, did you also time it front-to-back? What I wonder is\nif we might commonly hit that worst case for back-to-front when we're\ncontinually popping and inserting one new commit at the front of the\nqueue. If there's a bunch of stale cruft in the back end of the queue,\nwe'll walk over it repeatedly to find the new commit, and our cache will\nnever (or seldom) remain valid. (I know it's a heap, not a real queue,\nbut I think the far end of the array will still tend to represent stuff\nthat is further away from being popped due to the heap property).\n\nWhereas looking from front to back, we are likely to cache something\nthat is going to be popped soon. But in that case we find it quickly,\nand the longer we search the more likely it is to hang around in the\nqueue and remain valid.\n\n> and also clear the cache when the cached entry goes stale.\n\nI think this happens naturally when we call into queue_has_nonstale().\nWe only use the cached value if it's still non-stale. If it's gone stale\nthen we either find a new commit, or if we can't then we return false\n(everything is stale). I guess the stale commit is left in the cache in\nthe latter case, but it doesn't matter because the loop ends anyway (and\neven if it didn't, it is OK to repeatedly ignore the stale commit, as\ndoing so is O(1) and we have nothing better to cache).\n\nThat said, it is probably only one line to explicitly set it to NULL in\nqueue_has_nonstale(), so I am OK with that. ;)\n\nIf you're proposing to notice when we set the STALE flag on a commit\nwhich matches the cached value, I'd prefer to avoid that, just because\nit muddies up the code.\n\n> I can rewrite the patchset with this approach and add you as co-author or\n> suggested-by? Or I think I can wait for you to push it yourself.\n> You did all the work here, and just didn't have enough data points to\n> motivate it?\n\nI think testing and writing the commit messages will be more work than\nthe code. I am happy to live on in a trailer if you will do those other\nparts. ;)\n\n-Peff\n"},{"id":"544051","messageId":"20260525100215.GB3868724@coredump.intra.peff.net","threadId":"65684","inReplyTo":"CAL71e4ODJeCJctKg=3o9PKD6Rw3_xHnrjc+zT_MYFc=CdNc59A@mail.gmail.com","subject":"Re: [PATCH 1/3] commit-reach: deduplicate queue entries in paint_down_to_common","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-25T10:02:15Z","receivedAt":"2026-05-25T10:02:17Z","isPatch":true,"body":"On Mon, May 25, 2026 at 09:53:09AM +0200, Kristofer Karlsson wrote:\n\n> Good catch Jeff! I think it's possible that I missed the flag cleanup case\n> here, but it's also possible that I got lucky and it worked anyway.\n\nWell, you did add it to ALL_FLAGS, so it might have been your\nsubconscious making you lucky. :)\n\n> That said, I think the observation in the other email thread/commit is key\n> here. I will reply back in that one, but it seems like this can all be\n> simplified using Jeff's idea with an amortized O(1) solution by caching a\n> known non-stale entry in the queue, and thus becomes obsolete. I will post\n> a new patchset when the discussion slows down.\n\nNifty, thanks.\n\n> As for general flag management, I will spend some more time thinking about it.\n> I don't fully trust static code analysis to work, but some cheap assertion\n> based model might give a nice trade-off.\n\nI think it would be really nice if we had per-operation flags kept\noutside of the structs completely. If you're a masochist, I fiddled\naround a bit with using a hash instead in this thread:\n\n https://lore.kernel.org/git/20250826055210.GA1031277@coredump.intra.peff.net/\n\nIt's sadly (but not surprisingly) quite slow. I do wonder how a slab\nwould work there, but it would take a bit more surgery. We only allocate\nslab ids for commits, and we'd have to do so for all objects if we want\nto hold flags.\n\nProbably a dead-end, but it would be neat if all of these flag\nallocation worries just went away.\n\n-Peff\n"},{"id":"544060","messageId":"CAL71e4P0Ls9r0oAOeFoEUzD8Z+fBNKGAvLi-1zH+gb_nV=Ro7Q@mail.gmail.com","threadId":"65684","inReplyTo":"20260525095506.GA3868724@coredump.intra.peff.net","subject":"Re: [PATCH 0/3] commit-reach: replace queue_has_nonstale with a counter","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-05-25T10:47:32Z","receivedAt":"2026-05-25T10:47:45Z","isPatch":true,"body":"Good point, it may not truly be amortized O(1) — you can construct cases\nwhere all the interesting commits cluster at the front and the cache is\nrepeatedly invalidated.\n\nThat said, I started thinking about what happens if we upgrade the cache\non every enqueue, and I think there is a clean O(1) solution that\neliminates scanning entirely.\n\nThe key observation: commits transition from non-stale to stale but\nnever the other way. So if we track the lowest-priority non-stale\ncommit in the queue and maintain it on every enqueue, we get a tight\ninvariant:\n\nstruct nonstale_queue {\n struct prio_queue pq;\n struct commit *max_nonstale;\n};\n\nstatic void nonstale_queue_put(struct nonstale_queue *nsq,\n struct commit *commit) {\n prio_queue_put(&nsq->pq, commit);\n if (commit->object.flags & STALE)\n return;\n if (!nsq->max_nonstale ||\n nsq->pq.compare(nsq->max_nonstale, commit,\n nsq->pq.cb_data) < 0)\n nsq->max_nonstale = commit;\n}\n\nstatic struct commit *nonstale_queue_get(struct nonstale_queue *nsq)\n{\n struct commit *commit = prio_queue_get(&nsq->pq);\n if (commit == nsq->max_nonstale) nsq->max_nonstale = NULL;\n return commit;\n}\n\nThe loop condition becomes while (nsq.max_nonstale).\n\nWhy this works:\n\n1. max_nonstale always points to the lowest-priority non-stale entry\nwe have seen. Everything behind it in the priority order was stale\nat enqueue time, and stale is a one-way transition, so it stays\nstale.\n2. When max_nonstale is popped, every remaining entry has lower\npriority and is therefore stale. The popped commit's parents get\nenqueued though, and if any are non-stale they restore\nmax_nonstale via nonstale_queue_put().\n3. If max_nonstale becomes stale between pops (e.g. painted from\nboth sides), we don't notice immediately — the walk does a few\nextra iterations until it's popped. That's a small bounded cost.\n\nThis seems like the best of both worlds: O(1) like the counter\napproach but with the simplicity of the cache, and no new flags.\n\nI have it implemented and tested it locally and the performance is identical\nto the cache version on the monorepo.\n\nI can push an updated v2 patch with this approach later, unless something\nelse pops up from the discussions (maybe I am wrong about all this!)\n\n-- Kristofer\n\nOn Mon, 25 May 2026 at 11:55, Jeff King wrote:\n>\n> On Mon, May 25, 2026 at 09:59:59AM +0200, Kristofer Karlsson wrote:\n>\n> > That's an excellent approach! Much cleaner in general.\n> >\n> > I benchmarked it against the counter on a monorepo with wide-frontier DAGs\n> > (2.4M commits, component import merges). Using merge-base --all to bypass\n> > the early-exit optimization from kk/paint-down-to-common-optim:\n> >\n> > Baseline Cache Counter\n> > import(A) 8079ms 3686ms 3723ms\n> > import(B) 5498ms 3993ms 4038ms\n> > import(C) 4350ms 1748ms 1766ms\n> >\n> > The cache performs on par with the counter - within noise on all three\n> > cases. No new flags needed, much simpler diff.\n> > The amortized O(1) is just as good as true O(1) in practice, and it avoids\n> > the ENQUEUED flag and counter bookkeeping entirely.\n>\n> I'm not sure if it's technically amortized O(1), as I think in the worst\n> case we are still quadratic. That would happen if we've cached some\n> non-stale X, then pop it and put on some new commit Y. And then the next\n> round we have no cache (X was popped), but have to walk the whole queue\n> to find Y.\n>\n> So I think it's more of a \"heuristically O(1)\" or something.\n>\n> > I went with back-to-front scanning as you suggested\n>\n> Out of curiosity, did you also time it front-to-back? What I wonder is\n> if we might commonly hit that worst case for back-to-front when we're\n> continually popping and inserting one new commit at the front of the\n> queue. If there's a bunch of stale cruft in the back end of the queue,\n> we'll walk over it repeatedly to find the new commit, and our cache will\n> never (or seldom) remain valid. (I know it's a heap, not a real queue,\n> but I think the far end of the array will still tend to represent stuff\n> that is further away from being popped due to the heap property).\n>\n> Whereas looking from front to back, we are likely to cache something\n> that is going to be popped soon. But in that case we find it quickly,\n> and the longer we search the more likely it is to hang around in the\n> queue and remain valid.\n>\n> > and also clear the cache when the cached entry goes stale.\n>\n> I think this happens naturally when we call into queue_has_nonstale().\n> We only use the cached value if it's still non-stale. If it's gone stale\n> then we either find a new commit, or if we can't then we return false\n> (everything is stale). I guess the stale commit is left in the cache in\n> the latter case, but it doesn't matter because the loop ends anyway (and\n> even if it didn't, it is OK to repeatedly ignore the stale commit, as\n> doing so is O(1) and we have nothing better to cache).\n>\n> That said, it is probably only one line to explicitly set it to NULL in\n> queue_has_nonstale(), so I am OK with that. ;)\n>\n> If you're proposing to notice when we set the STALE flag on a commit\n> which matches the cached value, I'd prefer to avoid that, just because\n> it muddies up the code.\n>\n> > I can rewrite the patchset with this approach and add you as co-author or\n> > suggested-by? Or I think I can wait for you to push it yourself.\n> > You did all the work here, and just didn't have enough data points to\n> > motivate it?\n>\n> I think testing and writing the commit messages will be more work than\n> the code. I am happy to live on in a trailer if you will do those other\n> parts. ;)\n>\n> -Peff\n"},{"id":"544063","messageId":"105f4646c2ded721c6f6ad69a5e72cf1201989d7.1779719286.git.gitgitgadget@gmail.com","threadId":"65684","inReplyTo":"pull.2124.v2.git.1779719286.gitgitgadget@gmail.com","subject":"[PATCH v2 1/3] object.h: fix stale entries in object flag allocation table","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-25T14:28:03Z","receivedAt":"2026-05-25T14:28:09Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nUpdate three stale entries found during an audit of the flag\nallocation table:\n\n - sha1-name.c was renamed to object-name.c\n - builtin/show-branch.c uses bits 0 and 2-28, not 0-26\n (REV_SHIFT=2, MAX_REVS=FLAG_BITS-REV_SHIFT=27)\n - negotiator/skipping.c uses bits 2-5 like negotiator/default.c\n (ADVERTISED on bit 3 instead of COMMON_REF)\n\nSigned-off-by: Kristofer Karlsson \n---\n object.h | 5 +++--\n 1 file changed, 3 insertions(+), 2 deletions(-)\n\ndiff --git a/object.h b/object.h\nindex d814647ebe..2b26de3044 100644\n--- a/object.h\n+++ b/object.h\n@@ -67,6 +67,7 @@ void object_array_init(struct object_array *array);\n * revision.h: 0---------10 15 23--------28\n * fetch-pack.c: 01 67\n * negotiator/default.c: 2--5\n+ * negotiator/skipping.c: 2--5\n * walker.c: 0-2\n * upload-pack.c: 4 11-----14 16-----19\n * builtin/blame.c: 12-13\n@@ -76,13 +77,13 @@ void object_array_init(struct object_array *array);\n * commit-graph.c: 15\n * commit-reach.c: 16-----19\n * builtin/last-modified.c: 1617\n- * sha1-name.c: 20\n+ * object-name.c: 20\n * list-objects-filter.c: 21\n * bloom.c: 2122\n * builtin/fsck.c: 0--3\n * builtin/index-pack.c: 2021\n * reflog.c: 10--12\n- * builtin/show-branch.c: 0-------------------------------------------26\n+ * builtin/show-branch.c: 0-----------------------------------------------28\n * builtin/unpack-objects.c: 2021\n * pack-bitmap.h: 2122\n */\n-- \ngitgitgadget\n\n"},{"id":"544064","messageId":"fc38c0f856e93b80073ec3f1b9f641b9ab187e4e.1779719286.git.gitgitgadget@gmail.com","threadId":"65684","inReplyTo":"pull.2124.v2.git.1779719286.gitgitgadget@gmail.com","subject":"[PATCH v2 2/3] commit-reach: deduplicate queue entries in paint_down_to_common","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-25T14:28:04Z","receivedAt":"2026-05-25T14:28:10Z","isPatch":true,"body":"From: Kristofer Karlsson \n\npaint_down_to_common() can enqueue the same commit multiple times\nwhen it is reached through different parents with different flag\ncombinations. Add an ENQUEUED flag to track whether a commit is\ncurrently in the priority queue, and skip it if already present.\n\nIntroduce prio_queue_put_dedup() and prio_queue_get_dedup()\nwrappers that manage the ENQUEUED flag on enqueue and dequeue.\n\nThis change is performance-neutral on its own: the O(n)\nqueue_has_nonstale() scan still dominates the per-iteration cost.\nHowever, the deduplication guarantee (each commit appears in the\nqueue at most once) is a prerequisite for the next commit, which\nreplaces that scan with O(1) tracking.\n\nSigned-off-by: Kristofer Karlsson \n---\n commit-reach.c | 27 ++++++++++++++++++++++-----\n object.h | 2 +-\n 2 files changed, 23 insertions(+), 6 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 5a52be90a6..85583ae359 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -17,8 +17,9 @@\n #define PARENT2\t\t(1u<<17)\n #define STALE\t\t(1u<<18)\n #define RESULT\t\t(1u<<19)\n+#define ENQUEUED\t(1u<<20)\n \n-static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);\n+static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT | ENQUEUED);\n \n static int compare_commits_by_gen(const void *_a, const void *_b)\n {\n@@ -39,6 +40,22 @@ static int compare_commits_by_gen(const void *_a, const void *_b)\n \treturn 0;\n }\n \n+static void prio_queue_put_dedup(struct prio_queue *queue, struct commit *c)\n+{\n+\tif (c->object.flags & ENQUEUED)\n+\t\treturn;\n+\tc->object.flags |= ENQUEUED;\n+\tprio_queue_put(queue, c);\n+}\n+\n+static struct commit *prio_queue_get_dedup(struct prio_queue *queue)\n+{\n+\tstruct commit *commit = prio_queue_get(queue);\n+\tif (commit)\n+\t\tcommit->object.flags &= ~ENQUEUED;\n+\treturn commit;\n+}\n+\n static int queue_has_nonstale(struct prio_queue *queue)\n {\n \tfor (size_t i = 0; i < queue->nr; i++) {\n@@ -70,15 +87,15 @@ static int paint_down_to_common(struct repository *r,\n \t\tcommit_list_append(one, result);\n \t\treturn 0;\n \t}\n-\tprio_queue_put(&queue, one);\n+\tprio_queue_put_dedup(&queue, one);\n \n \tfor (i = 0; i < n; i++) {\n \t\ttwos[i]->object.flags |= PARENT2;\n-\t\tprio_queue_put(&queue, twos[i]);\n+\t\tprio_queue_put_dedup(&queue, twos[i]);\n \t}\n \n \twhile (queue_has_nonstale(&queue)) {\n-\t\tstruct commit *commit = prio_queue_get(&queue);\n+\t\tstruct commit *commit = prio_queue_get_dedup(&queue);\n \t\tstruct commit_list *parents;\n \t\tint flags;\n \t\ttimestamp_t generation = commit_graph_generation(commit);\n@@ -132,7 +149,7 @@ static int paint_down_to_common(struct repository *r,\n \t\t\t\t\t oid_to_hex(&p->object.oid));\n \t\t\t}\n \t\t\tp->object.flags |= flags;\n-\t\t\tprio_queue_put(&queue, p);\n+\t\t\tprio_queue_put_dedup(&queue, p);\n \t\t}\n \t}\n \ndiff --git a/object.h b/object.h\nindex 2b26de3044..8fb03ff90a 100644\n--- a/object.h\n+++ b/object.h\n@@ -75,7 +75,7 @@ void object_array_init(struct object_array *array);\n * bundle.c: 16\n * http-push.c: 11-----14\n * commit-graph.c: 15\n- * commit-reach.c: 16-----19\n+ * commit-reach.c: 16-------20\n * builtin/last-modified.c: 1617\n * object-name.c: 20\n * list-objects-filter.c: 21\n-- \ngitgitgadget\n\n"},{"id":"544065","messageId":"03771eb34c3ef1a896f5a63b4247b0a79f1589bb.1779719286.git.gitgitgadget@gmail.com","threadId":"65684","inReplyTo":"pull.2124.v2.git.1779719286.gitgitgadget@gmail.com","subject":"[PATCH v2 3/3] commit-reach: replace queue_has_nonstale() scan with O(1) tracking","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-25T14:28:05Z","receivedAt":"2026-05-25T14:28:11Z","isPatch":true,"body":"From: Kristofer Karlsson \n\npaint_down_to_common() and ahead_behind() call queue_has_nonstale()\non every iteration to decide whether to continue the walk.\nqueue_has_nonstale() performs a linear scan of the priority queue,\nmaking the overall walk O(n*m) where n is the number of commits\nwalked and m is the queue size.\n\nIntroduce 'struct nonstale_queue', a thin wrapper around prio_queue\nthat maintains a 'max_nonstale' pointer — the lowest-priority\n(oldest) non-stale commit seen so far. When this commit is popped,\nevery remaining queue entry is known to be stale, so the walk can\nstop. This reduces the per-iteration termination check from O(m)\nto O(1).\n\nUses <= 0 (not < 0) when comparing priorities so that among distinct\ncommits with equal priority (same generation and timestamp) the\nlast-enqueued one is tracked. Since prio_queue breaks ties by\ninsertion order, this ensures max_nonstale is always the last in its\npriority class to be popped, making pointer equality on pop\nsufficient for correctness.\n\nThe previous commit's ENQUEUED deduplication guarantees each commit\nappears at most once in the queue, which is required for the pointer\nequality check to be unambiguous.\n\nOn a large monorepo (3.7M commits), this yields ~2x end-to-end\nspeedup for merge-base calculations on deep import branches.\nProfiling shows paint_down_to_common() drops from 50% to 4% of\ntotal runtime (~27x faster), with the remaining time in commit\ngraph lookups and heap operations:\n\n Before: 8536ms / 5757ms / 4743ms (three test cases)\n After: 3956ms / 4383ms / 1927ms\n\nSuggested-by: Jeff King \nSigned-off-by: Kristofer Karlsson \n---\n commit-reach.c | 96 ++++++++++++++++++++++++++++++++++----------------\n 1 file changed, 65 insertions(+), 31 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 85583ae359..b5328a804c 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -40,32 +40,62 @@ static int compare_commits_by_gen(const void *_a, const void *_b)\n \treturn 0;\n }\n \n-static void prio_queue_put_dedup(struct prio_queue *queue, struct commit *c)\n+/*\n+ * A prio_queue with O(1) termination check. 'max_nonstale' tracks\n+ * the lowest-priority non-stale commit enqueued so far; once it is\n+ * popped, every remaining entry is known to be STALE.\n+ */\n+struct nonstale_queue {\n+\tstruct prio_queue pq;\n+\tstruct commit *max_nonstale;\n+};\n+\n+static void nonstale_queue_put(struct nonstale_queue *queue,\n+\t\t\t struct commit *c)\n+{\n+\tstruct commit *old = queue->max_nonstale;\n+\n+\tprio_queue_put(&queue->pq, c);\n+\tif (c->object.flags & STALE)\n+\t\treturn;\n+\tif (!old || queue->pq.compare(old, c, queue->pq.cb_data) <= 0)\n+\t\tqueue->max_nonstale = c;\n+}\n+\n+static struct commit *nonstale_queue_get(struct nonstale_queue *queue)\n+{\n+\tstruct commit *commit = prio_queue_get(&queue->pq);\n+\n+\tif (commit == queue->max_nonstale)\n+\t\tqueue->max_nonstale = NULL;\n+\n+\treturn commit;\n+}\n+\n+static void clear_nonstale_queue(struct nonstale_queue *queue)\n+{\n+\tclear_prio_queue(&queue->pq);\n+\tqueue->max_nonstale = NULL;\n+}\n+\n+static void nonstale_queue_put_dedup(struct nonstale_queue *queue,\n+\t\t\t\t struct commit *c)\n {\n \tif (c->object.flags & ENQUEUED)\n \t\treturn;\n \tc->object.flags |= ENQUEUED;\n-\tprio_queue_put(queue, c);\n+\tnonstale_queue_put(queue, c);\n }\n \n-static struct commit *prio_queue_get_dedup(struct prio_queue *queue)\n+static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)\n {\n-\tstruct commit *commit = prio_queue_get(queue);\n+\tstruct commit *commit = nonstale_queue_get(queue);\n+\n \tif (commit)\n \t\tcommit->object.flags &= ~ENQUEUED;\n \treturn commit;\n }\n \n-static int queue_has_nonstale(struct prio_queue *queue)\n-{\n-\tfor (size_t i = 0; i < queue->nr; i++) {\n-\t\tstruct commit *commit = queue->array[i].data;\n-\t\tif (!(commit->object.flags & STALE))\n-\t\t\treturn 1;\n-\t}\n-\treturn 0;\n-}\n-\n /* all input commits in one and twos[] must have been parsed! */\n static int paint_down_to_common(struct repository *r,\n \t\t\t\tstruct commit *one, int n,\n@@ -74,28 +104,30 @@ static int paint_down_to_common(struct repository *r,\n \t\t\t\tenum merge_base_flags mb_flags,\n \t\t\t\tstruct commit_list **result)\n {\n-\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n+\tstruct nonstale_queue queue = {\n+\t\t{ compare_commits_by_gen_then_commit_date }\n+\t};\n \tint i;\n \ttimestamp_t last_gen = GENERATION_NUMBER_INFINITY;\n \tstruct commit_list **tail = result;\n \n \tif (!min_generation && !corrected_commit_dates_enabled(r))\n-\t\tqueue.compare = compare_commits_by_commit_date;\n+\t\tqueue.pq.compare = compare_commits_by_commit_date;\n \n \tone->object.flags |= PARENT1;\n \tif (!n) {\n \t\tcommit_list_append(one, result);\n \t\treturn 0;\n \t}\n-\tprio_queue_put_dedup(&queue, one);\n+\tnonstale_queue_put_dedup(&queue, one);\n \n \tfor (i = 0; i < n; i++) {\n \t\ttwos[i]->object.flags |= PARENT2;\n-\t\tprio_queue_put_dedup(&queue, twos[i]);\n+\t\tnonstale_queue_put_dedup(&queue, twos[i]);\n \t}\n \n-\twhile (queue_has_nonstale(&queue)) {\n-\t\tstruct commit *commit = prio_queue_get_dedup(&queue);\n+\twhile (queue.max_nonstale) {\n+\t\tstruct commit *commit = nonstale_queue_get_dedup(&queue);\n \t\tstruct commit_list *parents;\n \t\tint flags;\n \t\ttimestamp_t generation = commit_graph_generation(commit);\n@@ -133,7 +165,7 @@ static int paint_down_to_common(struct repository *r,\n \t\t\tif ((p->object.flags & flags) == flags)\n \t\t\t\tcontinue;\n \t\t\tif (repo_parse_commit(r, p)) {\n-\t\t\t\tclear_prio_queue(&queue);\n+\t\t\t\tclear_nonstale_queue(&queue);\n \t\t\t\tcommit_list_free(*result);\n \t\t\t\t*result = NULL;\n \t\t\t\t/*\n@@ -149,11 +181,11 @@ static int paint_down_to_common(struct repository *r,\n \t\t\t\t\t oid_to_hex(&p->object.oid));\n \t\t\t}\n \t\t\tp->object.flags |= flags;\n-\t\t\tprio_queue_put_dedup(&queue, p);\n+\t\t\tnonstale_queue_put_dedup(&queue, p);\n \t\t}\n \t}\n \n-\tclear_prio_queue(&queue);\n+\tclear_nonstale_queue(&queue);\n \tcommit_list_sort_by_date(result);\n \treturn 0;\n }\n@@ -1057,11 +1089,11 @@ struct commit_list *get_reachable_subset(struct commit **from, size_t nr_from,\n define_commit_slab(bit_arrays, struct bitmap *);\n static struct bit_arrays bit_arrays;\n \n-static void insert_no_dup(struct prio_queue *queue, struct commit *c)\n+static void insert_no_dup(struct nonstale_queue *queue, struct commit *c)\n {\n \tif (c->object.flags & PARENT2)\n \t\treturn;\n-\tprio_queue_put(queue, c);\n+\tnonstale_queue_put(queue, c);\n \tc->object.flags |= PARENT2;\n }\n \n@@ -1086,7 +1118,9 @@ 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 {\n-\tstruct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };\n+\tstruct nonstale_queue queue = {\n+\t\t{ .compare = compare_commits_by_gen_then_commit_date }\n+\t};\n \tsize_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);\n \n \tif (!commits_nr || !counts_nr)\n@@ -1109,8 +1143,8 @@ void ahead_behind(struct repository *r,\n \t\tinsert_no_dup(&queue, c);\n \t}\n \n-\twhile (queue_has_nonstale(&queue)) {\n-\t\tstruct commit *c = prio_queue_get(&queue);\n+\twhile (queue.max_nonstale) {\n+\t\tstruct commit *c = nonstale_queue_get(&queue);\n \t\tstruct commit_list *p;\n \t\tstruct bitmap *bitmap_c = get_bit_array(c, width);\n \n@@ -1152,10 +1186,10 @@ 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-\tfor (size_t i = 0; i < queue.nr; i++)\n-\t\tfree_bit_array(queue.array[i].data);\n+\tfor (size_t i = 0; i < queue.pq.nr; i++)\n+\t\tfree_bit_array(queue.pq.array[i].data);\n \tclear_bit_arrays(&bit_arrays);\n-\tclear_prio_queue(&queue);\n+\tclear_nonstale_queue(&queue);\n }\n \n struct commit_and_index {\n-- \ngitgitgadget\n"},{"id":"544066","messageId":"pull.2124.v2.git.1779719286.gitgitgadget@gmail.com","threadId":"65684","inReplyTo":"pull.2124.git.1779644541.gitgitgadget@gmail.com","subject":"[PATCH v2 0/3] commit-reach: replace queue_has_nonstale() scan with O(1) tracking","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-25T14:28:02Z","receivedAt":"2026-05-25T14:28:14Z","isPatch":true,"body":"This is v2 of the series to replace the O(n) queue_has_nonstale() scan with\nO(1) tracking.\n\nChanges since v1:\n\n * Replaced the nonstale counter with a max_nonstale pointer approach, as\n suggested by Jeff King. Instead of counting non-stale entries, we track\n the lowest-priority non-stale commit; when it is popped, all remaining\n entries must be stale.\n\n * Restructured from 5 patches to 3:\n \n 1. object.h: fix stale entries in object flag allocation table\n 2. commit-reach: deduplicate queue entries in paint_down_to_common\n 3. commit-reach: replace queue_has_nonstale() scan with O(1) tracking\n\n * Separated concerns: ENQUEUED dedup is a paint_down_to_common concern\n (commit 2), while nonstale_queue is a general wrapper usable by both\n paint_down_to_common and ahead_behind (commit 3). ahead_behind uses its\n own PARENT2-based dedup via insert_no_dup.\n\n * The nonstale_queue struct is intentionally kept thin (no ENQUEUED\n handling). Dedup variants (nonstale_queue_put_dedup /\n nonstale_queue_get_dedup) are layered on top for paint_down_to_common.\n\nPerformance on a large monorepo (3.7M commits), merge-base --all on deep\nimport branches:\n\n Baseline Patched\ncomponent import, wide frontier (1): 8536ms 3956ms\ncomponent import, wide frontier (2): 5757ms 4383ms\ncomponent import, wide frontier (3): 4743ms 1927ms\n\n\nProfiling shows paint_down_to_common() drops from 50% to 4% of total runtime\n(~27x faster). The remaining time is in commit graph lookups, heap\noperations, and object management — per-commit costs that are not addressed\nby this series.\n\nSimple/linear cases show no regression (sub-15ms regardless).\n\nKristofer Karlsson (3):\n object.h: fix stale entries in object flag allocation table\n commit-reach: deduplicate queue entries in paint_down_to_common\n commit-reach: replace queue_has_nonstale() scan with O(1) tracking\n\n commit-reach.c | 101 +++++++++++++++++++++++++++++++++++++------------\n object.h | 7 ++--\n 2 files changed, 80 insertions(+), 28 deletions(-)\n\n\nbase-commit: 56a4f3c3a221adf1df9b39da69b8a6890f803157\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2124%2Fspkrka%2Fqueue-has-nonstale-v3-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2124/spkrka/queue-has-nonstale-v3-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/2124\n\nRange-diff vs v1:\n\n -: ---------- > 1: 105f4646c2 object.h: fix stale entries in object flag allocation table\n 1: 1d3751569b ! 2: fc38c0f856 commit-reach: deduplicate queue entries in paint_down_to_common\n @@ Commit message\n combinations. Add an ENQUEUED flag to track whether a commit is\n currently in the priority queue, and skip it if already present.\n \n + Introduce prio_queue_put_dedup() and prio_queue_get_dedup()\n + wrappers that manage the ENQUEUED flag on enqueue and dequeue.\n +\n This change is performance-neutral on its own: the O(n)\n queue_has_nonstale() scan still dominates the per-iteration cost.\n However, the deduplication guarantee (each commit appears in the\n queue at most once) is a prerequisite for the next commit, which\n - replaces that scan with an O(1) nonstale counter.\n + replaces that scan with O(1) tracking.\n \n Signed-off-by: Kristofer Karlsson \n \n @@ commit-reach.c: static int compare_commits_by_gen(const void *_a, const void *_b\n \treturn 0;\n }\n \n -+static void maybe_enqueue(struct prio_queue *queue, struct commit *c)\n ++static void prio_queue_put_dedup(struct prio_queue *queue, struct commit *c)\n +{\n +\tif (c->object.flags & ENQUEUED)\n +\t\treturn;\n +\tc->object.flags |= ENQUEUED;\n +\tprio_queue_put(queue, c);\n +}\n ++\n ++static struct commit *prio_queue_get_dedup(struct prio_queue *queue)\n ++{\n ++\tstruct commit *commit = prio_queue_get(queue);\n ++\tif (commit)\n ++\t\tcommit->object.flags &= ~ENQUEUED;\n ++\treturn commit;\n ++}\n +\n static int queue_has_nonstale(struct prio_queue *queue)\n {\n @@ commit-reach.c: static int paint_down_to_common(struct repository *r,\n \t\treturn 0;\n \t}\n -\tprio_queue_put(&queue, one);\n -+\tmaybe_enqueue(&queue, one);\n ++\tprio_queue_put_dedup(&queue, one);\n \n \tfor (i = 0; i < n; i++) {\n \t\ttwos[i]->object.flags |= PARENT2;\n -\t\tprio_queue_put(&queue, twos[i]);\n -+\t\tmaybe_enqueue(&queue, twos[i]);\n ++\t\tprio_queue_put_dedup(&queue, twos[i]);\n \t}\n \n \twhile (queue_has_nonstale(&queue)) {\n -@@ commit-reach.c: static int paint_down_to_common(struct repository *r,\n +-\t\tstruct commit *commit = prio_queue_get(&queue);\n ++\t\tstruct commit *commit = prio_queue_get_dedup(&queue);\n + \t\tstruct commit_list *parents;\n \t\tint flags;\n \t\ttimestamp_t generation = commit_graph_generation(commit);\n - \n -+\t\tcommit->object.flags &= ~ENQUEUED;\n -+\n - \t\tif (min_generation && generation > last_gen)\n - \t\t\tBUG(\"bad generation skip %\"PRItime\" > %\"PRItime\" at %s\",\n - \t\t\t generation, last_gen,\n @@ commit-reach.c: static int paint_down_to_common(struct repository *r,\n \t\t\t\t\t oid_to_hex(&p->object.oid));\n \t\t\t}\n \t\t\tp->object.flags |= flags;\n -\t\t\tprio_queue_put(&queue, p);\n -+\t\t\tmaybe_enqueue(&queue, p);\n ++\t\t\tprio_queue_put_dedup(&queue, p);\n \t\t}\n \t}\n \n @@ object.h: void object_array_init(struct object_array *array);\n - * commit-reach.c: 16-----19\n + * commit-reach.c: 16-------20\n * builtin/last-modified.c: 1617\n - * sha1-name.c: 20\n + * object-name.c: 20\n * list-objects-filter.c: 21\n 2: 4742f5e634 < -: ---------- commit-reach: optimize queue scan in paint_down_to_common\n 3: 711a0e2235 ! 3: 03771eb34c commit-reach: optimize queue scan in ahead_behind\n @@ Metadata\n Author: Kristofer Karlsson \n \n ## Commit message ##\n - commit-reach: optimize queue scan in ahead_behind\n + commit-reach: replace queue_has_nonstale() scan with O(1) tracking\n \n - Apply the same nonstale_count optimization from the previous commit\n - to ahead_behind(). This replaces the remaining caller of the O(n)\n - queue_has_nonstale() scan with an O(1) counter check, allowing\n - queue_has_nonstale() to be removed.\n + paint_down_to_common() and ahead_behind() call queue_has_nonstale()\n + on every iteration to decide whether to continue the walk.\n + queue_has_nonstale() performs a linear scan of the priority queue,\n + making the overall walk O(n*m) where n is the number of commits\n + walked and m is the queue size.\n \n - ahead_behind() already deduplicates queue entries using the PARENT2\n - flag (via insert_no_dup), so the counter is maintained through\n - insert_no_dup() and mark_stale() using PARENT2 as the queued_flag.\n + Introduce 'struct nonstale_queue', a thin wrapper around prio_queue\n + that maintains a 'max_nonstale' pointer — the lowest-priority\n + (oldest) non-stale commit seen so far. When this commit is popped,\n + every remaining queue entry is known to be stale, so the walk can\n + stop. This reduces the per-iteration termination check from O(m)\n + to O(1).\n \n + Uses <= 0 (not < 0) when comparing priorities so that among distinct\n + commits with equal priority (same generation and timestamp) the\n + last-enqueued one is tracked. Since prio_queue breaks ties by\n + insertion order, this ensures max_nonstale is always the last in its\n + priority class to be popped, making pointer equality on pop\n + sufficient for correctness.\n +\n + The previous commit's ENQUEUED deduplication guarantees each commit\n + appears at most once in the queue, which is required for the pointer\n + equality check to be unambiguous.\n +\n + On a large monorepo (3.7M commits), this yields ~2x end-to-end\n + speedup for merge-base calculations on deep import branches.\n + Profiling shows paint_down_to_common() drops from 50% to 4% of\n + total runtime (~27x faster), with the remaining time in commit\n + graph lookups and heap operations:\n +\n + Before: 8536ms / 5757ms / 4743ms (three test cases)\n + After: 3956ms / 4383ms / 1927ms\n +\n + Suggested-by: Jeff King \n Signed-off-by: Kristofer Karlsson \n \n ## commit-reach.c ##\n -@@ commit-reach.c: static void mark_stale(struct commit *c, unsigned queued_flag,\n - \t}\n +@@ commit-reach.c: static int compare_commits_by_gen(const void *_a, const void *_b)\n + \treturn 0;\n + }\n + \n +-static void prio_queue_put_dedup(struct prio_queue *queue, struct commit *c)\n ++/*\n ++ * A prio_queue with O(1) termination check. 'max_nonstale' tracks\n ++ * the lowest-priority non-stale commit enqueued so far; once it is\n ++ * popped, every remaining entry is known to be STALE.\n ++ */\n ++struct nonstale_queue {\n ++\tstruct prio_queue pq;\n ++\tstruct commit *max_nonstale;\n ++};\n ++\n ++static void nonstale_queue_put(struct nonstale_queue *queue,\n ++\t\t\t struct commit *c)\n ++{\n ++\tstruct commit *old = queue->max_nonstale;\n ++\n ++\tprio_queue_put(&queue->pq, c);\n ++\tif (c->object.flags & STALE)\n ++\t\treturn;\n ++\tif (!old || queue->pq.compare(old, c, queue->pq.cb_data) <= 0)\n ++\t\tqueue->max_nonstale = c;\n ++}\n ++\n ++static struct commit *nonstale_queue_get(struct nonstale_queue *queue)\n ++{\n ++\tstruct commit *commit = prio_queue_get(&queue->pq);\n ++\n ++\tif (commit == queue->max_nonstale)\n ++\t\tqueue->max_nonstale = NULL;\n ++\n ++\treturn commit;\n ++}\n ++\n ++static void clear_nonstale_queue(struct nonstale_queue *queue)\n ++{\n ++\tclear_prio_queue(&queue->pq);\n ++\tqueue->max_nonstale = NULL;\n ++}\n ++\n ++static void nonstale_queue_put_dedup(struct nonstale_queue *queue,\n ++\t\t\t\t struct commit *c)\n + {\n + \tif (c->object.flags & ENQUEUED)\n + \t\treturn;\n + \tc->object.flags |= ENQUEUED;\n +-\tprio_queue_put(queue, c);\n ++\tnonstale_queue_put(queue, c);\n + }\n + \n +-static struct commit *prio_queue_get_dedup(struct prio_queue *queue)\n ++static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)\n + {\n +-\tstruct commit *commit = prio_queue_get(queue);\n ++\tstruct commit *commit = nonstale_queue_get(queue);\n ++\n + \tif (commit)\n + \t\tcommit->object.flags &= ~ENQUEUED;\n + \treturn commit;\n }\n \n -static int queue_has_nonstale(struct prio_queue *queue)\n @@ commit-reach.c: static void mark_stale(struct commit *c, unsigned queued_flag,\n /* all input commits in one and twos[] must have been parsed! */\n static int paint_down_to_common(struct repository *r,\n \t\t\t\tstruct commit *one, int n,\n +@@ commit-reach.c: static int paint_down_to_common(struct repository *r,\n + \t\t\t\tenum merge_base_flags mb_flags,\n + \t\t\t\tstruct commit_list **result)\n + {\n +-\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n ++\tstruct nonstale_queue queue = {\n ++\t\t{ compare_commits_by_gen_then_commit_date }\n ++\t};\n + \tint i;\n + \ttimestamp_t last_gen = GENERATION_NUMBER_INFINITY;\n + \tstruct commit_list **tail = result;\n + \n + \tif (!min_generation && !corrected_commit_dates_enabled(r))\n +-\t\tqueue.compare = compare_commits_by_commit_date;\n ++\t\tqueue.pq.compare = compare_commits_by_commit_date;\n + \n + \tone->object.flags |= PARENT1;\n + \tif (!n) {\n + \t\tcommit_list_append(one, result);\n + \t\treturn 0;\n + \t}\n +-\tprio_queue_put_dedup(&queue, one);\n ++\tnonstale_queue_put_dedup(&queue, one);\n + \n + \tfor (i = 0; i < n; i++) {\n + \t\ttwos[i]->object.flags |= PARENT2;\n +-\t\tprio_queue_put_dedup(&queue, twos[i]);\n ++\t\tnonstale_queue_put_dedup(&queue, twos[i]);\n + \t}\n + \n +-\twhile (queue_has_nonstale(&queue)) {\n +-\t\tstruct commit *commit = prio_queue_get_dedup(&queue);\n ++\twhile (queue.max_nonstale) {\n ++\t\tstruct commit *commit = nonstale_queue_get_dedup(&queue);\n + \t\tstruct commit_list *parents;\n + \t\tint flags;\n + \t\ttimestamp_t generation = commit_graph_generation(commit);\n +@@ commit-reach.c: static int paint_down_to_common(struct repository *r,\n + \t\t\tif ((p->object.flags & flags) == flags)\n + \t\t\t\tcontinue;\n + \t\t\tif (repo_parse_commit(r, p)) {\n +-\t\t\t\tclear_prio_queue(&queue);\n ++\t\t\t\tclear_nonstale_queue(&queue);\n + \t\t\t\tcommit_list_free(*result);\n + \t\t\t\t*result = NULL;\n + \t\t\t\t/*\n +@@ commit-reach.c: static int paint_down_to_common(struct repository *r,\n + \t\t\t\t\t oid_to_hex(&p->object.oid));\n + \t\t\t}\n + \t\t\tp->object.flags |= flags;\n +-\t\t\tprio_queue_put_dedup(&queue, p);\n ++\t\t\tnonstale_queue_put_dedup(&queue, p);\n + \t\t}\n + \t}\n + \n +-\tclear_prio_queue(&queue);\n ++\tclear_nonstale_queue(&queue);\n + \tcommit_list_sort_by_date(result);\n + \treturn 0;\n + }\n @@ commit-reach.c: struct commit_list *get_reachable_subset(struct commit **from, size_t nr_from,\n define_commit_slab(bit_arrays, struct bitmap *);\n static struct bit_arrays bit_arrays;\n \n -static void insert_no_dup(struct prio_queue *queue, struct commit *c)\n -+static void insert_no_dup(struct prio_queue *queue, struct commit *c,\n -+\t\t\t int *nonstale_count)\n ++static void insert_no_dup(struct nonstale_queue *queue, struct commit *c)\n {\n \tif (c->object.flags & PARENT2)\n \t\treturn;\n - \tprio_queue_put(queue, c);\n +-\tprio_queue_put(queue, c);\n ++\tnonstale_queue_put(queue, c);\n \tc->object.flags |= PARENT2;\n -+\tif (!(c->object.flags & STALE))\n -+\t\t(*nonstale_count)++;\n }\n \n - static struct bitmap *get_bit_array(struct commit *c, int width)\n @@ commit-reach.c: 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 {\n - \tstruct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };\n +-\tstruct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };\n ++\tstruct nonstale_queue queue = {\n ++\t\t{ .compare = compare_commits_by_gen_then_commit_date }\n ++\t};\n \tsize_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);\n -+\tint nonstale_count = 0;\n \n \tif (!commits_nr || !counts_nr)\n - \t\treturn;\n @@ commit-reach.c: void ahead_behind(struct repository *r,\n - \t\tstruct bitmap *bitmap = get_bit_array(c, width);\n - \n - \t\tbitmap_set(bitmap, i);\n --\t\tinsert_no_dup(&queue, c);\n -+\t\tinsert_no_dup(&queue, c, &nonstale_count);\n + \t\tinsert_no_dup(&queue, c);\n \t}\n \n -\twhile (queue_has_nonstale(&queue)) {\n -+\twhile (nonstale_count > 0) {\n - \t\tstruct commit *c = prio_queue_get(&queue);\n +-\t\tstruct commit *c = prio_queue_get(&queue);\n ++\twhile (queue.max_nonstale) {\n ++\t\tstruct commit *c = nonstale_queue_get(&queue);\n \t\tstruct commit_list *p;\n \t\tstruct bitmap *bitmap_c = get_bit_array(c, width);\n \n -+\t\tif (!(c->object.flags & STALE))\n -+\t\t\tnonstale_count--;\n -+\n - \t\tfor (size_t i = 0; i < counts_nr; i++) {\n - \t\t\tint reach_from_tip = !!bitmap_get(bitmap_c, counts[i].tip_index);\n - \t\t\tint reach_from_base = !!bitmap_get(bitmap_c, counts[i].base_index);\n @@ commit-reach.c: void ahead_behind(struct repository *r,\n - \t\t\t * queue is STALE.\n - \t\t\t */\n - \t\t\tif (bitmap_popcount(bitmap_p) == commits_nr)\n --\t\t\t\tp->item->object.flags |= STALE;\n -+\t\t\t\tmark_stale(p->item, PARENT2, &nonstale_count);\n \n --\t\t\tinsert_no_dup(&queue, p->item);\n -+\t\t\tinsert_no_dup(&queue, p->item, &nonstale_count);\n - \t\t}\n + \t/* STALE is used here, PARENT2 is used by insert_no_dup(). */\n + \trepo_clear_commit_marks(r, PARENT2 | STALE);\n +-\tfor (size_t i = 0; i < queue.nr; i++)\n +-\t\tfree_bit_array(queue.array[i].data);\n ++\tfor (size_t i = 0; i < queue.pq.nr; i++)\n ++\t\tfree_bit_array(queue.pq.array[i].data);\n + \tclear_bit_arrays(&bit_arrays);\n +-\tclear_prio_queue(&queue);\n ++\tclear_nonstale_queue(&queue);\n + }\n \n - \t\tfree_bit_array(c);\n + struct commit_and_index {\n\n-- \ngitgitgadget\n"},{"id":"544082","messageId":"xmqqzf1ncded.fsf@gitster.g","threadId":"65684","inReplyTo":"fc38c0f856e93b80073ec3f1b9f641b9ab187e4e.1779719286.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 2/3] commit-reach: deduplicate queue entries in paint_down_to_common","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-05-25T22:50:18Z","receivedAt":"2026-05-25T22:50:20Z","isPatch":true,"body":"\"Kristofer Karlsson via GitGitGadget\" \nwrites:\n\n> From: Kristofer Karlsson \n>\n> paint_down_to_common() can enqueue the same commit multiple times\n> when it is reached through different parents with different flag\n> combinations. Add an ENQUEUED flag to track whether a commit is\n> currently in the priority queue, and skip it if already present.\n>\n> Introduce prio_queue_put_dedup() and prio_queue_get_dedup()\n> wrappers that manage the ENQUEUED flag on enqueue and dequeue.\n\nOK. I guess an obvious alternative design would be to have an\nassociated hashtable for deduping, or tweak prio_queue_get() so\nthat it notices duplicated entry just before it returns (i.e.,\npeek and discard until queue->array[0].data is different from\nwhat you are going to return). Both would not beat the cheap cost\nof using a single bit per object, I guess ;-)\n\n> This change is performance-neutral on its own: the O(n)\n> queue_has_nonstale() scan still dominates the per-iteration cost.\n> However, the deduplication guarantee (each commit appears in the\n> queue at most once) is a prerequisite for the next commit, which\n> replaces that scan with O(1) tracking.\n>\n> Signed-off-by: Kristofer Karlsson \n> ---\n> commit-reach.c | 27 ++++++++++++++++++++++-----\n> object.h | 2 +-\n> 2 files changed, 23 insertions(+), 6 deletions(-)\n\nThanks for the clean-up in the previous step, by the way.\n\n> diff --git a/commit-reach.c b/commit-reach.c\n> index 5a52be90a6..85583ae359 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -17,8 +17,9 @@\n> #define PARENT2\t\t(1u<<17)\n> #define STALE\t\t(1u<<18)\n> #define RESULT\t\t(1u<<19)\n> +#define ENQUEUED\t(1u<<20)\n> \n> -static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);\n> +static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT | ENQUEUED);\n> \n> static int compare_commits_by_gen(const void *_a, const void *_b)\n> {\n> @@ -39,6 +40,22 @@ static int compare_commits_by_gen(const void *_a, const void *_b)\n> \treturn 0;\n> }\n> \n> +static void prio_queue_put_dedup(struct prio_queue *queue, struct commit *c)\n> +{\n> +\tif (c->object.flags & ENQUEUED)\n> +\t\treturn;\n> +\tc->object.flags |= ENQUEUED;\n> +\tprio_queue_put(queue, c);\n> +}\n> +\n> +static struct commit *prio_queue_get_dedup(struct prio_queue *queue)\n> +{\n> +\tstruct commit *commit = prio_queue_get(queue);\n> +\tif (commit)\n> +\t\tcommit->object.flags &= ~ENQUEUED;\n> +\treturn commit;\n> +}\n> +\n> static int queue_has_nonstale(struct prio_queue *queue)\n> {\n> \tfor (size_t i = 0; i < queue->nr; i++) {\n> @@ -70,15 +87,15 @@ static int paint_down_to_common(struct repository *r,\n> \t\tcommit_list_append(one, result);\n> \t\treturn 0;\n> \t}\n> -\tprio_queue_put(&queue, one);\n> +\tprio_queue_put_dedup(&queue, one);\n> \n> \tfor (i = 0; i < n; i++) {\n> \t\ttwos[i]->object.flags |= PARENT2;\n> -\t\tprio_queue_put(&queue, twos[i]);\n> +\t\tprio_queue_put_dedup(&queue, twos[i]);\n> \t}\n> \n> \twhile (queue_has_nonstale(&queue)) {\n> -\t\tstruct commit *commit = prio_queue_get(&queue);\n> +\t\tstruct commit *commit = prio_queue_get_dedup(&queue);\n> \t\tstruct commit_list *parents;\n> \t\tint flags;\n> \t\ttimestamp_t generation = commit_graph_generation(commit);\n> @@ -132,7 +149,7 @@ static int paint_down_to_common(struct repository *r,\n> \t\t\t\t\t oid_to_hex(&p->object.oid));\n> \t\t\t}\n> \t\t\tp->object.flags |= flags;\n> -\t\t\tprio_queue_put(&queue, p);\n> +\t\t\tprio_queue_put_dedup(&queue, p);\n> \t\t}\n> \t}\n> \n> diff --git a/object.h b/object.h\n> index 2b26de3044..8fb03ff90a 100644\n> --- a/object.h\n> +++ b/object.h\n> @@ -75,7 +75,7 @@ void object_array_init(struct object_array *array);\n> * bundle.c: 16\n> * http-push.c: 11-----14\n> * commit-graph.c: 15\n> - * commit-reach.c: 16-----19\n> + * commit-reach.c: 16-------20\n> * builtin/last-modified.c: 1617\n> * object-name.c: 20\n> * list-objects-filter.c: 21\n"},{"id":"544101","messageId":"CAL71e4OFniTMgG2Sj3LDMdfdZzYh-J71maNcWaobEHri9ox43g@mail.gmail.com","threadId":"65684","inReplyTo":"xmqqzf1ncded.fsf@gitster.g","subject":"Re: [PATCH v2 2/3] commit-reach: deduplicate queue entries in paint_down_to_common","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-05-26T06:57:13Z","receivedAt":"2026-05-26T06:57:25Z","isPatch":true,"body":"On Tue, 26 May 2026 at 00:50, Junio C Hamano wrote:\n> OK. I guess an obvious alternative design would be to have an\n> associated hashtable for deduping, or tweak prio_queue_get() so\n> that it notices duplicated entry just before it returns (i.e.,\n> peek and discard until queue->array[0].data is different from\n> what you are going to return). Both would not beat the cheap cost\n> of using a single bit per object, I guess ;-)\n\nYes, I think a hashtable or hashset would work here too. I realize that I\nhave done a lot of local experimentation with alternative approaches but I\nforgot to mention the ones I discarded for various reasons - but that\nwould be useful information for you to have too. Let me rectify that here.\n\noidset instead of enqueued flag: Works fine, but is ~15-20% slower end-to-end.\nBoth are O(1) but the overhead is quite significant compared to a flag.\n\nPeek and discard: the problem here is that the commits are not necessarily\nordered. We can have a sequence of A,B,A if we are unlucky. What I did try\nhowever was an alternative to this - just change the fast-exit heuristic to\novershoot until comparison returns > 0 - i.e. consume some\nextra commits in the queue. This works and in my example data we typically\nwould only need to walk ~16 extra commits with this heuristic, so it's not\nbad at all. But the extra comparisons we need to run on each iteration make\nit ~15-20% slower.\n\nAnother thing I tried was simply tracking the minimum generation seen and\nterminate as soon as we have gone past it. This is fast and simple and does\nnot require deduping, but it only works if we have a commit graph and\ngeneration numbers.\n\nThe advantage of the approach with deduping via the ENQUEUED flag and then\njust tracking the most recently enqueued commit is that it works independently\nof ordering guarantees. All it needs to work is the fact that we can prove\nthat we have reached a point where queue no longer has any non-stale commits\nat all.\n\nSummary:\n Approach Dedup Works w/o commit-graph? Speed\n ENQUEUED flag yes (1 bit) yes fastest\n Hashtable yes yes 15-20% slower\n Peek-discard - - broken\n Cmp overshoot no yes 15-20% slower\n Gen overshoot no no same as ENQUEUED\n"}]}