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

From: Kristofer Karlsson <[email-masked]>
Date: Mon, 25 May 2026 10:54:12 +0200

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 <[email-masked]> wrote:
>
> On 5/24/26 1:42 PM, Kristofer Karlsson via GitGitGadget wrote:
> > From: Kristofer Karlsson <[email-masked]>
> >
> > 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
>