Re: [PATCH v7 05/10] commit-reach: add trace2 instrumentation to paint_down_to_common()

From: Elijah Newren <newren@gmail.com>
Date: Aug 7, 2026, 03:02 UTC
Message-ID: <CABPp-BHLHGQxuG3gO+nCa-FPFyOFEU2rk_oxLtFjekLqENvQUw@mail.gmail.com>
In-Reply-To: <490be76befc4689d463d472829c0271351b69a43.1786013982.git.gitgitgadget@gmail.com>

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

Show 7 quoted lines

>
> From: Kristofer Karlsson <krka@spotify.com>
>
> Add a step counter and trace2_data_intmax() call so that the number
> of commits visited during the paint walk is observable via
> GIT_TRACE2_EVENT. This provides a way to measure the impact of
> future optimizations without relying on wall-clock benchmarks alone.

Ooh, I like it.

Show 102 quoted lines

> Signed-off-by: Kristofer Karlsson <krka@spotify.com>
> ---
>  commit-reach.c        |  5 +++++
>  t/t6600-test-reach.sh | 44 ++++++++++++++++++++++++++++++-------------
>  2 files changed, 36 insertions(+), 13 deletions(-)
>
> diff --git a/commit-reach.c b/commit-reach.c
> index 8541264136..d59e76a2e2 100644
> --- a/commit-reach.c
> +++ b/commit-reach.c
> @@ -11,6 +11,7 @@
>  #include "tag.h"
>  #include "commit-reach.h"
>  #include "ewah/ewok.h"
> +#include "trace2.h"
>
>  /* Remember to update object flag allocation in object.h */
>  #define PARENT1                (1u<<16)
> @@ -113,6 +114,7 @@ static int paint_down_to_common(struct repository *r,
>         };
>         int i;
>         int gen_ordered = 1;
> +       int steps = 0;
>         timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
>         struct commit_list **tail = result;
>
> @@ -138,6 +140,7 @@ static int paint_down_to_common(struct repository *r,
>                 struct commit_list *parents;
>                 int flags;
>                 timestamp_t generation = commit_graph_generation(commit);
> +               steps++;
>
>                 if (min_generation && generation > last_gen)
>                         BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
> @@ -194,6 +197,8 @@ static int paint_down_to_common(struct repository *r,
>         }
>
>         clear_nonstale_queue(&queue);
> +       trace2_data_intmax("paint_down_to_common", r,
> +                          "steps", steps);
>         commit_list_sort_by_date(result);
>         return 0;
>  }
> diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
> index 698b831a6e..45aa26cd44 100755
> --- a/t/t6600-test-reach.sh
> +++ b/t/t6600-test-reach.sh
> @@ -153,24 +153,34 @@ test_expect_success 'setup' '
>  '
>
>  run_all_modes () {
> -       test_when_finished rm -rf .git/objects/info/commit-graph &&
> -       "$@" <input >actual &&
> -       test_cmp expect actual &&
> -       cp commit-graph-full .git/objects/info/commit-graph &&
> -       "$@" <input >actual &&
> -       test_cmp expect actual &&
> -       cp commit-graph-half .git/objects/info/commit-graph &&
> -       "$@" <input >actual &&
> -       test_cmp expect actual &&
> -       cp commit-graph-no-gdat .git/objects/info/commit-graph &&
> -       "$@" <input >actual &&
> -       test_cmp expect actual
> +       graph=.git/objects/info/commit-graph &&
> +       test_when_finished rm -rf "$graph" "${graph}s" &&
> +       rm -f trace-mode-*.txt &&
> +
> +       for mode in none full half no-gdat
> +       do
> +               rm -rf "$graph" "${graph}s" &&
> +               cp "commit-graph-${mode}" "$graph" 2>/dev/null ||
> +               true &&
> +               GIT_TRACE2_EVENT="$(pwd)/trace-mode-${mode}.txt" \
> +                       "$@" <input >actual &&
> +               test_cmp expect actual || return 1
> +       done
>  }
>
>  test_all_modes () {
>         run_all_modes test-tool reach "$@"
>  }
>
> +test_paint_down_steps () {
> +       for mode in none full half no-gdat
> +       do
> +               test_trace2_data_singular paint_down_to_common steps "$1" \
> +                       "mode=$mode" <"trace-mode-${mode}.txt" || return 1
> +               shift
> +       done
> +}
> +
>  test_expect_success 'ref_newer:miss' '
>         cat >input <<-\EOF &&
>         A:commit-5-7
> @@ -244,7 +254,8 @@ test_expect_success 'in_merge_bases_many:self' '
>         X:commit-6-8
>         EOF
>         echo "in_merge_bases_many(A,X):1" >expect &&
> -       test_all_modes in_merge_bases_many
> +       test_all_modes in_merge_bases_many &&
> +       test_paint_down_steps 45 2 25 3
>  '

Whoa, what? <Digs around for a while.> So, this is really confusing at first to a reviewer; it makes me think you are testing that you've already written the optimization and that some forms of commit-graphs provide a speedup from your work that doesn't land until later in the series. It might help if you point out either in the commit message or a comment here that this code is just relying on pre-existing optimization where a min_generation is passed and --all is not passed. (In contrast to below where --all is passed, so it has to dig deeper with or without the commit graph).

Show 18 quoted lines

>
>  test_expect_success 'is_descendant_of:hit' '
> @@ -329,6 +340,13 @@ test_expect_success 'get_merge_bases_many:infinity-both-sides' '
>         test_all_modes get_merge_bases_many
>  '
>
> +test_expect_success 'merge-base --all commit-walk steps' '
> +       >input &&
> +       git rev-parse commit-9-1 >expect &&
> +       run_all_modes git merge-base --all commit-9-9 commit-9-1 &&
> +       test_paint_down_steps 81 80 81 81
> +'
> +
>  test_expect_success 'reduce_heads' '
>         cat >input <<-\EOF &&
>         X:commit-1-10
> --
> gitgitgadget

Other than the double take above, looks good.