Re: [PATCH 0/3] commit-reach: replace queue_has_nonstale with a counter
- From
Jeff King <peff@peff.net>
- Date
- May 25, 2026, 06:47 UTC
- Message-ID
- <20260525064755.GA2737798@coredump.intra.peff.net>
- In-Reply-To
- <pull.2124.git.1779644541.gitgitgadget@gmail.com>
On Sun, May 24, 2026 at 05:42:17PM +0000, Kristofer Karlsson via GitGitGadget wrote:
Show 5 quoted lines
> paint_down_to_common() and ahead_behind() terminate when every commit in > their priority queue is STALE. The current check, queue_has_nonstale(), does > an O(n) linear scan of the queue on every iteration, costing O(n*m) total > where n is the queue size and m is the number of commits processed. This > series replaces that scan with an O(1) counter.
We faced a similar problem in limit_list() but solved it a bit differently (mostly because I was worried about keeping the counter up to date in all cases).
It's described in more detail in b6e8a3b540 (limit_list: avoid quadratic behavior from still_interesting, 2015-04-17), but the general idea is to just cache the interesting element we found, and invalidate the cache when it gets removed from the queue or gets marked UNINTERESTING.
The equivalent code for the STALE flag here is something like this:
diff --git a/commit-reach.c b/commit-reach.c index d3a9b3ed6f..d1621be89f 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -39,12 +39,25 @@ static int compare_commits_by_gen(const void *_a, const void *_b) return 0; } -static int queue_has_nonstale(struct prio_queue *queue) +static int queue_has_nonstale(struct prio_queue *queue, + struct commit **nonstale_cache) { + if (*nonstale_cache) { + struct commit *commit = *nonstale_cache; + if (!(commit->object.flags & STALE)) + return 1; + } + + /* + * This might also benefit from looking back-to-front, since + * earlier commits are more likely to get popped sooner. + */ for (size_t i = 0; i < queue->nr; i++) { struct commit *commit = queue->array[i].data; - if (!(commit->object.flags & STALE)) + if (!(commit->object.flags & STALE)) { + *nonstale_cache = commit; return 1; + } } return 0; } @@ -61,6 +74,7 @@ static int paint_down_to_common(struct repository *r, int i; timestamp_t last_gen = GENERATION_NUMBER_INFINITY; struct commit_list **tail = result; + struct commit *nonstale_cache = NULL; if (!min_generation && !corrected_commit_dates_enabled(r)) queue.compare = compare_commits_by_commit_date; @@ -77,12 +91,15 @@ static int paint_down_to_common(struct repository *r, prio_queue_put(&queue, twos[i]); } - while (queue_has_nonstale(&queue)) { + while (queue_has_nonstale(&queue, &nonstale_cache)) { struct commit *commit = prio_queue_get(&queue); struct commit_list *parents; int flags; timestamp_t generation = commit_graph_generation(commit); + if (nonstale_cache == commit) + nonstale_cache = NULL; + if (min_generation && generation > last_gen) BUG("bad generation skip %"PRItime" > %"PRItime" at %s", generation, last_gen, @@ -1053,6 +1070,7 @@ void ahead_behind(struct repository *r, { struct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date }; size_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD); + struct commit *nonstale_cache = NULL; if (!commits_nr || !counts_nr) return; @@ -1074,11 +1092,14 @@ void ahead_behind(struct repository *r, insert_no_dup(&queue, c); } - while (queue_has_nonstale(&queue)) { + while (queue_has_nonstale(&queue, &nonstale_cache)) { struct commit *c = prio_queue_get(&queue); struct commit_list *p; struct bitmap *bitmap_c = get_bit_array(c, width); + if (c == nonstale_cache) + nonstale_cache = NULL; + for (size_t i = 0; i < counts_nr; i++) { int reach_from_tip = !!bitmap_get(bitmap_c, counts[i].tip_index); int reach_from_base = !!bitmap_get(bitmap_c, counts[i].base_index); I don't have a repo handy which reproduces the problem, so I can't see if it improves things. But if it's easy to do, can you report on the timing change with your monorepo? I do think what I've shown here is a bit hacky (just like the limit_list() one), as we are relying on heuristics about the order in which items are taken from the queue. So even if it performs well, we may still prefer the counter version for being truly O(1). But having timing numbers would be useful for comparing the two approaches. -Peff