Re: [PATCH v7 07/10] commit-reach: introduce struct paint_state with per-side counters

From: Elijah Newren <newren@gmail.com>
Date: Aug 7, 2026, 03:02 UTC
Message-ID: <CABPp-BFqghtx4p_Nqx+AWpU7SVn3mXOZGDQ0yoN-ZYQgXmZC=g@mail.gmail.com>
In-Reply-To: <a1c8e89ef9f1d0fb5cb10ec9687633df8792ec7b.1786013982.git.gitgitgadget@gmail.com>

On Thu, Aug 6, 2026 at 4:05 AM Kristofer Karlsson via GitGitGadget <gitgitgadget@gmail.com> wrote:

Show 18 quoted lines

>
> From: Kristofer Karlsson <krka@spotify.com>
>
> Add a paint_state struct for use by paint_down_to_common() that
> wraps a prio_queue with per-side commit counters. Each non-stale
> queued commit occupies exactly one counter bucket based on its
> paint flags: PARENT1-only, PARENT2-only, or both sides (a pending
> merge-base candidate).
>
> The counters are maintained by paint_count_update() which adjusts
> the appropriate bucket by a signed delta. An exhaustive switch on
> the paint+stale bits documents all valid flag combinations in one
> place.
>
> Convert paint_down_to_common() to use paint_state. The loop now
> drains the queue via paint_queue_get() which returns NULL when all
> counters reach zero, replacing the old pointer-based termination
> (max_nonstale).

Ooh, I like this setup for what comes later; it sets the stage perfectly for the key insight behind the optimization. Very nice.

Show 11 quoted lines

> This is equivalent behavior -- both conditions
> detect that no non-stale entries remain.
>
> paint_queue_get() uses a "pop first" form: it dequeues a commit,
> then checks the counters. This means the loop exits one iteration
> earlier than the old code in some topologies (the popped stale
> commit is never processed), so a few step counts drop by one.
>
> The existing nonstale_queue is left in place for ahead_behind(),
> though nonstale_queue_put_dedup() and nonstale_queue_get_dedup()
> became unused and are removed.

became -> become

Show 79 quoted lines

