From: Kristofer Karlsson via GitGitGadget Date: Sun, 24 May 2026 17:42:19 GMT Subject: [PATCH 2/3] commit-reach: optimize queue scan in paint_down_to_common Message-ID: <4742f5e634b55820f3b5a626ec97e24617fdae3d.1779644541.git.gitgitgadget@gmail.com> In-Reply-To: From: Kristofer Karlsson paint_down_to_common() terminates when every commit remaining in its priority queue is STALE. This was checked by queue_has_nonstale(), which performed an O(n) linear scan of the entire queue on every iteration, resulting in O(n*m) total overhead where n is the queue size and m is the number of commits processed. Replace this with an O(1) nonstale_count that tracks the number of non-stale commits currently in the queue. The counter is incremented by maybe_enqueue() and decremented on dequeue and by mark_stale() when a commit transitions to STALE while still in the queue. Since each commit appears at most once (guaranteed by the ENQUEUED flag from the previous commit), the counter is exact. ahead_behind() also uses queue_has_nonstale() and will be converted in the next commit. Signed-off-by: Kristofer Karlsson --- commit-reach.c | 28 +++++++++++++++++++++++----- 1 file changed, 23 insertions(+), 5 deletions(-) diff --git a/commit-reach.c b/commit-reach.c index c16d4b061c..356ff52d08 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -40,12 +40,25 @@ static int compare_commits_by_gen(const void *_a, const void *_b) return 0; } -static void maybe_enqueue(struct prio_queue *queue, struct commit *c) +static void maybe_enqueue(struct prio_queue *queue, struct commit *c, + int *nonstale_count) { if (c->object.flags & ENQUEUED) return; c->object.flags |= ENQUEUED; prio_queue_put(queue, c); + if (!(c->object.flags & STALE)) + (*nonstale_count)++; +} + +static void mark_stale(struct commit *c, unsigned queued_flag, + int *nonstale_count) +{ + if (!(c->object.flags & STALE)) { + if (c->object.flags & queued_flag) + (*nonstale_count)--; + c->object.flags |= STALE; + } } static int queue_has_nonstale(struct prio_queue *queue) @@ -68,6 +81,7 @@ static int paint_down_to_common(struct repository *r, { struct prio_queue queue = { compare_commits_by_gen_then_commit_date }; int i; + int nonstale_count = 0; timestamp_t last_gen = GENERATION_NUMBER_INFINITY; struct commit_list **tail = result; @@ -79,20 +93,22 @@ static int paint_down_to_common(struct repository *r, commit_list_append(one, result); return 0; } - maybe_enqueue(&queue, one); + maybe_enqueue(&queue, one, &nonstale_count); for (i = 0; i < n; i++) { twos[i]->object.flags |= PARENT2; - maybe_enqueue(&queue, twos[i]); + maybe_enqueue(&queue, twos[i], &nonstale_count); } - while (queue_has_nonstale(&queue)) { + while (nonstale_count > 0) { struct commit *commit = prio_queue_get(&queue); struct commit_list *parents; int flags; timestamp_t generation = commit_graph_generation(commit); commit->object.flags &= ~ENQUEUED; + if (!(commit->object.flags & STALE)) + nonstale_count--; if (min_generation && generation > last_gen) BUG("bad generation skip %"PRItime" > %"PRItime" at %s", @@ -134,8 +150,10 @@ static int paint_down_to_common(struct repository *r, return error(_("could not parse commit %s"), oid_to_hex(&p->object.oid)); } + if (flags & STALE) + mark_stale(p, ENQUEUED, &nonstale_count); p->object.flags |= flags; - maybe_enqueue(&queue, p); + maybe_enqueue(&queue, p, &nonstale_count); } } -- gitgitgadget