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

Re: [PATCH 1/2] commit-graph: add trace2 instrumentation for generation DFS

From
Junio C Hamano <gitster@pobox.com>
Date
Jul 7, 2026, 16:55 UTC
Message-ID
<xmqq1pde7n8h.fsf@gitster.g>
In-Reply-To
<b865c2bcff53a32637aac426dd2c6ef4a4c27077.1783418384.git.gitgitgadget@gmail.com>

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

Show 7 quoted lines
> From: Kristofer Karlsson <krka@spotify.com>
>
> Add a step counter and trace2_data_intmax call to
> compute_reachable_generation_numbers() to make the cost of
> the generation number DFS observable.  This exposes a
> regression introduced in 199d452758 (commit-graph: fix
> "filling in" topological levels, 2025-04-07) where
Where did "fix filling in" came from?  Are you blaming
    199d452758 (commit-graph: return the prepared commit graph from
    `prepare_commit_graph()`, 2025-09-04)
or something else that happend in April that year?
> incremental commit-graph writes re-walk the entire commit
> ancestry instead of reading topo levels from lower graph
> layers.
Show 6 quoted lines
> Add a test that demonstrates the problem: with a two-layer
> split commit-graph, writing a new incremental layer for a
> commit whose parent is in the base layer walks all the way
> down to the root (7 steps for 5 base commits) instead of
> reading the existing topo level and stopping immediately
> (1 step).

OK. I expect that [2/2] would update this exact test to demonstrate that with code updated in [2/2] the extra walk will no longer happen.

Show 34 quoted lines
> Signed-off-by: Kristofer Karlsson <krka@spotify.com>
> ---
>  commit-graph.c                |  5 +++++
>  t/t5324-split-commit-graph.sh | 28 ++++++++++++++++++++++++++++
>  2 files changed, 33 insertions(+)
>
> diff --git a/commit-graph.c b/commit-graph.c
> index 801471a098..4e39a048c4 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -1653,6 +1653,7 @@ static void compute_reachable_generation_numbers(
>  {
>  	int i;
>  	struct commit_list *list = NULL;
> +	intmax_t steps = 0;
>  
>  	for (i = 0; i < info->commits->nr; i++) {
>  		struct commit *c = info->commits->items[i];
> @@ -1671,6 +1672,7 @@ static void compute_reachable_generation_numbers(
>  			int all_parents_computed = 1;
>  			timestamp_t max_gen = 0;
>  
> +			steps++;
>  			for (parent = current->parents; parent; parent = parent->next) {
>  				repo_parse_commit(info->r, parent->item);
>  				gen = info->get_generation(parent->item, info->data);
> @@ -1694,6 +1696,9 @@ static void compute_reachable_generation_numbers(
>  			}
>  		}
>  	}
> +
> +	trace2_data_intmax("commit-graph", info->r,
> +			   "generation-dfs-steps", steps);
>  }
Pretty-much trivial addition of a trace element.
Show 39 quoted lines
> diff --git a/t/t5324-split-commit-graph.sh b/t/t5324-split-commit-graph.sh
> index 49a057cc2e..f9c57760f4 100755
> --- a/t/t5324-split-commit-graph.sh
> +++ b/t/t5324-split-commit-graph.sh
> @@ -718,6 +718,34 @@ test_expect_success 'write generation data chunk when commit-graph chain is repl
>  	)
>  '
>  
> +test_expect_success 'incremental write reads topo levels from all layers' '
> +	git init topo-from-lower &&
> +	(
> +		cd topo-from-lower &&
> +
> +		for i in $(test_seq 5)
> +		do
> +			test_commit base-$i || return 1
> +		done &&
> +		git commit-graph write --reachable &&
> +
> +		test_commit extra &&
> +		git commit-graph write --reachable --split=no-merge &&
> +
> +		git checkout base-3 &&
> +		test_commit new-branch &&
> +
> +		GIT_TRACE2_EVENT="$(pwd)/trace.txt" \
> +			git commit-graph write --reachable --split=no-merge &&
> +
> +		# BUG: topo levels from lower graph layers are not
> +		# propagated, so the DFS re-walks from base-3 down to
> +		# the root (7 steps) instead of reading topo levels
> +		# from the existing graph (1 step).
> +		test_trace2_data commit-graph generation-dfs-steps 7 <trace.txt
> +	)
> +'
> +
>  test_expect_success 'temporary graph layer is discarded upon failure' '
>  	git init layer-discard &&
>  	(
Previous: Kristofer KarlssonNext: Kristofer Karlsson
Message 12 of 28 in “commit-graph: fix topo_levels slab propagation regression”
  1. 0/2 commit-graph: fix topo_levels slab propagation regressionKristofer Karlsson via GitGitGadget, Jul 7, 2026
  2. 1/2 commit-graph: add trace2 instrumentation for generation DFSKristofer Karlsson via GitGitGadget, Jul 7, 2026
  3. Taylor BlauJul 7, 2026
  4. Kristofer KarlssonJul 7, 2026
  5. Taylor BlauJul 10, 2026
  6. Junio C HamanoJul 10, 2026
  7. Taylor BlauJul 10, 2026
  8. Junio C HamanoJul 11, 2026
  9. Kristofer KarlssonJul 13, 2026
  10. Junio C HamanoJul 13, 2026
  11. Kristofer KarlssonJul 13, 2026
  12. Junio C HamanoJul 7, 2026
  13. Kristofer KarlssonJul 7, 2026
  14. 2/2 commit-graph: propagate topo_levels slab to all chain layersKristofer Karlsson via GitGitGadget, Jul 7, 2026
  15. Taylor BlauJul 7, 2026
  16. Kristofer KarlssonJul 7, 2026
  17. Kristofer KarlssonJul 7, 2026
  18. Taylor BlauJul 10, 2026
  19. Patrick SteinhardtJul 13, 2026
  20. Taylor BlauJul 14, 2026
  21. Junio C HamanoJul 7, 2026
  22. Kristofer KarlssonJul 7, 2026
  23. Junio C HamanoJul 7, 2026
  24. Patrick SteinhardtJul 9, 2026
  25. 0/2 commit-graph: fix topo_levels slab propagation regressionKristofer Karlsson via GitGitGadget, Jul 9, 2026
  26. 1/2 commit-graph: add trace2 instrumentation for generation DFSKristofer Karlsson via GitGitGadget, Jul 9, 2026
  27. 2/2 commit-graph: propagate topo_levels slab to all chain layersKristofer Karlsson via GitGitGadget, Jul 9, 2026
  28. Taylor BlauJul 10, 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.