From: Kristofer Karlsson Date: Mon, 25 May 2026 08:54:12 GMT Subject: Re: [PATCH 2/3] commit-reach: optimize queue scan in paint_down_to_common Message-ID: 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 wrote: > > On 5/24/26 1:42 PM, Kristofer Karlsson via GitGitGadget wrote: > > From: Kristofer Karlsson > > > > 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 >