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

Re: [PATCH 0/3] commit-reach: replace queue_has_nonstale with a counter

From
Jeff King <peff@peff.net>
Date
May 25, 2026, 06:47 UTC
Message-ID
<20260525064755.GA2737798@coredump.intra.peff.net>
In-Reply-To
<pull.2124.git.1779644541.gitgitgadget@gmail.com>
On Sun, May 24, 2026 at 05:42:17PM +0000, Kristofer Karlsson via GitGitGadget wrote:
Show 5 quoted lines
> paint_down_to_common() and ahead_behind() terminate when every commit in
> their priority queue is STALE. The current check, queue_has_nonstale(), does
> an O(n) linear scan of the queue on every iteration, costing O(n*m) total
> where n is the queue size and m is the number of commits processed. This
> series replaces that scan with an O(1) counter.

We faced a similar problem in limit_list() but solved it a bit differently (mostly because I was worried about keeping the counter up to date in all cases).

It's described in more detail in b6e8a3b540 (limit_list: avoid quadratic behavior from still_interesting, 2015-04-17), but the general idea is to just cache the interesting element we found, and invalidate the cache when it gets removed from the queue or gets marked UNINTERESTING.

The equivalent code for the STALE flag here is something like this:
diff --git a/commit-reach.c b/commit-reach.c
index d3a9b3ed6f..d1621be89f 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -39,12 +39,25 @@ static int compare_commits_by_gen(const void *_a, const void *_b)
 	return 0;
 }
 
-static int queue_has_nonstale(struct prio_queue *queue)
+static int queue_has_nonstale(struct prio_queue *queue,
+			      struct commit **nonstale_cache)
 {
+	if (*nonstale_cache) {
+		struct commit *commit = *nonstale_cache;
+		if (!(commit->object.flags & STALE))
+			return 1;
+	}
+
+	/*
+	 * This might also benefit from looking back-to-front, since
+	 * earlier commits are more likely to get popped sooner.
+	 */
 	for (size_t i = 0; i < queue->nr; i++) {
 		struct commit *commit = queue->array[i].data;
-		if (!(commit->object.flags & STALE))
+		if (!(commit->object.flags & STALE)) {
+			*nonstale_cache = commit;
 			return 1;
+		}
 	}
 	return 0;
 }
@@ -61,6 +74,7 @@ static int paint_down_to_common(struct repository *r,
 	int i;
 	timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
 	struct commit_list **tail = result;
+	struct commit *nonstale_cache = NULL;
 
 	if (!min_generation && !corrected_commit_dates_enabled(r))
 		queue.compare = compare_commits_by_commit_date;
@@ -77,12 +91,15 @@ static int paint_down_to_common(struct repository *r,
 		prio_queue_put(&queue, twos[i]);
 	}
 
-	while (queue_has_nonstale(&queue)) {
+	while (queue_has_nonstale(&queue, &nonstale_cache)) {
 		struct commit *commit = prio_queue_get(&queue);
 		struct commit_list *parents;
 		int flags;
 		timestamp_t generation = commit_graph_generation(commit);
 
+		if (nonstale_cache == commit)
+			nonstale_cache = NULL;
+
 		if (min_generation && generation > last_gen)
 			BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
 			    generation, last_gen,
@@ -1053,6 +1070,7 @@ void ahead_behind(struct repository *r,
 {
 	struct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };
 	size_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);
+	struct commit *nonstale_cache = NULL;
 
 	if (!commits_nr || !counts_nr)
 		return;
@@ -1074,11 +1092,14 @@ void ahead_behind(struct repository *r,
 		insert_no_dup(&queue, c);
 	}
 
-	while (queue_has_nonstale(&queue)) {
+	while (queue_has_nonstale(&queue, &nonstale_cache)) {
 		struct commit *c = prio_queue_get(&queue);
 		struct commit_list *p;
 		struct bitmap *bitmap_c = get_bit_array(c, width);
 
+		if (c == nonstale_cache)
+			nonstale_cache = NULL;
+
 		for (size_t i = 0; i < counts_nr; i++) {
 			int reach_from_tip = !!bitmap_get(bitmap_c, counts[i].tip_index);
 			int reach_from_base = !!bitmap_get(bitmap_c, counts[i].base_index);


I don't have a repo handy which reproduces the problem, so I can't see
if it improves things. But if it's easy to do, can you report on the
timing change with your monorepo?

I do think what I've shown here is a bit hacky (just like the
limit_list() one), as we are relying on heuristics about the order in
which items are taken from the queue. So even if it performs well, we
may still prefer the counter version for being truly O(1). But having
timing numbers would be useful for comparing the two approaches.

-Peff
Previous: Jeff KingNext: Kristofer Karlsson
Message 16 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.