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

[PATCH 1/3] commit-reach: deduplicate queue entries in paint_down_to_common

From
Kristofer Karlsson via GitGitGadget <gitgitgadget@gmail.com>
Date
May 24, 2026, 17:42 UTC
Message-ID
<1d3751569ba3a5f0c353fb468578d6c5bcd0b738.1779644541.git.gitgitgadget@gmail.com>
In-Reply-To
<pull.2124.git.1779644541.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>

paint_down_to_common() can enqueue the same commit multiple times when it is reached through different parents with different flag combinations. Add an ENQUEUED flag to track whether a commit is currently in the priority queue, and skip it if already present.

This change is performance-neutral on its own: the O(n) queue_has_nonstale() scan still dominates the per-iteration cost. However, the deduplication guarantee (each commit appears in the queue at most once) is a prerequisite for the next commit, which replaces that scan with an O(1) nonstale counter.

Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
 commit-reach.c | 19 +++++++++++++++----
 object.h       |  2 +-
 2 files changed, 16 insertions(+), 5 deletions(-)
diff --git a/commit-reach.c b/commit-reach.c
index d3a9b3ed6f..c16d4b061c 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -17,8 +17,9 @@
 #define PARENT2		(1u<<17)
 #define STALE		(1u<<18)
 #define RESULT		(1u<<19)
+#define ENQUEUED	(1u<<20)
 
-static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);
+static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT | ENQUEUED);
 
 static int compare_commits_by_gen(const void *_a, const void *_b)
 {
@@ -39,6 +40,14 @@ static int compare_commits_by_gen(const void *_a, const void *_b)
 	return 0;
 }
 
+static void maybe_enqueue(struct prio_queue *queue, struct commit *c)
+{
+	if (c->object.flags & ENQUEUED)
+		return;
+	c->object.flags |= ENQUEUED;
+	prio_queue_put(queue, c);
+}
+
 static int queue_has_nonstale(struct prio_queue *queue)
 {
 	for (size_t i = 0; i < queue->nr; i++) {
@@ -70,11 +79,11 @@ static int paint_down_to_common(struct repository *r,
 		commit_list_append(one, result);
 		return 0;
 	}
-	prio_queue_put(&queue, one);
+	maybe_enqueue(&queue, one);
 
 	for (i = 0; i < n; i++) {
 		twos[i]->object.flags |= PARENT2;
-		prio_queue_put(&queue, twos[i]);
+		maybe_enqueue(&queue, twos[i]);
 	}
 
 	while (queue_has_nonstale(&queue)) {
@@ -83,6 +92,8 @@ static int paint_down_to_common(struct repository *r,
 		int flags;
 		timestamp_t generation = commit_graph_generation(commit);
 
+		commit->object.flags &= ~ENQUEUED;
+
 		if (min_generation && generation > last_gen)
 			BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
 			    generation, last_gen,
@@ -124,7 +135,7 @@ static int paint_down_to_common(struct repository *r,
 					     oid_to_hex(&p->object.oid));
 			}
 			p->object.flags |= flags;
-			prio_queue_put(&queue, p);
+			maybe_enqueue(&queue, p);
 		}
 	}
 
diff --git a/object.h b/object.h
index d814647ebe..05cbf728e9 100644
--- a/object.h
+++ b/object.h
@@ -74,7 +74,7 @@ void object_array_init(struct object_array *array);
  * bundle.c:                                        16
  * http-push.c:                          11-----14
  * commit-graph.c:                                15
- * commit-reach.c:                                  16-----19
+ * commit-reach.c:                                  16-------20
  * builtin/last-modified.c:                         1617
  * sha1-name.c:                                              20
  * list-objects-filter.c:                                      21
-- 
gitgitgadget
Previous: Kristofer Karlsson via GitGitGadgetNext: Junio C Hamano
Message 2 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.