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