[PATCH v2 00/17] pack-objects: add --path-walk option for better deltas

This is a reviewable series introducing the path-walk API and its application within the 'git pack-objects --path-walk' machinery. This API was previously discussed in the path-walk RFC [1] and the patch series around the --full-name-hash option (branch ds/pack-name-hash-tweak) [2]. This series conflicts with ds/pack-name-hash-tweak, but that was on hold because it did not seem as critical based on community interest.

[1] https://lore.kernel.org/git/pull.1786.git.1725935335.gitgitgadget@gmail.com

[2] https://lore.kernel.org/git/pull.1785.git.1725890210.gitgitgadget@gmail.com

The primary motivation for this feature is its use to shrink the packfile created by 'git push' when there are many name-hash collisions. This need was discovered in several Javascript repositories that use the beachball tool [3] to generate CHANGELOG.md and CHANGELOG.json files. When a batch of these files are created at the same time and pushed to a release branch, the 'git pack-objects' process has many collisions among these files and delta bases are selected poorly.

[3] https://github.com/microsoft/beachball

In some cases, 'git push' is pushing 60-100 MB when the new path-walk algorithm will identify better delta bases and pack the same objects into a thin pack less than 1 MB. This was the most extreme example we could find and is present in a private monorepo. However, the microsoft/fluentui repo [4] is a good example for demonstrating similar improvements. The patch descriptions frequently refer to this repo and which commit should be checked out to reproduce this behavior.

[4] https://github.com/microsoft/fluentui

The path-walk API is a new way to walk objects. Traditionally, the revision API walks objects by visiting a commit, then visiting its root tree and recursing through trees to visit reachable objects that were not previously visited. The path-walk API visits objects in batches based on the path walked from a root tree to that object. (Only the first discovered path is chosen; this avoids certain kinds of Git bombs.)

This has an immediate application to 'git pack-objects'.

When using the traditional revision API to walk objects, each object is emitted with an associated path. Since this path may appear for many objects spread across the full list, a heuristic is used: the "name-hash" is stored for that object instead of the full path name. This name-hash will group objects at the same path together, but also has a form of "locality" to group likely-similar objects together. When there are few collisions in the name-hash function, this helps compress objects that appear at the same path as well as help compress objects across different paths that have similar suffixes. When there are many versions of the same path, then finding delta bases across that family of objects is very important. When there are few versions of the same path, then finding cross-name delta bases is also important. The former is important for clones and repacks while the latter is important for shallow clones. They can both be important for pushes. In all cases, this approach is fraught when there are many name-hash collisions as the window size becomes a limiting factor for finding quality delta bases.

When using the path-walk API to walk objects, we group objects by the same path from the start. We don't need to store the path name, since we have the objects already in a group. We can compute deltas within that group and then use the name-hash approach to resort the object list and look for opportunistic cross-path deltas. Thus, the path-walk approach allows finding delta bases at least as good as the traditional revision API approach. (Caveat: if we assume delta reuse and the existing deltas were computed with the revision API approach, then the path-walk API approach may result in slightly worse delta compression. The performance tests in this series use --no-reuse-delta for this reason.)

Once 'git pack-objects --path-walk' exists, we have a few ways to take advantage of it in other places:

 * The new 'pack.usePathWalk' config option will assume the --path-walk
   option. This allows 'git push' to assume this value and get the effect we
   want. This is similar to the 'pack.useSparse' config option that uses a
   similar path-based walk to limit the set of boundary objects.

 * 'git repack' learns a '--path-walk' option to pass to its child 'git
   pack-objects' process. This is also implied by 'pack.usePathWalk' but
   allows for testing without modifying repository config.

I'll repeat the following table of repacking results when using 'git repack -adf [--path-walk]' on a set of repositories with many name-hash collisions. Only the microsoft/fluentui repository is publicly available for testing, so the others are left as Repo B/C/D.

| Repo     | Standard Repack | With --path-walk |
|----------|-----------------|------------------|
| fluentui |         438 MB  |          148 MB  |
| Repo B   |       6,255 MB  |          778 MB  |
| Repo C   |      37,737 MB  |        6,158 MB  |
| Repo D   |     130,049 MB  |        4,432 MB  |

