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
Derrick Stolee <stolee@gmail.com>
Date
May 25, 2026, 01:59 UTC
Message-ID
<42aef000-7952-482d-8532-2287cf32b275@gmail.com>
In-Reply-To
<4742f5e634b55820f3b5a626ec97e24617fdae3d.1779644541.git.gitgitgadget@gmail.com>
On 5/24/26 1:42 PM, Kristofer Karlsson via GitGitGadget wrote:
Show 14 quoted lines
> 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.

Show 21 quoted lines
> -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).
Show 6 quoted lines
>   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: Kristofer Karlsson via GitGitGadgetNext: Kristofer Karlsson
Message 12 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.