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
>