While this series is replacing ds/pack-name-hash-tweak and its introduction of the --full-name-hash option, it is worth comparing that option to the --path-walk option.

 * The --full-name-hash option is a much smaller code change, as it drops
   into the existing uses of the name-hash function.

 * The --full-name-hash option is more likely to integrate with server-side
   features such as delta islands and reachability bitmaps due to not
   changing the object walk. It was already noted that the .bitmap files
   store name-hash values, so there is some compatibility required to
   integrate with bitmaps. The --path-walk option will be more difficult to
   integrate with those options (at least during a repack), but maybe is not
   impossible; the --path-walk option will not work when reading
   reachability bitmaps, since we are avoiding walking trees entirely.

 * The --full-name-hash option is good when there are many name-hash
   collisions and many versions of the paths with those collisions. When
   creating a shallow clone or certain kinds of pushes, the --full-name-hash
   option is much worse at finding cross-path delta bases since it loses the
   locality of the standard name-hash function. The --path-walk option
   includes a second pass of delta computation using the standard name-hash
   function and thus finds good cross-path delta bases when they improve
   upon the same-path delta bases.

There are a few differences from the RFC version of this series:

 1. The last two patches refactor the approach to perform delta calculations
    by path after the object walk and then allows those delta calculations
    to happen in a threaded manner.

 2. Both 'git pack-objects' and 'git repack' are removed from the t0450
    exclusion list.

 3. The path-walk API has improved technical documentation that is extended
    as its functionality is expanded.

 4. Various bugs have been patched with matching tests. The new 'test-tool
    path-walk' helper allows for careful testing of the API separately from
    its use within other commands.

Updates in v2 =============

I'm sending this v2 to request some review feedback on the series. I'm sorry it's so long.

There are two updates in this version:

 * Fixed a performance issue in the presence of many annotated tags. This is
   caught by p5313 when run on a repo with 10,000+ annotated tags.
 * The Scalar config was previously wrong and should be pack.usePathWalk,
   not push.usePathWalk.

Thanks, - Stolee

Derrick Stolee (17):
  path-walk: introduce an object walk by path
  t6601: add helper for testing path-walk API
  path-walk: allow consumer to specify object types
  path-walk: allow visiting tags
  revision: create mark_trees_uninteresting_dense()
  path-walk: add prune_all_uninteresting option
  pack-objects: extract should_attempt_deltas()
  pack-objects: add --path-walk option
  pack-objects: update usage to match docs
  p5313: add performance tests for --path-walk
  pack-objects: introduce GIT_TEST_PACK_PATH_WALK
  repack: add --path-walk option
  repack: update usage to match docs
  pack-objects: enable --path-walk via config
  scalar: enable path-walk during push via config
  pack-objects: refactor path-walk delta phase
  pack-objects: thread the path-based compression

 Documentation/config/feature.txt          |   4 +
 Documentation/config/pack.txt             |   8 +
 Documentation/git-pack-objects.txt        |  23 +-
 Documentation/git-repack.txt              |  17 +-
 Documentation/technical/api-path-walk.txt |  73 ++++
 Makefile                                  |   2 +
 builtin/pack-objects.c                    | 410 ++++++++++++++++++++--
 builtin/repack.c                          |   9 +-
 ci/run-build-and-tests.sh                 |   1 +
 pack-objects.h                            |  12 +
 path-walk.c                               | 406 +++++++++++++++++++++
 path-walk.h                               |  64 ++++
 repo-settings.c                           |   3 +
 repo-settings.h                           |   1 +
 revision.c                                |  15 +
 revision.h                                |   1 +
 scalar.c                                  |   1 +
 t/README                                  |   4 +
 t/helper/test-path-walk.c                 | 114 ++++++
 t/helper/test-tool.c                      |   1 +
 t/helper/test-tool.h                      |   1 +
 t/perf/p5313-pack-objects.sh              |  77 ++++
 t/t0411-clone-from-partial.sh             |   6 +
 t/t0450/txt-help-mismatches               |   2 -
 t/t5300-pack-object.sh                    |  21 ++
 t/t5306-pack-nobase.sh                    |   5 +
 t/t5310-pack-bitmaps.sh                   |  13 +-
 t/t5316-pack-delta-depth.sh               |   9 +-
 t/t5332-multi-pack-reuse.sh               |   7 +
 t/t6601-path-walk.sh                      | 301 ++++++++++++++++
 t/t7406-submodule-update.sh               |   4 +
 31 files changed, 1565 insertions(+), 50 deletions(-)
 create mode 100644 Documentation/technical/api-path-walk.txt
 create mode 100644 path-walk.c
 create mode 100644 path-walk.h
 create mode 100644 t/helper/test-path-walk.c
 create mode 100755 t/perf/p5313-pack-objects.sh
 create mode 100755 t/t6601-path-walk.sh

