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

Re: [PATCH v2 2/3] commit-reach: deduplicate queue entries in paint_down_to_common

From
Junio C Hamano <gitster@pobox.com>
Date
May 25, 2026, 22:50 UTC
Message-ID
<xmqqzf1ncded.fsf@gitster.g>
In-Reply-To
<fc38c0f856e93b80073ec3f1b9f641b9ab187e4e.1779719286.git.gitgitgadget@gmail.com>

"Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com> writes:

Show 9 quoted lines
> 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.
>
> Introduce prio_queue_put_dedup() and prio_queue_get_dedup()
> wrappers that manage the ENQUEUED flag on enqueue and dequeue.

OK. I guess an obvious alternative design would be to have an associated hashtable for deduping, or tweak prio_queue_get() so that it notices duplicated entry just before it returns (i.e., peek and discard until queue->array[0].data is different from what you are going to return). Both would not beat the cheap cost of using a single bit per object, I guess ;-)

Show 11 quoted lines
> 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 O(1) tracking.
>
> Signed-off-by: Kristofer Karlsson <krka@spotify.com>
> ---
>  commit-reach.c | 27 ++++++++++++++++++++++-----
>  object.h       |  2 +-
>  2 files changed, 23 insertions(+), 6 deletions(-)
Thanks for the clean-up in the previous step, by the way.
Show 79 quoted lines
> diff --git a/commit-reach.c b/commit-reach.c
> index 5a52be90a6..85583ae359 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,22 @@ static int compare_commits_by_gen(const void *_a, const void *_b)
>  	return 0;
>  }
>  
> +static void prio_queue_put_dedup(struct prio_queue *queue, struct commit *c)
> +{
> +	if (c->object.flags & ENQUEUED)
> +		return;
> +	c->object.flags |= ENQUEUED;
> +	prio_queue_put(queue, c);
> +}
> +
> +static struct commit *prio_queue_get_dedup(struct prio_queue *queue)
> +{
> +	struct commit *commit = prio_queue_get(queue);
> +	if (commit)
> +		commit->object.flags &= ~ENQUEUED;
> +	return commit;
> +}
> +
>  static int queue_has_nonstale(struct prio_queue *queue)
>  {
>  	for (size_t i = 0; i < queue->nr; i++) {
> @@ -70,15 +87,15 @@ static int paint_down_to_common(struct repository *r,
>  		commit_list_append(one, result);
>  		return 0;
>  	}
> -	prio_queue_put(&queue, one);
> +	prio_queue_put_dedup(&queue, one);
>  
>  	for (i = 0; i < n; i++) {
>  		twos[i]->object.flags |= PARENT2;
> -		prio_queue_put(&queue, twos[i]);
> +		prio_queue_put_dedup(&queue, twos[i]);
>  	}
>  
>  	while (queue_has_nonstale(&queue)) {
> -		struct commit *commit = prio_queue_get(&queue);
> +		struct commit *commit = prio_queue_get_dedup(&queue);
>  		struct commit_list *parents;
>  		int flags;
>  		timestamp_t generation = commit_graph_generation(commit);
> @@ -132,7 +149,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);
> +			prio_queue_put_dedup(&queue, p);
>  		}
>  	}
>  
> diff --git a/object.h b/object.h
> index 2b26de3044..8fb03ff90a 100644
> --- a/object.h
> +++ b/object.h
> @@ -75,7 +75,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
>   * object-name.c:                                            20
>   * list-objects-filter.c:                                      21
Previous: Kristofer Karlsson via GitGitGadgetNext: Kristofer Karlsson
Message 24 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.