From fc62e033cd93ff6b93e312d89bfb5683a4c6f90c Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Mon, 27 Jan 2025 19:02:29 +0000 Subject: pack-objects: add --name-hash-version option 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= 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. To promote the safety of this parameter, the validate_name_hash_version() method will die() if the given name-hash version is incorrect and will disable newer versions if not yet compatible with other features, such as --write-bitmap-index. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- t/t5300-pack-object.sh | 31 +++++++++++++++++++++++++++++++ 1 file changed, 31 insertions(+) (limited to 't') diff --git a/t/t5300-pack-object.sh b/t/t5300-pack-object.sh index 3b9dae331a..4270eabe8b 100755 --- a/t/t5300-pack-object.sh +++ b/t/t5300-pack-object.sh @@ -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 -- cgit v1.3-5-g9baa From 928ef41dd879a1e12373842e865477e9e1167621 Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Mon, 27 Jan 2025 19:02:30 +0000 Subject: repack: add --name-hash-version option 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. Since we are modifying the 'git repack' command, let's bring its usage in line with the Documentation's synopsis. This removes it from the allow list in t0450 so it will remain in sync in the future. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- Documentation/git-repack.txt | 9 ++++++++- builtin/repack.c | 9 ++++++++- t/t0450/txt-help-mismatches | 1 - t/t7700-repack.sh | 6 ++++++ t/test-lib-functions.sh | 26 ++++++++++++++++++++++++++ 5 files changed, 48 insertions(+), 3 deletions(-) (limited to 't') diff --git a/Documentation/git-repack.txt b/Documentation/git-repack.txt index c902512a9e..5852a5c973 100644 --- a/Documentation/git-repack.txt +++ b/Documentation/git-repack.txt @@ -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=] [--depth=] [--threads=] [--keep-pack=] [--write-midx] +'git repack' [-a] [-A] [-d] [-f] [-F] [-l] [-n] [-q] [-b] [-m] + [--window=] [--depth=] [--threads=] [--keep-pack=] + [--write-midx] [--name-hash-version=] DESCRIPTION ----------- @@ -249,6 +251,11 @@ 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=:: + Provide this argument to the underlying `git pack-objects` process. + See linkgit:git-pack-objects[1] for full details. + + CONFIGURATION ------------- diff --git a/builtin/repack.c b/builtin/repack.c index d6bb37e84a..5e7ff919c1 100644 --- a/builtin/repack.c +++ b/builtin/repack.c @@ -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 []"), + N_("git repack [-a] [-A] [-d] [-f] [-F] [-l] [-n] [-q] [-b] [-m]\n" + "[--window=] [--depth=] [--threads=] [--keep-pack=]\n" + "[--write-midx] [--name-hash-version=]"), NULL }; @@ -58,6 +60,7 @@ struct pack_objects_args { int no_reuse_object; int quiet; int local; + int name_hash_version; struct list_objects_filter_options filter_options; }; @@ -306,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) @@ -1203,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")), diff --git a/t/t0450/txt-help-mismatches b/t/t0450/txt-help-mismatches index 28003f18c9..c4a15fd0cb 100644 --- a/t/t0450/txt-help-mismatches +++ b/t/t0450/txt-help-mismatches @@ -45,7 +45,6 @@ rebase remote remote-ext remote-fd -repack reset restore rev-parse diff --git a/t/t7700-repack.sh b/t/t7700-repack.sh index c4c3d1a15d..b9a5759e01 100755 --- a/t/t7700-repack.sh +++ b/t/t7700-repack.sh @@ -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 ... < +# +# 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. # -- cgit v1.3-5-g9baa From ce961135ccf5bc008b8160404cc7c995789b942e Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Mon, 27 Jan 2025 19:02:31 +0000 Subject: pack-objects: add GIT_TEST_NAME_HASH_VERSION Add a new environment variable to opt-in to different values of the --name-hash-version= 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 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. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- 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 | 3 ++- t/t5510-fetch.sh | 7 ++++++- t/t6020-bundle-misc.sh | 6 +++++- t/t7406-submodule-update.sh | 4 +++- t/t7700-repack.sh | 10 ++++++++-- 9 files changed, 41 insertions(+), 10 deletions(-) (limited to 't') diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c index d0c717e9d0..8ae77deb92 100644 --- a/builtin/pack-objects.c +++ b/builtin/pack-objects.c @@ -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; /** * Check whether the name_hash_version chosen by user input is appropriate, @@ -4616,6 +4616,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 (use_delta_islands) diff --git a/t/README b/t/README index 8c0319b58e..e63d236085 100644 --- a/t/README +++ b/t/README @@ -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=, when set, causes 'git pack-objects' to +assume '--name-hash-version='. + + Naming Tests ------------ diff --git a/t/t5300-pack-object.sh b/t/t5300-pack-object.sh index 4270eabe8b..97fe9e561c 100755 --- a/t/t5300-pack-object.sh +++ b/t/t5300-pack-object.sh @@ -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 diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh index 7044c7d7c6..c30522b57f 100755 --- a/t/t5310-pack-bitmaps.sh +++ b/t/t5310-pack-bitmaps.sh @@ -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 ) ' diff --git a/t/t5333-pseudo-merge-bitmaps.sh b/t/t5333-pseudo-merge-bitmaps.sh index eca4a1eb8c..971f9d2d4e 100755 --- a/t/t5333-pseudo-merge-bitmaps.sh +++ b/t/t5333-pseudo-merge-bitmaps.sh @@ -209,7 +209,8 @@ test_expect_success 'bitmapPseudoMerge.stableThreshold creates stable groups' ' ' test_expect_success 'out of order thresholds are rejected' ' - test_must_fail git \ + # Disable the test var to remove a stderr message. + test_must_fail env GIT_TEST_NAME_HASH_VERSION=1 git \ -c bitmapPseudoMerge.test.pattern="refs/*" \ -c bitmapPseudoMerge.test.threshold=1.month.ago \ -c bitmapPseudoMerge.test.stableThreshold=1.week.ago \ diff --git a/t/t5510-fetch.sh b/t/t5510-fetch.sh index 0890b9f61c..1699c3a3bb 100755 --- a/t/t5510-fetch.sh +++ b/t/t5510-fetch.sh @@ -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 ' diff --git a/t/t6020-bundle-misc.sh b/t/t6020-bundle-misc.sh index 34b5cd62c2..a1f18ae71f 100755 --- a/t/t6020-bundle-misc.sh +++ b/t/t6020-bundle-misc.sh @@ -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 && diff --git a/t/t7406-submodule-update.sh b/t/t7406-submodule-update.sh index 0f0c86f9cb..ebd9941075 100755 --- a/t/t7406-submodule-update.sh +++ b/t/t7406-submodule-update.sh @@ -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 ) && diff --git a/t/t7700-repack.sh b/t/t7700-repack.sh index b9a5759e01..16861f80c9 100755 --- a/t/t7700-repack.sh +++ b/t/t7700-repack.sh @@ -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 -- cgit v1.3-5-g9baa From 30696be71f64ca3764b1d334927da927d6d8df78 Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Mon, 27 Jan 2025 19:02:32 +0000 Subject: p5313: add size comparison test 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 | Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- t/perf/p5313-pack-objects.sh | 70 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 70 insertions(+) create mode 100755 t/perf/p5313-pack-objects.sh (limited to 't') diff --git a/t/perf/p5313-pack-objects.sh b/t/perf/p5313-pack-objects.sh new file mode 100755 index 0000000000..be5229a0ec --- /dev/null +++ b/t/perf/p5313-pack-objects.sh @@ -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 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 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 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 -- cgit v1.3-5-g9baa From 7f9870794f743922aff6caa24e1991d5600b1b8a Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Mon, 27 Jan 2025 19:02:33 +0000 Subject: test-tool: add helper for name-hash values 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. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- 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 (limited to 't') diff --git a/Makefile b/Makefile index 6f5986b66e..65403f6dd0 100644 --- a/Makefile +++ b/Makefile @@ -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 diff --git a/t/helper/test-name-hash.c b/t/helper/test-name-hash.c new file mode 100644 index 0000000000..af1d52de10 --- /dev/null +++ b/t/helper/test-name-hash.c @@ -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((unsigned const char *)line.buf)); + printf("%s\n", line.buf); + } + + strbuf_release(&line); + return 0; +} diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c index 1ebb69a5dc..e794058ab6 100644 --- a/t/helper/test-tool.c +++ b/t/helper/test-tool.c @@ -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 }, diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h index 21802ac27d..26ff30a5a9 100644 --- a/t/helper/test-tool.h +++ b/t/helper/test-tool.h @@ -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); diff --git a/t/perf/p5314-name-hash.sh b/t/perf/p5314-name-hash.sh new file mode 100755 index 0000000000..4ef0ba7711 --- /dev/null +++ b/t/perf/p5314-name-hash.sh @@ -0,0 +1,31 @@ +#!/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_size 'paths at head' ' + git ls-tree -r --name-only HEAD >path-list && + wc -l name-hashes +' + +for version in 1 2 +do + test_size "distinct hash value: v$version" ' + awk "{ print \$$version; }" name-hash-count && + wc -l names <<-\EOF && + first + second + third + 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 out && + + cat >expect <<-\EOF && + 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 +' + test_bitmap_cases () { writeLookupTable=false for i in "$@" -- cgit v1.3-5-g9baa