>
> Signed-off-by: Kristofer Karlsson <krka@spotify.com>
> ---
>  .../technical/paint-down-to-common.adoc       |   9 +-
>  commit-reach.c                                | 103 +++++++++++++-----
>  t/t6600-test-reach.sh                         |   6 +-
>  3 files changed, 82 insertions(+), 36 deletions(-)
>
> diff --git a/Documentation/technical/paint-down-to-common.adoc b/Documentation/technical/paint-down-to-common.adoc
> index cea0cc2f91..37fa6f93c1 100644
> --- a/Documentation/technical/paint-down-to-common.adoc
> +++ b/Documentation/technical/paint-down-to-common.adoc
> @@ -103,15 +103,12 @@ re-enqueued is bounded by the number of flag transitions.
>  Termination
>  -----------
>
> -The walk uses a `nonstale_queue` wrapper around `prio_queue` that
> -tracks `max_nonstale`: the lowest-priority non-stale commit enqueued
> -so far. Once that commit is dequeued, every remaining entry is known
> -to be STALE and the loop terminates. Specifically, the main loop
> +The walk tracks the number of commits of each type in the queue
> +(PARENT1-only, PARENT2-only, pending merge-base). The main loop
>  ends when one of the following conditions holds:
>
>    1. The queue is empty.
> -  2. `max_nonstale` has been dequeued, meaning the queue only contains
> -     STALE entries.
> +  2. The queue contains only stale entries.
>    3. Generation cutoff: the dequeued commit's generation is below
>       a caller-supplied `min_generation` threshold.
>    4. Single result: the caller only needs one merge base, one has
> diff --git a/commit-reach.c b/commit-reach.c
> index d59e76a2e2..a62b5e4624 100644
> --- a/commit-reach.c
> +++ b/commit-reach.c
> @@ -79,21 +79,73 @@ static void clear_nonstale_queue(struct nonstale_queue *queue)
>         queue->max_nonstale = NULL;
>  }
>
> -static void nonstale_queue_put_dedup(struct nonstale_queue *queue,
> -                                    struct commit *c)
> +/*
> + * Priority queue with per-side commit counters for paint_down_to_common().
> + * Each non-stale queued commit occupies exactly one bucket: PARENT1-only,
> + * PARENT2-only, or both (a pending merge-base candidate).
> + */
> +struct paint_state {
> +       struct prio_queue queue;
> +       size_t parent1_count;
> +       size_t parent2_count;
> +       size_t mb_candidate_count;
> +       int gen_ordered;
> +};
> +
> +static void paint_count_update(struct paint_state *state,
> +                              unsigned flags, int delta)
>  {
> -       if (c->object.flags & ENQUEUED)
> -               return;
> -       c->object.flags |= ENQUEUED;
> -       nonstale_queue_put(queue, c);
> +       switch (flags & (PARENT1 | PARENT2 | STALE)) {
> +       case PARENT1:
> +               state->parent1_count += delta;
> +               break;
> +
> +       case PARENT2:
> +               state->parent2_count += delta;
> +               break;
> +
> +       case PARENT1 | PARENT2:
> +               state->mb_candidate_count += delta;
> +               break;
> +
> +       case PARENT1 | PARENT2 | STALE:
> +               break;
> +
> +       default:
> +               BUG("unexpected paint state");

So, if anyone tries to refactor and adds a nonsense flag combination, e.g. PARENT1 | STALE, this will trip. Good.

Show 12 quoted lines

> +       }
> +}
> +
> +static void paint_queue_put(struct paint_state *state,
> +                           struct commit *c, unsigned add_flags)
> +{
> +       unsigned old_flags = c->object.flags;
> +       c->object.flags |= add_flags;
> +
> +       if (old_flags & ENQUEUED) {
> +               paint_count_update(state, old_flags, -1);
> +               paint_count_update(state, c->object.flags, 1);

If this object was already in the queue, remove the old counters for
it (e.g. PARENT1), and add the new union counters for it (e.g. PARENT1
| PARENT2).  Good.

> +       } else {
> +               c->object.flags |= ENQUEUED;
> +               prio_queue_put(&state->queue, c);
> +               paint_count_update(state, c->object.flags, 1);

...and if it wasn't, put it in the queue and add the counters for it. Also good.

Show 23 quoted lines

> +       }
>  }
>
> -static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
> +static struct commit *paint_queue_get(struct paint_state *state)
>  {
> -       struct commit *commit = nonstale_queue_get(queue);
> +       struct commit *commit = prio_queue_get(&state->queue);
> +
> +       if (!commit)
> +               return NULL;
> +
> +       commit->object.flags &= ~ENQUEUED;
> +
> +       if (!state->parent1_count && !state->parent2_count &&
> +           !state->mb_candidate_count)
> +               return NULL;
>
> -       if (commit)
> -               commit->object.flags &= ~ENQUEUED;
> +       paint_count_update(state, commit->object.flags, -1);
>         return commit;
>  }

So: pop, clear, check the counters, and _then_ decrement the counters.
This means the zero-counter-check still include the just-popped
commit.  If the decrement were before the check, we'd actually just
barely miss the merge-base most the time, so this order is important.

Show 79 quoted lines