base-commit: e9356ba3ea2a6754281ff7697b3e5a1697b21e24
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1813%2Fderrickstolee%2Fpath-walk-upstream-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1813/derrickstolee/path-walk-upstream-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/1813

Range-diff vs v1:

  1:  98bdc94a773 =  1:  98bdc94a773 path-walk: introduce an object walk by path
  2:  a00ab0c62c9 =  2:  a00ab0c62c9 t6601: add helper for testing path-walk API
  3:  14375d19392 =  3:  14375d19392 path-walk: allow consumer to specify object types
  4:  6f48cddadc0 !  4:  c321f58c62d path-walk: allow visiting tags
     @@ path-walk.c: int walk_objects_by_path(struct path_walk_info *info)
      +			if (obj->type == OBJ_COMMIT || obj->flags & SEEN)
      +				continue;
      +
     -+			obj->flags |= SEEN;
     -+
      +			while (obj->type == OBJ_TAG) {
      +				struct tag *tag = lookup_tag(info->revs->repo,
      +							     &obj->oid);
     -+				if (oid_array_lookup(&tags, &obj->oid) < 0)
     ++				if (!(obj->flags & SEEN)) {
     ++					obj->flags |= SEEN;
      +					oid_array_append(&tags, &obj->oid);
     ++				}
      +				obj = tag->tagged;
      +			}
      +
     ++			if ((obj->flags & SEEN))
     ++				continue;
     ++			obj->flags |= SEEN;
     ++
      +			switch (obj->type) {
      +			case OBJ_TREE:
     -+				if (info->trees &&
     -+				    oid_array_lookup(&root_tree_list->oids, &obj->oid) < 0)
     ++				if (info->trees)
      +					oid_array_append(&root_tree_list->oids, &obj->oid);
      +				break;
      +
      +			case OBJ_BLOB:
     -+				if (info->blobs &&
     -+				    oid_array_lookup(&tagged_blob_list, &obj->oid) < 0)
     ++				if (info->blobs)
      +					oid_array_append(&tagged_blob_list, &obj->oid);
      +				break;
      +
  5:  cd98447f7c8 =  5:  6e89fb219b5 revision: create mark_trees_uninteresting_dense()
  6:  214e10a9984 =  6:  238d7d95715 path-walk: add prune_all_uninteresting option
  7:  cd360ad1040 =  7:  3fdb57edbc5 pack-objects: extract should_attempt_deltas()
  8:  f8ee11d3003 =  8:  a0475c7cba8 pack-objects: add --path-walk option
  9:  eaeb40980f4 =  9:  73c8b61e87b pack-objects: update usage to match docs
 10:  3113ead1e01 = 10:  21dc3723c36 p5313: add performance tests for --path-walk
 11:  211a16ae889 = 11:  6f96b1c227a pack-objects: introduce GIT_TEST_PACK_PATH_WALK
 12:  507ed0f6f90 = 12:  834c9ea2709 repack: add --path-walk option
 13:  eae96e8214f = 13:  6ef8d67af4b repack: update usage to match docs
 14:  2a9ae02217f = 14:  1db90e361ba pack-objects: enable --path-walk via config
 15:  adcb3167809 ! 15:  0f3040b4b90 scalar: enable path-walk during push via config
     @@ scalar.c: static int set_recommended_config(int reconfigure)
       		{ "core.autoCRLF", "false" },
       		{ "core.safeCRLF", "false" },
       		{ "fetch.showForcedUpdates", "false" },
     -+		{ "push.usePathWalk", "true" },
     ++		{ "pack.usePathWalk", "true" },
       		{ NULL, NULL },
       	};
       	int i;
 16:  c3f24dc3647 = 16:  030d8ec238e pack-objects: refactor path-walk delta phase
 17:  264affbf058 = 17:  fddc320eb0b pack-objects: thread the path-based compression