From: Junio C Hamano Date: Mon, 25 May 2026 22:50:18 GMT Subject: Re: [PATCH v2 2/3] commit-reach: deduplicate queue entries in paint_down_to_common Message-ID: In-Reply-To: "Kristofer Karlsson via GitGitGadget" writes: > From: Kristofer Karlsson > > 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 ;-) > 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 > --- > 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. > 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