pack-objects: Create an alternative name hash algorithm (recreated)

This is a recreation of the topic in [1] that was closed. (I force-pushed my branch and GitHub won't let me reopen the PR for GitGitGadget to create this as v3.)

[1]
https://lore.kernel.org/git/[email protected]/

I've been focused recently on understanding and mitigating the growth of a few internal repositories. Some of these are growing much larger than expected for the number of contributors, and there are multiple aspects to why this growth is so large.

This is part of the RFC I submitted [2] involving the path-walk API, though this doesn't use the path-walk API directly. In full repack cases, it seems that the --full-name-hash option gets nearly as good compression as the --path-walk option introduced in that series. I continue to work on that feature as well, so we can review it after this series is complete.

[2]
https://lore.kernel.org/git/[email protected]/

The main issue plaguing these repositories is that deltas are not being computed against objects that appear at the same path. While the size of these files at tip is one aspect of growth that would prevent this issue, the changes to these files are reasonable and should result in good delta compression. However, Git is not discovering the connections across different versions of the same file.

One way to find some improvement in these repositories is to increase the window size, which was an initial indicator that the delta compression could be improved, but was not a clear indicator. After some digging (and prototyping some analysis tools) the main discovery was that the current name-hash algorithm only considers the last 16 characters in the path name and has some naturally-occurring collisions within that scope.

This series introduces a new name-hash algorithm, but does not replace the existing one. There are cases, such as packing a single snapshot of a repository, where the existing algorithm outperforms the new one.

However, my findings show that when a repository has many versions of files at the same path (and especially when there are many name-hash collisions) then there are significant gains to be made using the new algorithm.

(This table is updated in v2 with even more private examples that were found while communicating findings internally.)

| Repo     | Standard Repack | With --full-name-hash |
|----------|-----------------|-----------------------|
| fluentui |         438 MB  |               168 MB  |
| Repo B   |       6,255 MB  |               829 MB  |
| Repo C   |      37,737 MB  |             7,125 MB  |
| Repo D   |     130,049 MB  |             6,190 MB  |
| Repo E   |     100,957 MB  |            22,979 MB  |
| Repo F   |       8,308 MB  |               746 MB  |
| Repo G   |       4,329 MB  |             3,643 MB  |

Since there has been some interest in these repacking results since [3] was published, I'll say that "Repo D" is the one mentioned in that post. The --path-walk repack further improves the results to under 4GB.

[3]
https://www.jonathancreamer.com/how-we-shrunk-our-git-repo-size-by-94-percent/

I include Repo G here as an example where the improvement is less drastic, since this repo does not demonstrate a very high rate of name-hash collisions; the collisions that exist seem to be in paths that are not changed very often. Thus, the standard name-hash algorithm is nearly as effective in these full repacks.

The main change in this series is in patch 1, which adds the algorithm and the option to 'git pack-objects' and 'git repack'. The remaining patches are focused on creating more evidence around the value of the new name-hash algorithm and its effects on the packfiles created with it.

I will also try to make clear that I've been focused on client-side performance and size concerns. Based on discussions in v1, it appears that the following is true:

* This feature is completely orthogonal to delta islands.

* Changing the name-hash function can lead to compatibility issues with .bitmap files, as they store a name-hash value. Without augmenting the data structure to indicate which name-hash value was used at write time, the full-name-hash values should not be stored in the .bitmap files or used when reading .bitmap files and other objects. Thus, the full-name-hash is marked as incompatible with bitmaps for now. (In this version, the 'git pack-objects' process will not fail but will prefer the standard name hash algorithm.)

* The --path-walk option is likely incompatible with the delta-islands feature without significant work, so this suggests that the --full-name-hash is a better long-term solution for servers. This would still require the .bitmap modifications to make it work, but it's a smaller leap to get there.

Thanks, -Stolee

UPDATES SINCE PREVIOUS VERSION
==============================

This is recreated after pursuing the path-walk API with 'git pack-objects --path-walk' [4] and also cutting the series into fewer patches and only including the path-walk API in [5].

[4]
https://lore.kernel.org/git/[email protected]/

[5]
https://lore.kernel.org/git/[email protected]/

This re-roll has these changes:

* The performance script is updated to include a simulation of a depth-1 shallow clone.

* The performance numbers in the commit messages are updated with the latest results and include more example repositories.

* Small style nits, especially around whitespace.

* To prevent the --full-name-hash option from having compatibility issues with .bitmap files, the previous version would cause the 'git pack-objects' process to fail. Now, the process succeeds, but the --full-name-hash option is disabled with a warning.

* These patches are rebased on a recent copy of 'master' and thus there are some new tests that need adjustment to work with GIT_TEST_FULL_NAME_HASH=1. They all care about an exact match with stderr and the warning to disable --full-name-hash causes a mismatch.

Here is the range-diff since the previous version:

1: 9c8f8f35f34 ! 1: 812257e197c pack-objects: add --full-name-hash option

    @@ Commit message
         Future changes could include making --full-name-hash implied by a config
         value or even implied by default during a full repack.
     
    +    It is important to point out that the name hash value is stored in the
    +    .bitmap file format, so we must disable the --full-name-hash option when
    +    bitmaps are being read or written. Later, the bitmap format could be
    +    updated to be aware of the name hash version so deltas can be quickly
    +    computed across the bitmapped/not-bitmapped boundary.
    +
         Signed-off-by: Derrick Stolee <[email protected]>
     
      ## Documentation/git-pack-objects.txt ##
    @@ builtin/pack-objects.c: static void add_cruft_object_entry(const struct object_i
      					    0, name && no_try_delta(name),
      					    pack, offset);
      	}
    -@@ builtin/pack-objects.c: int cmd_pack_objects(int argc, const char **argv, const char *prefix)
    +@@ builtin/pack-objects.c: int cmd_pack_objects(int argc,
      		OPT_STRING_LIST(0, "uri-protocol", &uri_protocols,
      				N_("protocol"),
      				N_("exclude any configured uploadpack.blobpackfileuri with this protocol")),
    @@ builtin/pack-objects.c: int cmd_pack_objects(int argc, const char **argv, const
      		OPT_END(),
      	};
      
    -@@ builtin/pack-objects.c: int cmd_pack_objects(int argc, const char **argv, const char *prefix)
    +@@ builtin/pack-objects.c: int cmd_pack_objects(int argc,
      	if (pack_to_stdout || !rev_list_all)
      		write_bitmap_index = 0;
      
    -+	if (write_bitmap_index && use_full_name_hash)
    -+		die(_("currently, the --full-name-hash option is incompatible with --write-bitmap-index"));
    ++	if (write_bitmap_index && use_full_name_hash) {
    ++		warning(_("currently, the --full-name-hash option is incompatible with --write-bitmap-index"));
    ++		use_full_name_hash = 0;
    ++	}
     +
      	if (use_delta_islands)
      		strvec_push(&rp, "--topo-order");
    @@ builtin/repack.c: static void prepare_pack_objects(struct child_process *cmd,
      	if (args->local)
      		strvec_push(&cmd->args,  "--local");
      	if (args->quiet)
    -@@ builtin/repack.c: int cmd_repack(int argc, const char **argv, const char *prefix)
    +@@ builtin/repack.c: int cmd_repack(int argc,
      				N_("pass --no-reuse-delta to git-pack-objects")),
      		OPT_BOOL('F', NULL, &po_args.no_reuse_object,
      				N_("pass --no-reuse-object to git-pack-objects")),
    @@ t/t5300-pack-object.sh: do
     +# TODO: Make these compatible in the future and replace this test with the
     +# expected behavior when both are specified.
     +test_expect_success '--full-name-hash and --write-bitmap-index are incompatible' '
    -+	test_must_fail git pack-objects base --all \
    -+		--full-name-hash --write-bitmap-index 2>err &&
    -+	grep incompatible err &&
    ++	git pack-objects base --all --full-name-hash --write-bitmap-index 2>err &&
    ++	test_grep incompatible err &&
     +
     +	# --stdout option silently removes --write-bitmap-index
    -+	git pack-objects --stdout --all --full-name-hash --write-bitmap-index >out
    ++	git pack-objects --stdout --all --full-name-hash --write-bitmap-index >out 2>err &&
    ++	! test_grep incompatible err
     +'
     +
      test_done

2: 612dbd1951b ! 2: 93395c93347 repack: test --full-name-hash option
@@ Metadata
Author: Derrick Stolee <[email protected]>

## Commit message ##
- repack: test --full-name-hash option
+ repack: add --full-name-hash option

The new '--full-name-hash' option for 'git repack' is a simple pass-through to the underlying 'git pack-objects' subcommand. However,
@@ t/test-lib-functions.sh: test_subcommand () {
fi
}

-+
+# Check that the given subcommand was run with the given set of +# arguments in order (but with possible extra arguments).
+#
3: e173de67b6a ! 3: 259734e0bce pack-objects: add GIT_TEST_FULL_NAME_HASH
@@ Commit message
now, do the minimal change to make the test work by disabling the test variable.

+ Third, there are some tests that compare the exact output of a 'git
+ pack-objects' process when using bitmaps. The warning that disables the
+ --full-name-hash option causes these tests to fail. Disable the
+ environment variable to get around this issue.
+

## builtin/pack-objects.c ##
@@ builtin/pack-objects.c: struct configured_exclusion {

static inline uint32_t pack_name_hash_fn(const char *name)
{
-@@ builtin/pack-objects.c: int cmd_pack_objects(int argc, const char **argv, const char *prefix) +@@ builtin/pack-objects.c: int cmd_pack_objects(int argc,
if (pack_to_stdout || !rev_list_all)
write_bitmap_index = 0;

-- if (write_bitmap_index && use_full_name_hash)
-+ if (write_bitmap_index && use_full_name_hash > 0)
- die(_("currently, the --full-name-hash option is incompatible with --write-bitmap-index"));
+- if (write_bitmap_index && use_full_name_hash) {
+ if (use_full_name_hash < 0)
+ use_full_name_hash = git_env_bool("GIT_TEST_FULL_NAME_HASH", 0);
-
- if (use_delta_islands)
- strvec_push(&rp, "--topo-order");
++
++ if (write_bitmap_index && use_full_name_hash > 0) {
+ warning(_("currently, the --full-name-hash option is incompatible with --write-bitmap-index"));
+ use_full_name_hash = 0;
+ }

## ci/run-build-and-tests.sh ##
@@ ci/run-build-and-tests.sh: linux-TEST-vars)
@@ t/README: a test and then fails then the whole test run will abort. This can hel
------------

+ ## t/t5310-pack-bitmaps.sh ##
+@@ t/t5310-pack-bitmaps.sh: test_bitmap_cases () {
+ cat >expect <<-\EOF &&
+ error: missing value for '\''pack.preferbitmaptips'\''
+ EOF
++
++ # Disable --full-name-hash test due to stderr comparison.
++ GIT_TEST_FULL_NAME_HASH=0 \
+ git repack -adb 2>actual &&
+ test_cmp expect actual
+ )
+
+ ## t/t5333-pseudo-merge-bitmaps.sh ##
+@@ t/t5333-pseudo-merge-bitmaps.sh: test_expect_success 'bitmapPseudoMerge.stableThreshold creates stable groups' '
+ '
+
+ test_expect_success 'out of order thresholds are rejected' '
++ # Disable this option to avoid stderr message
++ GIT_TEST_FULL_NAME_HASH=0 &&
++ export GIT_TEST_FULL_NAME_HASH &&
++
+ test_must_fail git \
+ -c bitmapPseudoMerge.test.pattern="refs/*" \
+ -c bitmapPseudoMerge.test.threshold=1.month.ago \
+
## t/t5510-fetch.sh ##
@@ t/t5510-fetch.sh: test_expect_success 'all boundary commits are excluded' '
test_tick &&
@@ t/t6020-bundle-misc.sh: test_expect_success 'create bundle with --since option'
--since "Thu Apr 7 15:27:00 2005 -0700" \
--all &&

+
+ ## t/t7406-submodule-update.sh ##
+@@ t/t7406-submodule-update.sh: test_expect_success 'submodule update --quiet passes quietness to fetch with a s
+ ) &&
+ git clone super4 super5 &&
+ (cd super5 &&
++ # This test var can mess with the stderr output checked in this test.
++ GIT_TEST_FULL_NAME_HASH=0 \
+ git submodule update --quiet --init --depth=1 submodule3 >out 2>err &&
+ test_must_be_empty out &&
+ test_must_be_empty err
+
+ ## t/t7700-repack.sh ##
+@@ t/t7700-repack.sh: test_expect_success 'no bitmaps created if .keep files present' '
+ keep=${pack%.pack}.keep &&
+ test_when_finished "rm -f \"\$keep\"" &&
+ >"$keep" &&
++
++ # Disable --full-name-hash test due to stderr comparison.
++ GIT_TEST_FULL_NAME_HASH=0 \
+ git -C bare.git repack -ad 2>stderr &&
+ test_must_be_empty stderr &&
+ find bare.git/objects/pack/ -type f -name "*.bitmap" >actual &&
+@@ t/t7700-repack.sh: test_expect_success 'auto-bitmaps do not complain if unavailable' '
+ blob=$(test-tool genrandom big $((1024*1024)) |
+ git -C bare.git hash-object -w --stdin) &&
+ git -C bare.git update-ref refs/tags/big $blob &&
++
++ # Disable --full-name-hash test due to stderr comparison.
++ GIT_TEST_FULL_NAME_HASH=0 \
+ git -C bare.git repack -ad 2>stderr &&
+ test_must_be_empty stderr &&
+ find bare.git/objects/pack -type f -name "*.bitmap" >actual &&

4:  543382b2702 = 4:  65784f85bce git-repack: update usage to match docs
5:  4d2381a19c4 ! 5:  c14ef6879e4 p5313: add size comparison test

@@ Commit message

Checked out at the parent of [2], I see the following statistics:

- Test this tree
- ------------------------------------------------------------------
- 5313.2: thin pack 0.02(0.01+0.01)
- 5313.3: thin pack size 1.1K
- 5313.4: thin pack with --full-name-hash 0.02(0.01+0.00)
- 5313.5: thin pack size with --full-name-hash 3.0K
- 5313.6: big pack 1.65(3.35+0.24)
- 5313.7: big pack size 58.0M
- 5313.8: big pack with --full-name-hash 1.53(2.52+0.18)
- 5313.9: big pack size with --full-name-hash 57.6M
- 5313.10: repack 176.52(706.60+3.53)
- 5313.11: repack size 446.7K
- 5313.12: repack with --full-name-hash 37.47(134.18+3.06)
- 5313.13: repack size with --full-name-hash 183.1K
-
- Note that this demonstrates a 3x size _increase_ in the case that
- simulates a small "git push". The size change is neutral on the case of
- pushing the difference between HEAD and HEAD~1000.
-
- However, the full repack case is both faster and more efficient.
+ Test HEAD
+ ---------------------------------------------------------------------
+ 5313.2: thin pack 0.37(0.43+0.02)
+ 5313.3: thin pack size 1.2M
+ 5313.4: thin pack with --full-name-hash 0.06(0.09+0.02)
+ 5313.5: thin pack size with --full-name-hash 20.4K
+ 5313.6: big pack 2.01(7.73+0.23)
+ 5313.7: big pack size 20.3M
+ 5313.8: big pack with --full-name-hash 1.32(2.77+0.27)
+ 5313.9: big pack size with --full-name-hash 19.9M
+ 5313.10: shallow fetch pack 1.40(3.01+0.08)
+ 5313.11: shallow pack size 34.4M
+ 5313.12: shallow pack with --full-name-hash 1.08(1.25+0.14)
+ 5313.13: shallow pack size with --full-name-hash 35.4M
+ 5313.14: repack 90.70(672.88+2.46)
+ 5313.15: repack size 439.6M
+ 5313.16: repack with --full-name-hash 18.53(123.41+2.53)
+ 5313.17: repack size with --full-name-hash 169.7M
+
+ In this case, we see positive behaviors such as a significant shrink in
+ the size of the thin pack and full repack. The big pack is slightly
+ smaller with --full-name-hash than without. The shallow pack is slightly
+ larger with --full-name-hash.
+
+ In the case of the Git repository, these numbers show some of the issues
+ with this approach:
+
+ Test HEAD
+ --------------------------------------------------------------------
+ 5313.2: thin pack 0.00(0.00+0.00)
+ 5313.3: thin pack size 589
+ 5313.4: thin pack with --full-name-hash 0.00(0.00+0.00)
+ 5313.5: thin pack size with --full-name-hash 14.9K
+ 5313.6: big pack 2.07(3.57+0.17)
+ 5313.7: big pack size 17.6M
+ 5313.8: big pack with --full-name-hash 2.00(3.07+0.19)
+ 5313.9: big pack size with --full-name-hash 17.9M
+ 5313.10: shallow fetch pack 1.41(2.23+0.06)
+ 5313.11: shallow pack size 12.1M
+ 5313.12: shallow pack with --full-name-hash 1.22(1.66+0.04)
+ 5313.13: shallow pack size with --full-name-hash 12.4M
+ 5313.14: repack 15.75(89.29+1.54)
+ 5313.15: repack size 126.4M
+ 5313.16: repack with --full-name-hash 15.56(89.78+1.32)
+ 5313.17: repack size with --full-name-hash 126.0M
+
+ The thin pack that simulates a push is much worse with --full-name-hash
+ in this case. The name hash values are doing a lot to assist with delta
+ bases, it seems. The big pack and shallow clone cases are slightly worse
+ with the --full-name-hash option. Only the full repack gains some
+ benefits in size.
+
+ The results are similar with the nodejs/node repo:
+
+ Test HEAD
+ ---------------------------------------------------------------------
+ 5313.2: thin pack 0.01(0.01+0.00)
+ 5313.3: thin pack size 1.6K
+ 5313.4: thin pack with --full-name-hash 0.01(0.00+0.00)
+ 5313.5: thin pack size with --full-name-hash 3.1K
+ 5313.6: big pack 4.26(8.03+0.24)
+ 5313.7: big pack size 56.0M
+ 5313.8: big pack with --full-name-hash 4.16(6.55+0.22)
+ 5313.9: big pack size with --full-name-hash 56.2M
+ 5313.10: shallow fetch pack 7.67(11.80+0.29)
+ 5313.11: shallow pack size 104.6M
+ 5313.12: shallow pack with --full-name-hash 7.52(9.65+0.23)
+ 5313.13: shallow pack size with --full-name-hash 105.9M
+ 5313.14: repack 71.22(317.61+3.95)
+ 5313.15: repack size 739.9M
+ 5313.16: repack with --full-name-hash 48.85(267.02+3.72)
+ 5313.17: repack size with --full-name-hash 793.5M
+
+ The Linux kernel repository was the initial target of the default name
+ hash value, and its naming conventions are practically build to take the
+ most advantage of the default name hash values:
+
+ Test HEAD
+ -------------------------------------------------------------------------
+ 5313.2: thin pack 0.15(0.01+0.03)
+ 5313.3: thin pack size 4.6K
+ 5313.4: thin pack with --full-name-hash 0.03(0.02+0.01)
+ 5313.5: thin pack size with --full-name-hash 6.8K
+ 5313.6: big pack 18.51(33.74+0.95)
+ 5313.7: big pack size 201.1M
+ 5313.8: big pack with --full-name-hash 16.01(29.81+0.88)
+ 5313.9: big pack size with --full-name-hash 202.1M
+ 5313.10: shallow fetch pack 11.49(17.61+0.54)
+ 5313.11: shallow pack size 269.2M
+ 5313.12: shallow pack with --full-name-hash 11.24(15.25+0.56)
+ 5313.13: shallow pack size with --full-name-hash 269.8M
+ 5313.14: repack 1001.25(2271.06+38.86)
+ 5313.15: repack size 2.5G
+ 5313.16: repack with --full-name-hash 625.75(1941.96+36.09)
+ 5313.17: repack size with --full-name-hash 2.6G
+
+ Finally, an internal Javascript repo of moderate size shows significant
+ gains when repacking with --full-name-hash due to it having many name
+ hash collisions. However, it's worth noting that only the full repack
+ case has enough improvement to be worth it. But the improvements are
+ significant: 6.4 GB to 862 MB.
+
+ Test HEAD
+ --------------------------------------------------------------------------
+ 5313.2: thin pack 0.03(0.02+0.00)
+ 5313.3: thin pack size 1.2K
+ 5313.4: thin pack with --full-name-hash 0.03(0.03+0.00)
+ 5313.5: thin pack size with --full-name-hash 2.6K
+ 5313.6: big pack 2.20(3.23+0.30)
+ 5313.7: big pack size 130.7M
+ 5313.8: big pack with --full-name-hash 2.33(3.17+0.34)
+ 5313.9: big pack size with --full-name-hash 131.0M
+ 5313.10: shallow fetch pack 3.56(6.02+0.32)
+ 5313.11: shallow pack size 44.5M
+ 5313.12: shallow pack with --full-name-hash 2.94(3.94+0.32)
+ 5313.13: shallow pack size with --full-name-hash 45.3M
+ 5313.14: repack 2435.22(12523.11+23.53)
+ 5313.15: repack size 6.4G
+ 5313.16: repack with --full-name-hash 473.25(1805.11+17.22)
+ 5313.17: repack size with --full-name-hash 861.9M
+
+ These tests demonstrate that it is important to be careful about which
+ cases are best for using the --full-name-hash option.

@@ t/perf/p5313-pack-objects.sh (new)
+ ^$(git rev-parse HEAD~1)
+ EOF
+
-+ cat >in-big <<-EOF
++ cat >in-big <<-EOF &&
+ $(git rev-parse HEAD)
+ ^$(git rev-parse HEAD~1000)
+ EOF
++
++ cat >in-shallow <<-EOF
++ $(git rev-parse HEAD)
++ --shallow $(git rev-parse HEAD)
++ EOF
+'
+
+test_perf 'thin pack' '
@@ t/perf/p5313-pack-objects.sh (new)
+ test_file_size out
+'
+
++test_perf 'shallow fetch pack' '
++ git pack-objects --stdout --revs --sparse --shallow <in-shallow >out
++'
++
++test_size 'shallow pack size' '
++ test_file_size out
++'
++
++test_perf 'shallow pack with --full-name-hash' '
++ git pack-objects --stdout --revs --sparse --shallow --full-name-hash <in-shallow >out
++'
++
++test_size 'shallow pack size with --full-name-hash' '
++ test_file_size out
++'
++
+test_perf 'repack' '
+ git repack -adf
+'

-:  ----------- > 6:  b8a055cb196 pack-objects: disable --full-name-hash when shallow
6:  80ba362f256 = 7:  ab341dd0e58 test-tool: add helper for name-hash values

Derrick Stolee (7):
pack-objects: add --full-name-hash option
repack: add --full-name-hash option
pack-objects: add GIT_TEST_FULL_NAME_HASH
git-repack: update usage to match docs
p5313: add size comparison test
pack-objects: disable --full-name-hash when shallow
test-tool: add helper for name-hash values

 Documentation/git-pack-objects.txt |  3 +-
 Documentation/git-repack.txt       |  4 +-
 Makefile                           |  1 +
 builtin/pack-objects.c             | 34 +++++++++--
 builtin/repack.c                   |  9 ++-
 ci/run-build-and-tests.sh          |  1 +
 pack-objects.h                     | 21 +++++++
 t/README                           |  4 ++
 t/helper/test-name-hash.c          | 24 ++++++++
 t/helper/test-tool.c               |  1 +
 t/helper/test-tool.h               |  1 +
 t/perf/p5313-pack-objects.sh       | 95 ++++++++++++++++++++++++++++++
 t/perf/p5314-name-hash.sh          | 41 +++++++++++++
 t/t0450/txt-help-mismatches        |  1 -
 t/t5300-pack-object.sh             | 15 +++++
 t/t5310-pack-bitmaps.sh            | 29 +++++++++
 t/t5333-pseudo-merge-bitmaps.sh    |  4 ++
 t/t5510-fetch.sh                   |  7 ++-
 t/t5616-partial-clone.sh           | 26 +++++++-
 t/t6020-bundle-misc.sh             |  6 +-
 t/t7406-submodule-update.sh        |  2 +
 t/t7700-repack.sh                  | 13 ++++
 t/test-lib-functions.sh            | 26 ++++++++
 23 files changed, 355 insertions(+), 13 deletions(-)
 create mode 100644 t/helper/test-name-hash.c
 create mode 100755 t/perf/p5313-pack-objects.sh
 create mode 100755 t/perf/p5314-name-hash.sh

base-commit: 8f8d6eee531b3fa1a8ef14f169b0cb5035f7a772
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1823%2Fderrickstolee%2Ffull-name-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1823/derrickstolee/full-name-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1823

gitgitgadget

From: Derrick Stolee <[email protected]>

The pack_name_hash() method has not been materially changed since it was introduced in ce0bd64299a (pack-objects: improve path grouping heuristics., 2006-06-05). The intention here is to group objects by path name, but also attempt to group similar file types together by making the most-significant digits of the hash be focused on the final characters.

Here's the crux of the implementation:

	/*
	 * This effectively just creates a sortable number from the
	 * last sixteen non-whitespace characters. Last characters
	 * count "most", so things that end in ".c" sort together.
	 */
	while ((c = *name++) != 0) {
		if (isspace(c))
			continue;
		hash = (hash >> 2) + (c << 24);
	}

As the comment mentions, this only cares about the last sixteen non-whitespace characters. This cause some filenames to collide more than others. Here are some examples that I've seen while investigating repositories that are growing more than they should be:

* "/CHANGELOG.json" is 15 characters, and is created by the beachball
[1] tool. Only the final character of the parent directory can differntiate different versions of this file, but also only the two most-significant digits. If that character is a letter, then this is always a collision. Similar issues occur with the similar "/CHANGELOG.md" path, though there is more opportunity for differences in the parent directory.

* Localization files frequently have common filenames but differentiate via parent directories. In C#, the name "/strings.resx.lcl" is used for these localization files and they will all collide in name-hash.

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

I've come across many other examples where some internal tool uses a common name across multiple directories and is causing Git to repack poorly due to name-hash collisions.

It is clear that the existing name-hash algorithm is optimized for repositories with short path names, but also is optimized for packing a single snapshot of a repository, not a repository with many versions of the same file. In my testing, this has proven out where the name-hash algorithm does a good job of finding peer files as delta bases when unable to use a historical version of that exact file.

However, for repositories that have many versions of most files and directories, it is more important that the objects that appear at the same path are grouped together.

Create a new pack_full_name_hash() method and a new --full-name-hash option for 'git pack-objects' to call that method instead. Add a simple pass-through for 'git repack --full-name-hash' for additional testing in the context of a full repack, where I expect this will be most effective.

The hash algorithm is as simple as possible to be reasonably effective:
for each character of the path string, add a multiple of that character and a large prime number (chosen arbitrarily, but intended to be large relative to the size of a uint32_t). Then, shift the current hash value to the right by 5, with overlap. The addition and shift parameters are standard mechanisms for creating hard-to-predict behaviors in the bits of the resulting hash.

This is not meant to be cryptographic at all, but uniformly distributed across the possible hash values. This creates a hash that appears pseudorandom. There is no ability to consider similar file types as being close to each other.

In a later change, a test-tool will be added so the effectiveness of this hash can be demonstrated directly.

For now, let's consider how effective this mechanism is when repacking a repository with and without the --full-name-hash option. Specifically, let's use 'git repack -adf [--full-name-hash]' as our test.

On the Git repository, we do not expect much difference. All path names are short. This is backed by our results:

| Stage                 | Pack Size | Repack Time |
|-----------------------|-----------|-------------|
| After clone           | 260 MB    | N/A         |
| Standard Repack       | 127MB     | 106s        |
| With --full-name-hash | 126 MB    | 99s         |

This example demonstrates how there is some natural overhead coming from the cloned copy because the server is hosting many forks and has not optimized for exactly this set of reachable objects. But the full repack has similar characteristics with and without --full-name-hash.

However, we can test this in a repository that uses one of the problematic naming conventions above. The fluentui [2] repo uses beachball to generate CHANGELOG.json and CHANGELOG.md files, and these files have very poor delta characteristics when comparing against versions across parent directories.

| Stage                 | Pack Size | Repack Time |
|-----------------------|-----------|-------------|
| After clone           | 694 MB    | N/A         |
| Standard Repack       | 438 MB    | 728s        |
| With --full-name-hash | 168 MB    | 142s        |

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

In this example, we see significant gains in the compressed packfile size as well as the time taken to compute the packfile.

Using a collection of repositories that use the beachball tool, I was able to make similar comparisions with dramatic results. While the fluentui repo is public, the others are private so cannot be shared for reproduction. The results are so significant that I find it important to share here:

| Repo     | Standard Repack | With --full-name-hash |
|----------|-----------------|-----------------------|
| fluentui |         438 MB  |               168 MB  |
| Repo B   |       6,255 MB  |               829 MB  |
| Repo C   |      37,737 MB  |             7,125 MB  |
| Repo D   |     130,049 MB  |             6,190 MB  |

Future changes could include making --full-name-hash implied by a config value or even implied by default during a full repack.

It is important to point out that the name hash value is stored in the .bitmap file format, so we must disable the --full-name-hash option when bitmaps are being read or written. Later, the bitmap format could be updated to be aware of the name hash version so deltas can be quickly computed across the bitmapped/not-bitmapped boundary.

---
 Documentation/git-pack-objects.txt |  3 ++-
 builtin/pack-objects.c             | 25 ++++++++++++++++++++-----
 builtin/repack.c                   |  5 +++++
 pack-objects.h                     | 21 +++++++++++++++++++++
 t/t5300-pack-object.sh             | 15 +++++++++++++++
 5 files changed, 63 insertions(+), 6 deletions(-)

index e32404c6aae..93861d9f85b 100644
@@ -15,7 +15,8 @@ SYNOPSIS
 	[--revs [--unpacked | --all]] [--keep-pack=<pack-name>]
 	[--cruft] [--cruft-expiration=<time>]
 	[--stdout [--filter=<filter-spec>] | <base-name>]
-	[--shallow] [--keep-true-parents] [--[no-]sparse] < <object-list>
+	[--shallow] [--keep-true-parents] [--[no-]sparse]
+	[--full-name-hash] < <object-list>
 
 
 DESCRIPTION

index 08007142671..85595dfcd88 100644
@@ -266,6 +266,14 @@ struct configured_exclusion {
 static struct oidmap configured_exclusions;
 
 static struct oidset excluded_by_config;
+static int use_full_name_hash;
+
+static inline uint32_t pack_name_hash_fn(const char *name)
+{
+	if (use_full_name_hash)
+		return pack_full_name_hash(name);
+	return pack_name_hash(name);
+}
 
 /*
  * stats

@@ -1698,7 +1706,7 @@ static int add_object_entry(const struct object_id *oid, enum object_type type,
 		return 0;
 	}
 
-	create_object_entry(oid, type, pack_name_hash(name),
+	create_object_entry(oid, type, pack_name_hash_fn(name),
 			    exclude, name && no_try_delta(name),
 			    found_pack, found_offset);
 	return 1;

@@ -1912,7 +1920,7 @@ static void add_preferred_base_object(const char *name)
 {
 	struct pbase_tree *it;
 	size_t cmplen;
-	unsigned hash = pack_name_hash(name);
+	unsigned hash = pack_name_hash_fn(name);
 
 	if (!num_preferred_base || check_pbase_path(hash))
 		return;

@@ -3422,7 +3430,7 @@ static void show_object_pack_hint(struct object *object, const char *name,
 	 * here using a now in order to perhaps improve the delta selection
 	 * process.
 	 */
-	oe->hash = pack_name_hash(name);
+	oe->hash = pack_name_hash_fn(name);
 	oe->no_try_delta = name && no_try_delta(name);
 
 	stdin_packs_hints_nr++;

@@ -3572,7 +3580,7 @@ static void add_cruft_object_entry(const struct object_id *oid, enum object_type
 	entry = packlist_find(&to_pack, oid);
 	if (entry) {
 		if (name) {
-			entry->hash = pack_name_hash(name);
+			entry->hash = pack_name_hash_fn(name);
 			entry->no_try_delta = no_try_delta(name);
 		}
 	} else {

@@ -3595,7 +3603,7 @@ static void add_cruft_object_entry(const struct object_id *oid, enum object_type
 			return;
 		}
 
-		entry = create_object_entry(oid, type, pack_name_hash(name),
+		entry = create_object_entry(oid, type, pack_name_hash_fn(name),
 					    0, name && no_try_delta(name),
 					    pack, offset);
 	}

@@ -4429,6 +4437,8 @@ int cmd_pack_objects(int argc,
 		OPT_STRING_LIST(0, "uri-protocol", &uri_protocols,
 				N_("protocol"),
 				N_("exclude any configured uploadpack.blobpackfileuri with this protocol")),
+		OPT_BOOL(0, "full-name-hash", &use_full_name_hash,
+			 N_("optimize delta compression across identical path names over time")),
 		OPT_END(),
 	};
 

@@ -4576,6 +4586,11 @@ int cmd_pack_objects(int argc,
 	if (pack_to_stdout || !rev_list_all)
 		write_bitmap_index = 0;
 
+	if (write_bitmap_index && use_full_name_hash) {
+		warning(_("currently, the --full-name-hash option is incompatible with --write-bitmap-index"));
+		use_full_name_hash = 0;
+	}
+
 	if (use_delta_islands)
 		strvec_push(&rp, "--topo-order");
 

index d6bb37e84ae..ab2a2e46b20 100644
@@ -58,6 +58,7 @@ struct pack_objects_args {
 	int no_reuse_object;
 	int quiet;
 	int local;
+	int full_name_hash;
 	struct list_objects_filter_options filter_options;
 };
 

@@ -306,6 +307,8 @@ static void prepare_pack_objects(struct child_process *cmd,
 		strvec_pushf(&cmd->args, "--no-reuse-delta");
 	if (args->no_reuse_object)
 		strvec_pushf(&cmd->args, "--no-reuse-object");
+	if (args->full_name_hash)
+		strvec_pushf(&cmd->args, "--full-name-hash");
 	if (args->local)
 		strvec_push(&cmd->args,  "--local");
 	if (args->quiet)

@@ -1203,6 +1206,8 @@ int cmd_repack(int argc,
 				N_("pass --no-reuse-delta to git-pack-objects")),
 		OPT_BOOL('F', NULL, &po_args.no_reuse_object,
 				N_("pass --no-reuse-object to git-pack-objects")),
+		OPT_BOOL(0, "full-name-hash", &po_args.full_name_hash,
+				N_("pass --full-name-hash to git-pack-objects")),
 		OPT_NEGBIT('n', NULL, &run_update_server_info,
 				N_("do not run git-update-server-info"), 1),
 		OPT__QUIET(&po_args.quiet, N_("be quiet")),

index b9898a4e64b..88360aa3e8e 100644
@@ -207,6 +207,27 @@ static inline uint32_t pack_name_hash(const char *name)
 	return hash;
 }
 
+static inline uint32_t pack_full_name_hash(const char *name)
+{
+	const uint32_t bigp = 1234572167U;
+	uint32_t c, hash = bigp;
+
+	if (!name)
+		return 0;
+
+	/*
+	 * Do the simplest thing that will resemble pseudo-randomness: add
+	 * random multiples of a large prime number with a binary shift.
+	 * The goal is not to be cryptographic, but to be generally
+	 * uniformly distributed.
+	 */
+	while ((c = *name++) != 0) {
+		hash += c * bigp;
+		hash = (hash >> 5) | (hash << 27);
+	}
+	return hash;
+}
+
 static inline enum object_type oe_type(const struct object_entry *e)
 {
 	return e->type_valid ? e->type_ : OBJ_BAD;

index 3b9dae331a5..7585cac6595 100755
@@ -674,4 +674,19 @@ do
 	'
 done
 
+# The following test is not necessarily a permanent choice, but since we do not
+# have a "name hash version" bit in the .bitmap file format, we cannot write the
+# full-name hash values into the .bitmap file without risking breakage later.
+#
+# TODO: Make these compatible in the future and replace this test with the
+# expected behavior when both are specified.
+test_expect_success '--full-name-hash and --write-bitmap-index are incompatible' '
+	git pack-objects base --all --full-name-hash --write-bitmap-index 2>err &&
+	test_grep incompatible err &&
+
+	# --stdout option silently removes --write-bitmap-index
+	git pack-objects --stdout --all --full-name-hash --write-bitmap-index >out 2>err &&
+	! test_grep incompatible err
+'
+
 test_done

gitgitgadget

Hah. I like that the existing implementation is small enough to fit (in its entirety!) into the commit message!

s/differntiate/differentiate ;-).

I'm not sure I entirely agree with the suggestion that the existing hash function is only about packing repositories with short pathnames. I think an important part of the existing implementation is that tries to group similar files together, regardless of whether or not they appear in the same tree.

As you have shown, this can be a problem when the fact two files that happen to end in "CHANGELOG.json" end up in vastly different trees and *aren't* related. I don't think that nailing all of these details in the commit message is necessary, but I do think it's worth adjusting what the original commit message says in terms of what the existing algorithm is optimized for.

I think you hint at this in the series' cover letter, but I suspect that this pseduorandom behavior hurts in some small number of cases and that the full-name hash idea isn't a pure win, e.g., when we really do want to delta two paths that both end in CHAGNELOG.json despite being in different parts of the tree.

You have some tables here below that demonstrate a significant improvement with the full-name hash in use, which I think is good worth keeping in my own opinion. It may be worth updating those to include the new examples you highlighted in your revised cover letter as well.

Is this repository publicly available? If so, it may be worth mentioning here.

Ahh. Here's a great example of it helping to a smaller extent. Thanks for including this as part of demonstrating the full picture (both the benefits and drawbacks).

Good.

Amazing!

Agreed.

    static inline uint32_t pack_name_hash(const char *name)
    {
        if (use_full_name_hash)
            BUG("called pack_name_hash() with --full-name-hash")
        /* ... */
    }

Oops, one thing I forgot (which reading Peff's message in [1] reminded me of) is that I think we need to disable full-name hashing when we're reusing existing packfiles as is the case with try_partial_reuse().

There we're always looking at classic name hash values, so mixing the two would be a mistake. I think that amounts to:

--- 8< ---

index 762949e4c8..7e370bcfc9 100644
@@ -4070,6 +4070,8 @@ static int get_object_list_from_bitmap(struct rev_info *revs)
 	if (!(bitmap_git = prepare_bitmap_walk(revs, 0)))
 		return -1;
 
+	use_full_name_hash = 0;
+
 	if (pack_options_allow_reuse())
 		reuse_partial_packfile_from_bitmap(bitmap_git,
 						   &reuse_packfiles,

--- >8 ---

Thanks,
Taylor

[1]: https://lore.kernel.org/git/[email protected]/

I'll be more explicit about the design for "hash locality" earlier in the message, but also pointing out that the locality only makes sense as a benefit when there are not enough versions of a file in history, since it's nearly always better to choose a previous version of the same file instead of a different path with a name-hash collision. Directory renames are on place where this is a positive decision, but those are typically rare compared to the full history of a large repo.

I mention that this doesn't work well in all cases when operating under a 'git push' or in a shallow clone. Shallow clones are disabled in a later commit and we don't have the necessary implementation to make this hash function be selected within 'git push'.

I'll try to remember to move the newer examples to the cover letter.

Here, by "when repacking a repository" I mean "we are going to test repacking a number of example repositories, that will be listed in detail in the coming tables".

These repos B, C, and D are _not_ publicly available, though.

I'll fix that. Thanks. As well as moving the 'git repack' changes out of this patch. I'll adjust the commit message to say "packing all objects' instead of 'git repack' to be clear that this can be done with a direct call to 'git pack-objects' instead of needing 'git repack'.

I think this is interesting defensive programming for future contributions.

We essentially want the methods to only be called by pack_name_hash_fn() and don't have method privacy. We could extract it to its own header file but then would need to modify the prototype to include the signal for which hash type to use, but that would cause us to lose our ability to check for a bug like this.

It may be even better to store a static value for the value of use_full_name_hash when it first executes, so it can exit if it notices a different value. (This is becoming large enough for its own patch.)

Interesting. I've not considered these functions before.

Yes, I should delay that to patch 2.

Thanks,
-Stole

I was wondering a bit about this: is there any reason why we cannot have both, that is reap the benefits of "--full-name-hash" but end up writing a bitmap with the old name hash so that we can continue to generate bitmaps?

Forgive me if this question is naive, I'm more at home in the refs subsystem :)

From: Derrick Stolee <[email protected]>

The new '--full-name-hash' option for 'git repack' is a simple pass-through to the underlying 'git pack-objects' subcommand. However, this subcommand may have other options and a temporary filename as part of the subcommand execution that may not be predictable or could change over time.

The existing test_subcommand method requires an exact list of arguments for the subcommand. This is too rigid for our needs here, so create a new method, test_subcommand_flex. Use it to check that the --full-name-hash option is passing through.

---
 t/t7700-repack.sh       |  7 +++++++
 t/test-lib-functions.sh | 26 ++++++++++++++++++++++++++
 2 files changed, 33 insertions(+)

index c4c3d1a15d9..fc2cc9d37be 100755
@@ -777,6 +777,13 @@ test_expect_success 'repack -ad cleans up old .tmp-* packs' '
 	test_must_be_empty tmpfiles
 '
 
+test_expect_success '--full-name-hash option passes through to pack-objects' '
+	GIT_TRACE2_EVENT="$(pwd)/full-trace.txt" \
+		git repack -a --full-name-hash &&
+	test_subcommand_flex git pack-objects --full-name-hash <full-trace.txt
+'
+
+
 test_expect_success 'setup for update-server-info' '
 	git init update-server-info &&
 	test_commit -C update-server-info message

index 78e054ab503..af47247f25f 100644
@@ -1886,6 +1886,32 @@ test_subcommand () {
 	fi
 }
 
+# Check that the given subcommand was run with the given set of
+# arguments in order (but with possible extra arguments).
+#
+#	test_subcommand_flex [!] <command> <args>... < <trace>
+#
+# If the first parameter passed is !, this instead checks that
+# the given command was not called.
+#
+test_subcommand_flex () {
+	local negate=
+	if test "$1" = "!"
+	then
+		negate=t
+		shift
+	fi
+
+	local expr="$(printf '"%s".*' "$@")"
+
+	if test -n "$negate"
+	then
+		! grep "\[$expr\]"
+	else
+		grep "\[$expr\]"
+	fi
+}
+
 # Check that the given command was invoked as part of the
 # trace2-format trace on stdin.
 #

gitgitgadget

OK, I stand by my thinking in the previous patch that this one is where the changes to builtin/repack.c belong.

Yes. I should have done this already.

This does require knowing a bit about the internals of test_subcommand that may be too much of a burden for future contributors.

Thanks,
-Stolee

From: Derrick Stolee <[email protected]>

Add a new environment variable to opt-in to the --full-name-hash option in 'git pack-objects'. This allows for extra testing of the feature without repeating all of the test scenarios.

But this option isn't free. There are a few tests that change behavior with the variable enabled.

First, there are a few tests that are very sensitive to certain delta bases being picked. These are both involving the generation of thin bundles and then counting their objects via 'git index-pack --fix-thin' which pulls the delta base into the new packfile. For these tests, disable the option as a decent long-term option.

Second, there are two tests in t5616-partial-clone.sh that I believe are actually broken scenarios. While the client is set up to clone the 'promisor-server' repo via a treeless partial clone filter (tree:0), that filter does not translate to the 'server' repo. Thus, fetching from these repos causes the server to think that the client has all reachable trees and blobs from the commits advertised as 'haves'. This leads the server to providing a thin pack assuming those objects as delta bases. Changing the name-hash algorithm presents new delta bases and thus breaks the expectations of these tests. An alternative could be to set up 'server' as a promisor server with the correct filter enabled. This may also point out more issues with partial clone being set up as a remote-based filtering mechanism and not a repository-wide setting. For now, do the minimal change to make the test work by disabling the test variable.

Third, there are some tests that compare the exact output of a 'git pack-objects' process when using bitmaps. The warning that disables the --full-name-hash option causes these tests to fail. Disable the environment variable to get around this issue.

---
 builtin/pack-objects.c          |  7 +++++--
 ci/run-build-and-tests.sh       |  1 +
 t/README                        |  4 ++++
 t/t5310-pack-bitmaps.sh         |  3 +++
 t/t5333-pseudo-merge-bitmaps.sh |  4 ++++
 t/t5510-fetch.sh                |  7 ++++++-
 t/t5616-partial-clone.sh        | 26 ++++++++++++++++++++++++--
 t/t6020-bundle-misc.sh          |  6 +++++-
 t/t7406-submodule-update.sh     |  2 ++
 t/t7700-repack.sh               |  6 ++++++
 10 files changed, 60 insertions(+), 6 deletions(-)

index 85595dfcd88..7cb6f0e0942 100644
@@ -266,7 +266,7 @@ struct configured_exclusion {
 static struct oidmap configured_exclusions;
 
 static struct oidset excluded_by_config;
-static int use_full_name_hash;
+static int use_full_name_hash = -1;
 
 static inline uint32_t pack_name_hash_fn(const char *name)
 {

@@ -4586,7 +4586,10 @@ int cmd_pack_objects(int argc,
 	if (pack_to_stdout || !rev_list_all)
 		write_bitmap_index = 0;
 
-	if (write_bitmap_index && use_full_name_hash) {
+	if (use_full_name_hash < 0)
+		use_full_name_hash = git_env_bool("GIT_TEST_FULL_NAME_HASH", 0);
+
+	if (write_bitmap_index && use_full_name_hash > 0) {
 		warning(_("currently, the --full-name-hash option is incompatible with --write-bitmap-index"));
 		use_full_name_hash = 0;
 	}

index 2e28d02b20f..75b40f07bbd 100755
@@ -30,6 +30,7 @@ linux-TEST-vars)
 	export GIT_TEST_NO_WRITE_REV_INDEX=1
 	export GIT_TEST_CHECKOUT_WORKERS=2
 	export GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1
+	export GIT_TEST_FULL_NAME_HASH=1
 	;;
 linux-clang)
 	export GIT_TEST_DEFAULT_HASH=sha1

index 8c0319b58e5..fe3f89b5b28 100644
@@ -492,6 +492,10 @@ a test and then fails then the whole test run will abort. This can help to make
 sure the expected tests are executed and not silently skipped when their
 dependency breaks or is simply not present in a new environment.
 
+GIT_TEST_FULL_NAME_HASH=<boolean>, when true, sets the default name-hash
+function in 'git pack-objects' to be the one used by the --full-name-hash
+option.
+
 Naming Tests
 ------------
 

index 7044c7d7c6d..caa3c125548 100755
@@ -420,6 +420,9 @@ test_bitmap_cases () {
 			cat >expect <<-\EOF &&
 			error: missing value for '\''pack.preferbitmaptips'\''
 			EOF
+
+			# Disable --full-name-hash test due to stderr comparison.
+			GIT_TEST_FULL_NAME_HASH=0 \
 			git repack -adb 2>actual &&
 			test_cmp expect actual
 		)

index eca4a1eb8c6..0c7c3e33986 100755
@@ -209,6 +209,10 @@ test_expect_success 'bitmapPseudoMerge.stableThreshold creates stable groups' '
 '
 
 test_expect_success 'out of order thresholds are rejected' '
+	# Disable this option to avoid stderr message
+	GIT_TEST_FULL_NAME_HASH=0 &&
+	export GIT_TEST_FULL_NAME_HASH &&
+
 	test_must_fail git \
 		-c bitmapPseudoMerge.test.pattern="refs/*" \
 		-c bitmapPseudoMerge.test.threshold=1.month.ago \

index 0890b9f61c5..be79c72495e 100755
@@ -1062,7 +1062,12 @@ test_expect_success 'all boundary commits are excluded' '
 	test_tick &&
 	git merge otherside &&
 	ad=$(git log --no-walk --format=%ad HEAD) &&
-	git bundle create twoside-boundary.bdl main --since="$ad" &&
+
+	# If the --full-name-hash function is used here, then no delta
+	# pair is found and the bundle does not expand to three objects
+	# when fixing the thin object.
+	GIT_TEST_FULL_NAME_HASH=0 \
+		git bundle create twoside-boundary.bdl main --since="$ad" &&
 	test_bundle_object_count --thin twoside-boundary.bdl 3
 '
 

index c53e93be2f7..425aa8d8789 100755
@@ -516,7 +516,18 @@ test_expect_success 'fetch lazy-fetches only to resolve deltas' '
 	# Exercise to make sure it works. Git will not fetch anything from the
 	# promisor remote other than for the big tree (because it needs to
 	# resolve the delta).
-	GIT_TRACE_PACKET="$(pwd)/trace" git -C client \
+	#
+	# TODO: the --full-name-hash option is disabled here, since this test
+	# is fundamentally broken! When GIT_TEST_FULL_NAME_HASH=1, the server
+	# recognizes delta bases in a different way and then sends a _blob_ to
+	# the client with a delta base that the client does not have! This is
+	# because the client is cloned from "promisor-server" with tree:0 but
+	# is now fetching from "server" withot any filter. This is violating the
+	# promise to the server that all reachable objects exist and could be
+	# used as delta bases!
+	GIT_TRACE_PACKET="$(pwd)/trace" \
+	GIT_TEST_FULL_NAME_HASH=0 \
+		git -C client \
 		fetch "file://$(pwd)/server" main &&
 
 	# Verify the assumption that the client needed to fetch the delta base

@@ -535,7 +546,18 @@ test_expect_success 'fetch lazy-fetches only to resolve deltas, protocol v2' '
 	# Exercise to make sure it works. Git will not fetch anything from the
 	# promisor remote other than for the big blob (because it needs to
 	# resolve the delta).
-	GIT_TRACE_PACKET="$(pwd)/trace" git -C client \
+	#
+	# TODO: the --full-name-hash option is disabled here, since this test
+	# is fundamentally broken! When GIT_TEST_FULL_NAME_HASH=1, the server
+	# recognizes delta bases in a different way and then sends a _blob_ to
+	# the client with a delta base that the client does not have! This is
+	# because the client is cloned from "promisor-server" with tree:0 but
+	# is now fetching from "server" withot any filter. This is violating the
+	# promise to the server that all reachable objects exist and could be
+	# used as delta bases!
+	GIT_TRACE_PACKET="$(pwd)/trace" \
+	GIT_TEST_FULL_NAME_HASH=0 \
+		git -C client \
 		fetch "file://$(pwd)/server" main &&
 
 	# Verify that protocol version 2 was used.

index 34b5cd62c20..553a20d10e9 100755
@@ -247,7 +247,11 @@ test_expect_success 'create bundle with --since option' '
 	EOF
 	test_cmp expect actual &&
 
-	git bundle create since.bdl \
+	# If the --full-name-hash option is used, then one fewer
+	# delta base is found and this counts a different number
+	# of objects after performing --fix-thin.
+	GIT_TEST_FULL_NAME_HASH=0 \
+		git bundle create since.bdl \
 		--since "Thu Apr 7 15:27:00 2005 -0700" \
 		--all &&
 

index 0f0c86f9cb2..03f8c976720 100755
@@ -1094,6 +1094,8 @@ test_expect_success 'submodule update --quiet passes quietness to fetch with a s
 	) &&
 	git clone super4 super5 &&
 	(cd super5 &&
+	 # This test var can mess with the stderr output checked in this test.
+	 GIT_TEST_FULL_NAME_HASH=0 \
 	 git submodule update --quiet --init --depth=1 submodule3 >out 2>err &&
 	 test_must_be_empty out &&
 	 test_must_be_empty err

index fc2cc9d37be..e3787bacdad 100755
@@ -309,6 +309,9 @@ test_expect_success 'no bitmaps created if .keep files present' '
 	keep=${pack%.pack}.keep &&
 	test_when_finished "rm -f \"\$keep\"" &&
 	>"$keep" &&
+
+	# Disable --full-name-hash test due to stderr comparison.
+	GIT_TEST_FULL_NAME_HASH=0 \
 	git -C bare.git repack -ad 2>stderr &&
 	test_must_be_empty stderr &&
 	find bare.git/objects/pack/ -type f -name "*.bitmap" >actual &&

@@ -320,6 +323,9 @@ test_expect_success 'auto-bitmaps do not complain if unavailable' '
 	blob=$(test-tool genrandom big $((1024*1024)) |
 	       git -C bare.git hash-object -w --stdin) &&
 	git -C bare.git update-ref refs/tags/big $blob &&
+
+	# Disable --full-name-hash test due to stderr comparison.
+	GIT_TEST_FULL_NAME_HASH=0 \
 	git -C bare.git repack -ad 2>stderr &&
 	test_must_be_empty stderr &&
 	find bare.git/objects/pack -type f -name "*.bitmap" >actual &&

gitgitgadget

You make good points that this does not need to be here.

It's enough that someone could manually check the test suite with this test variable to make sure that enough of the other options are tested with this feature.

Thanks,
-Stolee

I took a look...this is a tricky one.

It is expected that the server sometimes sends deltas based on objects that the client doesn't have. In fact, this test tests the ability of Git to lazy-fetch delta bases.

To be precise, the change resulted in no deltas being sent (before this change, one delta was sent). Here's what is meant to happen. The server has:

commitB - treeB - file1 ("make the tree big\nanother line\n"), file2...file100
|
commitA - treeA - file1...file100 ("make the tree big\n")

The client only has commitA. (The client does not have treeA or any blob, since it was cloned with --filter=tree:0.)

When GIT_TEST_FULL_NAME_HASH=0 (matching the current behavior), the server sends a non-delta commitB, a delta treeB (with base treeA), and a non-delta blob "make the tree big\nanother line\n". This triggers a lazy fetch of treeA, and thus treeB is inflated successfully. During the subsequent connectivity check (with --exclude-promisor-objects, see connected.c), it is noticed that the "make the tree big\n" blob is missing, but since it is a promisor object (referenced by treeA, which was fetched from the promisor remote), the connectivity check since passes.

When GIT_TEST_FULL_NAME_HASH=1, the server sends a non-delta commitB, a non-delta treeB, and a non-delta blob "make the tree big\nanother line\n". No lazy fetch is triggered. During the subsequent connectivity check, the "make the tree big\n" blob (referenced by treeB) is missing. There is nothing that can vouch for it (the client does not have treeA, remember) so the client does not consider it a promisor object, and thus the connectivity check fails.

Investigating this was made a bit harder due to a missing "git -C promisor-remote config --local uploadpack.allowfilter 1" in the test. The above behavior is after this is included in the test.

I think the solution is to have an algorithm that preserves the property that treeB is sent as a delta object - if not, we need to find another way to test the lazy-fetch of delta bases. My proposal in [1] does do that.

[1] https://lore.kernel.org/git/[email protected]/

It is sad that it is a (probably unfixable) flaw in the "promisor object" concept that the "promisor object"-ness of blobA depends on the lazy-fetch status of treeA. This is not merely a test failure, but it would cause blobA pruned if such a lazy fetch happens in the wild and then "git gc" triggers, no? It may not manifest as a repository corruption, since we would lazily fetch it again if the user requests to fully fetch what commitA and treeA need, but it does feel somewhat suboptimal.

Thanks for a detailed explanation on what is going on.

Right now, it won't be pruned since we never prune promisor objects (we just concatenate all of them into one file). But in the future, we might only keep reachable promisor objects, in which case, yes, blobA will be pruned. In this case, though, I think blobA is like any other unreachable object in git. If a user memorizes a commit hash but does not point a ref to it (or point a ref to one of its descendants), that commit is still subject to being lost by GC. I think it's the same case here.

Sorry, but I am lost. In the scenario discussed, you have two commits A and B with their trees and blobs. You initially only have commit A because the partial clone is done with "tree:0". Then you fetch commit B (A's child), tree B in non-delta form, and blob B contained within tree B. Due to the tweak in the name hash function, we do not know of tree A (we used to learn about it because tree B was sent as a delta against it with the old name hash). If blob B was sent as a delta against blob A, lazy fetch would later materialize blob A even if you do not still have tree A, no?

I thought the story was that we would not know who refers to blobA when treeA hasn't been lazily fetched, hence we cannot tell if blobA is a "promisor object" to begin with, no?

The blob in such a scenario may be reclaimed by GC and we may still be able to refetch from the promisor, so it may not be the end of the world, but feels suboptimal.

Yes, that's correct.

Just to be clear, this is not happening right now (blob B is sent whole, not as a delta). But let's suppose that blob B was sent as a delta, then yes, the lazy fetch would materialize blob A...

...ah, in this case, blob A vouches for itself. Whenever we lazy fetch, all objects that are fetched go into promisor packs (packfiles with an associated .promisor file), so we know that they are promisor objects.

Thanks.

From: Derrick Stolee <[email protected]>

This also adds the '--full-name-hash' option introduced in the previous change and adds newlines to the synopsis.

---
 Documentation/git-repack.txt | 4 +++-
 builtin/repack.c             | 4 +++-
 t/t0450/txt-help-mismatches  | 1 -
 3 files changed, 6 insertions(+), 3 deletions(-)

index c902512a9e8..457a793fa89 100644
@@ -9,7 +9,9 @@ git-repack - Pack unpacked objects in a repository
 SYNOPSIS
 --------
 [verse]
-'git repack' [-a] [-A] [-d] [-f] [-F] [-l] [-n] [-q] [-b] [-m] [--window=<n>] [--depth=<n>] [--threads=<n>] [--keep-pack=<pack-name>] [--write-midx]
+'git repack' [-a] [-A] [-d] [-f] [-F] [-l] [-n] [-q] [-b] [-m]
+	[--window=<n>] [--depth=<n>] [--threads=<n>] [--keep-pack=<pack-name>]
+	[--write-midx] [--full-name-hash]
 
 DESCRIPTION
 -----------

index ab2a2e46b20..e5f53a6eac7 100644
@@ -39,7 +39,9 @@ static int run_update_server_info = 1;
 static char *packdir, *packtmp_name, *packtmp;
 
 static const char *const git_repack_usage[] = {
-	N_("git repack [<options>]"),
+	N_("git repack [-a] [-A] [-d] [-f] [-F] [-l] [-n] [-q] [-b] [-m]\n"
+	   "[--window=<n>] [--depth=<n>] [--threads=<n>] [--keep-pack=<pack-name>]\n"
+	   "[--write-midx] [--full-name-hash]"),
 	NULL
 };
 

index 28003f18c92..c4a15fd0cb8 100644
@@ -45,7 +45,6 @@ rebase
 remote
 remote-ext
 remote-fd
-repack
 reset
 restore
 rev-parse

gitgitgadget

I think "the previous change" is not quite accurate here, even if you move the implementation to pass through '--full-name-hash' via repack into the second patch.

It would be nice to have the option added in 'repack' in the same commit as adjusts the documentation instead of splitting them apart.

Thanks,
Taylor

Ah, I should definitely rearrange the commits.

Part of the point of the split was that the synopsis in builtin/repack.c needs more than just the addition of the --full-name-hash option in order to make it match the Documentation synopsis.

But you're right, the code change is small enough that these things can be combined.

Thanks,
-Stolee

From: Derrick Stolee <[email protected]>

As custom options are added to 'git pack-objects' and 'git repack' to adjust how compression is done, use this new performance test script to demonstrate their effectiveness in performance and size.

The recently-added --full-name-hash option swaps the default name-hash algorithm with one that attempts to uniformly distribute the hashes based on the full path name instead of the last 16 characters.

This has a dramatic effect on full repacks for repositories with many versions of most paths. It can have a negative impact on cases such as pushing a single change.

This can be seen by running pt5313 on the open source fluentui repository [1]. Most commits will have this kind of output for the thin and big pack cases, though certain commits (such as [2]) will have problematic thin pack size for other reasons.

[1] https://github.com/microsoft/fluentui
[2] a637a06df05360ce5ff21420803f64608226a875

Checked out at the parent of [2], I see the following statistics:

Test HEAD
---------------------------------------------------------------------
5313.2: thin pack 0.37(0.43+0.02)
5313.3: thin pack size 1.2M
5313.4: thin pack with --full-name-hash 0.06(0.09+0.02)
5313.5: thin pack size with --full-name-hash 20.4K
5313.6: big pack 2.01(7.73+0.23)
5313.7: big pack size 20.3M
5313.8: big pack with --full-name-hash 1.32(2.77+0.27)
5313.9: big pack size with --full-name-hash 19.9M
5313.10: shallow fetch pack 1.40(3.01+0.08)
5313.11: shallow pack size 34.4M
5313.12: shallow pack with --full-name-hash 1.08(1.25+0.14)
5313.13: shallow pack size with --full-name-hash 35.4M
5313.14: repack 90.70(672.88+2.46)
5313.15: repack size 439.6M
5313.16: repack with --full-name-hash 18.53(123.41+2.53)
5313.17: repack size with --full-name-hash 169.7M

In this case, we see positive behaviors such as a significant shrink in the size of the thin pack and full repack. The big pack is slightly smaller with --full-name-hash than without. The shallow pack is slightly larger with --full-name-hash.

In the case of the Git repository, these numbers show some of the issues with this approach:

Test HEAD
--------------------------------------------------------------------
5313.2: thin pack 0.00(0.00+0.00)
5313.3: thin pack size 589
5313.4: thin pack with --full-name-hash 0.00(0.00+0.00)
5313.5: thin pack size with --full-name-hash 14.9K
5313.6: big pack 2.07(3.57+0.17)
5313.7: big pack size 17.6M
5313.8: big pack with --full-name-hash 2.00(3.07+0.19)
5313.9: big pack size with --full-name-hash 17.9M
5313.10: shallow fetch pack 1.41(2.23+0.06)
5313.11: shallow pack size 12.1M
5313.12: shallow pack with --full-name-hash 1.22(1.66+0.04)
5313.13: shallow pack size with --full-name-hash 12.4M
5313.14: repack 15.75(89.29+1.54)
5313.15: repack size 126.4M
5313.16: repack with --full-name-hash 15.56(89.78+1.32)
5313.17: repack size with --full-name-hash 126.0M

The thin pack that simulates a push is much worse with --full-name-hash in this case. The name hash values are doing a lot to assist with delta bases, it seems. The big pack and shallow clone cases are slightly worse with the --full-name-hash option. Only the full repack gains some benefits in size.

The results are similar with the nodejs/node repo:

Test HEAD
---------------------------------------------------------------------
5313.2: thin pack 0.01(0.01+0.00)
5313.3: thin pack size 1.6K
5313.4: thin pack with --full-name-hash 0.01(0.00+0.00)
5313.5: thin pack size with --full-name-hash 3.1K
5313.6: big pack 4.26(8.03+0.24)
5313.7: big pack size 56.0M
5313.8: big pack with --full-name-hash 4.16(6.55+0.22)
5313.9: big pack size with --full-name-hash 56.2M
5313.10: shallow fetch pack 7.67(11.80+0.29)
5313.11: shallow pack size 104.6M
5313.12: shallow pack with --full-name-hash 7.52(9.65+0.23)
5313.13: shallow pack size with --full-name-hash 105.9M
5313.14: repack 71.22(317.61+3.95)
5313.15: repack size 739.9M
5313.16: repack with --full-name-hash 48.85(267.02+3.72)
5313.17: repack size with --full-name-hash 793.5M

The Linux kernel repository was the initial target of the default name hash value, and its naming conventions are practically build to take the most advantage of the default name hash values:

Test HEAD
-------------------------------------------------------------------------
5313.2: thin pack 0.15(0.01+0.03)
5313.3: thin pack size 4.6K
5313.4: thin pack with --full-name-hash 0.03(0.02+0.01)
5313.5: thin pack size with --full-name-hash 6.8K
5313.6: big pack 18.51(33.74+0.95)
5313.7: big pack size 201.1M
5313.8: big pack with --full-name-hash 16.01(29.81+0.88)
5313.9: big pack size with --full-name-hash 202.1M
5313.10: shallow fetch pack 11.49(17.61+0.54)
5313.11: shallow pack size 269.2M
5313.12: shallow pack with --full-name-hash 11.24(15.25+0.56)
5313.13: shallow pack size with --full-name-hash 269.8M
5313.14: repack 1001.25(2271.06+38.86)
5313.15: repack size 2.5G
5313.16: repack with --full-name-hash 625.75(1941.96+36.09)
5313.17: repack size with --full-name-hash 2.6G

Finally, an internal Javascript repo of moderate size shows significant gains when repacking with --full-name-hash due to it having many name hash collisions. However, it's worth noting that only the full repack case has enough improvement to be worth it. But the improvements are
significant: 6.4 GB to 862 MB.

Test HEAD
--------------------------------------------------------------------------
5313.2: thin pack 0.03(0.02+0.00)
5313.3: thin pack size 1.2K
5313.4: thin pack with --full-name-hash 0.03(0.03+0.00)
5313.5: thin pack size with --full-name-hash 2.6K
5313.6: big pack 2.20(3.23+0.30)
5313.7: big pack size 130.7M
5313.8: big pack with --full-name-hash 2.33(3.17+0.34)
5313.9: big pack size with --full-name-hash 131.0M
5313.10: shallow fetch pack 3.56(6.02+0.32)
5313.11: shallow pack size 44.5M
5313.12: shallow pack with --full-name-hash 2.94(3.94+0.32)
5313.13: shallow pack size with --full-name-hash 45.3M
5313.14: repack 2435.22(12523.11+23.53)
5313.15: repack size 6.4G
5313.16: repack with --full-name-hash 473.25(1805.11+17.22)
5313.17: repack size with --full-name-hash 861.9M

These tests demonstrate that it is important to be careful about which cases are best for using the --full-name-hash option.

---
 t/perf/p5313-pack-objects.sh | 94 ++++++++++++++++++++++++++++++++++++
 1 file changed, 94 insertions(+)
 create mode 100755 t/perf/p5313-pack-objects.sh

new file mode 100755
index 00000000000..dfa29695315
@@ -0,0 +1,94 @@
+#!/bin/sh
+
+test_description='Tests pack performance using bitmaps'
+. ./perf-lib.sh
+
+GIT_TEST_PASSING_SANITIZE_LEAK=0
+export GIT_TEST_PASSING_SANITIZE_LEAK
+
+test_perf_large_repo
+
+test_expect_success 'create rev input' '
+	cat >in-thin <<-EOF &&
+	$(git rev-parse HEAD)
+	^$(git rev-parse HEAD~1)
+	EOF
+
+	cat >in-big <<-EOF &&
+	$(git rev-parse HEAD)
+	^$(git rev-parse HEAD~1000)
+	EOF
+
+	cat >in-shallow <<-EOF
+	$(git rev-parse HEAD)
+	--shallow $(git rev-parse HEAD)
+	EOF
+'
+
+test_perf 'thin pack' '
+	git pack-objects --thin --stdout --revs --sparse  <in-thin >out
+'
+
+test_size 'thin pack size' '
+	test_file_size out
+'
+
+test_perf 'thin pack with --full-name-hash' '
+	git pack-objects --thin --stdout --revs --sparse --full-name-hash <in-thin >out
+'
+
+test_size 'thin pack size with --full-name-hash' '
+	test_file_size out
+'
+
+test_perf 'big pack' '
+	git pack-objects --stdout --revs --sparse  <in-big >out
+'
+
+test_size 'big pack size' '
+	test_file_size out
+'
+
+test_perf 'big pack with --full-name-hash' '
+	git pack-objects --stdout --revs --sparse --full-name-hash <in-big >out
+'
+
+test_size 'big pack size with --full-name-hash' '
+	test_file_size out
+'
+
+test_perf 'shallow fetch pack' '
+	git pack-objects --stdout --revs --sparse --shallow <in-shallow >out
+'
+
+test_size 'shallow pack size' '
+	test_file_size out
+'
+
+test_perf 'shallow pack with --full-name-hash' '
+	git pack-objects --stdout --revs --sparse --shallow --full-name-hash <in-shallow >out
+'
+
+test_size 'shallow pack size with --full-name-hash' '
+	test_file_size out
+'
+
+test_perf 'repack' '
+	git repack -adf
+'
+
+test_size 'repack size' '
+	pack=$(ls .git/objects/pack/pack-*.pack) &&
+	test_file_size "$pack"
+'
+
+test_perf 'repack with --full-name-hash' '
+	git repack -adf --full-name-hash
+'
+
+test_size 'repack size with --full-name-hash' '
+	pack=$(ls .git/objects/pack/pack-*.pack) &&
+	test_file_size "$pack"
+'
+
+test_done

gitgitgadget

Nicely done, thank you for adding a perf test to allow readers to easily verify these changes themselves.

Not a problem with your patch, but just thinking aloud: do you think there is an easy/straightforward way to suggest when to use --full-name-hash or not?

    test_file_size "$(ls .git/objects/pack/pack-*.pack)"

    pack="$(ls $(git rev-parse --git-dir)/objects/pack/pack-*.pack)" &&
    test_file_size

The kinds of heuristics I would use are:

1. Are there enough commits that enough files have enough versions across history that it's very important to keep deltas within a path?

2. Is the repository at least 500MB such that there is actually room for a "meaningful" change in size?

3. Are there a lot of name-hash collisions? (The last patch in the series helps do this through a test-helper, but isn't something we can expect end users to check themselves.)

I also wanted to avoid having these commands be part of the time measurement, even if they are extremely small.

I believe this is a Junio recommendation from an earlier version.

Generally I prefer to split things into stages so the verbose output provides a clear definition of the value when calling the Git command.

While this would break a bare repo, the perf lib makes a bare repo be copied into a non-bare repo as follows:

test_perf_copy_repo_contents () {
	for stuff in "$1"/*
	do
		case "$stuff" in
		*/objects|*/hooks|*/config|*/commondir|*/gitdir|*/worktrees|*/fsmonitor--daemon*)
			;;
		*)
			cp -R "$stuff" "$repo/.git/" || exit 1
			;;
		esac
	done
}

I'll still add the git rev-parse suggestion because it's safest.

Thanks,
-Stolee

Is it possible to give general guidelines in our documentation that guides the end user for when to use the option and when not to use it? And if the answer is yes, is it possible for us to figure out at runtime what the current scenario is via some heuristics and enable the option automatically in a subset of cases?

Patrick

From: Derrick Stolee <[email protected]>

As demonstrated in the previous change, the --full-name-hash option of 'git pack-objects' is less effective in a trunctated history. Thus, even when the option is selected via a command-line option or config, disable this option when the '--shallow' option is specified. This will help performance in servers that choose to enable the --full-name-hash option by default for a repository while not regressing their ability to serve shallow clones.

This will not present a compatibility issue in the future when the full name hash values are stored in the reachability bitmaps, since shallow clones disable bitmaps.

---
 builtin/pack-objects.c       | 6 ++++++
 t/perf/p5313-pack-objects.sh | 1 +
 2 files changed, 7 insertions(+)

index 7cb6f0e0942..f68fc30c9b9 100644
@@ -4589,6 +4589,12 @@ int cmd_pack_objects(int argc,
 	if (use_full_name_hash < 0)
 		use_full_name_hash = git_env_bool("GIT_TEST_FULL_NAME_HASH", 0);
 
+	if (shallow && use_full_name_hash > 0 &&
+	    !git_env_bool("GIT_TEST_USE_FULL_NAME_HASH_WITH_SHALLOW", 0)) {
+		use_full_name_hash = 0;
+		warning("the --full-name-hash option is disabled with the --shallow option");
+	}
+
 	if (write_bitmap_index && use_full_name_hash > 0) {
 		warning(_("currently, the --full-name-hash option is incompatible with --write-bitmap-index"));
 		use_full_name_hash = 0;

index dfa29695315..a7f4e0bf8d8 100755
@@ -66,6 +66,7 @@ test_size 'shallow pack size' '
 '
 
 test_perf 'shallow pack with --full-name-hash' '
+	GIT_TEST_USE_FULL_NAME_HASH_WITH_SHALLOW=1 \
 	git pack-objects --stdout --revs --sparse --shallow --full-name-hash <in-shallow >out
 '
 

gitgitgadget

I appreciate demonstrating the value of declaring --shallow and --full-name-hash incompatible by showing the performance numbers in the previous patch.

But TBH I think that it would be equally fine or slightly better to say up front "when combined with --shallow, this option produces larger packs during testing, so the two are incompatible for now". You could include some performance numbers there to illustrate that difference in the commit log too if you wanted.

But I don't think it's worth introducing the pair as compatible only to mark them incompatible later on in the same series.

Thanks,
Taylor

I disagree and here's why: they are not functionally incompatible. This performance-focused change is worth justifying with performance test data _and_ isolating from the initial implementation with its own reasoning for future history spelunkers. Having these warning lines blame to this patch instead of the initial implementation will make it much easier to understand the justification of this change.

But maybe this patch can be removed if we use Jonathan's function. I'll check the performance tests to see if this continues to be justified.

Thanks,
-Stolee

From: Derrick Stolee <[email protected]>

Add a new test-tool helper, name-hash, to output the value of the name-hash algorithms for the input list of strings, one per line.

Since the name-hash values can be stored in the .bitmap files, it is important that these hash functions do not change across Git versions. Add a simple test to t5310-pack-bitmaps.sh to provide some testing of the current values. Due to how these functions are implemented, it would be difficult to change them without disturbing these values.

Create a performance test that uses test_size to demonstrate how collisions occur for these hash algorithms. This test helps inform someone as to the behavior of the name-hash algorithms for their repo based on the paths at HEAD.

My copy of the Git repository shows modest statistics around the collisions of the default name-hash algorithm:

Test this tree
-----------------------------------------------------------------

5314.1: paths at head                                        4.5K
5314.2: number of distinct name-hashes                       4.1K
5314.3: number of distinct full-name-hashes                  4.5K

5314.4: maximum multiplicity of name-hashes 13
5314.5: maximum multiplicity of fullname-hashes 1

Here, the maximum collision multiplicity is 13, but around 10% of paths have a collision with another path.

In a more interesting example, the microsoft/fluentui [1] repo had these statistics at time of committing:

Test this tree
-----------------------------------------------------------------
5314.1: paths at head 19.6K
5314.2: number of distinct name-hashes 8.2K
5314.3: number of distinct full-name-hashes 19.6K
5314.4: maximum multiplicity of name-hashes 279
5314.5: maximum multiplicity of fullname-hashes 1

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

That demonstrates that of the nearly twenty thousand path names, they are assigned around eight thousand distinct values. 279 paths are assigned to a single value, leading the packing algorithm to sort objects from those paths together, by size.

In this repository, no collisions occur for the full-name-hash algorithm.

In a more extreme example, an internal monorepo had a much worse collision rate:

Test this tree
-----------------------------------------------------------------
5314.1: paths at head 221.6K
5314.2: number of distinct name-hashes 72.0K
5314.3: number of distinct full-name-hashes 221.6K
5314.4: maximum multiplicity of name-hashes 14.4K
5314.5: maximum multiplicity of fullname-hashes 2

Even in this repository with many more paths at HEAD, the collision rate was low and the maximum number of paths being grouped into a single bucket by the full-path-name algorithm was two.

---
 Makefile                  |  1 +
 t/helper/test-name-hash.c | 24 +++++++++++++++++++++++
 t/helper/test-tool.c      |  1 +
 t/helper/test-tool.h      |  1 +
 t/perf/p5314-name-hash.sh | 41 +++++++++++++++++++++++++++++++++++++++
 t/t5310-pack-bitmaps.sh   | 26 +++++++++++++++++++++++++
 6 files changed, 94 insertions(+)
 create mode 100644 t/helper/test-name-hash.c
 create mode 100755 t/perf/p5314-name-hash.sh

index 6f5986b66ea..65403f6dd09 100644
@@ -816,6 +816,7 @@ TEST_BUILTINS_OBJS += test-lazy-init-name-hash.o
 TEST_BUILTINS_OBJS += test-match-trees.o
 TEST_BUILTINS_OBJS += test-mergesort.o
 TEST_BUILTINS_OBJS += test-mktemp.o
+TEST_BUILTINS_OBJS += test-name-hash.o
 TEST_BUILTINS_OBJS += test-online-cpus.o
 TEST_BUILTINS_OBJS += test-pack-mtimes.o
 TEST_BUILTINS_OBJS += test-parse-options.o

new file mode 100644
index 00000000000..e4ecd159b76
@@ -0,0 +1,24 @@
+/*
+ * test-name-hash.c: Read a list of paths over stdin and report on their
+ * name-hash and full name-hash.
+ */
+
+#include "test-tool.h"
+#include "git-compat-util.h"
+#include "pack-objects.h"
+#include "strbuf.h"
+
+int cmd__name_hash(int argc UNUSED, const char **argv UNUSED)
+{
+	struct strbuf line = STRBUF_INIT;
+
+	while (!strbuf_getline(&line, stdin)) {
+		uint32_t name_hash = pack_name_hash(line.buf);
+		uint32_t full_hash = pack_full_name_hash(line.buf);
+
+		printf("%10"PRIu32"\t%10"PRIu32"\t%s\n", name_hash, full_hash, line.buf);
+	}
+
+	strbuf_release(&line);
+	return 0;
+}

index 1ebb69a5dc4..e794058ab6d 100644
@@ -44,6 +44,7 @@ static struct test_cmd cmds[] = {
 	{ "match-trees", cmd__match_trees },
 	{ "mergesort", cmd__mergesort },
 	{ "mktemp", cmd__mktemp },
+	{ "name-hash", cmd__name_hash },
 	{ "online-cpus", cmd__online_cpus },
 	{ "pack-mtimes", cmd__pack_mtimes },
 	{ "parse-options", cmd__parse_options },

index 21802ac27da..26ff30a5a9a 100644
@@ -37,6 +37,7 @@ int cmd__lazy_init_name_hash(int argc, const char **argv);
 int cmd__match_trees(int argc, const char **argv);
 int cmd__mergesort(int argc, const char **argv);
 int cmd__mktemp(int argc, const char **argv);
+int cmd__name_hash(int argc, const char **argv);
 int cmd__online_cpus(int argc, const char **argv);
 int cmd__pack_mtimes(int argc, const char **argv);
 int cmd__parse_options(int argc, const char **argv);

index caa3c125548..965c3abca5f 100755
@@ -27,6 +27,32 @@ has_any () {
 	grep -Ff "$1" "$2"
 }
 
+# Since name-hash values are stored in the .bitmap files, add a test
+# that checks that the name-hash calculations are stable across versions.
+# Not exhaustive, but these hashing algorithms would be hard to change
+# without causing deviations here.
+test_expect_success 'name-hash value stability' '
+	cat >names <<-\EOF &&
+	first
+	second
+	third
+	one-long-enough-for-collisions
+	two-long-enough-for-collisions
+	EOF
+
+	test-tool name-hash <names >out &&
+
+	cat >expect <<-\EOF &&
+	2582249472	3109209818	first
+	2289942528	3781118409	second
+	2300837888	3028707182	third
+	2544516325	3241327563	one-long-enough-for-collisions
+	2544516325	4207880830	two-long-enough-for-collisions
+	EOF
+
+	test_cmp expect out
+'
+
 test_bitmap_cases () {
 	writeLookupTable=false
 	for i in "$@"

gitgitgadget

Neat.

    printf("%10"PRIu32" %10"PRIu32"\t%s\n", name_hash, full_hash, line.buf);

    test-tool name-hash <path-list >name-hashes &&
    awk "{ print \$1; }" <name-hashes | sort | uniq -c >name-hash-count &&

I've looked at all 7 patches.

I didn't really understand the concern with shallow in patch 6 (in particular, the documentation of "git pack-objects --shallow" seems to imply that it's for use by a server to a shallow client, but at the point that the server would need such a feature, it probably would already have bitmaps packed with the new hash algorithm). I didn't look at it further, though, since I had an algorithm that seemed to also do OK in the shallow test. So we might be able to drop patch 6.

Other than that, and other than all my comments and Taylor's comments, this series looks good.

I came up with a hash function that both uses information from a lot more of the path (not the full name, though) and preserves the sortable property (diff at the end of this email). It also contains fixes to the existing algorithm: not wasting the most significant bits of the hash if files in the repo mostly end in a lowercase alphabetic character, and the cast from a possibly-signed-possibly-unsigned char to a uint32_t.

The results look quite good. In summary, the pack sizes are comparable to Stolee's results in the case of fluentui, and better than Stolee's results in the case of git.

Here's one run on the fluentui repo (git clone https://
github.com/microsoft/fluentui; cd fluentui; git checkout a637a06df05360ce5ff21420803f64608226a875^ following the instructions in [1]:

(before my change)

Test this tree
---------------------------------------------------------------------
5313.2: thin pack 0.03(0.01+0.01)
5313.3: thin pack size 1.1K
5313.4: thin pack with --full-name-hash 0.03(0.00+0.02)
5313.5: thin pack size with --full-name-hash 3.0K
5313.6: big pack 1.60(2.87+0.32)
5313.7: big pack size 57.9M
5313.8: big pack with --full-name-hash 1.41(1.94+0.37)
5313.9: big pack size with --full-name-hash 57.8M
5313.10: shallow fetch pack 1.69(2.70+0.22)
5313.11: shallow pack size 33.0M
5313.12: shallow pack with --full-name-hash 1.49(1.84+0.34)
5313.13: shallow pack size with --full-name-hash 33.6M
5313.14: repack 75.10(537.66+5.47)
5313.15: repack size 454.2M
5313.16: repack with --full-name-hash 18.10(92.50+5.14)
5313.17: repack size with --full-name-hash 174.8M

(after my change)

Test this tree
---------------------------------------------------------------------
5313.2: thin pack 0.03(0.01+0.02)
5313.3: thin pack size 1.1K
5313.4: thin pack with --full-name-hash 0.03(0.01+0.02)
5313.5: thin pack size with --full-name-hash 1.1K
5313.6: big pack 1.62(2.94+0.28)
5313.7: big pack size 57.9M
5313.8: big pack with --full-name-hash 1.35(2.07+0.37)
5313.9: big pack size with --full-name-hash 57.6M
5313.10: shallow fetch pack 1.63(2.52+0.29)
5313.11: shallow pack size 33.0M
5313.12: shallow pack with --full-name-hash 1.50(2.10+0.23)
5313.13: shallow pack size with --full-name-hash 33.1M
5313.14: repack 74.86(531.39+5.49)
5313.15: repack size 454.7M
5313.16: repack with --full-name-hash 19.71(111.39+5.12)
5313.17: repack size with --full-name-hash 165.6M

The tests were run by:

  GENERATE_COMPILATION_DATABASE=yes make CC=clang && (cd t/perf && env GIT_PERF_LARGE_REPO=~/tmp/fluentui ./run -- p5313*.sh)

The similarity in sizes looked suspicious, so I replaced the contents of the hash function with "return 0;" and indeed the sizes significantly increased, so hopefully there is nothing wrong with my setup.

The git repo was called out in [1] as demonstrating "some of the issues with this approach", but here are the results, run by:

  GENERATE_COMPILATION_DATABASE=yes make CC=clang && (cd t/perf && ./run -- p5313*.sh)

Test this tree
--------------------------------------------------------------------
5313.2: thin pack 0.03(0.00+0.02)
5313.3: thin pack size 2.9K
5313.4: thin pack with --full-name-hash 0.03(0.00+0.02)
5313.5: thin pack size with --full-name-hash 2.9K
5313.6: big pack 1.69(2.80+0.28)
5313.7: big pack size 18.7M
5313.8: big pack with --full-name-hash 1.68(2.82+0.31)
5313.9: big pack size with --full-name-hash 18.8M
5313.10: shallow fetch pack 0.96(1.47+0.16)
5313.11: shallow pack size 12.1M
5313.12: shallow pack with --full-name-hash 1.01(1.51+0.14)
5313.13: shallow pack size with --full-name-hash 12.1M
5313.14: repack 17.05(69.99+4.33)
5313.15: repack size 116.5M
5313.16: repack with --full-name-hash 15.74(67.03+4.18)
5313.17: repack size with --full-name-hash 116.1M

[1] https://lore.kernel.org/git/c14ef6879e451401381ebbdb8f30d33c8f56c25b.1730775908.git.gitgitgadget@gmail.com/

If the results are similar for some of the above repos (I do not have access to them), maybe it's worth considering using my hash function (or a variation of it).

I'll also take a look at the rest of the patch set.

---

index 88360aa3e8..c4f35eafa0 100644
@@ -209,23 +209,24 @@ static inline uint32_t pack_name_hash(const char *name)
 
 static inline uint32_t pack_full_name_hash(const char *name)
 {
-       const uint32_t bigp = 1234572167U;
-       uint32_t c, hash = bigp;
+       uint32_t hash = 0, base = 0;
+       uint8_t c;
 
        if (!name)
                return 0;
 
-       /*
-        * Do the simplest thing that will resemble pseudo-randomness: add
-        * random multiples of a large prime number with a binary shift.
-        * The goal is not to be cryptographic, but to be generally
-        * uniformly distributed.
-        */
-       while ((c = *name++) != 0) {
-               hash += c * bigp;
-               hash = (hash >> 5) | (hash << 27);
+       while ((c = (uint8_t) *name++) != 0) {
+               if (isspace(c))
+                       continue;
+               if (c == '/') {
+                       base = (base >> 6) ^ hash;
+                       hash = 0;
+               } else {
+                       uint8_t nybble_swapped = (c >> 4) + ((c & 15) << 4);
+                       hash = (hash >> 2) + (nybble_swapped << 24);
+               }
        }
-       return hash;
+       return (base >> 6) ^ hash;
 }

That is garbage. We could do the "shift in from the right and then reverse the result" for the hash accumulator, but not the "base" one. Sorry for the noise.

I was confused by the "rotates the whole thing only at a directory boundary" statement. I think one way to say what you mean is

Each path component is hashed similarly to the standard name-hash, and parent path component hashes are contributed via XOR after a down-shift of 6 bits per level.

So we are getting something like

	[ name-hash for level 0           ]
        ......[ name-hash for level 1     ](truncated by 6)

............[name-hash for level 2](truncated by 12) ..................[...for level 3 ](truncated by 18) ........................[ level 4 ](truncated by 24) ..............................[ 5 ](truncated by 30)

and at each layer we get the "last 16 bytes matter" issue, though it is balanced quite well. Also, the name-hash in each layer is adjusted for nybble swaps.

(I don't think my explanation is _better_ but just that it matches my personal mental model slightly better.)

I will give this a try in my private repos as well as with the name-hash collision perf test from patch 7.

Thanks,
-Stolee

Yeah, I guess it was confusing. What I meant was that the entire result is shifted down with new material from left to right, but unlike the original, the outer thing (i.e. what is given to the caller as the result) is shifted only at the directory boundary, so we are not as aggressive to lose early bits by shifting them down to the right, as we are not shifting as fast as before.

Yes.

Ah, yes, reversing is better than swapping nybbles (the least significant 2 bits have more entropy than the next-least significant 2 bits). When writing this, I didn't think of shifting in from the right (if I had thought of that, I would have indeed reversed the bits instead).

This is a recreation of the topic in [1] that was closed. (I force-pushed my branch and GitHub won't let me reopen the PR for GitGitGadget to create this as v3.)

[1]
https://lore.kernel.org/git/[email protected]/

I've been focused recently on understanding and mitigating the growth of a few internal repositories. Some of these are growing much larger than expected for the number of contributors, and there are multiple aspects to why this growth is so large.

This is part of the RFC I submitted [2] involving the path-walk API, though this doesn't use the path-walk API directly. In full repack cases, it seems that the --full-name-hash option gets nearly as good compression as the --path-walk option introduced in that series. I continue to work on that feature as well, so we can review it after this series is complete.

[2]
https://lore.kernel.org/git/[email protected]/

The main issue plaguing these repositories is that deltas are not being computed against objects that appear at the same path. While the size of these files at tip is one aspect of growth that would prevent this issue, the changes to these files are reasonable and should result in good delta compression. However, Git is not discovering the connections across different versions of the same file.

One way to find some improvement in these repositories is to increase the window size, which was an initial indicator that the delta compression could be improved, but was not a clear indicator. After some digging (and prototyping some analysis tools) the main discovery was that the current name-hash algorithm only considers the last 16 characters in the path name and has some naturally-occurring collisions within that scope.

This series creates a mechanism to select alternative name hashes using a new --name-hash-version=<n> option. The versions are:

1. Version 1 is the default name hash that already exists. This option focuses on the final bytes of the path to maximize locality for cross-path deltas.

2. Version 2 is the new path-component hash function suggested by Jonathan Tan in the previous version (with some modifications). This hash function essentially computes the v1 name hash of each path component and then overlays those hashes with a shift to make the parent directories contribute less to the final hash, but enough to break many collisions that exist in v1.

3. Version 3 is the hash function that I submitted under the --full-name-hash feature in the previous versions. This uses a pseudorandom hash procedure to minimize collisions but at the expense of losing on locality. This version is implemented in the final patch of the series mostly for comparison purposes, as it is unlikely to be selected as a valuable hash function over v2. The final patch could be omitted from the merged version.

See the patches themselves for detailed results in the p5313-pack-objects.sh performance test and the p5314-name-hash.sh test that demonstrates how many collisions occur with each hash function.

In general, the v2 name hash function gets very close to the compression results of v3 in the full repack case, even in the repositories that feature many name hash collisions. These benefits come as well without downsides to other kinds of packfiles, including small pushed packs, larger incremental fetch packs, and shallow clones.

I should point out that there is still a significant jump in compression effectiveness between these name hash version options and the --path-walk feature I suggested in my RFC [2] and has review underway in [3] (along with changes to git pack-objects and git repack in [4]).

[3]
https://lore.kernel.org/git/[email protected]/

[4] https://github.com/gitgitgadget/git/pull/1819

To compare these options in a set of Javascript repositories that have different levels of name hash collisions, see the following table that lists the size of the packfile after git repack -adf [--name-hash-version=<n>|--path-walk]:

| Repo     | V1 Size   | V2 Size | V3 Size | Path Walk Size |
|----------|-----------|---------|---------|----------------|
| fluentui |     440 M |   161 M |   170 M |          123 M |
| Repo B   |   6,248 M |   856 M |   840 M |          782 M |
| Repo C   |  37,278 M | 6,921 M | 6,755 M |        6,156 M |
| Repo D   | 131,204 M | 7,463 M | 7,124 M |        4,005 M |

As we can see, v2 nearly reaches the effectiveness of v3 (and outperforms it once!) but there is still a significant change between the --name-hash-version feature and the --path-walk feature.

The main reason we are considering this --name-hash-version feature is that it has the least amount of stretch required in order for it to be integrated with reachability bitmaps, required for server environments. In fact, the change in this version to use a numerical version makes it more obvious how to connect the version number to a value in the .bitmap file format. Tests are added to guarantee that the hash functions preserve their behavior over time, since data files depend on that.

Thanks, -Stolee

UPDATES SINCE V1
================

* BIG CHANGE: --full-name-hash is replaced with --name-hash-version=<n>.

* --name-hash-version=2 uses Jonathan Tan's hash function (with some adjustments). See the first patch for this implementation, credited to him.

* --name-hash-version=3 uses the hash function I wrote for the previous version's --full-name-hash. This is left as the final patch so it could be easily removed from the series if not considered worth having since it has some pain points that are resolved from v2 without significant issues to overall repo size.

* Commit messaes are updated with these changes, as well as a better attempt to indicate the benefit of cross-path delta pairs, such as renames or similar content based on file extension.

* Performance numbers are regenerated for the same set of repositories. Size data is somewhat nondeterministic due to concurrent threads competing over delta computations.

* The --name-hash-version option is not added to git repack until its own patch.

* The patch that updates git repack's synopsis match its docs is squashed into the patch that adds the option to git repack.

* Documentation is expanded for git pack-objects and reused for git repack.

* GIT_TEST_FULL_NAME_HASH is now GIT_TEST_NAME_HASH_VERSION with similar caveats required for tests. It is removed from the linux-TEST-vars CI job.

* The performance test p5313-pack-objects.sh is now organized via a loop over the different versions. This separates the scenarios, which makes things harder to compare directly, but makes it trivial to add new versions.

* The patch that disabled --full-name-hash when performing a shallow clone is no longer present, as it is not necessary when using --name-hash-version=2. Perhaps it would be valuable for repo using v3, if that is kept in the series.

* We force name hash version 1 when writing or reading bitmaps.

* A small patch is added to cause a BUG() failure if the name hash version global changes between calls to pack_name_hash_fn(). This is solely defensive programming.

* Several typos, style issues, or suggested comments are resolved.

Derrick Stolee (7):
pack-objects: add --name-hash-version option
repack: add --name-hash-version option
pack-objects: add GIT_TEST_NAME_HASH_VERSION
p5313: add size comparison test
test-tool: add helper for name-hash values
pack-objects: prevent name hash version change
pack-objects: add third name hash version

Jonathan Tan (1):
pack-objects: create new name-hash function version

 Documentation/git-pack-objects.txt | 41 ++++++++++++++++-
 Documentation/git-repack.txt       | 43 +++++++++++++++++-
 Makefile                           |  1 +
 builtin/pack-objects.c             | 63 ++++++++++++++++++++++++---
 builtin/repack.c                   |  9 +++-
 pack-objects.h                     | 54 +++++++++++++++++++++++
 t/README                           |  4 ++
 t/helper/test-name-hash.c          | 24 ++++++++++
 t/helper/test-tool.c               |  1 +
 t/helper/test-tool.h               |  1 +
 t/perf/p5313-pack-objects.sh       | 70 ++++++++++++++++++++++++++++++
 t/perf/p5314-name-hash.sh          | 31 +++++++++++++
 t/t0450/txt-help-mismatches        |  1 -
 t/t5300-pack-object.sh             | 34 +++++++++++++++
 t/t5310-pack-bitmaps.sh            | 35 ++++++++++++++-
 t/t5333-pseudo-merge-bitmaps.sh    |  4 ++
 t/t5510-fetch.sh                   |  7 ++-
 t/t5616-partial-clone.sh           | 26 ++++++++++-
 t/t6020-bundle-misc.sh             |  6 ++-
 t/t7406-submodule-update.sh        |  4 +-
 t/t7700-repack.sh                  | 16 ++++++-
 t/test-lib-functions.sh            | 26 +++++++++++
 22 files changed, 484 insertions(+), 17 deletions(-)
 create mode 100644 t/helper/test-name-hash.c
 create mode 100755 t/perf/p5313-pack-objects.sh
 create mode 100755 t/perf/p5314-name-hash.sh

base-commit: 8f8d6eee531b3fa1a8ef14f169b0cb5035f7a772
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1823%2Fderrickstolee%2Ffull-name-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1823/derrickstolee/full-name-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/1823

Range-diff vs v1:

 -:  ----------- > 1:  454b070d5bb pack-objects: create new name-hash function version
 1:  812257e197c ! 2:  fb52ca509da pack-objects: add --full-name-hash option

@@ Metadata
Author: Derrick Stolee <[email protected]>

## Commit message ##
- pack-objects: add --full-name-hash option
+ pack-objects: add --name-hash-version option

- The pack_name_hash() method has not been materially changed since it was
- introduced in ce0bd64299a (pack-objects: improve path grouping
- heuristics., 2006-06-05). The intention here is to group objects by path
- name, but also attempt to group similar file types together by making
- the most-significant digits of the hash be focused on the final
- characters.
+ The previous change introduced a new pack_name_hash_v2() function that
+ intends to satisfy much of the hash locality features of the existing
+ pack_name_hash() function while also distinguishing paths with similar
+ final components of their paths.

- Here's the crux of the implementation:
+ This change adds a new --name-hash-version option for 'git pack-objects'
+ to allow users to select their preferred function version. This use of
+ an integer version allows for future expansion and a direct way to later
+ store a name hash version in the .bitmap format.

- /*
- * This effectively just creates a sortable number from the
- * last sixteen non-whitespace characters. Last characters
- * count "most", so things that end in ".c" sort together.
- */
- while ((c = *name++) != 0) {
- if (isspace(c))
- continue;
- hash = (hash >> 2) + (c << 24);
- }
+ For now, let's consider how effective this mechanism is when repacking a
+ repository with different name hash versions. Specifically, we will
+ execute 'git pack-objects' the same way a 'git repack -adf' process
+ would, except we include --name-hash-version=<n> for testing.
+
+ On the Git repository, we do not expect much difference. All path names
+ are short. This is backed by our results:

- As the comment mentions, this only cares about the last sixteen
- non-whitespace characters. This cause some filenames to collide more
- than others. Here are some examples that I've seen while investigating
- repositories that are growing more than they should be:
+ | Stage | Pack Size | Repack Time |
+ |-----------------------|-----------|-------------|
+ | After clone | 260 MB | N/A |
+ | --name-hash-version=1 | 127 MB | 129s |
+ | --name-hash-version=2 | 127 MB | 112s |
+
+ This example demonstrates how there is some natural overhead coming from
+ the cloned copy because the server is hosting many forks and has not
+ optimized for exactly this set of reachable objects. But the full repack
+ has similar characteristics for both versions.
+
+ Let's consider some repositories that are hitting too many collisions
+ with version 1. First, let's explore the kinds of paths that are
+ commonly causing these collisions:

* "/CHANGELOG.json" is 15 characters, and is created by the beachball
[1] tool. Only the final character of the parent directory can
- differntiate different versions of this file, but also only the two
+ differentiate different versions of this file, but also only the two
most-significant digits. If that character is a letter, then this is always a collision. Similar issues occur with the similar "/CHANGELOG.md" path, though there is more opportunity for
- differences in the parent directory.
+ differences In the parent directory.

- * Localization files frequently have common filenames but differentiate
- via parent directories. In C#, the name "/strings.resx.lcl" is used
- for these localization files and they will all collide in name-hash.
+ * Localization files frequently have common filenames but
+ differentiates via parent directories. In C#, the name
+ "/strings.resx.lcl" is used for these localization files and they
+ will all collide in name-hash.

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

@@ Commit message
common name across multiple directories and is causing Git to repack poorly due to name-hash collisions.

- It is clear that the existing name-hash algorithm is optimized for
- repositories with short path names, but also is optimized for packing a
- single snapshot of a repository, not a repository with many versions of
- the same file. In my testing, this has proven out where the name-hash
- algorithm does a good job of finding peer files as delta bases when
- unable to use a historical version of that exact file.
-
- However, for repositories that have many versions of most files and
- directories, it is more important that the objects that appear at the
- same path are grouped together.
-
- Create a new pack_full_name_hash() method and a new --full-name-hash
- option for 'git pack-objects' to call that method instead. Add a simple
- pass-through for 'git repack --full-name-hash' for additional testing in
- the context of a full repack, where I expect this will be most
- effective.
-
- The hash algorithm is as simple as possible to be reasonably effective:
- for each character of the path string, add a multiple of that character
- and a large prime number (chosen arbitrarily, but intended to be large
- relative to the size of a uint32_t). Then, shift the current hash value
- to the right by 5, with overlap. The addition and shift parameters are
- standard mechanisms for creating hard-to-predict behaviors in the bits
- of the resulting hash.
-
- This is not meant to be cryptographic at all, but uniformly distributed
- across the possible hash values. This creates a hash that appears
- pseudorandom. There is no ability to consider similar file types as
- being close to each other.
-
- In a later change, a test-tool will be added so the effectiveness of
- this hash can be demonstrated directly.
-
- For now, let's consider how effective this mechanism is when repacking a
- repository with and without the --full-name-hash option. Specifically,
- let's use 'git repack -adf [--full-name-hash]' as our test.
-
- On the Git repository, we do not expect much difference. All path names
- are short. This is backed by our results:
-
- | Stage | Pack Size | Repack Time |
- |-----------------------|-----------|-------------|
- | After clone | 260 MB | N/A |
- | Standard Repack | 127MB | 106s |
- | With --full-name-hash | 126 MB | 99s |
-
- This example demonstrates how there is some natural overhead coming from
- the cloned copy because the server is hosting many forks and has not
- optimized for exactly this set of reachable objects. But the full repack
- has similar characteristics with and without --full-name-hash.
-
- However, we can test this in a repository that uses one of the
- problematic naming conventions above. The fluentui [2] repo uses
- beachball to generate CHANGELOG.json and CHANGELOG.md files, and these
- files have very poor delta characteristics when comparing against
- versions across parent directories.
+ One open-source example is the fluentui [2] repo, which uses beachball
+ to generate CHANGELOG.json and CHANGELOG.md files, and these files have
+ very poor delta characteristics when comparing against versions across
+ parent directories.

| Stage | Pack Size | Repack Time |
|-----------------------|-----------|-------------|
| After clone | 694 MB | N/A |
- | Standard Repack | 438 MB | 728s |
- | With --full-name-hash | 168 MB | 142s |
+ | --name-hash-version=1 | 438 MB | 728s |
+ | --name-hash-version=2 | 168 MB | 142s |

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

@@ Commit message
reproduction. The results are so significant that I find it important to share here:

- | Repo | Standard Repack | With --full-name-hash |
- |----------|-----------------|-----------------------|
- | fluentui | 438 MB | 168 MB |
- | Repo B | 6,255 MB | 829 MB |
- | Repo C | 37,737 MB | 7,125 MB |
- | Repo D | 130,049 MB | 6,190 MB |
+ | Repo | --name-hash-version=1 | --name-hash-version=2 |
+ |----------|-----------------------|-----------------------|
+ | fluentui | 440 MB | 161 MB |
+ | Repo B | 6,248 MB | 856 MB |
+ | Repo C | 37,278 MB | 6,755 MB |
+ | Repo D | 131,204 MB | 7,463 MB |

- Future changes could include making --full-name-hash implied by a config
+ Future changes could include making --name-hash-version implied by a config
value or even implied by default during a full repack.

It is important to point out that the name hash value is stored in the
- .bitmap file format, so we must disable the --full-name-hash option when
- bitmaps are being read or written. Later, the bitmap format could be
- updated to be aware of the name hash version so deltas can be quickly
- computed across the bitmapped/not-bitmapped boundary.
+ .bitmap file format, so we must force --name-hash-version=1 when bitmaps
+ are being read or written. Later, the bitmap format could be updated to
+ be aware of the name hash version so deltas can be quickly computed
+ across the bitmapped/not-bitmapped boundary.

@@ Documentation/git-pack-objects.txt: SYNOPSIS
[--stdout [--filter=<filter-spec>] | <base-name>]
- [--shallow] [--keep-true-parents] [--[no-]sparse] < <object-list>
+ [--shallow] [--keep-true-parents] [--[no-]sparse]
-+ [--full-name-hash] < <object-list>
++ [--name-hash-version=<n>] < <object-list>

DESCRIPTION
+@@ Documentation/git-pack-objects.txt: raise an error.
+ Restrict delta matches based on "islands". See DELTA ISLANDS
+ below.
+
++--name-hash-version=<n>::
++ While performing delta compression, Git groups objects that may be
++ similar based on heuristics using the path to that object. While
++ grouping objects by an exact path match is good for paths with
++ many versions, there are benefits for finding delta pairs across
++ different full paths. Git collects objects by type and then by a
++ "name hash" of the path and then by size, hoping to group objects
++ that will compress well together.
+++
++The default name hash version is 1, which prioritizes hash locality by ++considering the final bytes of the path as providing the maximum magnitude ++to the hash function. This version excels at distinguishing short paths ++and finding renames across directories. However, the hash function depends ++primarily on the final 16 bytes of the path. If there are many paths in ++the repo that have the same final 16 bytes and differ only by parent ++directory, then this name-hash may lead to too many collisions and cause ++poor results. At the moment, this version is required when writing ++reachability bitmap files with --write-bitmap-index.
+++
++The name hash version 2 has similar locality features as version 1, ++except it considers each path component separately and overlays the hashes ++with a shift. This still prioritizes the final bytes of the path, but also ++"salts" the lower bits of the hash using the parent directory names. This ++method allows for some of the locality benefits of version 1 while ++breaking most of the collisions from a similarly-named file appearing in ++many different directories. At the moment, this version is not allowed ++when writing reachability bitmap files with --write-bitmap-index and it ++will be automatically changed to version 1.
++
+
+ DELTA ISLANDS
+ -------------

## builtin/pack-objects.c ##
@@ builtin/pack-objects.c: struct configured_exclusion {
static struct oidmap configured_exclusions;

static struct oidset excluded_by_config;
-+static int use_full_name_hash;
++static int name_hash_version = 1;
++
++static void validate_name_hash_version(void)
++{
++ if (name_hash_version < 1 || name_hash_version > 2)
++ die(_("invalid --name-hash-version option: %d"), name_hash_version);
++}
+
+static inline uint32_t pack_name_hash_fn(const char *name) +{
-+ if (use_full_name_hash)
-+ return pack_full_name_hash(name);
-+ return pack_name_hash(name);
++ switch (name_hash_version)
++ {
++ case 1:
++ return pack_name_hash(name);
++
++ case 2:
++ return pack_name_hash_v2(name);
++
++ default:
++ BUG("invalid name-hash version: %d", name_hash_version);
++ }
+}

/*
@@ builtin/pack-objects.c: static void add_cruft_object_entry(const struct object_i
0, name && no_try_delta(name),
pack, offset);
}
+@@ builtin/pack-objects.c: static int get_object_list_from_bitmap(struct rev_info *revs)
+ if (!(bitmap_git = prepare_bitmap_walk(revs, 0)))
+ return -1;
+
++ /*
++ * For now, force the name-hash version to be 1 since that
++ * is the version implied by the bitmap format. Later, the
++ * format can include this version explicitly in its format,
++ * allowing readers to know the version that was used during
++ * the bitmap write.
++ */
++ name_hash_version = 1;
++
+ if (pack_options_allow_reuse())
+ reuse_partial_packfile_from_bitmap(bitmap_git,
+ &reuse_packfiles,
@@ builtin/pack-objects.c: int cmd_pack_objects(int argc,
OPT_STRING_LIST(0, "uri-protocol", &uri_protocols,
N_("protocol"),
N_("exclude any configured uploadpack.blobpackfileuri with this protocol")),
-+ OPT_BOOL(0, "full-name-hash", &use_full_name_hash,
-+ N_("optimize delta compression across identical path names over time")),
++ OPT_INTEGER(0, "name-hash-version", &name_hash_version,
++ N_("use the specified name-hash function to group similar objects")),
OPT_END(),
};

@@ builtin/pack-objects.c: int cmd_pack_objects(int argc,
if (pack_to_stdout || !rev_list_all)
write_bitmap_index = 0;

-+ if (write_bitmap_index && use_full_name_hash) {
-+ warning(_("currently, the --full-name-hash option is incompatible with --write-bitmap-index"));
-+ use_full_name_hash = 0;
++ validate_name_hash_version();
++ if (write_bitmap_index && name_hash_version != 1) {
++ warning(_("currently, --write-bitmap-index requires --name-hash-version=1"));
++ name_hash_version = 1;
+ }
+
if (use_delta_islands)
@@ builtin/repack.c: struct pack_objects_args {
struct list_objects_filter_options filter_options;
};

-@@ builtin/repack.c: static void prepare_pack_objects(struct child_process *cmd,
- strvec_pushf(&cmd->args, "--no-reuse-delta");
- if (args->no_reuse_object)
- strvec_pushf(&cmd->args, "--no-reuse-object");
-+ if (args->full_name_hash)
-+ strvec_pushf(&cmd->args, "--full-name-hash");
- if (args->local)
- strvec_push(&cmd->args, "--local");
- if (args->quiet)
-@@ builtin/repack.c: int cmd_repack(int argc,
- N_("pass --no-reuse-delta to git-pack-objects")),
- OPT_BOOL('F', NULL, &po_args.no_reuse_object,
- N_("pass --no-reuse-object to git-pack-objects")),
-+ OPT_BOOL(0, "full-name-hash", &po_args.full_name_hash,
-+ N_("pass --full-name-hash to git-pack-objects")),
- OPT_NEGBIT('n', NULL, &run_update_server_info,
- N_("do not run git-update-server-info"), 1),
- OPT__QUIET(&po_args.quiet, N_("be quiet")),
-
- ## pack-objects.h ##
-@@ pack-objects.h: static inline uint32_t pack_name_hash(const char *name)
- return hash;
- }
-
-+static inline uint32_t pack_full_name_hash(const char *name)
-+{
-+ const uint32_t bigp = 1234572167U;
-+ uint32_t c, hash = bigp;
-+
-+ if (!name)
-+ return 0;
-+
-+ /*
-+ * Do the simplest thing that will resemble pseudo-randomness: add
-+ * random multiples of a large prime number with a binary shift.
-+ * The goal is not to be cryptographic, but to be generally
-+ * uniformly distributed.
-+ */
-+ while ((c = *name++) != 0) {
-+ hash += c * bigp;
-+ hash = (hash >> 5) | (hash << 27);
-+ }
-+ return hash;
-+}
-+
- static inline enum object_type oe_type(const struct object_entry *e)
- {
- return e->type_valid ? e->type_ : OBJ_BAD;

## t/t5300-pack-object.sh ##
@@ t/t5300-pack-object.sh: do
'
done

++test_expect_success 'valid and invalid --name-hash-versions' '
++ # Valid values are hard to verify other than "do not fail".
++ # Performance tests will be more valuable to validate these versions.
++ for value in 1 2
++ do
++ git pack-objects base --all --name-hash-version=$value || return 1
++ done &&
++
++ # Invalid values have clear post-conditions.
++ for value in -1 0 3
++ do
++ test_must_fail git pack-objects base --all --name-hash-version=$value 2>err &&
++ test_grep "invalid --name-hash-version option" err || return 1
++ done
++'
++
+# The following test is not necessarily a permanent choice, but since we do not +# have a "name hash version" bit in the .bitmap file format, we cannot write the
-+# full-name hash values into the .bitmap file without risking breakage later. ++# hash values into the .bitmap file without risking breakage later.
+#
+# TODO: Make these compatible in the future and replace this test with the +# expected behavior when both are specified.
-+test_expect_success '--full-name-hash and --write-bitmap-index are incompatible' '
-+ git pack-objects base --all --full-name-hash --write-bitmap-index 2>err &&
-+ test_grep incompatible err &&
++test_expect_success '--name-hash-version=2 and --write-bitmap-index are incompatible' '
++ git pack-objects base --all --name-hash-version=2 --write-bitmap-index 2>err &&
++ test_grep "currently, --write-bitmap-index requires --name-hash-version=1" err &&
+
+ # --stdout option silently removes --write-bitmap-index
-+ git pack-objects --stdout --all --full-name-hash --write-bitmap-index >out 2>err &&
-+ ! test_grep incompatible err
++ git pack-objects --stdout --all --name-hash-version=2 --write-bitmap-index >out 2>err &&
++ ! test_grep "currently, --write-bitmap-index requires --name-hash-version=1" err
+'
+
test_done
2: 93395c93347 ! 3: 1947d1bf448 repack: add --full-name-hash option
@@ Metadata
Author: Derrick Stolee <[email protected]>

## Commit message ##
- repack: add --full-name-hash option
+ repack: add --name-hash-version option

- The new '--full-name-hash' option for 'git repack' is a simple
+ The new '--name-hash-version' option for 'git repack' is a simple
pass-through to the underlying 'git pack-objects' subcommand. However, this subcommand may have other options and a temporary filename as part of the subcommand execution that may not be predictable or could change
@@ Commit message
The existing test_subcommand method requires an exact list of arguments for the subcommand. This is too rigid for our needs here, so create a new method, test_subcommand_flex. Use it to check that the
- --full-name-hash option is passing through.
+ --name-hash-version option is passing through.

+ ## Documentation/git-repack.txt ##
+@@ Documentation/git-repack.txt: git-repack - Pack unpacked objects in a repository
+ SYNOPSIS
+ --------
+ [verse]
+-'git repack' [-a] [-A] [-d] [-f] [-F] [-l] [-n] [-q] [-b] [-m] [--window=<n>] [--depth=<n>] [--threads=<n>] [--keep-pack=<pack-name>] [--write-midx] ++'git repack' [-a] [-A] [-d] [-f] [-F] [-l] [-n] [-q] [-b] [-m]
++ [--window=<n>] [--depth=<n>] [--threads=<n>] [--keep-pack=<pack-name>]
++ [--write-midx] [--name-hash-version=<n>]
+
+ DESCRIPTION
+ -----------
+@@ Documentation/git-repack.txt: linkgit:git-multi-pack-index[1]).
+ Write a multi-pack index (see linkgit:git-multi-pack-index[1])
+ containing the non-redundant packs.
+
++--name-hash-version=<n>::
++ While performing delta compression, Git groups objects that may be
++ similar based on heuristics using the path to that object. While
++ grouping objects by an exact path match is good for paths with
++ many versions, there are benefits for finding delta pairs across
++ different full paths. Git collects objects by type and then by a
++ "name hash" of the path and then by size, hoping to group objects
++ that will compress well together.
+++
++The default name hash version is 1, which prioritizes hash locality by
++considering the final bytes of the path as providing the maximum magnitude
++to the hash function. This version excels at distinguishing short paths
++and finding renames across directories. However, the hash function depends
++primarily on the final 16 bytes of the path. If there are many paths in
++the repo that have the same final 16 bytes and differ only by parent
++directory, then this name-hash may lead to too many collisions and cause
++poor results. At the moment, this version is required when writing
++reachability bitmap files with --write-bitmap-index.
+++
++The name hash version 2 has similar locality features as version 1,
++except it considers each path component separately and overlays the hashes
++with a shift. This still prioritizes the final bytes of the path, but also
++"salts" the lower bits of the hash using the parent directory names. This
++method allows for some of the locality benefits of version 1 while
++breaking most of the collisions from a similarly-named file appearing in
++many different directories. At the moment, this version is not allowed
++when writing reachability bitmap files with --write-bitmap-index and it
++will be automatically changed to version 1.
++
++
+ CONFIGURATION
+ -------------
+
+
+ ## builtin/repack.c ##
+@@ builtin/repack.c: static int run_update_server_info = 1;
+ static char *packdir, *packtmp_name, *packtmp;
+
+ static const char *const git_repack_usage[] = {
+- N_("git repack [<options>]"),
++ N_("git repack [-a] [-A] [-d] [-f] [-F] [-l] [-n] [-q] [-b] [-m]\n"
++ "[--window=<n>] [--depth=<n>] [--threads=<n>] [--keep-pack=<pack-name>]\n"
++ "[--write-midx] [--name-hash-version=<n>]"),
+ NULL
+ };
+
+@@ builtin/repack.c: struct pack_objects_args {
+ int no_reuse_object;
+ int quiet;
+ int local;
+- int full_name_hash;
++ int name_hash_version;
+ struct list_objects_filter_options filter_options;
+ };
+
+@@ builtin/repack.c: static void prepare_pack_objects(struct child_process *cmd,
+ strvec_pushf(&cmd->args, "--no-reuse-delta");
+ if (args->no_reuse_object)
+ strvec_pushf(&cmd->args, "--no-reuse-object");
++ if (args->name_hash_version)
++ strvec_pushf(&cmd->args, "--name-hash-version=%d", args->name_hash_version);
+ if (args->local)
+ strvec_push(&cmd->args, "--local");
+ if (args->quiet)
+@@ builtin/repack.c: int cmd_repack(int argc,
+ N_("pass --no-reuse-delta to git-pack-objects")),
+ OPT_BOOL('F', NULL, &po_args.no_reuse_object,
+ N_("pass --no-reuse-object to git-pack-objects")),
++ OPT_INTEGER(0, "name-hash-version", &po_args.name_hash_version,
++ N_("specify the name hash version to use for grouping similar objects by path")),
+ OPT_NEGBIT('n', NULL, &run_update_server_info,
+ N_("do not run git-update-server-info"), 1),
+ OPT__QUIET(&po_args.quiet, N_("be quiet")),
+
+ ## t/t0450/txt-help-mismatches ##
+@@ t/t0450/txt-help-mismatches: rebase
+ remote
+ remote-ext
+ remote-fd
+-repack
+ reset
+ restore
+ rev-parse
+
## t/t7700-repack.sh ##
@@ t/t7700-repack.sh: test_expect_success 'repack -ad cleans up old .tmp-* packs' '
test_must_be_empty tmpfiles
'

-+test_expect_success '--full-name-hash option passes through to pack-objects' '
-+ GIT_TRACE2_EVENT="$(pwd)/full-trace.txt" \
-+ git repack -a --full-name-hash &&
-+ test_subcommand_flex git pack-objects --full-name-hash <full-trace.txt
++test_expect_success '--name-hash-version option passes through to pack-objects' '
++ GIT_TRACE2_EVENT="$(pwd)/hash-trace.txt" \
++ git repack -a --name-hash-version=2 &&
++ test_subcommand_flex git pack-objects --name-hash-version=2 <hash-trace.txt
+'
-+
+
test_expect_success 'setup for update-server-info' '
git init update-server-info &&
3: 259734e0bce ! 4: 6a95708bf97 pack-objects: add GIT_TEST_FULL_NAME_HASH
@@ Metadata
Author: Derrick Stolee <[email protected]>

## Commit message ##
- pack-objects: add GIT_TEST_FULL_NAME_HASH
+ pack-objects: add GIT_TEST_NAME_HASH_VERSION

- Add a new environment variable to opt-in to the --full-name-hash option
- in 'git pack-objects'. This allows for extra testing of the feature
- without repeating all of the test scenarios.
+ Add a new environment variable to opt-in to differen values of the
+ --name-hash-version=<n> option in 'git pack-objects'. This allows for
+ extra testing of the feature without repeating all of the test
+ scenarios. Unlike many GIT_TEST_* variables, we are choosing to not add
+ this to the linux-TEST-vars CI build as that test run is already
+ overloaded. The behavior exposed by this test variable is of low risk
+ and should be sufficient to allow manual testing when an issue arises.

But this option isn't free. There are a few tests that change behavior with the variable enabled.
@@ Commit message
variable.

Third, there are some tests that compare the exact output of a 'git
- pack-objects' process when using bitmaps. The warning that disables the
- --full-name-hash option causes these tests to fail. Disable the
- environment variable to get around this issue.
+ pack-objects' process when using bitmaps. The warning that ignores the
+ --name-hash-version=2 and forces version 1 causes these tests to fail.
+ Disable the environment variable to get around this issue.

@@ builtin/pack-objects.c: struct configured_exclusion {
static struct oidmap configured_exclusions;

static struct oidset excluded_by_config;
--static int use_full_name_hash;
-+static int use_full_name_hash = -1;
+-static int name_hash_version = 1;
++static int name_hash_version = -1;

- static inline uint32_t pack_name_hash_fn(const char *name)
+ static void validate_name_hash_version(void)
{
@@ builtin/pack-objects.c: int cmd_pack_objects(int argc,
if (pack_to_stdout || !rev_list_all)
write_bitmap_index = 0;

-- if (write_bitmap_index && use_full_name_hash) {
-+ if (use_full_name_hash < 0)
-+ use_full_name_hash = git_env_bool("GIT_TEST_FULL_NAME_HASH", 0);
++ if (name_hash_version < 0)
++ name_hash_version = (int)git_env_ulong("GIT_TEST_NAME_HASH_VERSION", 1);
+
-+ if (write_bitmap_index && use_full_name_hash > 0) {
- warning(_("currently, the --full-name-hash option is incompatible with --write-bitmap-index"));
- use_full_name_hash = 0;
- }
-
- ## ci/run-build-and-tests.sh ##
-@@ ci/run-build-and-tests.sh: linux-TEST-vars)
- export GIT_TEST_NO_WRITE_REV_INDEX=1
- export GIT_TEST_CHECKOUT_WORKERS=2
- export GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1
-+ export GIT_TEST_FULL_NAME_HASH=1
- ;;
- linux-clang)
- export GIT_TEST_DEFAULT_HASH=sha1
+ validate_name_hash_version();
+ if (write_bitmap_index && name_hash_version != 1) {
+ warning(_("currently, --write-bitmap-index requires --name-hash-version=1"));

## t/README ##
@@ t/README: a test and then fails then the whole test run will abort. This can help to make
sure the expected tests are executed and not silently skipped when their dependency breaks or is simply not present in a new environment.

-+GIT_TEST_FULL_NAME_HASH=<boolean>, when true, sets the default name-hash -+function in 'git pack-objects' to be the one used by the --full-name-hash -+option.
++GIT_TEST_NAME_HASH_VERSION=<int>, when set, causes 'git pack-objects' to ++assume '--name-hash-version=<n>'.
++
+
Naming Tests
------------

+ ## t/t5300-pack-object.sh ##
+@@ t/t5300-pack-object.sh: do
+ done
+
+ test_expect_success 'valid and invalid --name-hash-versions' '
++ sane_unset GIT_TEST_NAME_HASH_VERSION &&
++
+ # Valid values are hard to verify other than "do not fail".
+ # Performance tests will be more valuable to validate these versions.
+- for value in 1 2
++ # Negative values are converted to version 1.
++ for value in -1 1 2
+ do
+ git pack-objects base --all --name-hash-version=$value || return 1
+ done &&
+
+ # Invalid values have clear post-conditions.
+- for value in -1 0 3
++ for value in 0 3
+ do
+ test_must_fail git pack-objects base --all --name-hash-version=$value 2>err &&
+ test_grep "invalid --name-hash-version option" err || return 1
+
## t/t5310-pack-bitmaps.sh ##
@@ t/t5310-pack-bitmaps.sh: test_bitmap_cases () {
cat >expect <<-\EOF &&
error: missing value for '\''pack.preferbitmaptips'\'' EOF
+- git repack -adb 2>actual &&
+
-+ # Disable --full-name-hash test due to stderr comparison.
-+ GIT_TEST_FULL_NAME_HASH=0 \
- git repack -adb 2>actual &&
++ # Disable name hash version adjustment due to stderr comparison.
++ GIT_TEST_NAME_HASH_VERSION=1 \
++ git repack -adb 2>actual &&
test_cmp expect actual
)
+ '

## t/t5333-pseudo-merge-bitmaps.sh ##
@@ t/t5333-pseudo-merge-bitmaps.sh: test_expect_success 'bitmapPseudoMerge.stableThreshold creates stable groups' '
@@ t/t5333-pseudo-merge-bitmaps.sh: test_expect_success 'bitmapPseudoMerge.stableTh

test_expect_success 'out of order thresholds are rejected' '
+ # Disable this option to avoid stderr message
-+ GIT_TEST_FULL_NAME_HASH=0 &&
-+ export GIT_TEST_FULL_NAME_HASH &&
++ GIT_TEST_NAME_HASH_VERSION=1 &&
++ export GIT_TEST_NAME_HASH_VERSION &&
+
test_must_fail git \
-c bitmapPseudoMerge.test.pattern="refs/*" \
@@ t/t5510-fetch.sh: test_expect_success 'all boundary commits are excluded' '
ad=$(git log --no-walk --format=%ad HEAD) &&
- git bundle create twoside-boundary.bdl main --since="$ad" &&
+
-+ # If the --full-name-hash function is used here, then no delta
++ # If the a different name hash function is used here, then no delta
+ # pair is found and the bundle does not expand to three objects
+ # when fixing the thin object.
-+ GIT_TEST_FULL_NAME_HASH=0 \
++ GIT_TEST_NAME_HASH_VERSION=1 \
+ git bundle create twoside-boundary.bdl main --since="$ad" &&
test_bundle_object_count --thin twoside-boundary.bdl 3
'
@@ t/t5616-partial-clone.sh: test_expect_success 'fetch lazy-fetches only to resolv
- GIT_TRACE_PACKET="$(pwd)/trace" git -C client \
+ #
+ # TODO: the --full-name-hash option is disabled here, since this test
-+ # is fundamentally broken! When GIT_TEST_FULL_NAME_HASH=1, the server
++ # is fundamentally broken! When GIT_TEST_NAME_HASH_VERSION=2, the server
+ # recognizes delta bases in a different way and then sends a _blob_ to
+ # the client with a delta base that the client does not have! This is
+ # because the client is cloned from "promisor-server" with tree:0 but
-+ # is now fetching from "server" withot any filter. This is violating the
++ # is now fetching from "server" without any filter. This is violating the
+ # promise to the server that all reachable objects exist and could be
+ # used as delta bases!
+ GIT_TRACE_PACKET="$(pwd)/trace" \
-+ GIT_TEST_FULL_NAME_HASH=0 \
++ GIT_TEST_NAME_HASH_VERSION=1 \
+ git -C client \
fetch "file://$(pwd)/server" main &&

@@ t/t5616-partial-clone.sh: test_expect_success 'fetch lazy-fetches only to resolv
- GIT_TRACE_PACKET="$(pwd)/trace" git -C client \
+ #
+ # TODO: the --full-name-hash option is disabled here, since this test
-+ # is fundamentally broken! When GIT_TEST_FULL_NAME_HASH=1, the server
++ # is fundamentally broken! When GIT_TEST_NAME_HASH_VERSION=2, the server
+ # recognizes delta bases in a different way and then sends a _blob_ to
+ # the client with a delta base that the client does not have! This is
+ # because the client is cloned from "promisor-server" with tree:0 but
-+ # is now fetching from "server" withot any filter. This is violating the
++ # is now fetching from "server" without any filter. This is violating the
+ # promise to the server that all reachable objects exist and could be
+ # used as delta bases!
+ GIT_TRACE_PACKET="$(pwd)/trace" \
-+ GIT_TEST_FULL_NAME_HASH=0 \
++ GIT_TEST_NAME_HASH_VERSION=1 \
+ git -C client \
fetch "file://$(pwd)/server" main &&

@@ t/t6020-bundle-misc.sh: test_expect_success 'create bundle with --since option'
test_cmp expect actual &&

- git bundle create since.bdl \
-+ # If the --full-name-hash option is used, then one fewer
++ # If a different name hash function is used, then one fewer
+ # delta base is found and this counts a different number
+ # of objects after performing --fix-thin.
-+ GIT_TEST_FULL_NAME_HASH=0 \
++ GIT_TEST_NAME_HASH_VERSION=1 \
+ git bundle create since.bdl \
--since "Thu Apr 7 15:27:00 2005 -0700" \
--all &&
@@ t/t7406-submodule-update.sh: test_expect_success 'submodule update --quiet passe
) &&
git clone super4 super5 &&
(cd super5 &&
+- git submodule update --quiet --init --depth=1 submodule3 >out 2>err &&
+ # This test var can mess with the stderr output checked in this test.
-+ GIT_TEST_FULL_NAME_HASH=0 \
- git submodule update --quiet --init --depth=1 submodule3 >out 2>err &&
++ GIT_TEST_NAME_HASH_VERSION=1 \
++ git submodule update --quiet --init --depth=1 submodule3 >out 2>err &&
test_must_be_empty out &&
test_must_be_empty err
+ ) &&

## t/t7700-repack.sh ##
@@ t/t7700-repack.sh: test_expect_success 'no bitmaps created if .keep files present' '
keep=${pack%.pack}.keep &&
test_when_finished "rm -f \"\$keep\"" &&
>"$keep" &&
+- git -C bare.git repack -ad 2>stderr &&
+
-+ # Disable --full-name-hash test due to stderr comparison.
-+ GIT_TEST_FULL_NAME_HASH=0 \
- git -C bare.git repack -ad 2>stderr &&
++ # Disable --name-hash-version test due to stderr comparison.
++ GIT_TEST_NAME_HASH_VERSION=1 \
++ git -C bare.git repack -ad 2>stderr &&
test_must_be_empty stderr &&
find bare.git/objects/pack/ -type f -name "*.bitmap" >actual &&
+ test_must_be_empty actual
@@ t/t7700-repack.sh: test_expect_success 'auto-bitmaps do not complain if unavailable' '
blob=$(test-tool genrandom big $((1024*1024)) |
git -C bare.git hash-object -w --stdin) &&
git -C bare.git update-ref refs/tags/big $blob &&
+- git -C bare.git repack -ad 2>stderr &&
+
-+ # Disable --full-name-hash test due to stderr comparison.
-+ GIT_TEST_FULL_NAME_HASH=0 \
- git -C bare.git repack -ad 2>stderr &&
++ # Disable --name-hash-version test due to stderr comparison.
++ GIT_TEST_NAME_HASH_VERSION=1 \
++ git -C bare.git repack -ad 2>stderr &&
test_must_be_empty stderr &&
find bare.git/objects/pack -type f -name "*.bitmap" >actual &&
+ test_must_be_empty actual

 4:  65784f85bce < -:  ----------- git-repack: update usage to match docs
 5:  c14ef6879e4 ! 5:  3b5697467c9 p5313: add size comparison test

@@ Commit message
adjust how compression is done, use this new performance test script to demonstrate their effectiveness in performance and size.

- The recently-added --full-name-hash option swaps the default name-hash
- algorithm with one that attempts to uniformly distribute the hashes
- based on the full path name instead of the last 16 characters.
+ The recently-added --name-hash-version option allows for testing
+ different name hash functions. Version 2 intends to preserve some of the
+ locality of version 1 while more often breaking collisions due to long
+ filenames.

- This has a dramatic effect on full repacks for repositories with many
- versions of most paths. It can have a negative impact on cases such as
- pushing a single change.
+ Distinguishing objects by more of the path is critical when there are
+ many name hash collisions and several versions of the same path in the
+ full history, giving a significant boost to the full repack case. The
+ locality of the hash function is critical to compressing something like
+ a shallow clone or a thin pack representing a push of a single commit.

This can be seen by running pt5313 on the open source fluentui repository [1]. Most commits will have this kind of output for the thin
@@ Commit message

Checked out at the parent of [2], I see the following statistics:

- Test HEAD
- ---------------------------------------------------------------------
- 5313.2: thin pack 0.37(0.43+0.02)
- 5313.3: thin pack size 1.2M
- 5313.4: thin pack with --full-name-hash 0.06(0.09+0.02)
- 5313.5: thin pack size with --full-name-hash 20.4K
- 5313.6: big pack 2.01(7.73+0.23)
- 5313.7: big pack size 20.3M
- 5313.8: big pack with --full-name-hash 1.32(2.77+0.27)
- 5313.9: big pack size with --full-name-hash 19.9M
- 5313.10: shallow fetch pack 1.40(3.01+0.08)
- 5313.11: shallow pack size 34.4M
- 5313.12: shallow pack with --full-name-hash 1.08(1.25+0.14)
- 5313.13: shallow pack size with --full-name-hash 35.4M
- 5313.14: repack 90.70(672.88+2.46)
- 5313.15: repack size 439.6M
- 5313.16: repack with --full-name-hash 18.53(123.41+2.53)
- 5313.17: repack size with --full-name-hash 169.7M
-
- In this case, we see positive behaviors such as a significant shrink in
- the size of the thin pack and full repack. The big pack is slightly
- smaller with --full-name-hash than without. The shallow pack is slightly
- larger with --full-name-hash.
+ Test HEAD
+ ---------------------------------------------------------------
+ 5313.2: thin pack with version 1 0.37(0.44+0.02)
+ 5313.3: thin pack size with version 1 1.2M
+ 5313.4: big pack with version 1 2.04(7.77+0.23)
+ 5313.5: big pack size with version 1 20.4M
+ 5313.6: shallow fetch pack with version 1 1.41(2.94+0.11)
+ 5313.7: shallow pack size with version 1 34.4M
+ 5313.8: repack with version 1 95.70(676.41+2.87)
+ 5313.9: repack size with version 1 439.3M
+ 5313.10: thin pack with version 2 0.12(0.12+0.06)
+ 5313.11: thin pack size with version 2 22.0K
+ 5313.12: big pack with version 2 2.80(5.43+0.34)
+ 5313.13: big pack size with version 2 25.9M
+ 5313.14: shallow fetch pack with version 2 1.77(2.80+0.19)
+ 5313.15: shallow pack size with version 2 33.7M
+ 5313.16: repack with version 2 33.68(139.52+2.58)
+ 5313.17: repack size with version 2 160.5M
+
+ To make comparisons easier, I will reformat this output into a different
+ table style:
+
+ | Test | V1 Time | V2 Time | V1 Size | V2 Size |
+ |--------------|---------|---------|---------|---------|
+ | Thin Pack | 0.37 s | 0.12 s | 1.2 M | 22.0 K |
+ | Big Pack | 2.04 s | 2.80 s | 20.4 M | 25.9 M |
+ | Shallow Pack | 1.41 s | 1.77 s | 34.4 M | 33.7 M |
+ | Repack | 95.70 s | 33.68 s | 439.3 M | 160.5 M |
+
+ The v2 hash function successfully differentiates the CHANGELOG.md files
+ from each other, which leads to significant improvements in the thin
+ pack (simulating a push of this commit) and the full repack. There is
+ some bloat in the "big pack" scenario and essentially the same results
+ for the shallow pack.

In the case of the Git repository, these numbers show some of the issues with this approach:

- Test HEAD
- --------------------------------------------------------------------
- 5313.2: thin pack 0.00(0.00+0.00)
- 5313.3: thin pack size 589
- 5313.4: thin pack with --full-name-hash 0.00(0.00+0.00)
- 5313.5: thin pack size with --full-name-hash 14.9K
- 5313.6: big pack 2.07(3.57+0.17)
- 5313.7: big pack size 17.6M
- 5313.8: big pack with --full-name-hash 2.00(3.07+0.19)
- 5313.9: big pack size with --full-name-hash 17.9M
- 5313.10: shallow fetch pack 1.41(2.23+0.06)
- 5313.11: shallow pack size 12.1M
- 5313.12: shallow pack with --full-name-hash 1.22(1.66+0.04)
- 5313.13: shallow pack size with --full-name-hash 12.4M
- 5313.14: repack 15.75(89.29+1.54)
- 5313.15: repack size 126.4M
- 5313.16: repack with --full-name-hash 15.56(89.78+1.32)
- 5313.17: repack size with --full-name-hash 126.0M
-
- The thin pack that simulates a push is much worse with --full-name-hash
- in this case. The name hash values are doing a lot to assist with delta
- bases, it seems. The big pack and shallow clone cases are slightly worse
- with the --full-name-hash option. Only the full repack gains some
- benefits in size.
+ | Test | V1 Time | V2 Time | V1 Size | V2 Size |
+ |--------------|---------|---------|---------|---------|
+ | Thin Pack | 0.02 s | 0.02 s | 1.1 K | 1.1 K |
+ | Big Pack | 1.69 s | 1.95 s | 13.5 M | 14.5 M |
+ | Shallow Pack | 1.26 s | 1.29 s | 12.0 M | 12.2 M |
+ | Repack | 29.51 s | 29.01 s | 237.7 M | 238.2 M |
+
+ Here, the attempts to remove conflicts in the v2 function seem to cause
+ slight bloat to these sizes. This shows that the Git repository benefits
+ a lot from cross-path delta pairs.

The results are similar with the nodejs/node repo:

- Test HEAD
- ---------------------------------------------------------------------
- 5313.2: thin pack 0.01(0.01+0.00)
- 5313.3: thin pack size 1.6K
- 5313.4: thin pack with --full-name-hash 0.01(0.00+0.00)
- 5313.5: thin pack size with --full-name-hash 3.1K
- 5313.6: big pack 4.26(8.03+0.24)
- 5313.7: big pack size 56.0M
- 5313.8: big pack with --full-name-hash 4.16(6.55+0.22)
- 5313.9: big pack size with --full-name-hash 56.2M
- 5313.10: shallow fetch pack 7.67(11.80+0.29)
- 5313.11: shallow pack size 104.6M
- 5313.12: shallow pack with --full-name-hash 7.52(9.65+0.23)
- 5313.13: shallow pack size with --full-name-hash 105.9M
- 5313.14: repack 71.22(317.61+3.95)
- 5313.15: repack size 739.9M
- 5313.16: repack with --full-name-hash 48.85(267.02+3.72)
- 5313.17: repack size with --full-name-hash 793.5M
+ | Test | V1 Time | V2 Time | V1 Size | V2 Size |
+ |--------------|---------|---------|---------|---------|
+ | Thin Pack | 0.02 s | 0.02 s | 1.6 K | 1.6 K |
+ | Big Pack | 4.61 s | 3.26 s | 56.0 M | 52.8 M |
+ | Shallow Pack | 7.82 s | 7.51 s | 104.6 M | 107.0 M |
+ | Repack | 88.90 s | 73.75 s | 740.1 M | 764.5 M |
+
+ Here, the v2 name-hash causes some size bloat more often than it reduces
+ the size, but it also universally improves performance time, which is an
+ interesting reversal. This must mean that it is helping to short-circuit
+ some delta computations even if it is not finding the most efficient
+ ones. The performance improvement cannot be explained only due to the
+ I/O cost of writing the resulting packfile.

The Linux kernel repository was the initial target of the default name hash value, and its naming conventions are practically build to take the most advantage of the default name hash values:

- Test HEAD
- -------------------------------------------------------------------------
- 5313.2: thin pack 0.15(0.01+0.03)
- 5313.3: thin pack size 4.6K
- 5313.4: thin pack with --full-name-hash 0.03(0.02+0.01)
- 5313.5: thin pack size with --full-name-hash 6.8K
- 5313.6: big pack 18.51(33.74+0.95)
- 5313.7: big pack size 201.1M
- 5313.8: big pack with --full-name-hash 16.01(29.81+0.88)
- 5313.9: big pack size with --full-name-hash 202.1M
- 5313.10: shallow fetch pack 11.49(17.61+0.54)
- 5313.11: shallow pack size 269.2M
- 5313.12: shallow pack with --full-name-hash 11.24(15.25+0.56)
- 5313.13: shallow pack size with --full-name-hash 269.8M
- 5313.14: repack 1001.25(2271.06+38.86)
- 5313.15: repack size 2.5G
- 5313.16: repack with --full-name-hash 625.75(1941.96+36.09)
- 5313.17: repack size with --full-name-hash 2.6G
+ | Test | V1 Time | V2 Time | V1 Size | V2 Size |
+ |--------------|----------|----------|---------|---------|
+ | Thin Pack | 0.17 s | 0.07 s | 4.6 K | 4.6 K |
+ | Big Pack | 17.88 s | 12.35 s | 201.1 M | 159.1 M |
+ | Shallow Pack | 11.05 s | 22.94 s | 269.2 M | 273.8 M |
+ | Repack | 727.39 s | 566.95 s | 2.5 G | 2.5 G |
+
+ Here, the thin and big packs gain some performance boosts in time, with
+ a modest gain in the size of the big pack. The shallow pack, however, is
+ more expensive to compute, likely because similarly-named files across
+ different directories are farther apart in the name hash ordering in v2.
+ The repack also gains benefits in computation time but no meaningful
+ change to the full size.

Finally, an internal Javascript repo of moderate size shows significant
- gains when repacking with --full-name-hash due to it having many name
+ gains when repacking with --name-hash-version=2 due to it having many name
hash collisions. However, it's worth noting that only the full repack
- case has enough improvement to be worth it. But the improvements are
- significant: 6.4 GB to 862 MB.
-
- Test HEAD
- --------------------------------------------------------------------------
- 5313.2: thin pack 0.03(0.02+0.00)
- 5313.3: thin pack size 1.2K
- 5313.4: thin pack with --full-name-hash 0.03(0.03+0.00)
- 5313.5: thin pack size with --full-name-hash 2.6K
- 5313.6: big pack 2.20(3.23+0.30)
- 5313.7: big pack size 130.7M
- 5313.8: big pack with --full-name-hash 2.33(3.17+0.34)
- 5313.9: big pack size with --full-name-hash 131.0M
- 5313.10: shallow fetch pack 3.56(6.02+0.32)
- 5313.11: shallow pack size 44.5M
- 5313.12: shallow pack with --full-name-hash 2.94(3.94+0.32)
- 5313.13: shallow pack size with --full-name-hash 45.3M
- 5313.14: repack 2435.22(12523.11+23.53)
- 5313.15: repack size 6.4G
- 5313.16: repack with --full-name-hash 473.25(1805.11+17.22)
- 5313.17: repack size with --full-name-hash 861.9M
-
- These tests demonstrate that it is important to be careful about which
- cases are best for using the --full-name-hash option.
+ case has significant differences from the v1 name hash:
+
+ | Test | V1 Time | V2 Time | V1 Size | V2 Size |
+ |-----------|-----------|----------|---------|---------|
+ | Thin Pack | 8.28 s | 7.28 s | 16.8 K | 16.8 K |
+ | Big Pack | 12.81 s | 11.66 s | 29.1 M | 29.1 M |
+ | Shallow | 4.86 s | 4.06 s | 42.5 M | 44.1 M |
+ | Repack | 3126.50 s | 496.33 s | 6.2 G | 855.6 M |

@@ t/perf/p5313-pack-objects.sh (new)
+ EOF
+'
+
-+test_perf 'thin pack' '
-+ git pack-objects --thin --stdout --revs --sparse <in-thin >out
-+'
-+
-+test_size 'thin pack size' '
-+ test_file_size out
-+'
++for version in 1 2
++do
++ export version
+
-+test_perf 'thin pack with --full-name-hash' '
-+ git pack-objects --thin --stdout --revs --sparse --full-name-hash <in-thin >out
-+'
++ test_perf "thin pack with version $version" '
++ git pack-objects --thin --stdout --revs --sparse \
++ --name-hash-version=$version <in-thin >out
++ '
+
-+test_size 'thin pack size with --full-name-hash' '
-+ test_file_size out
-+'
++ test_size "thin pack size with version $version" '
++ test_file_size out
++ '
+
-+test_perf 'big pack' '
-+ git pack-objects --stdout --revs --sparse <in-big >out
-+'
++ test_perf "big pack with version $version" '
++ git pack-objects --stdout --revs --sparse \
++ --name-hash-version=$version <in-big >out
++ '
+
-+test_size 'big pack size' '
-+ test_file_size out
-+'
++ test_size "big pack size with version $version" '
++ test_file_size out
++ '
+
-+test_perf 'big pack with --full-name-hash' '
-+ git pack-objects --stdout --revs --sparse --full-name-hash <in-big >out
-+'
++ test_perf "shallow fetch pack with version $version" '
++ git pack-objects --stdout --revs --sparse --shallow \
++ --name-hash-version=$version <in-shallow >out
++ '
+
-+test_size 'big pack size with --full-name-hash' '
-+ test_file_size out
-+'
++ test_size "shallow pack size with version $version" '
++ test_file_size out
++ '
+
-+test_perf 'shallow fetch pack' '
-+ git pack-objects --stdout --revs --sparse --shallow <in-shallow >out
-+'
++ test_perf "repack with version $version" '
++ git repack -adf --name-hash-version=$version
++ '
+
-+test_size 'shallow pack size' '
-+ test_file_size out
-+'
-+
-+test_perf 'shallow pack with --full-name-hash' '
-+ git pack-objects --stdout --revs --sparse --shallow --full-name-hash <in-shallow >out
-+'
-+
-+test_size 'shallow pack size with --full-name-hash' '
-+ test_file_size out
-+'
-+
-+test_perf 'repack' '
-+ git repack -adf
-+'
-+
-+test_size 'repack size' '
-+ pack=$(ls .git/objects/pack/pack-*.pack) &&
-+ test_file_size "$pack"
-+'
-+
-+test_perf 'repack with --full-name-hash' '
-+ git repack -adf --full-name-hash
-+'
-+
-+test_size 'repack size with --full-name-hash' '
-+ pack=$(ls .git/objects/pack/pack-*.pack) &&
-+ test_file_size "$pack"
-+'
++ test_size "repack size with version $version" '
++ gitdir=$(git rev-parse --git-dir) &&
++ pack=$(ls $gitdir/objects/pack/pack-*.pack) &&
++ test_file_size "$pack"
++ '
++done
+
+test_done

 6:  b8a055cb196 < -:  ----------- pack-objects: disable --full-name-hash when shallow
 7:  ab341dd0e58 ! 6:  36f2811e3d9 test-tool: add helper for name-hash values

@@ Commit message
important that these hash functions do not change across Git versions. Add a simple test to t5310-pack-bitmaps.sh to provide some testing of the current values. Due to how these functions are implemented, it would
- be difficult to change them without disturbing these values.
+ be difficult to change them without disturbing these values. The paths
+ used for this test are carefully selected to demonstrate some of the
+ behavior differences of the two current name hash versions, including
+ which conditions will cause them to collide.

Create a performance test that uses test_size to demonstrate how collisions occur for these hash algorithms. This test helps inform
@@ Commit message
My copy of the Git repository shows modest statistics around the collisions of the default name-hash algorithm:

- Test this tree
- -----------------------------------------------------------------
- 5314.1: paths at head 4.5K
- 5314.2: number of distinct name-hashes 4.1K
- 5314.3: number of distinct full-name-hashes 4.5K
- 5314.4: maximum multiplicity of name-hashes 13
- 5314.5: maximum multiplicity of fullname-hashes 1
+ Test this tree
+ --------------------------------------------------
+ 5314.1: paths at head 4.5K
+ 5314.2: distinct hash value: v1 4.1K
+ 5314.3: maximum multiplicity: v1 13
+ 5314.4: distinct hash value: v2 4.2K
+ 5314.5: maximum multiplicity: v2 9

Here, the maximum collision multiplicity is 13, but around 10% of paths have a collision with another path.
@@ Commit message
In a more interesting example, the microsoft/fluentui [1] repo had these statistics at time of committing:

- Test this tree
- -----------------------------------------------------------------
- 5314.1: paths at head 19.6K
- 5314.2: number of distinct name-hashes 8.2K
- 5314.3: number of distinct full-name-hashes 19.6K
- 5314.4: maximum multiplicity of name-hashes 279
- 5314.5: maximum multiplicity of fullname-hashes 1
+ Test this tree
+ --------------------------------------------------
+ 5314.1: paths at head 19.5K
+ 5314.2: distinct hash value: v1 8.2K
+ 5314.3: maximum multiplicity: v1 279
+ 5314.4: distinct hash value: v2 17.8K
+ 5314.5: maximum multiplicity: v2 44

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

@@ Commit message
assigned to a single value, leading the packing algorithm to sort objects from those paths together, by size.

- In this repository, no collisions occur for the full-name-hash
- algorithm.
+ With the v2 name hash function, the maximum multiplicity lowers to 44,
+ leaving some room for further improvement.

In a more extreme example, an internal monorepo had a much worse collision rate:

- Test this tree
- -----------------------------------------------------------------
- 5314.1: paths at head 221.6K
- 5314.2: number of distinct name-hashes 72.0K
- 5314.3: number of distinct full-name-hashes 221.6K
- 5314.4: maximum multiplicity of name-hashes 14.4K
- 5314.5: maximum multiplicity of fullname-hashes 2
+ Test this tree
+ --------------------------------------------------
+ 5314.1: paths at head 227.3K
+ 5314.2: distinct hash value: v1 72.3K
+ 5314.3: maximum multiplicity: v1 14.4K
+ 5314.4: distinct hash value: v2 166.5K
+ 5314.5: maximum multiplicity: v2 138

- Even in this repository with many more paths at HEAD, the collision rate
- was low and the maximum number of paths being grouped into a single
- bucket by the full-path-name algorithm was two.
+ Here, we can see that the v2 name hash function provides somem
+ improvements, but there are still a number of collisions that could lead
+ to repacking problems at this scale.

@@ t/helper/test-name-hash.c (new)
+ struct strbuf line = STRBUF_INIT;
+
+ while (!strbuf_getline(&line, stdin)) {
-+ uint32_t name_hash = pack_name_hash(line.buf);
-+ uint32_t full_hash = pack_full_name_hash(line.buf);
-+
-+ printf("%10"PRIu32"\t%10"PRIu32"\t%s\n", name_hash, full_hash, line.buf);
++ printf("%10u ", pack_name_hash(line.buf));
++ printf("%10u ", pack_name_hash_v2(line.buf));
++ printf("%s\n", line.buf);
+ }
+
+ strbuf_release(&line);
@@ t/perf/p5314-name-hash.sh (new)
+
+test_size 'paths at head' '
+ git ls-tree -r --name-only HEAD >path-list &&
-+ wc -l <path-list
-+'
-+
-+test_size 'number of distinct name-hashes' '
-+ cat path-list | test-tool name-hash >name-hashes &&
-+ cat name-hashes | awk "{ print \$1; }" | sort -n | uniq -c >name-hash-count &&
-+ wc -l <name-hash-count
++ wc -l <path-list &&
++ test-tool name-hash <path-list >name-hashes
+'
+
-+test_size 'number of distinct full-name-hashes' '
-+ cat name-hashes | awk "{ print \$2; }" | sort -n | uniq -c >full-name-hash-count &&
-+ wc -l <full-name-hash-count
-+'
++for version in 1 2
++do
++ test_size "distinct hash value: v$version" '
++ awk "{ print \$$version; }" <name-hashes | sort | \
++ uniq -c >name-hash-count &&
++ wc -l <name-hash-count
++ '
+
-+test_size 'maximum multiplicity of name-hashes' '
-+ cat name-hash-count | \
-+ sort -nr | \
-+ head -n 1 | \
-+ awk "{ print \$1; }"
-+'
-+
-+test_size 'maximum multiplicity of fullname-hashes' '
-+ cat full-name-hash-count | \
-+ sort -nr | \
-+ head -n 1 | \
-+ awk "{ print \$1; }"
-+'
++ test_size "maximum multiplicity: v$version" '
++ sort -nr <name-hash-count | head -n 1 | \
++ awk "{ print \$1; }"
++ '
++done
+
+test_done

@@ t/t5310-pack-bitmaps.sh: has_any () {
+ first
+ second
+ third
-+ one-long-enough-for-collisions
-+ two-long-enough-for-collisions
++ a/one-long-enough-for-collisions
++ b/two-long-enough-for-collisions
++ many/parts/to/this/path/enough/to/collide/in/v2
++ enough/parts/to/this/path/enough/to/collide/in/v2
+ EOF
+
+ test-tool name-hash <names >out &&
+
+ cat >expect <<-\EOF &&
-+ 2582249472 3109209818 first
-+ 2289942528 3781118409 second
-+ 2300837888 3028707182 third
-+ 2544516325 3241327563 one-long-enough-for-collisions
-+ 2544516325 4207880830 two-long-enough-for-collisions
++ 2582249472 1763573760 first
++ 2289942528 1188134912 second
++ 2300837888 1130758144 third
++ 2544516325 3963087891 a/one-long-enough-for-collisions
++ 2544516325 4013419539 b/two-long-enough-for-collisions
++ 1420111091 1709547268 many/parts/to/this/path/enough/to/collide/in/v2
++ 1420111091 1709547268 enough/parts/to/this/path/enough/to/collide/in/v2
+ EOF
+
+ test_cmp expect out

 -:  ----------- > 7:  3885ef8a2f7 pack-objects: prevent name hash version change
 -:  ----------- > 8:  64fd7b3ccad pack-objects: add third name hash version

gitgitgadget

From: Jonathan Tan <[email protected]>

As we will explore in later changes, the default name-hash function used in 'git pack-objects' has a tendency to cause collisions and cause poor delta selection. This change creates an alternative that avoids some collisions while preserving some amount of hash locality.

The pack_name_hash() method has not been materially changed since it was introduced in ce0bd64 (pack-objects: improve path grouping heuristics., 2006-06-05). The intention here is to group objects by path name, but also attempt to group similar file types together by making the most-significant digits of the hash be focused on the final characters.

Here's the crux of the implementation:

	/*
	 * This effectively just creates a sortable number from the
	 * last sixteen non-whitespace characters. Last characters
	 * count "most", so things that end in ".c" sort together.
	 */
	while ((c = *name++) != 0) {
		if (isspace(c))
			continue;
		hash = (hash >> 2) + (c << 24);
	}

As the comment mentions, this only cares about the last sixteen non-whitespace characters. This cause some filenames to collide more than others. This collision is somewhat by design in order to promote hash locality for files that have similar types (.c, .h, .json) or could be the same file across a directory rename (a/foo.txt to b/foo.txt). This leads to decent cross-path deltas in cases like shallow clones or packing a repository with very few historical versions of files that share common data with other similarly-named files.

However, when the name-hash instead leads to a large number of name-hash collisions for otherwise unrelated files, this can lead to confusing the delta calculation to prefer cross-path deltas over previous versions of the same file.

The new pack_name_hash_v2() function attempts to fix this issue by taking more of the directory path into account through its hash function. Its naming implies that we will later wire up details for choosing a name-hash function by version.

The first change is to be more careful about paths using non-ASCII characters. With these characters in mind, reverse the bits in the byte as the least-significant bits have the highest entropy and we want to maximize their influence. This is done with some bit manipulation that swaps the two halves, then the quarters within those halves, and then the bits within those quarters.

The second change is to perform hash composition operations at every level of the path. This is done by storing a 'base' hash value that contains the hash of the parent directory. When reaching a directory boundary, we XOR the current level's name-hash value with a downshift of the previous level's hash. This perturbation intends to create low-bit distinctions for paths with the same final 16 bytes but distinct parent directory structures.

The collision rate and effectiveness of this hash function will be explored in later changes as the function is integrated with 'git pack-objects' and 'git repack'.

---
 pack-objects.h | 28 ++++++++++++++++++++++++++++
 1 file changed, 28 insertions(+)

index b9898a4e64b..15be8368d21 100644
@@ -207,6 +207,34 @@ static inline uint32_t pack_name_hash(const char *name)
 	return hash;
 }
 
+static inline uint32_t pack_name_hash_v2(const char *name)
+{
+	uint32_t hash = 0, base = 0, c;
+
+	if (!name)
+		return 0;
+
+	while ((c = *name++)) {
+		if (isspace(c))
+			continue;
+		if (c == '/') {
+			base = (base >> 6) ^ hash;
+			hash = 0;
+		} else {
+			/*
+			 * 'c' is only a single byte. Reverse it and move
+			 * it to the top of the hash, moving the rest to
+			 * less-significant bits.
+			 */
+			c = (c & 0xF0) >> 4 | (c & 0x0F) << 4;
+			c = (c & 0xCC) >> 2 | (c & 0x33) << 2;
+			c = (c & 0xAA) >> 1 | (c & 0x55) << 1;
+			hash = (hash >> 2) + (c << 24);
+		}
+	}
+	return (base >> 6) ^ hash;
+}
+
 static inline enum object_type oe_type(const struct object_entry *e)
 {
 	return e->type_valid ? e->type_ : OBJ_BAD;

gitgitgadget

"Jonathan Tan via GitGitGadget" <[email protected]> writes:

[snip]

I am not Jonathan, but since the mixing-of-bits is done with XOR in the original that Linus and I wrote, I think the question applies to our version as well. We prefer not to lose entropy from input bytes, so we do not want to use OR or AND, which tend to paint everything with 1 or 0 as you mix in bits from more bytes.

Anyway the question sounds like "generally when you take tests you write with a pencil, but right now you are merely taking notes and not taking any tests. why are you writing with a pencil?" There are multiple occasions that a pencil is a great fit as writing equipment.

Thanks for the answering. My reasoning at the start was more of my thoughts on why XOR could be used here and your explanation makes it clearer.

I'd say my questions was more of "I know a pencil is used when taking tests because of XYZ reasons. On similar lines, why is a pencil used here?" :)

I think you meant the type of "name", and your worry is that *name may pick up a negative integer from there when the platform char is signed? Here we are dealing with a pathname that has often UTF-8 encoded non-ASCII letters with 8th bit set, and I agree with you that being explicitly unsigned would certainly help reduce the cognitive load.

Thanks.

From: Derrick Stolee <[email protected]>

The previous change introduced a new pack_name_hash_v2() function that intends to satisfy much of the hash locality features of the existing pack_name_hash() function while also distinguishing paths with similar final components of their paths.

This change adds a new --name-hash-version option for 'git pack-objects' to allow users to select their preferred function version. This use of an integer version allows for future expansion and a direct way to later store a name hash version in the .bitmap format.

For now, let's consider how effective this mechanism is when repacking a repository with different name hash versions. Specifically, we will execute 'git pack-objects' the same way a 'git repack -adf' process would, except we include --name-hash-version=<n> for testing.

On the Git repository, we do not expect much difference. All path names are short. This is backed by our results:

| Stage                 | Pack Size | Repack Time |
|-----------------------|-----------|-------------|
| After clone           | 260 MB    | N/A         |
| --name-hash-version=1 | 127 MB    | 129s        |
| --name-hash-version=2 | 127 MB    | 112s        |

This example demonstrates how there is some natural overhead coming from the cloned copy because the server is hosting many forks and has not optimized for exactly this set of reachable objects. But the full repack has similar characteristics for both versions.

Let's consider some repositories that are hitting too many collisions with version 1. First, let's explore the kinds of paths that are commonly causing these collisions:

* "/CHANGELOG.json" is 15 characters, and is created by the beachball
[1] tool. Only the final character of the parent directory can differentiate different versions of this file, but also only the two most-significant digits. If that character is a letter, then this is always a collision. Similar issues occur with the similar "/CHANGELOG.md" path, though there is more opportunity for differences In the parent directory.

* Localization files frequently have common filenames but differentiates via parent directories. In C#, the name "/strings.resx.lcl" is used for these localization files and they will all collide in name-hash.

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

I've come across many other examples where some internal tool uses a common name across multiple directories and is causing Git to repack poorly due to name-hash collisions.

One open-source example is the fluentui [2] repo, which uses beachball to generate CHANGELOG.json and CHANGELOG.md files, and these files have very poor delta characteristics when comparing against versions across parent directories.

| Stage                 | Pack Size | Repack Time |
|-----------------------|-----------|-------------|
| After clone           | 694 MB    | N/A         |
| --name-hash-version=1 | 438 MB    | 728s        |
| --name-hash-version=2 | 168 MB    | 142s        |

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

In this example, we see significant gains in the compressed packfile size as well as the time taken to compute the packfile.

Using a collection of repositories that use the beachball tool, I was able to make similar comparisions with dramatic results. While the fluentui repo is public, the others are private so cannot be shared for reproduction. The results are so significant that I find it important to share here:

| Repo     | --name-hash-version=1 | --name-hash-version=2 |
|----------|-----------------------|-----------------------|
| fluentui |               440 MB  |               161 MB  |
| Repo B   |             6,248 MB  |               856 MB  |
| Repo C   |            37,278 MB  |             6,755 MB  |
| Repo D   |           131,204 MB  |             7,463 MB  |

Future changes could include making --name-hash-version implied by a config value or even implied by default during a full repack.

It is important to point out that the name hash value is stored in the .bitmap file format, so we must force --name-hash-version=1 when bitmaps are being read or written. Later, the bitmap format could be updated to be aware of the name hash version so deltas can be quickly computed across the bitmapped/not-bitmapped boundary.

---
 Documentation/git-pack-objects.txt | 32 ++++++++++++++++++-
 builtin/pack-objects.c             | 49 +++++++++++++++++++++++++++---
 builtin/repack.c                   |  1 +
 t/t5300-pack-object.sh             | 31 +++++++++++++++++++
 4 files changed, 107 insertions(+), 6 deletions(-)

index e32404c6aae..7f69ae4855f 100644
@@ -15,7 +15,8 @@ SYNOPSIS
 	[--revs [--unpacked | --all]] [--keep-pack=<pack-name>]
 	[--cruft] [--cruft-expiration=<time>]
 	[--stdout [--filter=<filter-spec>] | <base-name>]
-	[--shallow] [--keep-true-parents] [--[no-]sparse] < <object-list>
+	[--shallow] [--keep-true-parents] [--[no-]sparse]
+	[--name-hash-version=<n>] < <object-list>
 
 
 DESCRIPTION

@@ -345,6 +346,35 @@ raise an error.
 	Restrict delta matches based on "islands". See DELTA ISLANDS
 	below.
 
+--name-hash-version=<n>::
+	While performing delta compression, Git groups objects that may be
+	similar based on heuristics using the path to that object. While
+	grouping objects by an exact path match is good for paths with
+	many versions, there are benefits for finding delta pairs across
+	different full paths. Git collects objects by type and then by a
+	"name hash" of the path and then by size, hoping to group objects
+	that will compress well together.
++
+The default name hash version is `1`, which prioritizes hash locality by
+considering the final bytes of the path as providing the maximum magnitude
+to the hash function. This version excels at distinguishing short paths
+and finding renames across directories. However, the hash function depends
+primarily on the final 16 bytes of the path. If there are many paths in
+the repo that have the same final 16 bytes and differ only by parent
+directory, then this name-hash may lead to too many collisions and cause
+poor results. At the moment, this version is required when writing
+reachability bitmap files with `--write-bitmap-index`.
++
+The name hash version `2` has similar locality features as version `1`,
+except it considers each path component separately and overlays the hashes
+with a shift. This still prioritizes the final bytes of the path, but also
+"salts" the lower bits of the hash using the parent directory names. This
+method allows for some of the locality benefits of version `1` while
+breaking most of the collisions from a similarly-named file appearing in
+many different directories. At the moment, this version is not allowed
+when writing reachability bitmap files with `--write-bitmap-index` and it
+will be automatically changed to version `1`.
+
 
 DELTA ISLANDS
 -------------

index d6bb37e84ae..05e13adb87f 100644
@@ -58,6 +58,7 @@ struct pack_objects_args {
 	int no_reuse_object;
 	int quiet;
 	int local;
+	int full_name_hash;
 	struct list_objects_filter_options filter_options;
 };
 

index 3b9dae331a5..4270eabe8b7 100755
@@ -674,4 +674,35 @@ do
 	'
 done
 
+test_expect_success 'valid and invalid --name-hash-versions' '
+	# Valid values are hard to verify other than "do not fail".
+	# Performance tests will be more valuable to validate these versions.
+	for value in 1 2
+	do
+		git pack-objects base --all --name-hash-version=$value || return 1
+	done &&
+
+	# Invalid values have clear post-conditions.
+	for value in -1 0 3
+	do
+		test_must_fail git pack-objects base --all --name-hash-version=$value 2>err &&
+		test_grep "invalid --name-hash-version option" err || return 1
+	done
+'
+
+# The following test is not necessarily a permanent choice, but since we do not
+# have a "name hash version" bit in the .bitmap file format, we cannot write the
+# hash values into the .bitmap file without risking breakage later.
+#
+# TODO: Make these compatible in the future and replace this test with the
+# expected behavior when both are specified.
+test_expect_success '--name-hash-version=2 and --write-bitmap-index are incompatible' '
+	git pack-objects base --all --name-hash-version=2 --write-bitmap-index 2>err &&
+	test_grep "currently, --write-bitmap-index requires --name-hash-version=1" err &&
+
+	# --stdout option silently removes --write-bitmap-index
+	git pack-objects --stdout --all --name-hash-version=2 --write-bitmap-index >out 2>err &&
+	! test_grep "currently, --write-bitmap-index requires --name-hash-version=1" err
+'
+
 test_done

gitgitgadget

"Derrick Stolee via GitGitGadget" <[email protected]> writes:

[snip]

From: Derrick Stolee <[email protected]>

The new '--name-hash-version' option for 'git repack' is a simple pass-through to the underlying 'git pack-objects' subcommand. However, this subcommand may have other options and a temporary filename as part of the subcommand execution that may not be predictable or could change over time.

The existing test_subcommand method requires an exact list of arguments for the subcommand. This is too rigid for our needs here, so create a new method, test_subcommand_flex. Use it to check that the --name-hash-version option is passing through.

---
 Documentation/git-repack.txt | 34 +++++++++++++++++++++++++++++++++-
 builtin/repack.c             | 10 ++++++++--
 t/t0450/txt-help-mismatches  |  1 -
 t/t7700-repack.sh            |  6 ++++++
 t/test-lib-functions.sh      | 26 ++++++++++++++++++++++++++
 5 files changed, 73 insertions(+), 4 deletions(-)

index c902512a9e8..ea69fbe1891 100644
@@ -9,7 +9,9 @@ git-repack - Pack unpacked objects in a repository
 SYNOPSIS
 --------
 [verse]
-'git repack' [-a] [-A] [-d] [-f] [-F] [-l] [-n] [-q] [-b] [-m] [--window=<n>] [--depth=<n>] [--threads=<n>] [--keep-pack=<pack-name>] [--write-midx]
+'git repack' [-a] [-A] [-d] [-f] [-F] [-l] [-n] [-q] [-b] [-m]
+	[--window=<n>] [--depth=<n>] [--threads=<n>] [--keep-pack=<pack-name>]
+	[--write-midx] [--name-hash-version=<n>]
 
 DESCRIPTION
 -----------

@@ -249,6 +251,36 @@ linkgit:git-multi-pack-index[1]).
 	Write a multi-pack index (see linkgit:git-multi-pack-index[1])
 	containing the non-redundant packs.
 
+--name-hash-version=<n>::
+	While performing delta compression, Git groups objects that may be
+	similar based on heuristics using the path to that object. While
+	grouping objects by an exact path match is good for paths with
+	many versions, there are benefits for finding delta pairs across
+	different full paths. Git collects objects by type and then by a
+	"name hash" of the path and then by size, hoping to group objects
+	that will compress well together.
++
+The default name hash version is `1`, which prioritizes hash locality by
+considering the final bytes of the path as providing the maximum magnitude
+to the hash function. This version excels at distinguishing short paths
+and finding renames across directories. However, the hash function depends
+primarily on the final 16 bytes of the path. If there are many paths in
+the repo that have the same final 16 bytes and differ only by parent
+directory, then this name-hash may lead to too many collisions and cause
+poor results. At the moment, this version is required when writing
+reachability bitmap files with `--write-bitmap-index`.
++
+The name hash version `2` has similar locality features as version `1`,
+except it considers each path component separately and overlays the hashes
+with a shift. This still prioritizes the final bytes of the path, but also
+"salts" the lower bits of the hash using the parent directory names. This
+method allows for some of the locality benefits of version `1` while
+breaking most of the collisions from a similarly-named file appearing in
+many different directories. At the moment, this version is not allowed
+when writing reachability bitmap files with `--write-bitmap-index` and it
+will be automatically changed to version `1`.
+
+
 CONFIGURATION
 -------------
 

index 05e13adb87f..5e7ff919c1a 100644
@@ -39,7 +39,9 @@ static int run_update_server_info = 1;
 static char *packdir, *packtmp_name, *packtmp;
 
 static const char *const git_repack_usage[] = {
-	N_("git repack [<options>]"),
+	N_("git repack [-a] [-A] [-d] [-f] [-F] [-l] [-n] [-q] [-b] [-m]\n"
+	   "[--window=<n>] [--depth=<n>] [--threads=<n>] [--keep-pack=<pack-name>]\n"
+	   "[--write-midx] [--name-hash-version=<n>]"),
 	NULL
 };
 

@@ -58,7 +60,7 @@ struct pack_objects_args {
 	int no_reuse_object;
 	int quiet;
 	int local;
-	int full_name_hash;
+	int name_hash_version;
 	struct list_objects_filter_options filter_options;
 };
 

@@ -307,6 +309,8 @@ static void prepare_pack_objects(struct child_process *cmd,
 		strvec_pushf(&cmd->args, "--no-reuse-delta");
 	if (args->no_reuse_object)
 		strvec_pushf(&cmd->args, "--no-reuse-object");
+	if (args->name_hash_version)
+		strvec_pushf(&cmd->args, "--name-hash-version=%d", args->name_hash_version);
 	if (args->local)
 		strvec_push(&cmd->args,  "--local");
 	if (args->quiet)

@@ -1204,6 +1208,8 @@ int cmd_repack(int argc,
 				N_("pass --no-reuse-delta to git-pack-objects")),
 		OPT_BOOL('F', NULL, &po_args.no_reuse_object,
 				N_("pass --no-reuse-object to git-pack-objects")),
+		OPT_INTEGER(0, "name-hash-version", &po_args.name_hash_version,
+				N_("specify the name hash version to use for grouping similar objects by path")),
 		OPT_NEGBIT('n', NULL, &run_update_server_info,
 				N_("do not run git-update-server-info"), 1),
 		OPT__QUIET(&po_args.quiet, N_("be quiet")),

index 28003f18c92..c4a15fd0cb8 100644
@@ -45,7 +45,6 @@ rebase
 remote
 remote-ext
 remote-fd
-repack
 reset
 restore
 rev-parse

index c4c3d1a15d9..b9a5759e01d 100755
@@ -777,6 +777,12 @@ test_expect_success 'repack -ad cleans up old .tmp-* packs' '
 	test_must_be_empty tmpfiles
 '
 
+test_expect_success '--name-hash-version option passes through to pack-objects' '
+	GIT_TRACE2_EVENT="$(pwd)/hash-trace.txt" \
+		git repack -a --name-hash-version=2 &&
+	test_subcommand_flex git pack-objects --name-hash-version=2 <hash-trace.txt
+'
+
 test_expect_success 'setup for update-server-info' '
 	git init update-server-info &&
 	test_commit -C update-server-info message

index 78e054ab503..af47247f25f 100644
@@ -1886,6 +1886,32 @@ test_subcommand () {
 	fi
 }
 
+# Check that the given subcommand was run with the given set of
+# arguments in order (but with possible extra arguments).
+#
+#	test_subcommand_flex [!] <command> <args>... < <trace>
+#
+# If the first parameter passed is !, this instead checks that
+# the given command was not called.
+#
+test_subcommand_flex () {
+	local negate=
+	if test "$1" = "!"
+	then
+		negate=t
+		shift
+	fi
+
+	local expr="$(printf '"%s".*' "$@")"
+
+	if test -n "$negate"
+	then
+		! grep "\[$expr\]"
+	else
+		grep "\[$expr\]"
+	fi
+}
+
 # Check that the given command was invoked as part of the
 # trace2-format trace on stdin.
 #

gitgitgadget

"Derrick Stolee via GitGitGadget" <[email protected]> writes:

[snip]

From: Derrick Stolee <[email protected]>

Add a new environment variable to opt-in to differen values of the --name-hash-version=<n> option in 'git pack-objects'. This allows for extra testing of the feature without repeating all of the test scenarios. Unlike many GIT_TEST_* variables, we are choosing to not add this to the linux-TEST-vars CI build as that test run is already overloaded. The behavior exposed by this test variable is of low risk and should be sufficient to allow manual testing when an issue arises.

But this option isn't free. There are a few tests that change behavior with the variable enabled.

First, there are a few tests that are very sensitive to certain delta bases being picked. These are both involving the generation of thin bundles and then counting their objects via 'git index-pack --fix-thin' which pulls the delta base into the new packfile. For these tests, disable the option as a decent long-term option.

Second, there are two tests in t5616-partial-clone.sh that I believe are actually broken scenarios. While the client is set up to clone the 'promisor-server' repo via a treeless partial clone filter (tree:0), that filter does not translate to the 'server' repo. Thus, fetching from these repos causes the server to think that the client has all reachable trees and blobs from the commits advertised as 'haves'. This leads the server to providing a thin pack assuming those objects as delta bases. Changing the name-hash algorithm presents new delta bases and thus breaks the expectations of these tests. An alternative could be to set up 'server' as a promisor server with the correct filter enabled. This may also point out more issues with partial clone being set up as a remote-based filtering mechanism and not a repository-wide setting. For now, do the minimal change to make the test work by disabling the test variable.

Third, there are some tests that compare the exact output of a 'git pack-objects' process when using bitmaps. The warning that ignores the --name-hash-version=2 and forces version 1 causes these tests to fail. Disable the environment variable to get around this issue.

---
 builtin/pack-objects.c          |  5 ++++-
 t/README                        |  4 ++++
 t/t5300-pack-object.sh          |  7 +++++--
 t/t5310-pack-bitmaps.sh         |  5 ++++-
 t/t5333-pseudo-merge-bitmaps.sh |  4 ++++
 t/t5510-fetch.sh                |  7 ++++++-
 t/t5616-partial-clone.sh        | 26 ++++++++++++++++++++++++--
 t/t6020-bundle-misc.sh          |  6 +++++-
 t/t7406-submodule-update.sh     |  4 +++-
 t/t7700-repack.sh               | 10 ++++++++--
 10 files changed, 67 insertions(+), 11 deletions(-)

index e36a93a0082..e2f6431d614 100644
@@ -266,7 +266,7 @@ struct configured_exclusion {
 static struct oidmap configured_exclusions;
 
 static struct oidset excluded_by_config;
-static int name_hash_version = 1;
+static int name_hash_version = -1;
 
 static void validate_name_hash_version(void)
 {

@@ -4609,6 +4609,9 @@ int cmd_pack_objects(int argc,
 	if (pack_to_stdout || !rev_list_all)
 		write_bitmap_index = 0;
 
+	if (name_hash_version < 0)
+		name_hash_version = (int)git_env_ulong("GIT_TEST_NAME_HASH_VERSION", 1);
+
 	validate_name_hash_version();
 	if (write_bitmap_index && name_hash_version != 1) {
 		warning(_("currently, --write-bitmap-index requires --name-hash-version=1"));

index 8c0319b58e5..e63d2360852 100644
@@ -492,6 +492,10 @@ a test and then fails then the whole test run will abort. This can help to make
 sure the expected tests are executed and not silently skipped when their
 dependency breaks or is simply not present in a new environment.
 
+GIT_TEST_NAME_HASH_VERSION=<int>, when set, causes 'git pack-objects' to
+assume '--name-hash-version=<n>'.
+
+
 Naming Tests
 ------------
 

index 4270eabe8b7..97fe9e561c6 100755
@@ -675,15 +675,18 @@ do
 done
 
 test_expect_success 'valid and invalid --name-hash-versions' '
+	sane_unset GIT_TEST_NAME_HASH_VERSION &&
+
 	# Valid values are hard to verify other than "do not fail".
 	# Performance tests will be more valuable to validate these versions.
-	for value in 1 2
+	# Negative values are converted to version 1.
+	for value in -1 1 2
 	do
 		git pack-objects base --all --name-hash-version=$value || return 1
 	done &&
 
 	# Invalid values have clear post-conditions.
-	for value in -1 0 3
+	for value in 0 3
 	do
 		test_must_fail git pack-objects base --all --name-hash-version=$value 2>err &&
 		test_grep "invalid --name-hash-version option" err || return 1

index 7044c7d7c6d..c30522b57fd 100755
@@ -420,7 +420,10 @@ test_bitmap_cases () {
 			cat >expect <<-\EOF &&
 			error: missing value for '\''pack.preferbitmaptips'\''
 			EOF
-			git repack -adb 2>actual &&
+
+			# Disable name hash version adjustment due to stderr comparison.
+			GIT_TEST_NAME_HASH_VERSION=1 \
+				git repack -adb 2>actual &&
 			test_cmp expect actual
 		)
 	'

index eca4a1eb8c6..b1553cbaf7f 100755
@@ -209,6 +209,10 @@ test_expect_success 'bitmapPseudoMerge.stableThreshold creates stable groups' '
 '
 
 test_expect_success 'out of order thresholds are rejected' '
+	# Disable this option to avoid stderr message
+	GIT_TEST_NAME_HASH_VERSION=1 &&
+	export GIT_TEST_NAME_HASH_VERSION &&
+
 	test_must_fail git \
 		-c bitmapPseudoMerge.test.pattern="refs/*" \
 		-c bitmapPseudoMerge.test.threshold=1.month.ago \

index 0890b9f61c5..1699c3a3bb8 100755
@@ -1062,7 +1062,12 @@ test_expect_success 'all boundary commits are excluded' '
 	test_tick &&
 	git merge otherside &&
 	ad=$(git log --no-walk --format=%ad HEAD) &&
-	git bundle create twoside-boundary.bdl main --since="$ad" &&
+
+	# If the a different name hash function is used here, then no delta
+	# pair is found and the bundle does not expand to three objects
+	# when fixing the thin object.
+	GIT_TEST_NAME_HASH_VERSION=1 \
+		git bundle create twoside-boundary.bdl main --since="$ad" &&
 	test_bundle_object_count --thin twoside-boundary.bdl 3
 '
 

index c53e93be2f7..9371d2606c6 100755
@@ -516,7 +516,18 @@ test_expect_success 'fetch lazy-fetches only to resolve deltas' '
 	# Exercise to make sure it works. Git will not fetch anything from the
 	# promisor remote other than for the big tree (because it needs to
 	# resolve the delta).
-	GIT_TRACE_PACKET="$(pwd)/trace" git -C client \
+	#
+	# TODO: the --full-name-hash option is disabled here, since this test
+	# is fundamentally broken! When GIT_TEST_NAME_HASH_VERSION=2, the server
+	# recognizes delta bases in a different way and then sends a _blob_ to
+	# the client with a delta base that the client does not have! This is
+	# because the client is cloned from "promisor-server" with tree:0 but
+	# is now fetching from "server" without any filter. This is violating the
+	# promise to the server that all reachable objects exist and could be
+	# used as delta bases!
+	GIT_TRACE_PACKET="$(pwd)/trace" \
+		GIT_TEST_NAME_HASH_VERSION=1 \
+		git -C client \
 		fetch "file://$(pwd)/server" main &&
 
 	# Verify the assumption that the client needed to fetch the delta base

@@ -535,7 +546,18 @@ test_expect_success 'fetch lazy-fetches only to resolve deltas, protocol v2' '
 	# Exercise to make sure it works. Git will not fetch anything from the
 	# promisor remote other than for the big blob (because it needs to
 	# resolve the delta).
-	GIT_TRACE_PACKET="$(pwd)/trace" git -C client \
+	#
+	# TODO: the --full-name-hash option is disabled here, since this test
+	# is fundamentally broken! When GIT_TEST_NAME_HASH_VERSION=2, the server
+	# recognizes delta bases in a different way and then sends a _blob_ to
+	# the client with a delta base that the client does not have! This is
+	# because the client is cloned from "promisor-server" with tree:0 but
+	# is now fetching from "server" without any filter. This is violating the
+	# promise to the server that all reachable objects exist and could be
+	# used as delta bases!
+	GIT_TRACE_PACKET="$(pwd)/trace" \
+		GIT_TEST_NAME_HASH_VERSION=1 \
+		git -C client \
 		fetch "file://$(pwd)/server" main &&
 
 	# Verify that protocol version 2 was used.

index 34b5cd62c20..a1f18ae71f1 100755
@@ -247,7 +247,11 @@ test_expect_success 'create bundle with --since option' '
 	EOF
 	test_cmp expect actual &&
 
-	git bundle create since.bdl \
+	# If a different name hash function is used, then one fewer
+	# delta base is found and this counts a different number
+	# of objects after performing --fix-thin.
+	GIT_TEST_NAME_HASH_VERSION=1 \
+		git bundle create since.bdl \
 		--since "Thu Apr 7 15:27:00 2005 -0700" \
 		--all &&
 

index 0f0c86f9cb2..ebd9941075a 100755
@@ -1094,7 +1094,9 @@ test_expect_success 'submodule update --quiet passes quietness to fetch with a s
 	) &&
 	git clone super4 super5 &&
 	(cd super5 &&
-	 git submodule update --quiet --init --depth=1 submodule3 >out 2>err &&
+	 # This test var can mess with the stderr output checked in this test.
+	 GIT_TEST_NAME_HASH_VERSION=1 \
+		git submodule update --quiet --init --depth=1 submodule3 >out 2>err &&
 	 test_must_be_empty out &&
 	 test_must_be_empty err
 	) &&

index b9a5759e01d..16861f80c9c 100755
@@ -309,7 +309,10 @@ test_expect_success 'no bitmaps created if .keep files present' '
 	keep=${pack%.pack}.keep &&
 	test_when_finished "rm -f \"\$keep\"" &&
 	>"$keep" &&
-	git -C bare.git repack -ad 2>stderr &&
+
+	# Disable --name-hash-version test due to stderr comparison.
+	GIT_TEST_NAME_HASH_VERSION=1 \
+		git -C bare.git repack -ad 2>stderr &&
 	test_must_be_empty stderr &&
 	find bare.git/objects/pack/ -type f -name "*.bitmap" >actual &&
 	test_must_be_empty actual

@@ -320,7 +323,10 @@ test_expect_success 'auto-bitmaps do not complain if unavailable' '
 	blob=$(test-tool genrandom big $((1024*1024)) |
 	       git -C bare.git hash-object -w --stdin) &&
 	git -C bare.git update-ref refs/tags/big $blob &&
-	git -C bare.git repack -ad 2>stderr &&
+
+	# Disable --name-hash-version test due to stderr comparison.
+	GIT_TEST_NAME_HASH_VERSION=1 \
+		git -C bare.git repack -ad 2>stderr &&
 	test_must_be_empty stderr &&
 	find bare.git/objects/pack -type f -name "*.bitmap" >actual &&
 	test_must_be_empty actual

gitgitgadget

s/differen/different

The patch itself looked good to me.

[snip]

I believe the changes to this file are no longer needed.

You're right. They are only needed in the last patch when the v3 name-hash is possible.

(Unless maybe you fixed this issue in 'master' and I didn't see it)

Thanks,
-Stolee

From: Derrick Stolee <[email protected]>

As custom options are added to 'git pack-objects' and 'git repack' to adjust how compression is done, use this new performance test script to demonstrate their effectiveness in performance and size.

The recently-added --name-hash-version option allows for testing different name hash functions. Version 2 intends to preserve some of the locality of version 1 while more often breaking collisions due to long filenames.

Distinguishing objects by more of the path is critical when there are many name hash collisions and several versions of the same path in the full history, giving a significant boost to the full repack case. The locality of the hash function is critical to compressing something like a shallow clone or a thin pack representing a push of a single commit.

This can be seen by running pt5313 on the open source fluentui repository [1]. Most commits will have this kind of output for the thin and big pack cases, though certain commits (such as [2]) will have problematic thin pack size for other reasons.

[1] https://github.com/microsoft/fluentui
[2] a637a06df05360ce5ff21420803f64608226a875

Checked out at the parent of [2], I see the following statistics:

Test HEAD
---------------------------------------------------------------
5313.2: thin pack with version 1 0.37(0.44+0.02)
5313.3: thin pack size with version 1 1.2M
5313.4: big pack with version 1 2.04(7.77+0.23)
5313.5: big pack size with version 1 20.4M
5313.6: shallow fetch pack with version 1 1.41(2.94+0.11)
5313.7: shallow pack size with version 1 34.4M
5313.8: repack with version 1 95.70(676.41+2.87)
5313.9: repack size with version 1 439.3M
5313.10: thin pack with version 2 0.12(0.12+0.06)
5313.11: thin pack size with version 2 22.0K
5313.12: big pack with version 2 2.80(5.43+0.34)
5313.13: big pack size with version 2 25.9M
5313.14: shallow fetch pack with version 2 1.77(2.80+0.19)
5313.15: shallow pack size with version 2 33.7M
5313.16: repack with version 2 33.68(139.52+2.58)
5313.17: repack size with version 2 160.5M

To make comparisons easier, I will reformat this output into a different table style:

| Test         | V1 Time | V2 Time | V1 Size | V2 Size |
|--------------|---------|---------|---------|---------|
| Thin Pack    |  0.37 s |  0.12 s |   1.2 M |  22.0 K |
| Big Pack     |  2.04 s |  2.80 s |  20.4 M |  25.9 M |
| Shallow Pack |  1.41 s |  1.77 s |  34.4 M |  33.7 M |
| Repack       | 95.70 s | 33.68 s | 439.3 M | 160.5 M |

The v2 hash function successfully differentiates the CHANGELOG.md files from each other, which leads to significant improvements in the thin pack (simulating a push of this commit) and the full repack. There is some bloat in the "big pack" scenario and essentially the same results for the shallow pack.

In the case of the Git repository, these numbers show some of the issues with this approach:

| Test         | V1 Time | V2 Time | V1 Size | V2 Size |
|--------------|---------|---------|---------|---------|
| Thin Pack    |  0.02 s |  0.02 s |   1.1 K |   1.1 K |
| Big Pack     |  1.69 s |  1.95 s |  13.5 M |  14.5 M |
| Shallow Pack |  1.26 s |  1.29 s |  12.0 M |  12.2 M |
| Repack       | 29.51 s | 29.01 s | 237.7 M | 238.2 M |

Here, the attempts to remove conflicts in the v2 function seem to cause slight bloat to these sizes. This shows that the Git repository benefits a lot from cross-path delta pairs.

The results are similar with the nodejs/node repo:

| Test         | V1 Time | V2 Time | V1 Size | V2 Size |
|--------------|---------|---------|---------|---------|
| Thin Pack    |  0.02 s |  0.02 s |   1.6 K |   1.6 K |
| Big Pack     |  4.61 s |  3.26 s |  56.0 M |  52.8 M |
| Shallow Pack |  7.82 s |  7.51 s | 104.6 M | 107.0 M |
| Repack       | 88.90 s | 73.75 s | 740.1 M | 764.5 M |

Here, the v2 name-hash causes some size bloat more often than it reduces the size, but it also universally improves performance time, which is an interesting reversal. This must mean that it is helping to short-circuit some delta computations even if it is not finding the most efficient ones. The performance improvement cannot be explained only due to the I/O cost of writing the resulting packfile.

The Linux kernel repository was the initial target of the default name hash value, and its naming conventions are practically build to take the most advantage of the default name hash values:

| Test         | V1 Time  | V2 Time  | V1 Size | V2 Size |
|--------------|----------|----------|---------|---------|
| Thin Pack    |   0.17 s |   0.07 s |   4.6 K |   4.6 K |
| Big Pack     |  17.88 s |  12.35 s | 201.1 M | 159.1 M |
| Shallow Pack |  11.05 s |  22.94 s | 269.2 M | 273.8 M |
| Repack       | 727.39 s | 566.95 s |   2.5 G |   2.5 G |

Here, the thin and big packs gain some performance boosts in time, with a modest gain in the size of the big pack. The shallow pack, however, is more expensive to compute, likely because similarly-named files across different directories are farther apart in the name hash ordering in v2. The repack also gains benefits in computation time but no meaningful change to the full size.

Finally, an internal Javascript repo of moderate size shows significant gains when repacking with --name-hash-version=2 due to it having many name hash collisions. However, it's worth noting that only the full repack case has significant differences from the v1 name hash:

| Test      | V1 Time   | V2 Time  | V1 Size | V2 Size |
|-----------|-----------|----------|---------|---------|
| Thin Pack |    8.28 s |   7.28 s |  16.8 K |  16.8 K |
| Big Pack  |   12.81 s |  11.66 s |  29.1 M |  29.1 M |
| Shallow   |    4.86 s |   4.06 s |  42.5 M |  44.1 M |
| Repack    | 3126.50 s | 496.33 s |   6.2 G | 855.6 M |

---
 t/perf/p5313-pack-objects.sh | 70 ++++++++++++++++++++++++++++++++++++
 1 file changed, 70 insertions(+)
 create mode 100755 t/perf/p5313-pack-objects.sh

new file mode 100755
index 00000000000..be5229a0ecd
@@ -0,0 +1,70 @@
+#!/bin/sh
+
+test_description='Tests pack performance using bitmaps'
+. ./perf-lib.sh
+
+GIT_TEST_PASSING_SANITIZE_LEAK=0
+export GIT_TEST_PASSING_SANITIZE_LEAK
+
+test_perf_large_repo
+
+test_expect_success 'create rev input' '
+	cat >in-thin <<-EOF &&
+	$(git rev-parse HEAD)
+	^$(git rev-parse HEAD~1)
+	EOF
+
+	cat >in-big <<-EOF &&
+	$(git rev-parse HEAD)
+	^$(git rev-parse HEAD~1000)
+	EOF
+
+	cat >in-shallow <<-EOF
+	$(git rev-parse HEAD)
+	--shallow $(git rev-parse HEAD)
+	EOF
+'
+
+for version in 1 2
+do
+	export version
+
+	test_perf "thin pack with version $version" '
+		git pack-objects --thin --stdout --revs --sparse \
+			--name-hash-version=$version <in-thin >out
+	'
+
+	test_size "thin pack size with version $version" '
+		test_file_size out
+	'
+
+	test_perf "big pack with version $version" '
+		git pack-objects --stdout --revs --sparse \
+			--name-hash-version=$version <in-big >out
+	'
+
+	test_size "big pack size with version $version" '
+		test_file_size out
+	'
+
+	test_perf "shallow fetch pack with version $version" '
+		git pack-objects --stdout --revs --sparse --shallow \
+			--name-hash-version=$version <in-shallow >out
+	'
+
+	test_size "shallow pack size with version $version" '
+		test_file_size out
+	'
+
+	test_perf "repack with version $version" '
+		git repack -adf --name-hash-version=$version
+	'
+
+	test_size "repack size with version $version" '
+		gitdir=$(git rev-parse --git-dir) &&
+		pack=$(ls $gitdir/objects/pack/pack-*.pack) &&
+		test_file_size "$pack"
+	'
+done
+
+test_done

gitgitgadget

From: Derrick Stolee <[email protected]>

Add a new test-tool helper, name-hash, to output the value of the name-hash algorithms for the input list of strings, one per line.

Since the name-hash values can be stored in the .bitmap files, it is important that these hash functions do not change across Git versions. Add a simple test to t5310-pack-bitmaps.sh to provide some testing of the current values. Due to how these functions are implemented, it would be difficult to change them without disturbing these values. The paths used for this test are carefully selected to demonstrate some of the behavior differences of the two current name hash versions, including which conditions will cause them to collide.

Create a performance test that uses test_size to demonstrate how collisions occur for these hash algorithms. This test helps inform someone as to the behavior of the name-hash algorithms for their repo based on the paths at HEAD.

My copy of the Git repository shows modest statistics around the collisions of the default name-hash algorithm:

Test this tree
--------------------------------------------------
5314.1: paths at head 4.5K
5314.2: distinct hash value: v1 4.1K
5314.3: maximum multiplicity: v1 13
5314.4: distinct hash value: v2 4.2K
5314.5: maximum multiplicity: v2 9

Here, the maximum collision multiplicity is 13, but around 10% of paths have a collision with another path.

In a more interesting example, the microsoft/fluentui [1] repo had these statistics at time of committing:

Test this tree
--------------------------------------------------
5314.1: paths at head 19.5K
5314.2: distinct hash value: v1 8.2K
5314.3: maximum multiplicity: v1 279
5314.4: distinct hash value: v2 17.8K
5314.5: maximum multiplicity: v2 44

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

That demonstrates that of the nearly twenty thousand path names, they are assigned around eight thousand distinct values. 279 paths are assigned to a single value, leading the packing algorithm to sort objects from those paths together, by size.

With the v2 name hash function, the maximum multiplicity lowers to 44, leaving some room for further improvement.

In a more extreme example, an internal monorepo had a much worse collision rate:

Test this tree
--------------------------------------------------
5314.1: paths at head 227.3K
5314.2: distinct hash value: v1 72.3K
5314.3: maximum multiplicity: v1 14.4K
5314.4: distinct hash value: v2 166.5K
5314.5: maximum multiplicity: v2 138

Here, we can see that the v2 name hash function provides somem improvements, but there are still a number of collisions that could lead to repacking problems at this scale.

---
 Makefile                  |  1 +
 t/helper/test-name-hash.c | 23 +++++++++++++++++++++++
 t/helper/test-tool.c      |  1 +
 t/helper/test-tool.h      |  1 +
 t/perf/p5314-name-hash.sh | 31 +++++++++++++++++++++++++++++++
 t/t5310-pack-bitmaps.sh   | 30 ++++++++++++++++++++++++++++++
 6 files changed, 87 insertions(+)
 create mode 100644 t/helper/test-name-hash.c
 create mode 100755 t/perf/p5314-name-hash.sh

index 6f5986b66ea..65403f6dd09 100644
@@ -816,6 +816,7 @@ TEST_BUILTINS_OBJS += test-lazy-init-name-hash.o
 TEST_BUILTINS_OBJS += test-match-trees.o
 TEST_BUILTINS_OBJS += test-mergesort.o
 TEST_BUILTINS_OBJS += test-mktemp.o
+TEST_BUILTINS_OBJS += test-name-hash.o
 TEST_BUILTINS_OBJS += test-online-cpus.o
 TEST_BUILTINS_OBJS += test-pack-mtimes.o
 TEST_BUILTINS_OBJS += test-parse-options.o

new file mode 100644
index 00000000000..5b402362020
@@ -0,0 +1,23 @@
+/*
+ * test-name-hash.c: Read a list of paths over stdin and report on their
+ * name-hash and full name-hash.
+ */
+
+#include "test-tool.h"
+#include "git-compat-util.h"
+#include "pack-objects.h"
+#include "strbuf.h"
+
+int cmd__name_hash(int argc UNUSED, const char **argv UNUSED)
+{
+	struct strbuf line = STRBUF_INIT;
+
+	while (!strbuf_getline(&line, stdin)) {
+		printf("%10u ", pack_name_hash(line.buf));
+		printf("%10u ", pack_name_hash_v2(line.buf));
+		printf("%s\n", line.buf);
+	}
+
+	strbuf_release(&line);
+	return 0;
+}