[PATCH v2 0/2] fetch: write commit-graph using updated refs only

["Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com>]

When fetch.writeCommitGraph is enabled, the commit-graph is rebuilt from all
reachable refs after every fetch. This is unnecessarily expensive on
repositories with many refs, since add_ref_to_set() validates each ref
against the odb.

This series optimizes the commit-graph write by using only the newly updated
refs as seeds instead of scanning all refs. Since fetch writes the
commit-graph in split mode, the newly fetched history is added as a new
layer on top of the existing chain. A three-mode enum (REACHABLE / TIPS /
SKIP) makes the policy explicit:

 * No-op fetch: skip the commit-graph write entirely
 * Updated refs + existing graph: write incrementally from updated tips only
 * No existing graph or multi-remote fetch: fall back to full reachable scan

Patch 1 adds a commit-info subcommand to test-tool read-graph for verifying
graph contents in tests.

Patch 2 implements the optimization in builtin/fetch.c with tests covering
the incremental, unrelated-commit, no-op, fallback, and shallow-rejected
cases.

Benchmark on a synthetic setup: git.git with 200K extra packed refs (~206K
total), a local file:// remote, an existing split commit-graph and a warm
page cache. Times are the median of 9 runs of the trace2 region
fetch/write-commit-graph:

scenario          before    after
no-op fetch       380 ms    (skipped)
1 ref updated     357 ms    9.3 ms
10 refs updated   359 ms    8.9 ms


Changes since v1:

 * Explain in the commit message that fetch writes in split mode, so the new
   tips are added as a new layer on top of the existing chain, and that the
   incremental path relies on this (a non-split write would replace the
   graph with only the closure of the seeds).
 * Extend the incremental test to check that a local-only commit, which was
   in the graph before the fetch but is not reachable from the fetched tips,
   is still in the graph afterwards.
 * Add benchmark numbers to the commit message.
 * Add a comment explaining why shallow-rejected refs are skipped when
   collecting the updated tips (like store_updated_refs(), since their
   history is incomplete), and mention it in the commit message.
 * Add a test in t5537 for a fetch with fetch.writeCommitGraph where a ref
   is rejected because it would require changes to .git/shallow. Without the
   check, the commit-graph write dies on the missing parent.

Kristofer Karlsson (2):
  test-tool read-graph: add commit-info subcommand
  fetch: write commit-graph using updated refs only

 builtin/fetch.c            | 69 +++++++++++++++++++++++++++++++++-----
 commit-graph.c             |  2 +-
 commit-graph.h             |  1 +
 t/helper/test-read-graph.c | 23 ++++++++++++-
 t/t5510-fetch.sh           | 59 ++++++++++++++++++++++++++++++++
 t/t5537-fetch-shallow.sh   | 28 ++++++++++++++++
 6 files changed, 171 insertions(+), 11 deletions(-)


base-commit: 0f8e75abebff0877cae681a3d5ff31ac47f54220
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2239%2Fspkrka%2Fkrka%2Fincremental-commit-graph-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2239/spkrka/krka/incremental-commit-graph-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/2239

Range-diff vs v1:

 1:  36cc3ff3b3 = 1:  36cc3ff3b3 test-tool read-graph: add commit-info subcommand
 2:  fee92f3c20 ! 2:  7507354cc9 fetch: write commit-graph using updated refs only
     @@ Commit message
      
          Since do_fetch() already knows which refs were updated, collect them
          into an oidset and then pass them directly to write_commit_graph().
     -    In split mode, close_reachable() walks from the updated tips and
     -    stops at commits already present in the graph, efficiently adding
     -    the newly fetched history.  This reachability closure also covers
     -    auto-followed tags, since their targets are reachable from the
     -    fetched tips that caused them to be auto-followed.
     +    fetch always writes the commit-graph in split mode, so this adds a
     +    new layer on top of the existing chain rather than replacing it:
     +    close_reachable() walks from the updated tips and stops at commits
     +    already present in the graph, so the new layer only contains the
     +    newly fetched history, and commits covered by the existing layers
     +    remain covered.  This relies on split mode; a non-split write would
     +    replace the graph with just the closure of the seeds.
     +
     +    The reachability closure also covers auto-followed tags, since their
     +    targets are reachable from the fetched tips that caused them to be
     +    auto-followed.
     +
     +    Refs that are rejected because they would require changes to
     +    .git/shallow are skipped, just like store_updated_refs() does.  Their
     +    objects are received but their history is incomplete, so walking from
     +    them would make the commit-graph write fail.
      
          After fetch_one() returns, call prepare_commit_graph() (which is
          made non-static by this commit) to determine the graph-write mode:
     @@ Commit message
          which periodically rebuilds the commit-graph from all reachable
          refs.
      
     +    The effect was measured on a synthetic setup: git.git with 200K
     +    extra packed refs (~206K total), a local file:// remote, an existing
     +    split commit-graph and a warm page cache.  The times below are the
     +    median of 9 runs of the trace2 region fetch/write-commit-graph:
     +
     +        scenario          before    after
     +        no-op fetch       380 ms    (skipped)
     +        1 ref updated     357 ms    9.3 ms
     +        10 refs updated   359 ms    8.9 ms
     +
          Signed-off-by: Kristofer Karlsson <krka@spotify.com>
      
       ## builtin/fetch.c ##
     @@ builtin/fetch.c: out:
      +	struct ref *rm;
      +	for (rm = ref_map; rm; rm = rm->next) {
      +		struct commit *commit;
     ++		/*
     ++		 * Like store_updated_refs(), skip shallow-rejected refs:
     ++		 * they are not stored, and their history is incomplete.
     ++		 */
      +		if (rm->status == REF_STATUS_REJECT_SHALLOW)
      +			continue;
      +		if (is_null_oid(&rm->old_oid))
     @@ t/t5510-fetch.sh: test_expect_success 'fetch.writeCommitGraph' '
      +	git init incremental-source &&
      +	test_commit -C incremental-source one &&
      +	git clone incremental-source incremental-dest &&
     ++	test_commit -C incremental-dest local &&
      +	git -C incremental-dest commit-graph write --reachable --split &&
      +	test_commit -C incremental-source two &&
      +	test_commit -C incremental-source three &&
      +	(
      +		cd incremental-dest &&
      +		git -c fetch.writeCommitGraph=true fetch origin &&
     -+		test-tool read-graph commit-info three two
     ++		test-tool read-graph commit-info three two local
      +	)
      +'
      +
     @@ t/t5510-fetch.sh: test_expect_success 'fetch.writeCommitGraph' '
       test_expect_success 'fetch.writeCommitGraph with submodules' '
       	test_config_global protocol.file.allow always &&
       	git clone dups super &&
     +
     + ## t/t5537-fetch-shallow.sh ##
     +@@ t/t5537-fetch-shallow.sh: test_expect_success 'fetch that requires changes in .git/shallow is filtered' '
     + 	)
     + '
     + 
     ++test_expect_success 'fetch.writeCommitGraph skips refs that require changes in .git/shallow' '
     ++	git clone --no-local --depth=2 .git shallow-graph &&
     ++	(
     ++		cd shallow-graph &&
     ++		git checkout --orphan no-shallow &&
     ++		commit no-shallow
     ++	) &&
     ++	git init notshallow-graph &&
     ++	git -C notshallow-graph -c fetch.writeCommitGraph=true \
     ++		fetch ../shallow-graph/.git "refs/heads/*:refs/remotes/shallow/*" &&
     ++	(
     ++		cd shallow-graph &&
     ++		commit no-shallow-2
     ++	) &&
     ++	rejected=$(git -C shallow-graph rev-parse main) &&
     ++	(
     ++		cd notshallow-graph &&
     ++		git -c fetch.writeCommitGraph=true \
     ++			fetch ../shallow-graph/.git "refs/heads/*:refs/remotes/shallow/*" &&
     ++		git for-each-ref --format="%(refname)" >actual.refs &&
     ++		echo refs/remotes/shallow/no-shallow >expect.refs &&
     ++		test_cmp expect.refs actual.refs &&
     ++		test-tool read-graph commit-info shallow/no-shallow &&
     ++		test_expect_code 1 \
     ++			test-tool read-graph commit-info $rejected 2>/dev/null
     ++	)
     ++'
     ++
     + test_expect_success 'fetch --update-shallow' '
     + 	(
     + 	cd shallow &&

-- 
gitgitgadget