git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 0/3] commit-reach: replace queue_has_nonstale with a counter

From
Kristofer Karlsson <krka@spotify.com>
Date
May 25, 2026, 07:59 UTC
Message-ID
<CAL71e4MOH2iPve19dKixLHSgpC3ZAZz59zLWEWRoxW1a7vhMwg@mail.gmail.com>
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 <peff@peff.net> wrote:
Show 114 quoted lines
>
> 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
Previous: Jeff KingNext: Junio C Hamano
Message 17 of 26 in “commit-reach: replace queue_has_nonstale with a counter”
  1. 0/3 commit-reach: replace queue_has_nonstale with a counterKristofer Karlsson via GitGitGadget, May 24, 2026
  2. 1/3 commit-reach: deduplicate queue entries in paint_down_to_commonKristofer Karlsson via GitGitGadget, May 24, 2026
  3. Junio C HamanoMay 24, 2026
  4. Derrick StoleeMay 25, 2026
  5. Kristofer KarlssonMay 25, 2026
  6. Junio C HamanoMay 25, 2026
  7. Kristofer KarlssonMay 25, 2026
  8. Jeff KingMay 25, 2026
  9. Jeff KingMay 25, 2026
  10. Jeff KingMay 25, 2026
  11. 2/3 commit-reach: optimize queue scan in paint_down_to_commonKristofer Karlsson via GitGitGadget, May 24, 2026
  12. Derrick StoleeMay 25, 2026
  13. Kristofer KarlssonMay 25, 2026
  14. 3/3 commit-reach: optimize queue scan in ahead_behindKristofer Karlsson via GitGitGadget, May 24, 2026
  15. Jeff KingMay 25, 2026
  16. Jeff KingMay 25, 2026
  17. Kristofer KarlssonMay 25, 2026
  18. Junio C HamanoMay 25, 2026
  19. Jeff KingMay 25, 2026
  20. Kristofer KarlssonMay 25, 2026
  21. 0/3 commit-reach: replace queue_has_nonstale() scan with O(1) trackingKristofer Karlsson via GitGitGadget, May 25, 2026
  22. 1/3 object.h: fix stale entries in object flag allocation tableKristofer Karlsson via GitGitGadget, May 25, 2026
  23. 2/3 commit-reach: deduplicate queue entries in paint_down_to_commonKristofer Karlsson via GitGitGadget, May 25, 2026
  24. Junio C HamanoMay 25, 2026
  25. Kristofer KarlssonMay 26, 2026
  26. 3/3 commit-reach: replace queue_has_nonstale() scan with O(1) trackingKristofer Karlsson via GitGitGadget, May 25, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.