>
> @@ -109,18 +161,19 @@ static int paint_down_to_common(struct repository *r,
>                                 enum merge_base_flags mb_flags,
>                                 struct commit_list **result)
>  {
> -       struct nonstale_queue queue = {
> -               { compare_commits_by_gen_then_commit_date }
> +       struct paint_state state = {
> +               .queue = { compare_commits_by_gen_then_commit_date },
> +               .gen_ordered = 1,
>         };
> +       struct commit *commit;
>         int i;
> -       int gen_ordered = 1;
>         int steps = 0;
>         timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
>         struct commit_list **tail = result;
>
>         if (!min_generation && !corrected_commit_dates_enabled(r)) {
> -               queue.pq.compare = compare_commits_by_commit_date;
> -               gen_ordered = 0;
> +               state.queue.compare = compare_commits_by_commit_date;
> +               state.gen_ordered = 0;
>         }
>
>         one->object.flags |= PARENT1;
> @@ -128,15 +181,12 @@ static int paint_down_to_common(struct repository *r,
>                 commit_list_append(one, result);
>                 return 0;
>         }
> -       nonstale_queue_put_dedup(&queue, one);
> +       paint_queue_put(&state, one, 0);
>
> -       for (i = 0; i < n; i++) {
> -               twos[i]->object.flags |= PARENT2;
> -               nonstale_queue_put_dedup(&queue, twos[i]);
> -       }
> +       for (i = 0; i < n; i++)
> +               paint_queue_put(&state, twos[i], PARENT2);
>
> -       while (queue.max_nonstale) {
> -               struct commit *commit = nonstale_queue_get_dedup(&queue);
> +       while ((commit = paint_queue_get(&state))) {
>                 struct commit_list *parents;
>                 int flags;
>                 timestamp_t generation = commit_graph_generation(commit);
> @@ -162,7 +212,7 @@ static int paint_down_to_common(struct repository *r,
>                                  * descendant of this one.
>                                  */
>                                 if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
> -                                   gen_ordered &&
> +                                   state.gen_ordered &&
>                                     generation < GENERATION_NUMBER_INFINITY)
>                                         break;
>                         }
> @@ -176,7 +226,7 @@ static int paint_down_to_common(struct repository *r,
>                         if ((p->object.flags & flags) == flags)
>                                 continue;
>                         if (repo_parse_commit(r, p)) {
> -                               clear_nonstale_queue(&queue);
> +                               clear_prio_queue(&state.queue);
>                                 commit_list_free(*result);
>                                 *result = NULL;
>                                 /*
> @@ -191,12 +241,11 @@ static int paint_down_to_common(struct repository *r,
>                                 return error(_("could not parse commit %s"),
>                                              oid_to_hex(&p->object.oid));
>                         }
> -                       p->object.flags |= flags;
> -                       nonstale_queue_put_dedup(&queue, p);
> +                       paint_queue_put(&state, p, flags);
>                 }
>         }
>
> -       clear_nonstale_queue(&queue);
> +       clear_prio_queue(&state.queue);
>         trace2_data_intmax("paint_down_to_common", r,
>                            "steps", steps);
>         commit_list_sort_by_date(result);

Looks like the straightforward translation in paint_down_to_common() from the old algorithm to the new adjustment; nice that a few spots actually become a little shorter.

Show 33 quoted lines

> diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
> index 55aa220bb3..f9895f5fd7 100755
> --- a/t/t6600-test-reach.sh
> +++ b/t/t6600-test-reach.sh
> @@ -366,7 +366,7 @@ test_expect_success 'get_merge_bases_many:pending-stale' '
>                 git rev-parse ps-B
>         } >expect &&
>         test_all_modes get_merge_bases_many &&
> -       test_paint_down_steps 6 6 6 6
> +       test_paint_down_steps 5 5 5 5
>  '
>
>  test_expect_success 'get_merge_bases_many:infinity-both-sides' '
> @@ -381,7 +381,7 @@ test_expect_success 'get_merge_bases_many:infinity-both-sides' '
>                 git rev-parse pi-B
>         } >expect &&
>         test_all_modes get_merge_bases_many &&
> -       test_paint_down_steps 5 5 5 5
> +       test_paint_down_steps 5 4 5 5
>  '
>
>  test_expect_success 'setup mixed finite/INFINITY topology' '
> @@ -438,7 +438,7 @@ test_expect_success 'merge-base --all with clock skew and redundant ancestor (si
>         >input &&
>         git rev-parse se2-MB1 >expect &&
>         run_all_modes git merge-base --all se2-A se2-B &&
> -       test_paint_down_steps 8 7 8 8
> +       test_paint_down_steps 8 6 8 8
>  '
>
>  test_expect_success 'reduce_heads' '
> --
> gitgitgadget

Looks good.