From: Kristofer Karlsson Date: Mon, 25 May 2026 07:59:59 GMT Subject: Re: [PATCH 0/3] commit-reach: replace queue_has_nonstale with a counter Message-ID: In-Reply-To: <20260525064755.GA2737798@coredump.intra.peff.net> That's an excellent approach! Much cleaner in general. I benchmarked it against the counter on a monorepo with wide-frontier DAGs (2.4M commits, component import merges). Using merge-base --all to bypass the early-exit optimization from kk/paint-down-to-common-optim: Baseline Cache Counter import(A) 8079ms 3686ms 3723ms import(B) 5498ms 3993ms 4038ms import(C) 4350ms 1748ms 1766ms The cache performs on par with the counter - within noise on all three cases. No new flags needed, much simpler diff. The amortized O(1) is just as good as true O(1) in practice, and it avoids the ENQUEUED flag and counter bookkeeping entirely. I went with back-to-front scanning as you suggested, and also clear the cache when the cached entry goes stale. Applied to both paint_down_to_common and ahead_behind. I can rewrite the patchset with this approach and add you as co-author or suggested-by? Or I think I can wait for you to push it yourself. You did all the work here, and just didn't have enough data points to motivate it? - Kristofer On Mon, 25 May 2026 at 08:47, Jeff King wrote: > > On Sun, May 24, 2026 at 05:42:17PM +0000, Kristofer Karlsson via GitGitGadget wrote: > > > 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