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

Re: [PATCH 2/3] commit-reach: optimize queue scan in paint_down_to_common

From
Kristofer Karlsson <krka@spotify.com>
Date
May 25, 2026, 08:54 UTC
Message-ID
<CAL71e4PKL9e9empOBppF-RxufaQK95DJh0icAmtfd4cnGUN-Wg@mail.gmail.com>
In-Reply-To
<42aef000-7952-482d-8532-2287cf32b275@gmail.com>
I have been thinking a bit about encapsulation too - the problem is twofold:
1. ENQUEUED is a tag on the commit object but it represents membership
   inside the queue and so we already have an implicit assumption that it only
   matches one queue (at a time).
2. The counter is touched on enqueue/dequeue BUT also when mutating objects -
   that last part is tricky to encapsulate as a part of the queue.

That said, I think if we go in the direction of Jeff's idea with an amortized O(1) staleness check, this becomes simpler - and we can perhaps do something to structure _that_ code instead. Something like this perhaps:

struct stale_prio_queue {
  prio_queue pq;
  commit *nonstale_cache;
}
and add the corresponding wrapper functions.

I think the encapsulation idea becomes even stronger with that approach than with the counter based approach.

- Kristofer
On Mon, 25 May 2026 at 03:59, Derrick Stolee <stolee@gmail.com> wrote:
Show 101 quoted lines
>
> On 5/24/26 1:42 PM, Kristofer Karlsson via GitGitGadget wrote:
> > From: Kristofer Karlsson <krka@spotify.com>
> >
> > 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.
>
> This idea has a lot of merit, but I'm a bit concerned about the
> organization of data. My ideas of how to improve things may also
> impact patch 1's use of ENQUEUED.
>
> > -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;
> > +     }
> >   }
>
> These two methods have some concerns on my end:
>
> 1. We need to store the nonstale count somewhere other than the
>     priority queue, even though it's necessarily representing a
>     subset of the commits within the queue.
>
> 2. mark_stale() needs a queued_flag. (I need to check to see if
>     this is indeed changing in multiple callers or should always
>     be ENQUEUED).
>
> >   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;
>
> My preference would be to create a new struct that contains a
> prio_queue as a member _and_ a nonstale_count. It could initialize
> with compare_commits_by_gen_then_commit_date by default.
>
> The important thing is that consumers of such a "stale-tracking"
> queue would not be setting the STALE or ENQUEUED bits themselves,
> but instead the queue would be responsible for that.
>
> This could allow us to simplify callers by always assuming we can
> "add" an element to the queue and the queue will use its ENQUEUED
> bit to prevent duplicates from reaching its internal prio_queue.
>
> Such a data structure could be private to commit-reach.c for now,
> since all the methods that would use it seem to be colocated there.
>
> This is a big ask, but I'm interested to see if such an approach
> would simplify things here.
>
> Here's a potential breakdown of how to build such a thing in
> "small" patches:
>
> 1. Create the data structure and update paint_down_to_common and
>     ahead_behind to use that structure, but still use the existing
>     prio_queue methods on its internal member.
>
> 2. Add the ENQUEUED bit and methods on the new struct that add
>     that bit as it adds commits to the inner prio_queue. It would
>     also ignore commits that already have that bit. (Should it
>     also remove the bit as commits are removed from the queue?)
>
> 3. Now add the nonstale_count (or stale count?) to the struct and
>     have it control the STALE bit modifications, with increasing
>     the stale count when ENQUEUED is live, and decreasing the stale
>     count as such a STALE object is dequeued.
>
> I like the idea of this being encapsulated within the struct and
> its helper methods. But the proof will be in the implementation.
>
> Thanks,
> -Stolee
>
Previous: Derrick StoleeNext: Kristofer Karlsson via GitGitGadget
Message 13 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.