{"thread":{"id":"62085","subject":"[PATCH 0/4] pack-objects: create new name-hash algorithm","startedAt":"2024-09-09T13:56:55Z","lastAt":"2024-10-08T18:32:49Z","messageCount":38,"participants":["Derrick Stolee via GitGitGadget","Derrick Stolee","Junio C Hamano","Taylor Blau","Jeff King","Patrick Steinhardt"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"502442","messageId":"pull.1785.git.1725890210.gitgitgadget@gmail.com","threadId":"62085","inReplyTo":null,"subject":"[PATCH 0/4] pack-objects: create new name-hash algorithm","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-09T13:56:46Z","receivedAt":"2024-09-09T13:56:55Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"I've been focused recently on understanding and mitigating the growth of a\nfew internal repositories. Some of these are growing much larger than\nexpected for the number of contributors, and there are multiple aspects to\nwhy this growth is so large.\n\nI will be submitting an RFC with my deep dive into the many aspects of this\nissue, but the very last thing I discovered in this space is actually the\neasiest change to make.\n\nThe main issue plaguing these repositories is that deltas are not being\ncomputed against objects that appear at the same path. While the size of\nthese files at tip is one aspect of growth that would prevent this issue,\nthe changes to these files are reasonable and should result in good delta\ncompression. However, Git is not discovering the connections across\ndifferent versions of the same file.\n\nOne way to find some improvement in these repositories is to increase the\nwindow size, which was an initial indicator that the delta compression could\nbe improved, but was not a clear indicator. After some digging (and\nprototyping some analysis tools) the main discovery was that the current\nname-hash algorithm only considers the last 16 characters in the path name\nand has some naturally-occurring collisions within that scope.\n\nThis series introduces a new name-hash algorithm, but does not replace the\nexisting one. There are cases, such as packing a single snapshot of a\nrepository, where the existing algorithm outperforms the new one.\n\nHowever, my findings show that when a repository has many versions of files\nat the same path (and especially when there are many name-hash collisions)\nthen there are significant gains to be made using the new algorithm.\n\nRepo Standard Repack With --full-name-hash fluentui 438 MB 168 MB Repo B\n6,255 MB 829 MB Repo C 37,737 MB 7,125 MB Repo D 130,049 MB 6,190 MB\n\nThe main change in this series is in patch 1, which adds the algorithm and\nthe option to 'git pack-objects' and 'git repack'. The remaining patches are\nfocused on creating more evidence around the value of the new name-hash\nalgorithm and its effects on the packfiles created with it.\n\nI will also try to make clear that I've been focused on client-side\nperformance and size concerns. I do not know if using this option will have\nissues with advanced server-side repacking features, such as delta islands,\nreachability bitmaps, or serving clones and fetches from the resulting\npackfile. My educated guess is that the name-hash value does not affect\nthese features in any direct way, but I'll leave the testing of the server\nscenarios to the experts.\n\nThanks, -Stolee\n\nDerrick Stolee (4):\n  pack-objects: add --full-name-hash option\n  git-repack: update usage to match docs\n  p5313: add size comparison test\n  p5314: add a size test for name-hash collisions\n\n Documentation/git-pack-objects.txt |  3 +-\n Documentation/git-repack.txt       |  4 +-\n Makefile                           |  1 +\n builtin/pack-objects.c             | 20 ++++++---\n builtin/repack.c                   |  9 +++-\n pack-objects.h                     | 20 +++++++++\n t/helper/test-name-hash.c          | 23 ++++++++++\n t/helper/test-tool.c               |  1 +\n t/helper/test-tool.h               |  1 +\n t/perf/p5313-pack-objects.sh       | 71 ++++++++++++++++++++++++++++++\n t/perf/p5314-name-hash.sh          | 41 +++++++++++++++++\n t/t0450/txt-help-mismatches        |  1 -\n 12 files changed, 186 insertions(+), 9 deletions(-)\n create mode 100644 t/helper/test-name-hash.c\n create mode 100755 t/perf/p5313-pack-objects.sh\n create mode 100755 t/perf/p5314-name-hash.sh\n\n\nbase-commit: 4c42d5ff284067fa32837421408bebfef996bf81\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1785%2Fderrickstolee%2Ffull-name-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1785/derrickstolee/full-name-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/1785\n-- \ngitgitgadget\n"},{"id":"502443","messageId":"ff30f774ca82662bb25291804559bf3f2de061c2.1725890211.git.gitgitgadget@gmail.com","threadId":"62085","inReplyTo":"pull.1785.git.1725890210.gitgitgadget@gmail.com","subject":"[PATCH 1/4] pack-objects: add --full-name-hash option","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-09T13:56:47Z","receivedAt":"2024-09-09T13:56:55Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee <stolee@gmail.com>\n\nThe pack_name_hash() method has not been materially changed since it was\nintroduced in ce0bd64299a (pack-objects: improve path grouping\nheuristics., 2006-06-05). The intention here is to group objects by path\nname, but also attempt to group similar file types together by making\nthe most-significant digits of the hash be focused on the final\ncharacters.\n\nHere's the crux of the implementation:\n\n\t/*\n\t * This effectively just creates a sortable number from the\n\t * last sixteen non-whitespace characters. Last characters\n\t * count \"most\", so things that end in \".c\" sort together.\n\t */\n\twhile ((c = *name++) != 0) {\n\t\tif (isspace(c))\n\t\t\tcontinue;\n\t\thash = (hash >> 2) + (c << 24);\n\t}\n\nAs the comment mentions, this only cares about the last sixteen\nnon-whitespace characters. This cause some filenames to collide more\nthan others. Here are some examples that I've seen while investigating\nrepositories that are growing more than they should be:\n\n * \"/CHANGELOG.json\" is 15 characters, and is created by the beachball\n   [1] tool. Only the final character of the parent directory can\n   differntiate different versions of this file, but also only the two\n   most-significant digits. If that character is a letter, then this is\n   always a collision. Similar issues occur with the similar\n   \"/CHANGELOG.md\" path, though there is more opportunity for\n   differences in the parent directory.\n\n * Localization files frequently have common filenames but differentiate\n   via parent directories. In C#, the name \"/strings.resx.lcl\" is used\n   for these localization files and they will all collide in name-hash.\n\n[1] https://github.com/microsoft/beachball\n\nI've come across many other examples where some internal tool uses a\ncommon name across multiple directories and is causing Git to repack\npoorly due to name-hash collisions.\n\nIt is clear that the existing name-hash algorithm is optimized for\nrepositories with short path names, but also is optimized for packing a\nsingle snapshot of a repository, not a repository with many versions of\nthe same file. In my testing, this has proven out where the name-hash\nalgorithm does a good job of finding peer files as delta bases when\nunable to use a historical version of that exact file.\n\nHowever, for repositories that have many versions of most files and\ndirectories, it is more important that the objects that appear at the\nsame path are grouped together.\n\nCreate a new pack_full_name_hash() method and a new --full-name-hash\noption for 'git pack-objects' to call that method instead. Add a simple\npass-through for 'git repack --full-name-hash' for additional testing in\nthe context of a full repack, where I expect this will be most\neffective.\n\nThe hash algorithm is as simple as possible to be reasonably effective:\nfor each character of the path string, add a multiple of that character\nand a large prime number (chosen arbitrarily, but intended to be large\nrelative to the size of a uint32_t). Then, shift the current hash value\nto the right by 5, with overlap. The addition and shift parameters are\nstandard mechanisms for creating hard-to-predict behaviors in the bits\nof the resulting hash.\n\nThis is not meant to be cryptographic at all, but uniformly distributed\nacross the possible hash values. This creates a hash that appears\npseudorandom. There is no ability to consider similar file types as\nbeing close to each other.\n\nIn a later change, a test-tool will be added so the effectiveness of\nthis hash can be demonstrated directly.\n\nFor now, let's consider how effective this mechanism is when repacking a\nrepository with and without the --full-name-hash option. Specifically,\nlet's use 'git repack -adf [--full-name-hash]' as our test.\n\nOn the Git repository, we do not expect much difference. All path names\nare short. This is backed by our results:\n\n| Stage                 | Pack Size | Repack Time |\n|-----------------------|-----------|-------------|\n| After clone           | 260 MB    | N/A         |\n| Standard Repack       | 127MB     | 106s        |\n| With --full-name-hash | 126 MB    | 99s         |\n\nThis example demonstrates how there is some natural overhead coming from\nthe cloned copy because the server is hosting many forks and has not\noptimized for exactly this set of reachable objects. But the full repack\nhas similar characteristics with and without --full-name-hash.\n\nHowever, we can test this in a repository that uses one of the\nproblematic naming conventions above. The fluentui [2] repo uses\nbeachball to generate CHANGELOG.json and CHANGELOG.md files, and these\nfiles have very poor delta characteristics when comparing against\nversions across parent directories.\n\n| Stage                 | Pack Size | Repack Time |\n|-----------------------|-----------|-------------|\n| After clone           | 694 MB    | N/A         |\n| Standard Repack       | 438 MB    | 728s        |\n| With --full-name-hash | 168 MB    | 142s        |\n\n[2] https://github.com/microsoft/fluentui\n\nIn this example, we see significant gains in the compressed packfile\nsize as well as the time taken to compute the packfile.\n\nUsing a collection of repositories that use the beachball tool, I was\nable to make similar comparisions with dramatic results. While the\nfluentui repo is public, the others are private so cannot be shared for\nreproduction. The results are so significant that I find it important to\nshare here:\n\n| Repo     | Standard Repack | With --full-name-hash |\n|----------|-----------------|-----------------------|\n| fluentui |         438 MB  |               168 MB  |\n| Repo B   |       6,255 MB  |               829 MB  |\n| Repo C   |      37,737 MB  |             7,125 MB  |\n| Repo D   |     130,049 MB  |             6,190 MB  |\n\nFuture changes could include making --full-name-hash implied by a config\nvalue or even implied by default during a full repack.\n\nSigned-off-by: Derrick Stolee <stolee@gmail.com>\n---\n Documentation/git-pack-objects.txt |  3 ++-\n builtin/pack-objects.c             | 20 +++++++++++++++-----\n builtin/repack.c                   |  5 +++++\n pack-objects.h                     | 20 ++++++++++++++++++++\n 4 files changed, 42 insertions(+), 6 deletions(-)\n\ndiff --git a/Documentation/git-pack-objects.txt b/Documentation/git-pack-objects.txt\nindex e32404c6aae..93861d9f85b 100644\n--- a/Documentation/git-pack-objects.txt\n+++ b/Documentation/git-pack-objects.txt\n@@ -15,7 +15,8 @@ SYNOPSIS\n \t[--revs [--unpacked | --all]] [--keep-pack=<pack-name>]\n \t[--cruft] [--cruft-expiration=<time>]\n \t[--stdout [--filter=<filter-spec>] | <base-name>]\n-\t[--shallow] [--keep-true-parents] [--[no-]sparse] < <object-list>\n+\t[--shallow] [--keep-true-parents] [--[no-]sparse]\n+\t[--full-name-hash] < <object-list>\n \n \n DESCRIPTION\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 778be80f564..2a89666d89f 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -266,6 +266,14 @@ struct configured_exclusion {\n static struct oidmap configured_exclusions;\n \n static struct oidset excluded_by_config;\n+static int use_full_name_hash;\n+\n+static inline uint32_t pack_name_hash_fn(const char *name)\n+{\n+\tif (use_full_name_hash)\n+\t\treturn pack_full_name_hash(name);\n+\treturn pack_name_hash(name);\n+}\n \n /*\n  * stats\n@@ -1670,7 +1678,7 @@ static int add_object_entry(const struct object_id *oid, enum object_type type,\n \t\treturn 0;\n \t}\n \n-\tcreate_object_entry(oid, type, pack_name_hash(name),\n+\tcreate_object_entry(oid, type, pack_name_hash_fn(name),\n \t\t\t    exclude, name && no_try_delta(name),\n \t\t\t    found_pack, found_offset);\n \treturn 1;\n@@ -1884,7 +1892,7 @@ static void add_preferred_base_object(const char *name)\n {\n \tstruct pbase_tree *it;\n \tsize_t cmplen;\n-\tunsigned hash = pack_name_hash(name);\n+\tunsigned hash = pack_name_hash_fn(name);\n \n \tif (!num_preferred_base || check_pbase_path(hash))\n \t\treturn;\n@@ -3394,7 +3402,7 @@ static void show_object_pack_hint(struct object *object, const char *name,\n \t * here using a now in order to perhaps improve the delta selection\n \t * process.\n \t */\n-\toe->hash = pack_name_hash(name);\n+\toe->hash = pack_name_hash_fn(name);\n \toe->no_try_delta = name && no_try_delta(name);\n \n \tstdin_packs_hints_nr++;\n@@ -3544,7 +3552,7 @@ static void add_cruft_object_entry(const struct object_id *oid, enum object_type\n \tentry = packlist_find(&to_pack, oid);\n \tif (entry) {\n \t\tif (name) {\n-\t\t\tentry->hash = pack_name_hash(name);\n+\t\t\tentry->hash = pack_name_hash_fn(name);\n \t\t\tentry->no_try_delta = no_try_delta(name);\n \t\t}\n \t} else {\n@@ -3567,7 +3575,7 @@ static void add_cruft_object_entry(const struct object_id *oid, enum object_type\n \t\t\treturn;\n \t\t}\n \n-\t\tentry = create_object_entry(oid, type, pack_name_hash(name),\n+\t\tentry = create_object_entry(oid, type, pack_name_hash_fn(name),\n \t\t\t\t\t    0, name && no_try_delta(name),\n \t\t\t\t\t    pack, offset);\n \t}\n@@ -4398,6 +4406,8 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\tOPT_STRING_LIST(0, \"uri-protocol\", &uri_protocols,\n \t\t\t\tN_(\"protocol\"),\n \t\t\t\tN_(\"exclude any configured uploadpack.blobpackfileuri with this protocol\")),\n+\t\tOPT_BOOL(0, \"full-name-hash\", &use_full_name_hash,\n+\t\t\t N_(\"optimize delta compression across identical path names over time\")),\n \t\tOPT_END(),\n \t};\n \ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex 8bb875532b4..87d0cd4d2f2 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -57,6 +57,7 @@ struct pack_objects_args {\n \tint no_reuse_object;\n \tint quiet;\n \tint local;\n+\tint full_name_hash;\n \tstruct list_objects_filter_options filter_options;\n };\n \n@@ -288,6 +289,8 @@ static void prepare_pack_objects(struct child_process *cmd,\n \t\tstrvec_pushf(&cmd->args, \"--no-reuse-delta\");\n \tif (args->no_reuse_object)\n \t\tstrvec_pushf(&cmd->args, \"--no-reuse-object\");\n+\tif (args->full_name_hash)\n+\t\tstrvec_pushf(&cmd->args, \"--full-name-hash\");\n \tif (args->local)\n \t\tstrvec_push(&cmd->args,  \"--local\");\n \tif (args->quiet)\n@@ -1176,6 +1179,8 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \t\t\t\tN_(\"pass --no-reuse-delta to git-pack-objects\")),\n \t\tOPT_BOOL('F', NULL, &po_args.no_reuse_object,\n \t\t\t\tN_(\"pass --no-reuse-object to git-pack-objects\")),\n+\t\tOPT_BOOL(0, \"full-name-hash\", &po_args.full_name_hash,\n+\t\t\t\tN_(\"pass --full-name-hash to git-pack-objects\")),\n \t\tOPT_NEGBIT('n', NULL, &run_update_server_info,\n \t\t\t\tN_(\"do not run git-update-server-info\"), 1),\n \t\tOPT__QUIET(&po_args.quiet, N_(\"be quiet\")),\ndiff --git a/pack-objects.h b/pack-objects.h\nindex b9898a4e64b..50097552d03 100644\n--- a/pack-objects.h\n+++ b/pack-objects.h\n@@ -207,6 +207,26 @@ static inline uint32_t pack_name_hash(const char *name)\n \treturn hash;\n }\n \n+static inline uint32_t pack_full_name_hash(const char *name)\n+{\n+\tconst uint32_t bigp = 1234572167U;\n+\tuint32_t c, hash = bigp;\n+\n+\tif (!name)\n+\t\treturn 0;\n+\n+\t/*\n+\t * Just do the dumbest thing possible: add random multiples of a\n+\t * large prime number with a binary shift. Goal is not cryptographic,\n+\t * but generally uniformly distributed.\n+\t */\n+\twhile ((c = *name++) != 0) {\n+\t\thash += c * bigp;\n+\t\thash = (hash >> 5) | (hash << 27);\n+\t}\n+\treturn hash;\n+}\n+\n static inline enum object_type oe_type(const struct object_entry *e)\n {\n \treturn e->type_valid ? e->type_ : OBJ_BAD;\n-- \ngitgitgadget\n\n"},{"id":"502444","messageId":"eb0aa5f4e94647c12c595964ca1fe1c2020f0642.1725890211.git.gitgitgadget@gmail.com","threadId":"62085","inReplyTo":"pull.1785.git.1725890210.gitgitgadget@gmail.com","subject":"[PATCH 2/4] git-repack: update usage to match docs","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-09T13:56:48Z","receivedAt":"2024-09-09T13:56:56Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee <stolee@gmail.com>\n\nThis also adds the '--full-name-hash' option introduced in the previous\nchange and adds newlines to the synopsis.\n\nSigned-off-by: Derrick Stolee <stolee@gmail.com>\n---\n Documentation/git-repack.txt | 4 +++-\n builtin/repack.c             | 4 +++-\n t/t0450/txt-help-mismatches  | 1 -\n 3 files changed, 6 insertions(+), 3 deletions(-)\n\ndiff --git a/Documentation/git-repack.txt b/Documentation/git-repack.txt\nindex c902512a9e8..457a793fa89 100644\n--- a/Documentation/git-repack.txt\n+++ b/Documentation/git-repack.txt\n@@ -9,7 +9,9 @@ git-repack - Pack unpacked objects in a repository\n SYNOPSIS\n --------\n [verse]\n-'git repack' [-a] [-A] [-d] [-f] [-F] [-l] [-n] [-q] [-b] [-m] [--window=<n>] [--depth=<n>] [--threads=<n>] [--keep-pack=<pack-name>] [--write-midx]\n+'git repack' [-a] [-A] [-d] [-f] [-F] [-l] [-n] [-q] [-b] [-m]\n+\t[--window=<n>] [--depth=<n>] [--threads=<n>] [--keep-pack=<pack-name>]\n+\t[--write-midx] [--full-name-hash]\n \n DESCRIPTION\n -----------\ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex 87d0cd4d2f2..4fa2c25246d 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -38,7 +38,9 @@ static int run_update_server_info = 1;\n static char *packdir, *packtmp_name, *packtmp;\n \n static const char *const git_repack_usage[] = {\n-\tN_(\"git repack [<options>]\"),\n+\tN_(\"git repack [-a] [-A] [-d] [-f] [-F] [-l] [-n] [-q] [-b] [-m]\\n\"\n+\t   \"[--window=<n>] [--depth=<n>] [--threads=<n>] [--keep-pack=<pack-name>]\\n\"\n+\t   \"[--write-midx] [--full-name-hash]\"),\n \tNULL\n };\n \ndiff --git a/t/t0450/txt-help-mismatches b/t/t0450/txt-help-mismatches\nindex 28003f18c92..c4a15fd0cb8 100644\n--- a/t/t0450/txt-help-mismatches\n+++ b/t/t0450/txt-help-mismatches\n@@ -45,7 +45,6 @@ rebase\n remote\n remote-ext\n remote-fd\n-repack\n reset\n restore\n rev-parse\n-- \ngitgitgadget\n\n"},{"id":"502446","messageId":"ed3ea4281a909edac8623734283ef9c87548ec62.1725890211.git.gitgitgadget@gmail.com","threadId":"62085","inReplyTo":"pull.1785.git.1725890210.gitgitgadget@gmail.com","subject":"[PATCH 3/4] p5313: add size comparison test","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-09T13:56:49Z","receivedAt":"2024-09-09T13:56:56Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee <stolee@gmail.com>\n\nAs custom options are added to 'git pack-objects' and 'git repack' to\nadjust how compression is done, use this new performance test script to\ndemonstrate their effectiveness in performance and size.\n\nThe recently-added --full-name-hash option swaps the default name-hash\nalgorithm with one that attempts to uniformly distribute the hashes\nbased on the full path name instead of the last 16 characters.\n\nThis has a dramatic effect on full repacks for repositories with many\nversions of most paths. It can have a negative impact on cases such as\npushing a single change.\n\nThis can be seen by running pt5313 on the open source fluentui\nrepository [1]. Most commits will have this kind of output for the thin\nand big pack cases, though certain commits (such as [2]) will have\nproblematic thin pack size for other reasons.\n\n[1] https://github.com/microsoft/fluentui\n[2] a637a06df05360ce5ff21420803f64608226a875\n\nChecked out at the parent of [2], I see the following statistics:\n\nTest                                           this tree\n------------------------------------------------------------------\n5313.2: thin pack                              0.02(0.01+0.01)\n5313.3: thin pack size                                    1.1K\n5313.4: thin pack with --full-name-hash        0.02(0.01+0.00)\n5313.5: thin pack size with --full-name-hash              3.0K\n5313.6: big pack                               1.65(3.35+0.24)\n5313.7: big pack size                                    58.0M\n5313.8: big pack with --full-name-hash         1.53(2.52+0.18)\n5313.9: big pack size with --full-name-hash              57.6M\n5313.10: repack                                176.52(706.60+3.53)\n5313.11: repack size                                    446.7K\n5313.12: repack with --full-name-hash          37.47(134.18+3.06)\n5313.13: repack size with --full-name-hash              183.1K\n\nNote that this demonstrates a 3x size _increase_ in the case that\nsimulates a small \"git push\". The size change is neutral on the case of\npushing the difference between HEAD and HEAD~1000.\n\nHowever, the full repack case is both faster and more efficient.\n\nSigned-off-by: Derrick Stolee <stolee@gmail.com>\n---\n t/perf/p5313-pack-objects.sh | 71 ++++++++++++++++++++++++++++++++++++\n 1 file changed, 71 insertions(+)\n create mode 100755 t/perf/p5313-pack-objects.sh\n\ndiff --git a/t/perf/p5313-pack-objects.sh b/t/perf/p5313-pack-objects.sh\nnew file mode 100755\nindex 00000000000..88ea0a4698a\n--- /dev/null\n+++ b/t/perf/p5313-pack-objects.sh\n@@ -0,0 +1,71 @@\n+#!/bin/sh\n+\n+test_description='Tests pack performance using bitmaps'\n+. ./perf-lib.sh\n+\n+GIT_TEST_PASSING_SANITIZE_LEAK=0\n+export GIT_TEST_PASSING_SANITIZE_LEAK\n+\n+test_perf_large_repo\n+\n+test_expect_success 'create rev input' '\n+\tcat >in-thin <<-EOF &&\n+\t$(git rev-parse HEAD)\n+\t^$(git rev-parse HEAD~1)\n+\tEOF\n+\n+\tcat >in-big <<-EOF\n+\t$(git rev-parse HEAD)\n+\t^$(git rev-parse HEAD~1000)\n+\tEOF\n+'\n+\n+test_perf 'thin pack' '\n+\tgit pack-objects --thin --stdout --revs --sparse  <in-thin >out\n+'\n+\n+test_size 'thin pack size' '\n+\twc -c <out\n+'\n+\n+test_perf 'thin pack with --full-name-hash' '\n+\tgit pack-objects --thin --stdout --revs --sparse --full-name-hash <in-thin >out\n+'\n+\n+test_size 'thin pack size with --full-name-hash' '\n+\twc -c <out\n+'\n+\n+test_perf 'big pack' '\n+\tgit pack-objects --stdout --revs --sparse  <in-big >out\n+'\n+\n+test_size 'big pack size' '\n+\twc -c <out\n+'\n+\n+test_perf 'big pack with --full-name-hash' '\n+\tgit pack-objects --stdout --revs --sparse --full-name-hash <in-big >out\n+'\n+\n+test_size 'big pack size with --full-name-hash' '\n+\twc -c <out\n+'\n+\n+test_perf 'repack' '\n+\tgit repack -adf\n+'\n+\n+test_size 'repack size' '\n+\tdu -a .git/objects/pack | sort -nr | awk \"{ print \\$1; }\" | head -n 1\n+'\n+\n+test_perf 'repack with --full-name-hash' '\n+\tgit repack -adf --full-name-hash\n+'\n+\n+test_size 'repack size with --full-name-hash' '\n+\tdu -a .git/objects/pack | sort -nr | awk \"{ print \\$1; }\" | head -n 1\n+'\n+\n+test_done\n-- \ngitgitgadget\n\n"},{"id":"502445","messageId":"5bcbcce66650e0a4addabcc86fe834a6c9b1761c.1725890211.git.gitgitgadget@gmail.com","threadId":"62085","inReplyTo":"pull.1785.git.1725890210.gitgitgadget@gmail.com","subject":"[PATCH 4/4] p5314: add a size test for name-hash collisions","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-09T13:56:50Z","receivedAt":"2024-09-09T13:56:57Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee <stolee@gmail.com>\n\nAdd a new test-tool helper, name-hash, to output the value of the\nname-hash algorithms for the input list of strings, one per line.\n\nCreate a performance test that uses test_size to demonstrate how\ncollisions occur for these hash algorithms. This test helps inform\nsomeone as to the behavior of the name-hash algorithms for their repo\nbased on the paths at HEAD.\n\nMy copy of the Git repository shows modest statistics around the\ncollisions of the default name-hash algorithm:\n\nTest                                              this tree\n-----------------------------------------------------------------\n5314.1: paths at head                                        4.5K\n5314.2: number of distinct name-hashes                       4.1K\n5314.3: number of distinct full-name-hashes                  4.5K\n5314.4: maximum multiplicity of name-hashes                    13\n5314.5: maximum multiplicity of fullname-hashes                 1\n\nHere, the maximum collision multiplicity is 13, but around 10% of paths\nhave a collision with another path.\n\nIn a more interesting example, the microsoft/fluentui [1] repo had these\nstatistics at time of committing:\n\nTest                                              this tree\n-----------------------------------------------------------------\n5314.1: paths at head                                       19.6K\n5314.2: number of distinct name-hashes                       8.2K\n5314.3: number of distinct full-name-hashes                 19.6K\n5314.4: maximum multiplicity of name-hashes                   279\n5314.5: maximum multiplicity of fullname-hashes                 1\n\n[1] https://github.com/microsoft/fluentui\n\nThat demonstrates that of the nearly twenty thousand path names, they\nare assigned around eight thousand distinct values. 279 paths are\nassigned to a single value, leading the packing algorithm to sort\nobjects from those paths together, by size.\n\nIn this repository, no collisions occur for the full-name-hash\nalgorithm.\n\nIn a more extreme example, an internal monorepo had a much worse\ncollision rate:\n\nTest                                              this tree\n-----------------------------------------------------------------\n5314.1: paths at head                                      221.6K\n5314.2: number of distinct name-hashes                      72.0K\n5314.3: number of distinct full-name-hashes                221.6K\n5314.4: maximum multiplicity of name-hashes                 14.4K\n5314.5: maximum multiplicity of fullname-hashes                 2\n\nEven in this repository with many more paths at HEAD, the collision rate\nwas low and the maximum number of paths being grouped into a single\nbucket by the full-path-name algorithm was two.\n\nSigned-off-by: Derrick Stolee <stolee@gmail.com>\n---\n Makefile                  |  1 +\n t/helper/test-name-hash.c | 23 ++++++++++++++++++++++\n t/helper/test-tool.c      |  1 +\n t/helper/test-tool.h      |  1 +\n t/perf/p5314-name-hash.sh | 41 +++++++++++++++++++++++++++++++++++++++\n 5 files changed, 67 insertions(+)\n create mode 100644 t/helper/test-name-hash.c\n create mode 100755 t/perf/p5314-name-hash.sh\n\ndiff --git a/Makefile b/Makefile\nindex 91f65d7dc57..a5ce284cf4a 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -812,6 +812,7 @@ TEST_BUILTINS_OBJS += test-lazy-init-name-hash.o\n TEST_BUILTINS_OBJS += test-match-trees.o\n TEST_BUILTINS_OBJS += test-mergesort.o\n TEST_BUILTINS_OBJS += test-mktemp.o\n+TEST_BUILTINS_OBJS += test-name-hash.o\n TEST_BUILTINS_OBJS += test-oid-array.o\n TEST_BUILTINS_OBJS += test-online-cpus.o\n TEST_BUILTINS_OBJS += test-pack-mtimes.o\ndiff --git a/t/helper/test-name-hash.c b/t/helper/test-name-hash.c\nnew file mode 100644\nindex 00000000000..15fb8f853c1\n--- /dev/null\n+++ b/t/helper/test-name-hash.c\n@@ -0,0 +1,23 @@\n+/*\n+ * test-name-hash.c: Read a list of paths over stdin and report on their\n+ * name-hash and full name-hash.\n+ */\n+\n+#include \"test-tool.h\"\n+#include \"git-compat-util.h\"\n+#include \"pack-objects.h\"\n+#include \"strbuf.h\"\n+\n+int cmd__name_hash(int argc UNUSED, const char **argv UNUSED)\n+{\n+\tstruct strbuf line = STRBUF_INIT;\n+\n+\twhile (!strbuf_getline(&line, stdin)) {\n+\t\tuint32_t name_hash = pack_name_hash(line.buf);\n+\t\tuint32_t full_hash = pack_full_name_hash(line.buf);\n+\n+\t\tprintf(\"%10\"PRIu32\"\\t%10\"PRIu32\"\\t%s\\n\", name_hash, full_hash, line.buf);\n+\t}\n+\n+\treturn 0;\n+}\ndiff --git a/t/helper/test-tool.c b/t/helper/test-tool.c\nindex f8a67df7de9..4a603921002 100644\n--- a/t/helper/test-tool.c\n+++ b/t/helper/test-tool.c\n@@ -43,6 +43,7 @@ static struct test_cmd cmds[] = {\n \t{ \"match-trees\", cmd__match_trees },\n \t{ \"mergesort\", cmd__mergesort },\n \t{ \"mktemp\", cmd__mktemp },\n+\t{ \"name-hash\", cmd__name_hash },\n \t{ \"oid-array\", cmd__oid_array },\n \t{ \"online-cpus\", cmd__online_cpus },\n \t{ \"pack-mtimes\", cmd__pack_mtimes },\ndiff --git a/t/helper/test-tool.h b/t/helper/test-tool.h\nindex e74bc0ffd41..56a83bf3aac 100644\n--- a/t/helper/test-tool.h\n+++ b/t/helper/test-tool.h\n@@ -37,6 +37,7 @@ int cmd__lazy_init_name_hash(int argc, const char **argv);\n int cmd__match_trees(int argc, const char **argv);\n int cmd__mergesort(int argc, const char **argv);\n int cmd__mktemp(int argc, const char **argv);\n+int cmd__name_hash(int argc, const char **argv);\n int cmd__online_cpus(int argc, const char **argv);\n int cmd__pack_mtimes(int argc, const char **argv);\n int cmd__parse_options(int argc, const char **argv);\ndiff --git a/t/perf/p5314-name-hash.sh b/t/perf/p5314-name-hash.sh\nnew file mode 100755\nindex 00000000000..9fe26612fac\n--- /dev/null\n+++ b/t/perf/p5314-name-hash.sh\n@@ -0,0 +1,41 @@\n+#!/bin/sh\n+\n+test_description='Tests pack performance using bitmaps'\n+. ./perf-lib.sh\n+\n+GIT_TEST_PASSING_SANITIZE_LEAK=0\n+export GIT_TEST_PASSING_SANITIZE_LEAK\n+\n+test_perf_large_repo\n+\n+test_size 'paths at head' '\n+\tgit ls-tree -r --name-only HEAD >path-list &&\n+\twc -l <path-list\n+'\n+\n+test_size 'number of distinct name-hashes' '\n+\tcat path-list | test-tool name-hash >name-hashes &&\n+\tcat name-hashes | awk \"{ print \\$1; }\" | sort -n | uniq -c >name-hash-count &&\n+\twc -l <name-hash-count\n+'\n+\n+test_size 'number of distinct full-name-hashes' '\n+\tcat name-hashes | awk \"{ print \\$2; }\" | sort -n | uniq -c >full-name-hash-count &&\n+\twc -l <full-name-hash-count\n+'\n+\n+test_size 'maximum multiplicity of name-hashes' '\n+\tcat name-hash-count | \\\n+\t\tsort -nr | \\\n+\t\thead -n 1 | \\\n+\t\tawk \"{ print \\$1; }\"\n+'\n+\n+test_size 'maximum multiplicity of fullname-hashes' '\n+\tcat full-name-hash-count | \\\n+\t\tsort -nr | \\\n+\t\thead -n 1 | \\\n+\t\tawk \"{ print \\$1; }\"\n+'\n+\n+test_done\n-- \ngitgitgadget\n"},{"id":"502462","messageId":"86acb6f7-f1cd-499e-b95c-6cad4ff93863@gmail.com","threadId":"62085","inReplyTo":"pull.1785.git.1725890210.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/4] pack-objects: create new name-hash algorithm","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-09-09T16:07:53Z","receivedAt":"2024-09-09T16:07:56Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 9/9/24 9:56 AM, Derrick Stolee via GitGitGadget wrote:\n\n> However, my findings show that when a repository has many versions of files\n> at the same path (and especially when there are many name-hash collisions)\n> then there are significant gains to be made using the new algorithm.\n\nOf course this table didn't render correctly. Here's a readable version:\n\n| Repo     | Standard Repack | With --full-name-hash |\n|----------|-----------------|-----------------------|\n| fluentui |         438 MB  |               168 MB  |\n| Repo B   |       6,255 MB  |               829 MB  |\n| Repo C   |      37,737 MB  |             7,125 MB  |\n| Repo D   |     130,049 MB  |             6,190 MB  |\n\nThanks,\n-Stolee\n\n"},{"id":"502465","messageId":"xmqqed5ssots.fsf@gitster.g","threadId":"62085","inReplyTo":"ff30f774ca82662bb25291804559bf3f2de061c2.1725890211.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/4] pack-objects: add --full-name-hash option","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-09-09T17:45:51Z","receivedAt":"2024-09-09T17:45:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n> This is not meant to be cryptographic at all, but uniformly distributed\n> across the possible hash values. This creates a hash that appears\n> pseudorandom. There is no ability to consider similar file types as\n> being close to each other.\n\nAnother consideration we had when designing the current mechanism,\nwhich is more important than \"compare .c files with each other\", is\nto handle the case where a file is moved across directory boundary\nwithout changing its name.  These \"hash collissions\" are meant to be\na part of obtaining _good_ paring of blobs that ought to be similar\nto each other.  In other words, we wanted them to collide so that we\ndo not have to be negatively affected by moves.\n\nI am not saying that we should not update the pack name hash; I am\njust saying that \"consider similar file types\" as if that is the\nmost important aspect of the current hash, is misleading.\n\nThanks.\n\n\n\n"},{"id":"502466","messageId":"xmqqa5ggsoou.fsf@gitster.g","threadId":"62085","inReplyTo":"eb0aa5f4e94647c12c595964ca1fe1c2020f0642.1725890211.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 2/4] git-repack: update usage to match docs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-09-09T17:48:49Z","receivedAt":"2024-09-09T17:48:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n> diff --git a/t/t0450/txt-help-mismatches b/t/t0450/txt-help-mismatches\n> index 28003f18c92..c4a15fd0cb8 100644\n> --- a/t/t0450/txt-help-mismatches\n> +++ b/t/t0450/txt-help-mismatches\n> @@ -45,7 +45,6 @@ rebase\n>  remote\n>  remote-ext\n>  remote-fd\n> -repack\n>  reset\n>  restore\n>  rev-parse\n\nThis is very much appreciated ;-)\n"},{"id":"502467","messageId":"xmqqjzfkr9b0.fsf@gitster.g","threadId":"62085","inReplyTo":"pull.1785.git.1725890210.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/4] pack-objects: create new name-hash algorithm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-09-09T18:06:27Z","receivedAt":"2024-09-09T18:06:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n> One way to find some improvement in these repositories is to increase the\n> window size, which was an initial indicator that the delta compression could\n> be improved, but was not a clear indicator. After some digging (and\n> prototyping some analysis tools) the main discovery was that the current\n> name-hash algorithm only considers the last 16 characters in the path name\n> and has some naturally-occurring collisions within that scope.\n\nYes, as I explained in the other message, this \"collision\" is an\nintegral part of the design to allow us gather candidates together\nthat may yield good deltas among them.  In addition, header files\nwhose names end with \".h\" tend to share a bit comment at the\nbeginning of them in many projects, and the proximity (not\n\"collision\") of the hash value is used to make them delta candidates\nwith each other.\n\nI do agree that considering files at the same path from different\n(but close-by) revisions as the prime candidates is very important,\nbut if you spread the \"collissions\" very thin by using \"uniform\ndistribution\", I am afraid that you'd end up discarding anything but\nthe blobs at the same path, which may go too far.  Having name hash\nvalue that are close by no longer has any meaning in such a system.\n\nI hope you can find a solution that strikes a good balance at the\nend of the series (I saw only the first step), but I suspect an easy\nway to avoid the downsides you observed is to use both.  Compare\nwith a handful of blobs taken from nearby commits (the original\nobject order is roughly in traversal order, and you can take\nadvantage of that fact) from exactly the same path (using your\n\"uniform distribution\") before comparing with the blobs with close\nvalue (of the current function) like the current implementation\ndoes, may go a long way.\n\n"},{"id":"502523","messageId":"7d7b9c30-c95a-4dcd-a5d7-1fca5ddb99e7@gmail.com","threadId":"62085","inReplyTo":"xmqqed5ssots.fsf@gitster.g","subject":"Re: [PATCH 1/4] pack-objects: add --full-name-hash option","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-09-10T02:31:36Z","receivedAt":"2024-09-10T02:31:39Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 9/9/24 1:45 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n> \n>> This is not meant to be cryptographic at all, but uniformly distributed\n>> across the possible hash values. This creates a hash that appears\n>> pseudorandom. There is no ability to consider similar file types as\n>> being close to each other.\n> \n> Another consideration we had when designing the current mechanism,\n> which is more important than \"compare .c files with each other\", is\n> to handle the case where a file is moved across directory boundary\n> without changing its name.  These \"hash collissions\" are meant to be\n> a part of obtaining _good_ paring of blobs that ought to be similar\n> to each other.  In other words, we wanted them to collide so that we\n> do not have to be negatively affected by moves.\n> \n> I am not saying that we should not update the pack name hash; I am\n> just saying that \"consider similar file types\" as if that is the\n> most important aspect of the current hash, is misleading.\n\nThank you for this extra aspect, which has clarified some of my\nthinking and I will use in future versions.\n\nThanks,\n-Stolee\n\n"},{"id":"502524","messageId":"0e6dde0f-63e2-4db3-9225-9a8ca5e78eb3@gmail.com","threadId":"62085","inReplyTo":"xmqqjzfkr9b0.fsf@gitster.g","subject":"Re: [PATCH 0/4] pack-objects: create new name-hash algorithm","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-09-10T02:37:30Z","receivedAt":"2024-09-10T02:37:33Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 9/9/24 2:06 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n> \n>> One way to find some improvement in these repositories is to increase the\n>> window size, which was an initial indicator that the delta compression could\n>> be improved, but was not a clear indicator. After some digging (and\n>> prototyping some analysis tools) the main discovery was that the current\n>> name-hash algorithm only considers the last 16 characters in the path name\n>> and has some naturally-occurring collisions within that scope.\n> \n> Yes, as I explained in the other message, this \"collision\" is an\n> integral part of the design to allow us gather candidates together\n> that may yield good deltas among them.  In addition, header files\n> whose names end with \".h\" tend to share a bit comment at the\n> beginning of them in many projects, and the proximity (not\n> \"collision\") of the hash value is used to make them delta candidates\n> with each other.\n> \n> I do agree that considering files at the same path from different\n> (but close-by) revisions as the prime candidates is very important,\n> but if you spread the \"collissions\" very thin by using \"uniform\n> distribution\", I am afraid that you'd end up discarding anything but\n> the blobs at the same path, which may go too far.  Having name hash\n> value that are close by no longer has any meaning in such a system.\n\nYou are right that some \"nearby\" paths are lost in this change, and\nthis can be measured by trying to use this option in the pack-objects\nprocess underneath a small 'git push'.\n\nThe thing that surprised me is just how effective this is for the\ncreation of large pack-files that include many versions of most\nfiles. The cross-path deltas have less of an effect here, and the\nbenefits of avoiding name-hash collisions can be overwhelming in\nmany cases.\n\n> I hope you can find a solution that strikes a good balance at the\n> end of the series (I saw only the first step), but I suspect an easy\n> way to avoid the downsides you observed is to use both.  Compare\n> with a handful of blobs taken from nearby commits (the original\n> object order is roughly in traversal order, and you can take\n> advantage of that fact) from exactly the same path (using your\n> \"uniform distribution\") before comparing with the blobs with close\n> value (of the current function) like the current implementation\n> does, may go a long way.\n\nFunny you should say that, since the RFC I finally submitted [1]\nactually does just that. The --path-walk option changes the object\nwalk to consider batches of objects based on their path, computes\ndeltas among that batch, and then does the normal name-hash pass\nlater. This seems to really strike the balance that you are\nlooking for and solves the issues where small pushes need to stay\nsmall. It also fixes some problematic cases even when pushing a\nsingle commit.\n\n[1] https://lore.kernel.org/git/pull.1786.git.1725935335.gitgitgadget@gmail.com/\n\nHowever, the --path-walk option requires significant implementation\nof a \"path walk API\" and my RFC doesn't even do threading right.\nThe --path-walk version (probably) doesn't work with delta islands\nor other features the same way as the drop-in change to the name-\nhash heuristic can. For that reason, I think there is likely some\nlong-term value to the --full-name-hash option even though the\n--path-walk option will be better in many cases.\n\nThanks,\n-Stolee\n\n"},{"id":"502561","messageId":"ZuBeHh7uCfhq2XBB@nand.local","threadId":"62085","inReplyTo":"0e6dde0f-63e2-4db3-9225-9a8ca5e78eb3@gmail.com","subject":"Re: [PATCH 0/4] pack-objects: create new name-hash algorithm","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-09-10T14:56:30Z","receivedAt":"2024-09-10T14:56:32Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, Sep 09, 2024 at 10:37:30PM -0400, Derrick Stolee wrote:\n> > I do agree that considering files at the same path from different\n> > (but close-by) revisions as the prime candidates is very important,\n> > but if you spread the \"collissions\" very thin by using \"uniform\n> > distribution\", I am afraid that you'd end up discarding anything but\n> > the blobs at the same path, which may go too far.  Having name hash\n> > value that are close by no longer has any meaning in such a system.\n>\n> You are right that some \"nearby\" paths are lost in this change, and\n> this can be measured by trying to use this option in the pack-objects\n> process underneath a small 'git push'.\n>\n> The thing that surprised me is just how effective this is for the\n> creation of large pack-files that include many versions of most\n> files. The cross-path deltas have less of an effect here, and the\n> benefits of avoiding name-hash collisions can be overwhelming in\n> many cases.\n\nI think that Junio's suggestion is pretty interesting (though please\ntake my comments here with a grain of salt, since I haven't read the\nother series yet, and am not sure how much of this is redundant).\n\nImagine computing both the full and existing name-hash values for each\nblob/tree in the pack. Then objects would be sorted in the delta\nselection window by similar full-name hash and similar regular name hash\nvalues.\n\nI'm not sure which value you'd actually record in the pack, though.\nIdeally there is a hash function which captures some information about\nthe full path as well as the final path component, so we could use a\nsingle value here, though I suspect the implementation would be more\ncomplicated than what is presented here.\n\n> > I hope you can find a solution that strikes a good balance at the\n> > end of the series (I saw only the first step), but I suspect an easy\n> > way to avoid the downsides you observed is to use both.  Compare\n> > with a handful of blobs taken from nearby commits (the original\n> > object order is roughly in traversal order, and you can take\n> > advantage of that fact) from exactly the same path (using your\n> > \"uniform distribution\") before comparing with the blobs with close\n> > value (of the current function) like the current implementation\n> > does, may go a long way.\n>\n> Funny you should say that, since the RFC I finally submitted [1]\n> actually does just that. The --path-walk option changes the object\n> walk to consider batches of objects based on their path, computes\n> deltas among that batch, and then does the normal name-hash pass\n> later. This seems to really strike the balance that you are\n> looking for and solves the issues where small pushes need to stay\n> small. It also fixes some problematic cases even when pushing a\n> single commit.\n\nInteresting.\n\n> [1] https://lore.kernel.org/git/pull.1786.git.1725935335.gitgitgadget@gmail.com/\n\n> However, the --path-walk option requires significant implementation\n> of a \"path walk API\" and my RFC doesn't even do threading right.\n> The --path-walk version (probably) doesn't work with delta islands\n> or other features the same way as the drop-in change to the name-\n> hash heuristic can. For that reason, I think there is likely some\n> long-term value to the --full-name-hash option even though the\n> --path-walk option will be better in many cases.\n\nI suspect that this is going to be a significant sticking point. Not\nsupporting multi-threading is work-able for GitHub (since we set\npack.threads=1 today), but lacking support for delta-islands makes this\na non-starter to run at GitHub.\n\nDo you imagine that the --path-walk option could be made to work with\ndelta islands? I'm not all that worried about who does that work, but\nmore interested at this point in whether or not it's even possible to\nimplement.\n\nThanks,\nTaylor\n"},{"id":"502565","messageId":"xmqq4j6nlcfy.fsf@gitster.g","threadId":"62085","inReplyTo":"0e6dde0f-63e2-4db3-9225-9a8ca5e78eb3@gmail.com","subject":"Re: [PATCH 0/4] pack-objects: create new name-hash algorithm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-09-10T16:07:29Z","receivedAt":"2024-09-10T16:07:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee <stolee@gmail.com> writes:\n\n> The thing that surprised me is just how effective this is for the\n> creation of large pack-files that include many versions of most\n> files. The cross-path deltas have less of an effect here, and the\n> benefits of avoiding name-hash collisions can be overwhelming in\n> many cases.\n\nYes, \"make sure we notice a file F moving from directory A to B\" is\ninherently optimized for short span of history, i.e. a smallish push\nrather than a whole history clone, where the definition of\n\"smallish\" is that even if you create optimal delta chains, the\nlength of these delta chains will not exceed the \"--depth\" option.\n\nIf the history you are pushing modified A/F twice, renamed it to B/F\n(with or without modification at the same time), then modified B/F\ntwice more, you'd want to pack the 5-commit segment and having to\nartificially cut the delta chain that can contain all of these 5\nblobs into two at the renaming commit is a huge loss.\n\nCompared to that, a whole history clone is a very different story,\nas we will have to chomp delta chains at some depth anyway.  Before\nthe rename, it is reasonable to assume that A/F have evolved\nincrementally for number of revisions, and after that rename it is\nexpected B/F will evolve incrementally for number of revisions\nbefore it gets renamed again.  It is just the matter of choosing\nwhere in that long stretch of content evolution we would cut the\ndelta chain, and the commit that renamed the path may just be a\ngood, if not absolute optimal, point.\n\nSo I do agree that this is an important case to optimize for.  At\nsome point, even when taking only the blobs at the same path as\ndelta base candidates, your true best base may be outside of the\n--window in the list of candidates (sorted by size in decreasing\norder), but at that point you would be increasing window to find\nbetter delta base, not to skip unrelated blobs that happened to have\nthrown into the same hash bucket due to the design that optimizes\nfor different case, so we can say that it is worth spending the\nextra cycle and memory, if you need a larger window to gain even\nbetter packing result.\n\n> Funny you should say that, since the RFC I finally submitted [1]\n> actually does just that. The --path-walk option changes the object\n> walk to consider batches of objects based on their path, computes\n> deltas among that batch, and then does the normal name-hash pass\n> later. This seems to really strike the balance that you are\n> looking for and solves the issues where small pushes need to stay\n> small. It also fixes some problematic cases even when pushing a\n> single commit.\n\n;-).\n"},{"id":"502587","messageId":"xmqqikv3dz5l.fsf@gitster.g","threadId":"62085","inReplyTo":"xmqq4j6nlcfy.fsf@gitster.g","subject":"Re: [PATCH 0/4] pack-objects: create new name-hash algorithm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-09-10T20:36:22Z","receivedAt":"2024-09-10T20:36:26Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Derrick Stolee <stolee@gmail.com> writes:\n>\n>> The thing that surprised me is just how effective this is for the\n>> creation of large pack-files that include many versions of most\n>> files. The cross-path deltas have less of an effect here, and the\n>> benefits of avoiding name-hash collisions can be overwhelming in\n>> many cases.\n>\n> Yes, \"make sure we notice a file F moving from directory A to B\" is\n> inherently optimized for short span of history, i.e. a smallish push\n> rather than a whole history clone, where the definition of\n> \"smallish\" is that even if you create optimal delta chains, the\n> length of these delta chains will not exceed the \"--depth\" option.\n>\n> If the history you are pushing modified A/F twice, renamed it to B/F\n> (with or without modification at the same time), then modified B/F\n> twice more, you'd want to pack the 5-commit segment and having to\n> artificially cut the delta chain that can contain all of these 5\n> blobs into two at the renaming commit is a huge loss.\n\nWhich actually leads me to suspect that we probably do not even have\nto expose the --full-name-hash option to the end users in \"git repack\".\n\nIf we are doing incremental that would fit within the depth setting,\nit is likely that we would be better off without the full-name-hash\noptimization, and if we are doing \"repack -a\" for the whole\nrepository, especially with \"-f\", it would make sense to do the\nfull-name-hash optimization.\n\nIf we can tell how large a chunk of history we are packing before we\nactually start calling builtin/pack-objects.c:add_object_entry(), we\nprobably should be able to even select between with and without\nfull-name-hash automatically, but I do not think we know the object\ncount before we finish calling add_object_entry(), so unless we are\nwilling to compute and keep both while reading and pick between the\ntwo after we finish reading the list of objects, or something, it\nwill require a major surgery to do so, I am afraid.\n\n"},{"id":"502598","messageId":"81139d84-b428-4019-bbd1-cda3206d2d68@gmail.com","threadId":"62085","inReplyTo":"ZuBeHh7uCfhq2XBB@nand.local","subject":"Re: [PATCH 0/4] pack-objects: create new name-hash algorithm","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-09-10T21:05:09Z","receivedAt":"2024-09-10T21:05:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 9/10/24 10:56 AM, Taylor Blau wrote:\n> On Mon, Sep 09, 2024 at 10:37:30PM -0400, Derrick Stolee wrote:\n>>> I do agree that considering files at the same path from different\n>>> (but close-by) revisions as the prime candidates is very important,\n>>> but if you spread the \"collissions\" very thin by using \"uniform\n>>> distribution\", I am afraid that you'd end up discarding anything but\n>>> the blobs at the same path, which may go too far.  Having name hash\n>>> value that are close by no longer has any meaning in such a system.\n>>\n>> You are right that some \"nearby\" paths are lost in this change, and\n>> this can be measured by trying to use this option in the pack-objects\n>> process underneath a small 'git push'.\n>>\n>> The thing that surprised me is just how effective this is for the\n>> creation of large pack-files that include many versions of most\n>> files. The cross-path deltas have less of an effect here, and the\n>> benefits of avoiding name-hash collisions can be overwhelming in\n>> many cases.\n> \n> I think that Junio's suggestion is pretty interesting (though please\n> take my comments here with a grain of salt, since I haven't read the\n> other series yet, and am not sure how much of this is redundant).\n> \n> Imagine computing both the full and existing name-hash values for each\n> blob/tree in the pack. Then objects would be sorted in the delta\n> selection window by similar full-name hash and similar regular name hash\n> values.\n> \n> I'm not sure which value you'd actually record in the pack, though.\n> Ideally there is a hash function which captures some information about\n> the full path as well as the final path component, so we could use a\n> single value here, though I suspect the implementation would be more\n> complicated than what is presented here.\n\nIs the name hash stored in the pack itself? I know that it is stored\nin the 'struct object_entry' data in the packing data. While we could\nadd another uint32_t into that struct to store both hash values, this\nwould increase the memory requirements of repacking by four bytes per\nobject. The struct seemed to be very clear about trying as hard as\npossible to avoid doing that.\n\nBut maybe an alternative could be replacing that 32-bit number with\nan index into an array of paths that have their hash values stored\nthere.\n\nThis would still involve two passes, but might still be possible. I'll\nthink on this.\n\n>>> I hope you can find a solution that strikes a good balance at the\n>>> end of the series (I saw only the first step), but I suspect an easy\n>>> way to avoid the downsides you observed is to use both.  Compare\n>>> with a handful of blobs taken from nearby commits (the original\n>>> object order is roughly in traversal order, and you can take\n>>> advantage of that fact) from exactly the same path (using your\n>>> \"uniform distribution\") before comparing with the blobs with close\n>>> value (of the current function) like the current implementation\n>>> does, may go a long way.\n>>\n>> Funny you should say that, since the RFC I finally submitted [1]\n>> actually does just that. The --path-walk option changes the object\n>> walk to consider batches of objects based on their path, computes\n>> deltas among that batch, and then does the normal name-hash pass\n>> later. This seems to really strike the balance that you are\n>> looking for and solves the issues where small pushes need to stay\n>> small. It also fixes some problematic cases even when pushing a\n>> single commit.\n> \n> Interesting.\n> \n>> [1] https://lore.kernel.org/git/pull.1786.git.1725935335.gitgitgadget@gmail.com/\n> \n>> However, the --path-walk option requires significant implementation\n>> of a \"path walk API\" and my RFC doesn't even do threading right.\n>> The --path-walk version (probably) doesn't work with delta islands\n>> or other features the same way as the drop-in change to the name-\n>> hash heuristic can. For that reason, I think there is likely some\n>> long-term value to the --full-name-hash option even though the\n>> --path-walk option will be better in many cases.\n> \n> I suspect that this is going to be a significant sticking point. Not\n> supporting multi-threading is work-able for GitHub (since we set\n> pack.threads=1 today), but lacking support for delta-islands makes this\n> a non-starter to run at GitHub.\n> \n> Do you imagine that the --path-walk option could be made to work with\n> delta islands? I'm not all that worried about who does that work, but\n> more interested at this point in whether or not it's even possible to\n> implement.\nThis is part of the reason why I think the --full-name-hash option is\nan interesting consideration. It doesn't have any obvious reason why\nit couldn't work with features like delta islands, so it may provide\nsome quick wins in \"large enough\" repositories, or at least \"large in\nthe right way\".\n\nI unfortunately don't know enough about how the delta islands feature\nworks to be confident in the possibility of integrating it with the\n--path-walk option. At minimum, it would require two object walks:\nthe first would mark the objects and the second would do the delta\ncompression with those markings in mind.\n\nBut if there is a way to combine both approaches with a two-pass\ndelta compression technique, then this may be all avoided. I'll give\nit a try.\n\nThanks,\n-Stolee\n"},{"id":"502599","messageId":"1fe607db-04eb-4a6b-a523-9e18397f2d16@gmail.com","threadId":"62085","inReplyTo":"xmqqikv3dz5l.fsf@gitster.g","subject":"Re: [PATCH 0/4] pack-objects: create new name-hash algorithm","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-09-10T21:09:22Z","receivedAt":"2024-09-10T21:09:26Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 9/10/24 4:36 PM, Junio C Hamano wrote:\n> Junio C Hamano <gitster@pobox.com> writes:\n> \n>> Derrick Stolee <stolee@gmail.com> writes:\n>>\n>>> The thing that surprised me is just how effective this is for the\n>>> creation of large pack-files that include many versions of most\n>>> files. The cross-path deltas have less of an effect here, and the\n>>> benefits of avoiding name-hash collisions can be overwhelming in\n>>> many cases.\n>>\n>> Yes, \"make sure we notice a file F moving from directory A to B\" is\n>> inherently optimized for short span of history, i.e. a smallish push\n>> rather than a whole history clone, where the definition of\n>> \"smallish\" is that even if you create optimal delta chains, the\n>> length of these delta chains will not exceed the \"--depth\" option.\n>>\n>> If the history you are pushing modified A/F twice, renamed it to B/F\n>> (with or without modification at the same time), then modified B/F\n>> twice more, you'd want to pack the 5-commit segment and having to\n>> artificially cut the delta chain that can contain all of these 5\n>> blobs into two at the renaming commit is a huge loss.\n> \n> Which actually leads me to suspect that we probably do not even have\n> to expose the --full-name-hash option to the end users in \"git repack\".\n> \n> If we are doing incremental that would fit within the depth setting,\n> it is likely that we would be better off without the full-name-hash\n> optimization, and if we are doing \"repack -a\" for the whole\n> repository, especially with \"-f\", it would make sense to do the\n> full-name-hash optimization.\n\nDepending on how much we learn from others testing the --full-name-hash\noption, I could see the potential that -a could imply --full-name-hash.\nI hesitate to introduce that in the first release with this option,\nthough.\n\n> If we can tell how large a chunk of history we are packing before we\n> actually start calling builtin/pack-objects.c:add_object_entry(), we\n> probably should be able to even select between with and without\n> full-name-hash automatically, but I do not think we know the object\n> count before we finish calling add_object_entry(), so unless we are\n> willing to compute and keep both while reading and pick between the\n> two after we finish reading the list of objects, or something, it\n> will require a major surgery to do so, I am afraid.\n\nIt's also possible that we could check the list of paths at HEAD to\nsee how many collisions the default name-hash gives. In cases like\nthe Git repository, there are very few collisions and thus we don't\nneed to use --full-name-hash. Restricting to just HEAD (or the\ndefault ref) is not a complete analysis, but might be a good\nheuristic.\n\nThanks,\n-Stolee\n\n"},{"id":"502607","messageId":"20240911063203.GA1538586@coredump.intra.peff.net","threadId":"62085","inReplyTo":"81139d84-b428-4019-bbd1-cda3206d2d68@gmail.com","subject":"Re: [PATCH 0/4] pack-objects: create new name-hash algorithm","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-09-11T06:32:03Z","receivedAt":"2024-09-11T06:32:11Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 10, 2024 at 05:05:09PM -0400, Derrick Stolee wrote:\n\n> > I'm not sure which value you'd actually record in the pack, though.\n> > Ideally there is a hash function which captures some information about\n> > the full path as well as the final path component, so we could use a\n> > single value here, though I suspect the implementation would be more\n> > complicated than what is presented here.\n> \n> Is the name hash stored in the pack itself? I know that it is stored\n> in the 'struct object_entry' data in the packing data. While we could\n> add another uint32_t into that struct to store both hash values, this\n> would increase the memory requirements of repacking by four bytes per\n> object. The struct seemed to be very clear about trying as hard as\n> possible to avoid doing that.\n\nIt's stored in the .bitmap files, since otherwise a pack-objects which\nuses bitmaps to serve a fetch would have no clue of their path names.\nSee the \"HASH_CACHE\" bitmap extension.\n\nYou generally don't want to make deltas out of two entries in the bitmap\n(they're already in the same pack, so we'd usually skip them), but you\ndo want to consider making on-the-fly deltas against other objects.\n\nI guess we may also consider deltas between objects in two packs that\nare both covered by the same midx bitmap.\n\n> But maybe an alternative could be replacing that 32-bit number with\n> an index into an array of paths that have their hash values stored\n> there.\n\nYes, that would work, though how big is that path array going to be?\nUncompressed linux.git is probably 3-4MB, which actually doesn't sound\n_too_ bad. You could obviously go a long way with prefix compression,\ntoo.\n\nBut if I understand the proposal, it is just replacing one 32-bit hash\nwith another. You could just store that in the bitmap instead (or if the\ndirection is to use both, introduce a new extension to store both).\nObviously you'll get lousy results if the bitmap reader does not use the\nsame algorithm for its non-bitmap objects, but I don't think this is\nsomething you'd be flipping back and forth on.\n\n> This is part of the reason why I think the --full-name-hash option is\n> an interesting consideration. It doesn't have any obvious reason why\n> it couldn't work with features like delta islands, so it may provide\n> some quick wins in \"large enough\" repositories, or at least \"large in\n> the right way\".\n> \n> I unfortunately don't know enough about how the delta islands feature\n> works to be confident in the possibility of integrating it with the\n> --path-walk option. At minimum, it would require two object walks:\n> the first would mark the objects and the second would do the delta\n> compression with those markings in mind.\n\nThe delta islands code already does its own tree walk to propagate the\nbits down (it does rely on the base walk's show_commit() to propagate\nthrough the commits).\n\nOnce each object has its island bitmaps, I think however you choose to\ncome up with delta candidates (whether the current type/size/namehash\nsorted list, or some path walking), you should be able to use it. It's\nfundamentally just answering the question of \"am I allowed to delta\nbetween these two objects\".\n\nOf course the devil may be in the details. ;)\n\n-Peff\n"},{"id":"503022","messageId":"pull.1785.v2.git.1726692381.gitgitgadget@gmail.com","threadId":"62085","inReplyTo":"pull.1785.git.1725890210.gitgitgadget@gmail.com","subject":"[PATCH v2 0/6] pack-objects: create new name-hash algorithm","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-18T20:46:15Z","receivedAt":"2024-09-18T20:46:26Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"I've been focused recently on understanding and mitigating the growth of a\nfew internal repositories. Some of these are growing much larger than\nexpected for the number of contributors, and there are multiple aspects to\nwhy this growth is so large.\n\nThis is part of the RFC I submitted [1] [2] involving the path-walk API,\nthough this doesn't use the path-walk API directly. In full repack cases, it\nseems that the --full-name-hash option gets nearly as good compression as\nthe --path-walk option introduced in that series. I continue to work on that\nfeature as well, so we can review it after this series is complete.\n\n[1] https://github.com/gitgitgadget/git/pull/1786\n\n[2]\nhttps://lore.kernel.org/git/pull.1786.git.1725935335.gitgitgadget@gmail.com/\n\nThe main issue plaguing these repositories is that deltas are not being\ncomputed against objects that appear at the same path. While the size of\nthese files at tip is one aspect of growth that would prevent this issue,\nthe changes to these files are reasonable and should result in good delta\ncompression. However, Git is not discovering the connections across\ndifferent versions of the same file.\n\nOne way to find some improvement in these repositories is to increase the\nwindow size, which was an initial indicator that the delta compression could\nbe improved, but was not a clear indicator. After some digging (and\nprototyping some analysis tools) the main discovery was that the current\nname-hash algorithm only considers the last 16 characters in the path name\nand has some naturally-occurring collisions within that scope.\n\nThis series introduces a new name-hash algorithm, but does not replace the\nexisting one. There are cases, such as packing a single snapshot of a\nrepository, where the existing algorithm outperforms the new one.\n\nHowever, my findings show that when a repository has many versions of files\nat the same path (and especially when there are many name-hash collisions)\nthen there are significant gains to be made using the new algorithm.\n\n(This table is updated in v2 with even more private examples that were found\nwhile communicating findings internally.)\n\n| Repo     | Standard Repack | With --full-name-hash |\n|----------|-----------------|-----------------------|\n| fluentui |         438 MB  |               168 MB  |\n| Repo B   |       6,255 MB  |               829 MB  |\n| Repo C   |      37,737 MB  |             7,125 MB  |\n| Repo D   |     130,049 MB  |             6,190 MB  |\n| Repo E   |     100,957 MB  |            22,979 MB  |\n| Repo F   |       8,308 MB  |               746 MB  |\n| Repo G   |       4,329 MB  |             3,643 MB  |\n\n\nI include Repo G here as an example where the improvement is less drastic,\nsince this repo does not demonstrate a very high rate of name-hash\ncollisions; the collisions that exist seem to be in paths that are not\nchanged very often. Thus, the standard name-hash algorithm is nearly as\neffective in these full repacks.\n\nThe main change in this series is in patch 1, which adds the algorithm and\nthe option to 'git pack-objects' and 'git repack'. The remaining patches are\nfocused on creating more evidence around the value of the new name-hash\nalgorithm and its effects on the packfiles created with it.\n\nI will also try to make clear that I've been focused on client-side\nperformance and size concerns. Based on discussions in v1, it appears that\nthe following is true:\n\n * This feature is completely orthogonal to delta islands.\n * Changing the name-hash function can lead to compatibility issues with\n   .bitmap files, as they store a name-hash value. Without augmenting the\n   data structure to indicate which name-hash value was used at write time,\n   the full-name-hash values should not be stored in the .bitmap files or\n   used when reading .bitmap files and other objects. Thus, the\n   full-name-hash is marked as incompatible with bitmaps for now.\n * The --path-walk option from the RFC ([1] and [2]) is likely incompatible\n   with the delta-islands feature without significant work, so this suggests\n   that the --full-name-hash is a better long-term solution for servers.\n   This would still require the .bitmap modifications to make it work, but\n   it's a smaller leap to get there.\n\nThanks, -Stolee\n\n\nUPDATES IN V2\n=============\n\nThank you for all of the discussion on v1. Here are the things I've learned\nand how they have changed this patch series:\n\n * The test-tool name-hash helper change collides with the removal of\n   test-tool oid-array, so I have rebased this series onto the latest master\n   branch.\n * I learned (thanks, Taylor and Peff) that the .bitmap files store\n   name-hash values. This means that the --full-name-hash option risks\n   having different name-hash functions across bitmap reads and dynamic\n   computations from the object walk. For this reason, the option is now\n   made explicit to not work with bitmap walks. This could be corrected in\n   the future with a modification to the .bitmap data structure to store a\n   \"name-hash version\" value. This behavior is confirmed with a test.\n * A new test explicitly tests that git repack --full-name-hash passes the\n   option to git pack-objects. This uses a new helper method,\n   test_subcommand_flex that is more flexible than the existing\n   test_subcommand.\n * To get more testing across different cases, add a new\n   GIT_TEST_FULL_NAME_HASH environment variable. I point out which tests\n   need modification when this is enabled.\n * The size-comparison tests were not portable with their use of du.\n   Instead, use wc -c for the single pack-file that remains after a git\n   repack -adf ... command.\n * The final patch still updates the test-tool name-hash helper, which was\n   previously only used by a performance test. Now, use that test in a\n   regular test to help guarantee that the functions do not change over\n   time. This is directly related to the fact that these values can be\n   stored in the .bitmap files and we need stable hash functions to keep\n   compatibility with files written by previous versions of Git.\n\nOther things that have happened include investigations into ways to adapt\nthe full-name hash to improve upon the name-hash. I did some experimenting\nwith increasing the size of 'struct object_entry' by using a 64-bit hash\nvalue (name-hash, then full-name-hash) for a single-pass compression or two\n32-bit hash values for a two-pass compression process. I include my WIP\nbranch at [3] to show what I tried, though the single-pass option did not\npresent any improvements and the two-pass option seems to be broken to the\npoint that the compression is substantially worse. (I'll try to elaborate on\nthis in a reply to this cover letter.)\n\n[3]\nhttps://github.com/derrickstolee/git/compare/full-name...derrickstolee:git:full-name-wip\n\nDerrick Stolee (6):\n  pack-objects: add --full-name-hash option\n  repack: test --full-name-hash option\n  pack-objects: add GIT_TEST_FULL_NAME_HASH\n  git-repack: update usage to match docs\n  p5313: add size comparison test\n  test-tool: add helper for name-hash values\n\n Documentation/git-pack-objects.txt |  3 +-\n Documentation/git-repack.txt       |  4 +-\n Makefile                           |  1 +\n builtin/pack-objects.c             | 25 ++++++++---\n builtin/repack.c                   |  9 +++-\n ci/run-build-and-tests.sh          |  1 +\n pack-objects.h                     | 21 +++++++++\n t/README                           |  4 ++\n t/helper/test-name-hash.c          | 23 ++++++++++\n t/helper/test-tool.c               |  1 +\n t/helper/test-tool.h               |  1 +\n t/perf/p5313-pack-objects.sh       | 71 ++++++++++++++++++++++++++++++\n t/perf/p5314-name-hash.sh          | 41 +++++++++++++++++\n t/t0450/txt-help-mismatches        |  1 -\n t/t5300-pack-object.sh             | 15 +++++++\n t/t5310-pack-bitmaps.sh            | 26 +++++++++++\n t/t5510-fetch.sh                   |  7 ++-\n t/t5616-partial-clone.sh           | 26 ++++++++++-\n t/t6020-bundle-misc.sh             |  6 ++-\n t/t7700-repack.sh                  |  7 +++\n t/test-lib-functions.sh            | 27 ++++++++++++\n 21 files changed, 307 insertions(+), 13 deletions(-)\n create mode 100644 t/helper/test-name-hash.c\n create mode 100755 t/perf/p5313-pack-objects.sh\n create mode 100755 t/perf/p5314-name-hash.sh\n\n\nbase-commit: 3fb745257b30a643ee78c9a7c52ab107c82e4745\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1785%2Fderrickstolee%2Ffull-name-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1785/derrickstolee/full-name-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/1785\n\nRange-diff vs v1:\n\n 1:  ff30f774ca8 ! 1:  5f52e261765 pack-objects: add --full-name-hash option\n     @@ builtin/pack-objects.c: int cmd_pack_objects(int argc, const char **argv, const\n       \t\tOPT_END(),\n       \t};\n       \n     +@@ builtin/pack-objects.c: int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n     + \tif (pack_to_stdout || !rev_list_all)\n     + \t\twrite_bitmap_index = 0;\n     + \n     ++\tif (write_bitmap_index && use_full_name_hash)\n     ++\t\tdie(_(\"currently, the --full-name-hash option is incompatible with --write-bitmap-index\"));\n     ++\n     + \tif (use_delta_islands)\n     + \t\tstrvec_push(&rp, \"--topo-order\");\n     + \n      \n       ## builtin/repack.c ##\n      @@ builtin/repack.c: struct pack_objects_args {\n     @@ pack-objects.h: static inline uint32_t pack_name_hash(const char *name)\n      +\t\treturn 0;\n      +\n      +\t/*\n     -+\t * Just do the dumbest thing possible: add random multiples of a\n     -+\t * large prime number with a binary shift. Goal is not cryptographic,\n     -+\t * but generally uniformly distributed.\n     ++\t * Do the simplest thing that will resemble pseduo-randomness: add\n     ++\t * random multiples of a large prime number with a binary shift.\n     ++\t * The goal is not to be cryptographic, but to be generally\n     ++\t * uniformly distributed.\n      +\t */\n      +\twhile ((c = *name++) != 0) {\n      +\t\thash += c * bigp;\n     @@ pack-objects.h: static inline uint32_t pack_name_hash(const char *name)\n       static inline enum object_type oe_type(const struct object_entry *e)\n       {\n       \treturn e->type_valid ? e->type_ : OBJ_BAD;\n     +\n     + ## t/t5300-pack-object.sh ##\n     +@@ t/t5300-pack-object.sh: do\n     + \t'\n     + done\n     + \n     ++# The following test is not necessarily a permanent choice, but since we do not\n     ++# have a \"name hash version\" bit in the .bitmap file format, we cannot write the\n     ++# full-name hash values into the .bitmap file without risking breakage later.\n     ++#\n     ++# TODO: Make these compatible in the future and replace this test with the\n     ++# expected behavior when both are specified.\n     ++test_expect_success '--full-name-hash and --write-bitmap-index are incompatible' '\n     ++\ttest_must_fail git pack-objects base --all \\\n     ++\t\t--full-name-hash --write-bitmap-index 2>err &&\n     ++\tgrep incompatible err &&\n     ++\n     ++\t# --stdout option silently removes --write-bitmap-index\n     ++\tgit pack-objects --stdout --all --full-name-hash --write-bitmap-index >out\n     ++'\n     ++\n     + test_done\n -:  ----------- > 2:  48b87cccedb repack: test --full-name-hash option\n -:  ----------- > 3:  48b3876a102 pack-objects: add GIT_TEST_FULL_NAME_HASH\n 2:  eb0aa5f4e94 = 4:  c5827126120 git-repack: update usage to match docs\n 3:  ed3ea4281a9 ! 5:  999b1d09424 p5313: add size comparison test\n     @@ t/perf/p5313-pack-objects.sh (new)\n      +'\n      +\n      +test_size 'repack size' '\n     -+\tdu -a .git/objects/pack | sort -nr | awk \"{ print \\$1; }\" | head -n 1\n     ++\twc -c <.git/objects/pack/pack-*.pack\n      +'\n      +\n      +test_perf 'repack with --full-name-hash' '\n     @@ t/perf/p5313-pack-objects.sh (new)\n      +'\n      +\n      +test_size 'repack size with --full-name-hash' '\n     -+\tdu -a .git/objects/pack | sort -nr | awk \"{ print \\$1; }\" | head -n 1\n     ++\twc -c <.git/objects/pack/pack-*.pack\n      +'\n      +\n      +test_done\n 4:  5bcbcce6665 ! 6:  7e47fc8cb53 p5314: add a size test for name-hash collisions\n     @@ Metadata\n      Author: Derrick Stolee <dstolee@microsoft.com>\n      \n       ## Commit message ##\n     -    p5314: add a size test for name-hash collisions\n     +    test-tool: add helper for name-hash values\n      \n          Add a new test-tool helper, name-hash, to output the value of the\n          name-hash algorithms for the input list of strings, one per line.\n      \n     +    Since the name-hash values can be stored in the .bitmap files, it is\n     +    important that these hash functions do not change across Git versions.\n     +    Add a simple test to t5310-pack-bitmaps.sh to provide some testing of\n     +    the current values. Due to how these functions are implemented, it would\n     +    be difficult to change them without disturbing these values.\n     +\n          Create a performance test that uses test_size to demonstrate how\n          collisions occur for these hash algorithms. This test helps inform\n          someone as to the behavior of the name-hash algorithms for their repo\n     @@ Makefile: TEST_BUILTINS_OBJS += test-lazy-init-name-hash.o\n       TEST_BUILTINS_OBJS += test-mergesort.o\n       TEST_BUILTINS_OBJS += test-mktemp.o\n      +TEST_BUILTINS_OBJS += test-name-hash.o\n     - TEST_BUILTINS_OBJS += test-oid-array.o\n       TEST_BUILTINS_OBJS += test-online-cpus.o\n       TEST_BUILTINS_OBJS += test-pack-mtimes.o\n     + TEST_BUILTINS_OBJS += test-parse-options.o\n      \n       ## t/helper/test-name-hash.c (new) ##\n      @@\n     @@ t/helper/test-tool.c: static struct test_cmd cmds[] = {\n       \t{ \"mergesort\", cmd__mergesort },\n       \t{ \"mktemp\", cmd__mktemp },\n      +\t{ \"name-hash\", cmd__name_hash },\n     - \t{ \"oid-array\", cmd__oid_array },\n       \t{ \"online-cpus\", cmd__online_cpus },\n       \t{ \"pack-mtimes\", cmd__pack_mtimes },\n     + \t{ \"parse-options\", cmd__parse_options },\n      \n       ## t/helper/test-tool.h ##\n      @@ t/helper/test-tool.h: int cmd__lazy_init_name_hash(int argc, const char **argv);\n     @@ t/perf/p5314-name-hash.sh (new)\n      +'\n      +\n      +test_done\n     +\n     + ## t/t5310-pack-bitmaps.sh ##\n     +@@ t/t5310-pack-bitmaps.sh: has_any () {\n     + \tgrep -Ff \"$1\" \"$2\"\n     + }\n     + \n     ++# Since name-hash values are stored in the .bitmap files, add a test\n     ++# that checks that the name-hash calculations are stable across versions.\n     ++# Not exhaustive, but these hashing algorithms would be hard to change\n     ++# without causing deviations here.\n     ++test_expect_success 'name-hash value stability' '\n     ++\tcat >names <<-\\EOF &&\n     ++\tfirst\n     ++\tsecond\n     ++\tthird\n     ++\tone-long-enough-for-collisions\n     ++\ttwo-long-enough-for-collisions\n     ++\tEOF\n     ++\n     ++\ttest-tool name-hash <names >out &&\n     ++\n     ++\tcat >expect <<-\\EOF &&\n     ++\t2582249472\t3109209818\tfirst\n     ++\t2289942528\t3781118409\tsecond\n     ++\t2300837888\t3028707182\tthird\n     ++\t2544516325\t3241327563\tone-long-enough-for-collisions\n     ++\t2544516325\t4207880830\ttwo-long-enough-for-collisions\n     ++\tEOF\n     ++\n     ++\ttest_cmp expect out\n     ++'\n     ++\n     + test_bitmap_cases () {\n     + \twriteLookupTable=false\n     + \tfor i in \"$@\"\n\n-- \ngitgitgadget\n"},{"id":"503021","messageId":"5f52e2617654946c87fff0744393b984ccaab043.1726692381.git.gitgitgadget@gmail.com","threadId":"62085","inReplyTo":"pull.1785.v2.git.1726692381.gitgitgadget@gmail.com","subject":"[PATCH v2 1/6] pack-objects: add --full-name-hash option","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-18T20:46:16Z","receivedAt":"2024-09-18T20:46:27Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee <stolee@gmail.com>\n\nThe pack_name_hash() method has not been materially changed since it was\nintroduced in ce0bd64299a (pack-objects: improve path grouping\nheuristics., 2006-06-05). The intention here is to group objects by path\nname, but also attempt to group similar file types together by making\nthe most-significant digits of the hash be focused on the final\ncharacters.\n\nHere's the crux of the implementation:\n\n\t/*\n\t * This effectively just creates a sortable number from the\n\t * last sixteen non-whitespace characters. Last characters\n\t * count \"most\", so things that end in \".c\" sort together.\n\t */\n\twhile ((c = *name++) != 0) {\n\t\tif (isspace(c))\n\t\t\tcontinue;\n\t\thash = (hash >> 2) + (c << 24);\n\t}\n\nAs the comment mentions, this only cares about the last sixteen\nnon-whitespace characters. This cause some filenames to collide more\nthan others. Here are some examples that I've seen while investigating\nrepositories that are growing more than they should be:\n\n * \"/CHANGELOG.json\" is 15 characters, and is created by the beachball\n   [1] tool. Only the final character of the parent directory can\n   differntiate different versions of this file, but also only the two\n   most-significant digits. If that character is a letter, then this is\n   always a collision. Similar issues occur with the similar\n   \"/CHANGELOG.md\" path, though there is more opportunity for\n   differences in the parent directory.\n\n * Localization files frequently have common filenames but differentiate\n   via parent directories. In C#, the name \"/strings.resx.lcl\" is used\n   for these localization files and they will all collide in name-hash.\n\n[1] https://github.com/microsoft/beachball\n\nI've come across many other examples where some internal tool uses a\ncommon name across multiple directories and is causing Git to repack\npoorly due to name-hash collisions.\n\nIt is clear that the existing name-hash algorithm is optimized for\nrepositories with short path names, but also is optimized for packing a\nsingle snapshot of a repository, not a repository with many versions of\nthe same file. In my testing, this has proven out where the name-hash\nalgorithm does a good job of finding peer files as delta bases when\nunable to use a historical version of that exact file.\n\nHowever, for repositories that have many versions of most files and\ndirectories, it is more important that the objects that appear at the\nsame path are grouped together.\n\nCreate a new pack_full_name_hash() method and a new --full-name-hash\noption for 'git pack-objects' to call that method instead. Add a simple\npass-through for 'git repack --full-name-hash' for additional testing in\nthe context of a full repack, where I expect this will be most\neffective.\n\nThe hash algorithm is as simple as possible to be reasonably effective:\nfor each character of the path string, add a multiple of that character\nand a large prime number (chosen arbitrarily, but intended to be large\nrelative to the size of a uint32_t). Then, shift the current hash value\nto the right by 5, with overlap. The addition and shift parameters are\nstandard mechanisms for creating hard-to-predict behaviors in the bits\nof the resulting hash.\n\nThis is not meant to be cryptographic at all, but uniformly distributed\nacross the possible hash values. This creates a hash that appears\npseudorandom. There is no ability to consider similar file types as\nbeing close to each other.\n\nIn a later change, a test-tool will be added so the effectiveness of\nthis hash can be demonstrated directly.\n\nFor now, let's consider how effective this mechanism is when repacking a\nrepository with and without the --full-name-hash option. Specifically,\nlet's use 'git repack -adf [--full-name-hash]' as our test.\n\nOn the Git repository, we do not expect much difference. All path names\nare short. This is backed by our results:\n\n| Stage                 | Pack Size | Repack Time |\n|-----------------------|-----------|-------------|\n| After clone           | 260 MB    | N/A         |\n| Standard Repack       | 127MB     | 106s        |\n| With --full-name-hash | 126 MB    | 99s         |\n\nThis example demonstrates how there is some natural overhead coming from\nthe cloned copy because the server is hosting many forks and has not\noptimized for exactly this set of reachable objects. But the full repack\nhas similar characteristics with and without --full-name-hash.\n\nHowever, we can test this in a repository that uses one of the\nproblematic naming conventions above. The fluentui [2] repo uses\nbeachball to generate CHANGELOG.json and CHANGELOG.md files, and these\nfiles have very poor delta characteristics when comparing against\nversions across parent directories.\n\n| Stage                 | Pack Size | Repack Time |\n|-----------------------|-----------|-------------|\n| After clone           | 694 MB    | N/A         |\n| Standard Repack       | 438 MB    | 728s        |\n| With --full-name-hash | 168 MB    | 142s        |\n\n[2] https://github.com/microsoft/fluentui\n\nIn this example, we see significant gains in the compressed packfile\nsize as well as the time taken to compute the packfile.\n\nUsing a collection of repositories that use the beachball tool, I was\nable to make similar comparisions with dramatic results. While the\nfluentui repo is public, the others are private so cannot be shared for\nreproduction. The results are so significant that I find it important to\nshare here:\n\n| Repo     | Standard Repack | With --full-name-hash |\n|----------|-----------------|-----------------------|\n| fluentui |         438 MB  |               168 MB  |\n| Repo B   |       6,255 MB  |               829 MB  |\n| Repo C   |      37,737 MB  |             7,125 MB  |\n| Repo D   |     130,049 MB  |             6,190 MB  |\n\nFuture changes could include making --full-name-hash implied by a config\nvalue or even implied by default during a full repack.\n\nSigned-off-by: Derrick Stolee <stolee@gmail.com>\n---\n Documentation/git-pack-objects.txt |  3 ++-\n builtin/pack-objects.c             | 23 ++++++++++++++++++-----\n builtin/repack.c                   |  5 +++++\n pack-objects.h                     | 21 +++++++++++++++++++++\n t/t5300-pack-object.sh             | 15 +++++++++++++++\n 5 files changed, 61 insertions(+), 6 deletions(-)\n\ndiff --git a/Documentation/git-pack-objects.txt b/Documentation/git-pack-objects.txt\nindex e32404c6aae..93861d9f85b 100644\n--- a/Documentation/git-pack-objects.txt\n+++ b/Documentation/git-pack-objects.txt\n@@ -15,7 +15,8 @@ SYNOPSIS\n \t[--revs [--unpacked | --all]] [--keep-pack=<pack-name>]\n \t[--cruft] [--cruft-expiration=<time>]\n \t[--stdout [--filter=<filter-spec>] | <base-name>]\n-\t[--shallow] [--keep-true-parents] [--[no-]sparse] < <object-list>\n+\t[--shallow] [--keep-true-parents] [--[no-]sparse]\n+\t[--full-name-hash] < <object-list>\n \n \n DESCRIPTION\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex c6e2852d3ca..4a990d15609 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -266,6 +266,14 @@ struct configured_exclusion {\n static struct oidmap configured_exclusions;\n \n static struct oidset excluded_by_config;\n+static int use_full_name_hash;\n+\n+static inline uint32_t pack_name_hash_fn(const char *name)\n+{\n+\tif (use_full_name_hash)\n+\t\treturn pack_full_name_hash(name);\n+\treturn pack_name_hash(name);\n+}\n \n /*\n  * stats\n@@ -1698,7 +1706,7 @@ static int add_object_entry(const struct object_id *oid, enum object_type type,\n \t\treturn 0;\n \t}\n \n-\tcreate_object_entry(oid, type, pack_name_hash(name),\n+\tcreate_object_entry(oid, type, pack_name_hash_fn(name),\n \t\t\t    exclude, name && no_try_delta(name),\n \t\t\t    found_pack, found_offset);\n \treturn 1;\n@@ -1912,7 +1920,7 @@ static void add_preferred_base_object(const char *name)\n {\n \tstruct pbase_tree *it;\n \tsize_t cmplen;\n-\tunsigned hash = pack_name_hash(name);\n+\tunsigned hash = pack_name_hash_fn(name);\n \n \tif (!num_preferred_base || check_pbase_path(hash))\n \t\treturn;\n@@ -3422,7 +3430,7 @@ static void show_object_pack_hint(struct object *object, const char *name,\n \t * here using a now in order to perhaps improve the delta selection\n \t * process.\n \t */\n-\toe->hash = pack_name_hash(name);\n+\toe->hash = pack_name_hash_fn(name);\n \toe->no_try_delta = name && no_try_delta(name);\n \n \tstdin_packs_hints_nr++;\n@@ -3572,7 +3580,7 @@ static void add_cruft_object_entry(const struct object_id *oid, enum object_type\n \tentry = packlist_find(&to_pack, oid);\n \tif (entry) {\n \t\tif (name) {\n-\t\t\tentry->hash = pack_name_hash(name);\n+\t\t\tentry->hash = pack_name_hash_fn(name);\n \t\t\tentry->no_try_delta = no_try_delta(name);\n \t\t}\n \t} else {\n@@ -3595,7 +3603,7 @@ static void add_cruft_object_entry(const struct object_id *oid, enum object_type\n \t\t\treturn;\n \t\t}\n \n-\t\tentry = create_object_entry(oid, type, pack_name_hash(name),\n+\t\tentry = create_object_entry(oid, type, pack_name_hash_fn(name),\n \t\t\t\t\t    0, name && no_try_delta(name),\n \t\t\t\t\t    pack, offset);\n \t}\n@@ -4426,6 +4434,8 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\tOPT_STRING_LIST(0, \"uri-protocol\", &uri_protocols,\n \t\t\t\tN_(\"protocol\"),\n \t\t\t\tN_(\"exclude any configured uploadpack.blobpackfileuri with this protocol\")),\n+\t\tOPT_BOOL(0, \"full-name-hash\", &use_full_name_hash,\n+\t\t\t N_(\"optimize delta compression across identical path names over time\")),\n \t\tOPT_END(),\n \t};\n \n@@ -4573,6 +4583,9 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \tif (pack_to_stdout || !rev_list_all)\n \t\twrite_bitmap_index = 0;\n \n+\tif (write_bitmap_index && use_full_name_hash)\n+\t\tdie(_(\"currently, the --full-name-hash option is incompatible with --write-bitmap-index\"));\n+\n \tif (use_delta_islands)\n \t\tstrvec_push(&rp, \"--topo-order\");\n \ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex 8bb875532b4..87d0cd4d2f2 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -57,6 +57,7 @@ struct pack_objects_args {\n \tint no_reuse_object;\n \tint quiet;\n \tint local;\n+\tint full_name_hash;\n \tstruct list_objects_filter_options filter_options;\n };\n \n@@ -288,6 +289,8 @@ static void prepare_pack_objects(struct child_process *cmd,\n \t\tstrvec_pushf(&cmd->args, \"--no-reuse-delta\");\n \tif (args->no_reuse_object)\n \t\tstrvec_pushf(&cmd->args, \"--no-reuse-object\");\n+\tif (args->full_name_hash)\n+\t\tstrvec_pushf(&cmd->args, \"--full-name-hash\");\n \tif (args->local)\n \t\tstrvec_push(&cmd->args,  \"--local\");\n \tif (args->quiet)\n@@ -1176,6 +1179,8 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \t\t\t\tN_(\"pass --no-reuse-delta to git-pack-objects\")),\n \t\tOPT_BOOL('F', NULL, &po_args.no_reuse_object,\n \t\t\t\tN_(\"pass --no-reuse-object to git-pack-objects\")),\n+\t\tOPT_BOOL(0, \"full-name-hash\", &po_args.full_name_hash,\n+\t\t\t\tN_(\"pass --full-name-hash to git-pack-objects\")),\n \t\tOPT_NEGBIT('n', NULL, &run_update_server_info,\n \t\t\t\tN_(\"do not run git-update-server-info\"), 1),\n \t\tOPT__QUIET(&po_args.quiet, N_(\"be quiet\")),\ndiff --git a/pack-objects.h b/pack-objects.h\nindex b9898a4e64b..b0a2d80854f 100644\n--- a/pack-objects.h\n+++ b/pack-objects.h\n@@ -207,6 +207,27 @@ static inline uint32_t pack_name_hash(const char *name)\n \treturn hash;\n }\n \n+static inline uint32_t pack_full_name_hash(const char *name)\n+{\n+\tconst uint32_t bigp = 1234572167U;\n+\tuint32_t c, hash = bigp;\n+\n+\tif (!name)\n+\t\treturn 0;\n+\n+\t/*\n+\t * Do the simplest thing that will resemble pseduo-randomness: add\n+\t * random multiples of a large prime number with a binary shift.\n+\t * The goal is not to be cryptographic, but to be generally\n+\t * uniformly distributed.\n+\t */\n+\twhile ((c = *name++) != 0) {\n+\t\thash += c * bigp;\n+\t\thash = (hash >> 5) | (hash << 27);\n+\t}\n+\treturn hash;\n+}\n+\n static inline enum object_type oe_type(const struct object_entry *e)\n {\n \treturn e->type_valid ? e->type_ : OBJ_BAD;\ndiff --git a/t/t5300-pack-object.sh b/t/t5300-pack-object.sh\nindex 3b9dae331a5..fff49000c31 100755\n--- a/t/t5300-pack-object.sh\n+++ b/t/t5300-pack-object.sh\n@@ -674,4 +674,19 @@ do\n \t'\n done\n \n+# The following test is not necessarily a permanent choice, but since we do not\n+# have a \"name hash version\" bit in the .bitmap file format, we cannot write the\n+# full-name hash values into the .bitmap file without risking breakage later.\n+#\n+# TODO: Make these compatible in the future and replace this test with the\n+# expected behavior when both are specified.\n+test_expect_success '--full-name-hash and --write-bitmap-index are incompatible' '\n+\ttest_must_fail git pack-objects base --all \\\n+\t\t--full-name-hash --write-bitmap-index 2>err &&\n+\tgrep incompatible err &&\n+\n+\t# --stdout option silently removes --write-bitmap-index\n+\tgit pack-objects --stdout --all --full-name-hash --write-bitmap-index >out\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"503023","messageId":"48b87cccedb3d7920a3184ca86ca9eec77c0fd01.1726692381.git.gitgitgadget@gmail.com","threadId":"62085","inReplyTo":"pull.1785.v2.git.1726692381.gitgitgadget@gmail.com","subject":"[PATCH v2 2/6] repack: test --full-name-hash option","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-18T20:46:17Z","receivedAt":"2024-09-18T20:46:28Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee <stolee@gmail.com>\n\nThe new '--full-name-hash' option for 'git repack' is a simple\npass-through to the underlying 'git pack-objects' subcommand. However,\nthis subcommand may have other options and a temporary filename as part\nof the subcommand execution that may not be predictable or could change\nover time.\n\nThe existing test_subcommand method requires an exact list of arguments\nfor the subcommand. This is too rigid for our needs here, so create a\nnew method, test_subcommand_flex. Use it to check that the\n--full-name-hash option is passing through.\n\nSigned-off-by: Derrick Stolee <stolee@gmail.com>\n---\n t/t7700-repack.sh       |  7 +++++++\n t/test-lib-functions.sh | 27 +++++++++++++++++++++++++++\n 2 files changed, 34 insertions(+)\n\ndiff --git a/t/t7700-repack.sh b/t/t7700-repack.sh\nindex be1188e7365..1feb6643e69 100755\n--- a/t/t7700-repack.sh\n+++ b/t/t7700-repack.sh\n@@ -776,6 +776,13 @@ test_expect_success 'repack -ad cleans up old .tmp-* packs' '\n \ttest_must_be_empty tmpfiles\n '\n \n+test_expect_success '--full-name-hash option passes through to pack-objects' '\n+\tGIT_TRACE2_EVENT=\"$(pwd)/full-trace.txt\" \\\n+\t\tgit repack -a --full-name-hash &&\n+\ttest_subcommand_flex git pack-objects --full-name-hash <full-trace.txt\n+'\n+\n+\n test_expect_success 'setup for update-server-info' '\n \tgit init update-server-info &&\n \ttest_commit -C update-server-info message\ndiff --git a/t/test-lib-functions.sh b/t/test-lib-functions.sh\nindex fde9bf54fc3..0d94730924a 100644\n--- a/t/test-lib-functions.sh\n+++ b/t/test-lib-functions.sh\n@@ -1885,6 +1885,33 @@ test_subcommand () {\n \tfi\n }\n \n+\n+# Check that the given subcommand was run with the given set of\n+# arguments in order (but with possible extra arguments).\n+#\n+#\ttest_subcommand_flex [!] <command> <args>... < <trace>\n+#\n+# If the first parameter passed is !, this instead checks that\n+# the given command was not called.\n+#\n+test_subcommand_flex () {\n+\tlocal negate=\n+\tif test \"$1\" = \"!\"\n+\tthen\n+\t\tnegate=t\n+\t\tshift\n+\tfi\n+\n+\tlocal expr=\"$(printf '\"%s\".*' \"$@\")\"\n+\n+\tif test -n \"$negate\"\n+\tthen\n+\t\t! grep \"\\[$expr\\]\"\n+\telse\n+\t\tgrep \"\\[$expr\\]\"\n+\tfi\n+}\n+\n # Check that the given command was invoked as part of the\n # trace2-format trace on stdin.\n #\n-- \ngitgitgadget\n\n"},{"id":"503024","messageId":"48b3876a10247d2ba65a6e5f1ff8ed3a662813f8.1726692381.git.gitgitgadget@gmail.com","threadId":"62085","inReplyTo":"pull.1785.v2.git.1726692381.gitgitgadget@gmail.com","subject":"[PATCH v2 3/6] pack-objects: add GIT_TEST_FULL_NAME_HASH","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-18T20:46:18Z","receivedAt":"2024-09-18T20:46:28Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee <stolee@gmail.com>\n\nAdd a new environment variable to opt-in to the --full-name-hash option\nin 'git pack-objects'. This allows for extra testing of the feature\nwithout repeating all of the test scenarios.\n\nBut this option isn't free. There are a few tests that change behavior\nwith the variable enabled.\n\nFirst, there are a few tests that are very sensitive to certain delta\nbases being picked. These are both involving the generation of thin\nbundles and then counting their objects via 'git index-pack --fix-thin'\nwhich pulls the delta base into the new packfile. For these tests,\ndisable the option as a decent long-term option.\n\nSecond, there are two tests in t5616-partial-clone.sh that I believe are\nactually broken scenarios. While the client is set up to clone the\n'promisor-server' repo via a treeless partial clone filter (tree:0),\nthat filter does not translate to the 'server' repo. Thus, fetching from\nthese repos causes the server to think that the client has all reachable\ntrees and blobs from the commits advertised as 'haves'. This leads the\nserver to providing a thin pack assuming those objects as delta bases.\nChanging the name-hash algorithm presents new delta bases and thus\nbreaks the expectations of these tests. An alternative could be to set\nup 'server' as a promisor server with the correct filter enabled. This\nmay also point out more issues with partial clone being set up as a\nremote-based filtering mechanism and not a repository-wide setting. For\nnow, do the minimal change to make the test work by disabling the test\nvariable.\n\nSigned-off-by: Derrick Stolee <stolee@gmail.com>\n---\n builtin/pack-objects.c    |  6 ++++--\n ci/run-build-and-tests.sh |  1 +\n t/README                  |  4 ++++\n t/t5510-fetch.sh          |  7 ++++++-\n t/t5616-partial-clone.sh  | 26 ++++++++++++++++++++++++--\n t/t6020-bundle-misc.sh    |  6 +++++-\n 6 files changed, 44 insertions(+), 6 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 4a990d15609..8876fa3d641 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -266,7 +266,7 @@ struct configured_exclusion {\n static struct oidmap configured_exclusions;\n \n static struct oidset excluded_by_config;\n-static int use_full_name_hash;\n+static int use_full_name_hash = -1;\n \n static inline uint32_t pack_name_hash_fn(const char *name)\n {\n@@ -4583,8 +4583,10 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \tif (pack_to_stdout || !rev_list_all)\n \t\twrite_bitmap_index = 0;\n \n-\tif (write_bitmap_index && use_full_name_hash)\n+\tif (write_bitmap_index && use_full_name_hash > 0)\n \t\tdie(_(\"currently, the --full-name-hash option is incompatible with --write-bitmap-index\"));\n+\tif (use_full_name_hash < 0)\n+\t\tuse_full_name_hash = git_env_bool(\"GIT_TEST_FULL_NAME_HASH\", 0);\n \n \tif (use_delta_islands)\n \t\tstrvec_push(&rp, \"--topo-order\");\ndiff --git a/ci/run-build-and-tests.sh b/ci/run-build-and-tests.sh\nindex 2e28d02b20f..75b40f07bbd 100755\n--- a/ci/run-build-and-tests.sh\n+++ b/ci/run-build-and-tests.sh\n@@ -30,6 +30,7 @@ linux-TEST-vars)\n \texport GIT_TEST_NO_WRITE_REV_INDEX=1\n \texport GIT_TEST_CHECKOUT_WORKERS=2\n \texport GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1\n+\texport GIT_TEST_FULL_NAME_HASH=1\n \t;;\n linux-clang)\n \texport GIT_TEST_DEFAULT_HASH=sha1\ndiff --git a/t/README b/t/README\nindex 44c02d81298..eaaf9fcd57e 100644\n--- a/t/README\n+++ b/t/README\n@@ -488,6 +488,10 @@ a test and then fails then the whole test run will abort. This can help to make\n sure the expected tests are executed and not silently skipped when their\n dependency breaks or is simply not present in a new environment.\n \n+GIT_TEST_FULL_NAME_HASH=<boolean>, when true, sets the default name-hash\n+function in 'git pack-objects' to be the one used by the --full-name-hash\n+option.\n+\n Naming Tests\n ------------\n \ndiff --git a/t/t5510-fetch.sh b/t/t5510-fetch.sh\nindex 0890b9f61c5..be79c72495e 100755\n--- a/t/t5510-fetch.sh\n+++ b/t/t5510-fetch.sh\n@@ -1062,7 +1062,12 @@ test_expect_success 'all boundary commits are excluded' '\n \ttest_tick &&\n \tgit merge otherside &&\n \tad=$(git log --no-walk --format=%ad HEAD) &&\n-\tgit bundle create twoside-boundary.bdl main --since=\"$ad\" &&\n+\n+\t# If the --full-name-hash function is used here, then no delta\n+\t# pair is found and the bundle does not expand to three objects\n+\t# when fixing the thin object.\n+\tGIT_TEST_FULL_NAME_HASH=0 \\\n+\t\tgit bundle create twoside-boundary.bdl main --since=\"$ad\" &&\n \ttest_bundle_object_count --thin twoside-boundary.bdl 3\n '\n \ndiff --git a/t/t5616-partial-clone.sh b/t/t5616-partial-clone.sh\nindex 8415884754b..69d5bab73cd 100755\n--- a/t/t5616-partial-clone.sh\n+++ b/t/t5616-partial-clone.sh\n@@ -515,7 +515,18 @@ test_expect_success 'fetch lazy-fetches only to resolve deltas' '\n \t# Exercise to make sure it works. Git will not fetch anything from the\n \t# promisor remote other than for the big tree (because it needs to\n \t# resolve the delta).\n-\tGIT_TRACE_PACKET=\"$(pwd)/trace\" git -C client \\\n+\t#\n+\t# TODO: the --full-name-hash option is disabled here, since this test\n+\t# is fundamentally broken! When GIT_TEST_FULL_NAME_HASH=1, the server\n+\t# recognizes delta bases in a different way and then sends a _blob_ to\n+\t# the client with a delta base that the client does not have! This is\n+\t# because the client is cloned from \"promisor-server\" with tree:0 but\n+\t# is now fetching from \"server\" withot any filter. This is violating the\n+\t# promise to the server that all reachable objects exist and could be\n+\t# used as delta bases!\n+\tGIT_TRACE_PACKET=\"$(pwd)/trace\" \\\n+\tGIT_TEST_FULL_NAME_HASH=0 \\\n+\t\tgit -C client \\\n \t\tfetch \"file://$(pwd)/server\" main &&\n \n \t# Verify the assumption that the client needed to fetch the delta base\n@@ -534,7 +545,18 @@ test_expect_success 'fetch lazy-fetches only to resolve deltas, protocol v2' '\n \t# Exercise to make sure it works. Git will not fetch anything from the\n \t# promisor remote other than for the big blob (because it needs to\n \t# resolve the delta).\n-\tGIT_TRACE_PACKET=\"$(pwd)/trace\" git -C client \\\n+\t#\n+\t# TODO: the --full-name-hash option is disabled here, since this test\n+\t# is fundamentally broken! When GIT_TEST_FULL_NAME_HASH=1, the server\n+\t# recognizes delta bases in a different way and then sends a _blob_ to\n+\t# the client with a delta base that the client does not have! This is\n+\t# because the client is cloned from \"promisor-server\" with tree:0 but\n+\t# is now fetching from \"server\" withot any filter. This is violating the\n+\t# promise to the server that all reachable objects exist and could be\n+\t# used as delta bases!\n+\tGIT_TRACE_PACKET=\"$(pwd)/trace\" \\\n+\tGIT_TEST_FULL_NAME_HASH=0 \\\n+\t\tgit -C client \\\n \t\tfetch \"file://$(pwd)/server\" main &&\n \n \t# Verify that protocol version 2 was used.\ndiff --git a/t/t6020-bundle-misc.sh b/t/t6020-bundle-misc.sh\nindex 34b5cd62c20..553a20d10e9 100755\n--- a/t/t6020-bundle-misc.sh\n+++ b/t/t6020-bundle-misc.sh\n@@ -247,7 +247,11 @@ test_expect_success 'create bundle with --since option' '\n \tEOF\n \ttest_cmp expect actual &&\n \n-\tgit bundle create since.bdl \\\n+\t# If the --full-name-hash option is used, then one fewer\n+\t# delta base is found and this counts a different number\n+\t# of objects after performing --fix-thin.\n+\tGIT_TEST_FULL_NAME_HASH=0 \\\n+\t\tgit bundle create since.bdl \\\n \t\t--since \"Thu Apr 7 15:27:00 2005 -0700\" \\\n \t\t--all &&\n \n-- \ngitgitgadget\n\n"},{"id":"503025","messageId":"c58271261200779918d3329f31e4c4ffe59d6ec8.1726692381.git.gitgitgadget@gmail.com","threadId":"62085","inReplyTo":"pull.1785.v2.git.1726692381.gitgitgadget@gmail.com","subject":"[PATCH v2 4/6] git-repack: update usage to match docs","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-18T20:46:19Z","receivedAt":"2024-09-18T20:46:29Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee <stolee@gmail.com>\n\nThis also adds the '--full-name-hash' option introduced in the previous\nchange and adds newlines to the synopsis.\n\nSigned-off-by: Derrick Stolee <stolee@gmail.com>\n---\n Documentation/git-repack.txt | 4 +++-\n builtin/repack.c             | 4 +++-\n t/t0450/txt-help-mismatches  | 1 -\n 3 files changed, 6 insertions(+), 3 deletions(-)\n\ndiff --git a/Documentation/git-repack.txt b/Documentation/git-repack.txt\nindex c902512a9e8..457a793fa89 100644\n--- a/Documentation/git-repack.txt\n+++ b/Documentation/git-repack.txt\n@@ -9,7 +9,9 @@ git-repack - Pack unpacked objects in a repository\n SYNOPSIS\n --------\n [verse]\n-'git repack' [-a] [-A] [-d] [-f] [-F] [-l] [-n] [-q] [-b] [-m] [--window=<n>] [--depth=<n>] [--threads=<n>] [--keep-pack=<pack-name>] [--write-midx]\n+'git repack' [-a] [-A] [-d] [-f] [-F] [-l] [-n] [-q] [-b] [-m]\n+\t[--window=<n>] [--depth=<n>] [--threads=<n>] [--keep-pack=<pack-name>]\n+\t[--write-midx] [--full-name-hash]\n \n DESCRIPTION\n -----------\ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex 87d0cd4d2f2..4fa2c25246d 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -38,7 +38,9 @@ static int run_update_server_info = 1;\n static char *packdir, *packtmp_name, *packtmp;\n \n static const char *const git_repack_usage[] = {\n-\tN_(\"git repack [<options>]\"),\n+\tN_(\"git repack [-a] [-A] [-d] [-f] [-F] [-l] [-n] [-q] [-b] [-m]\\n\"\n+\t   \"[--window=<n>] [--depth=<n>] [--threads=<n>] [--keep-pack=<pack-name>]\\n\"\n+\t   \"[--write-midx] [--full-name-hash]\"),\n \tNULL\n };\n \ndiff --git a/t/t0450/txt-help-mismatches b/t/t0450/txt-help-mismatches\nindex 28003f18c92..c4a15fd0cb8 100644\n--- a/t/t0450/txt-help-mismatches\n+++ b/t/t0450/txt-help-mismatches\n@@ -45,7 +45,6 @@ rebase\n remote\n remote-ext\n remote-fd\n-repack\n reset\n restore\n rev-parse\n-- \ngitgitgadget\n\n"},{"id":"503026","messageId":"999b1d094241b0ba8d6924ac6976eafc64c7d4a6.1726692382.git.gitgitgadget@gmail.com","threadId":"62085","inReplyTo":"pull.1785.v2.git.1726692381.gitgitgadget@gmail.com","subject":"[PATCH v2 5/6] p5313: add size comparison test","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-18T20:46:20Z","receivedAt":"2024-09-18T20:46:31Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee <stolee@gmail.com>\n\nAs custom options are added to 'git pack-objects' and 'git repack' to\nadjust how compression is done, use this new performance test script to\ndemonstrate their effectiveness in performance and size.\n\nThe recently-added --full-name-hash option swaps the default name-hash\nalgorithm with one that attempts to uniformly distribute the hashes\nbased on the full path name instead of the last 16 characters.\n\nThis has a dramatic effect on full repacks for repositories with many\nversions of most paths. It can have a negative impact on cases such as\npushing a single change.\n\nThis can be seen by running pt5313 on the open source fluentui\nrepository [1]. Most commits will have this kind of output for the thin\nand big pack cases, though certain commits (such as [2]) will have\nproblematic thin pack size for other reasons.\n\n[1] https://github.com/microsoft/fluentui\n[2] a637a06df05360ce5ff21420803f64608226a875\n\nChecked out at the parent of [2], I see the following statistics:\n\nTest                                           this tree\n------------------------------------------------------------------\n5313.2: thin pack                              0.02(0.01+0.01)\n5313.3: thin pack size                                    1.1K\n5313.4: thin pack with --full-name-hash        0.02(0.01+0.00)\n5313.5: thin pack size with --full-name-hash              3.0K\n5313.6: big pack                               1.65(3.35+0.24)\n5313.7: big pack size                                    58.0M\n5313.8: big pack with --full-name-hash         1.53(2.52+0.18)\n5313.9: big pack size with --full-name-hash              57.6M\n5313.10: repack                                176.52(706.60+3.53)\n5313.11: repack size                                    446.7K\n5313.12: repack with --full-name-hash          37.47(134.18+3.06)\n5313.13: repack size with --full-name-hash              183.1K\n\nNote that this demonstrates a 3x size _increase_ in the case that\nsimulates a small \"git push\". The size change is neutral on the case of\npushing the difference between HEAD and HEAD~1000.\n\nHowever, the full repack case is both faster and more efficient.\n\nSigned-off-by: Derrick Stolee <stolee@gmail.com>\n---\n t/perf/p5313-pack-objects.sh | 71 ++++++++++++++++++++++++++++++++++++\n 1 file changed, 71 insertions(+)\n create mode 100755 t/perf/p5313-pack-objects.sh\n\ndiff --git a/t/perf/p5313-pack-objects.sh b/t/perf/p5313-pack-objects.sh\nnew file mode 100755\nindex 00000000000..5dcf52acb0d\n--- /dev/null\n+++ b/t/perf/p5313-pack-objects.sh\n@@ -0,0 +1,71 @@\n+#!/bin/sh\n+\n+test_description='Tests pack performance using bitmaps'\n+. ./perf-lib.sh\n+\n+GIT_TEST_PASSING_SANITIZE_LEAK=0\n+export GIT_TEST_PASSING_SANITIZE_LEAK\n+\n+test_perf_large_repo\n+\n+test_expect_success 'create rev input' '\n+\tcat >in-thin <<-EOF &&\n+\t$(git rev-parse HEAD)\n+\t^$(git rev-parse HEAD~1)\n+\tEOF\n+\n+\tcat >in-big <<-EOF\n+\t$(git rev-parse HEAD)\n+\t^$(git rev-parse HEAD~1000)\n+\tEOF\n+'\n+\n+test_perf 'thin pack' '\n+\tgit pack-objects --thin --stdout --revs --sparse  <in-thin >out\n+'\n+\n+test_size 'thin pack size' '\n+\twc -c <out\n+'\n+\n+test_perf 'thin pack with --full-name-hash' '\n+\tgit pack-objects --thin --stdout --revs --sparse --full-name-hash <in-thin >out\n+'\n+\n+test_size 'thin pack size with --full-name-hash' '\n+\twc -c <out\n+'\n+\n+test_perf 'big pack' '\n+\tgit pack-objects --stdout --revs --sparse  <in-big >out\n+'\n+\n+test_size 'big pack size' '\n+\twc -c <out\n+'\n+\n+test_perf 'big pack with --full-name-hash' '\n+\tgit pack-objects --stdout --revs --sparse --full-name-hash <in-big >out\n+'\n+\n+test_size 'big pack size with --full-name-hash' '\n+\twc -c <out\n+'\n+\n+test_perf 'repack' '\n+\tgit repack -adf\n+'\n+\n+test_size 'repack size' '\n+\twc -c <.git/objects/pack/pack-*.pack\n+'\n+\n+test_perf 'repack with --full-name-hash' '\n+\tgit repack -adf --full-name-hash\n+'\n+\n+test_size 'repack size with --full-name-hash' '\n+\twc -c <.git/objects/pack/pack-*.pack\n+'\n+\n+test_done\n-- \ngitgitgadget\n\n"},{"id":"503027","messageId":"7e47fc8cb53647ad92c86801204c3089a5dfe8e6.1726692382.git.gitgitgadget@gmail.com","threadId":"62085","inReplyTo":"pull.1785.v2.git.1726692381.gitgitgadget@gmail.com","subject":"[PATCH v2 6/6] test-tool: add helper for name-hash values","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-18T20:46:21Z","receivedAt":"2024-09-18T20:46:31Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee <stolee@gmail.com>\n\nAdd a new test-tool helper, name-hash, to output the value of the\nname-hash algorithms for the input list of strings, one per line.\n\nSince the name-hash values can be stored in the .bitmap files, it is\nimportant that these hash functions do not change across Git versions.\nAdd a simple test to t5310-pack-bitmaps.sh to provide some testing of\nthe current values. Due to how these functions are implemented, it would\nbe difficult to change them without disturbing these values.\n\nCreate a performance test that uses test_size to demonstrate how\ncollisions occur for these hash algorithms. This test helps inform\nsomeone as to the behavior of the name-hash algorithms for their repo\nbased on the paths at HEAD.\n\nMy copy of the Git repository shows modest statistics around the\ncollisions of the default name-hash algorithm:\n\nTest                                              this tree\n-----------------------------------------------------------------\n5314.1: paths at head                                        4.5K\n5314.2: number of distinct name-hashes                       4.1K\n5314.3: number of distinct full-name-hashes                  4.5K\n5314.4: maximum multiplicity of name-hashes                    13\n5314.5: maximum multiplicity of fullname-hashes                 1\n\nHere, the maximum collision multiplicity is 13, but around 10% of paths\nhave a collision with another path.\n\nIn a more interesting example, the microsoft/fluentui [1] repo had these\nstatistics at time of committing:\n\nTest                                              this tree\n-----------------------------------------------------------------\n5314.1: paths at head                                       19.6K\n5314.2: number of distinct name-hashes                       8.2K\n5314.3: number of distinct full-name-hashes                 19.6K\n5314.4: maximum multiplicity of name-hashes                   279\n5314.5: maximum multiplicity of fullname-hashes                 1\n\n[1] https://github.com/microsoft/fluentui\n\nThat demonstrates that of the nearly twenty thousand path names, they\nare assigned around eight thousand distinct values. 279 paths are\nassigned to a single value, leading the packing algorithm to sort\nobjects from those paths together, by size.\n\nIn this repository, no collisions occur for the full-name-hash\nalgorithm.\n\nIn a more extreme example, an internal monorepo had a much worse\ncollision rate:\n\nTest                                              this tree\n-----------------------------------------------------------------\n5314.1: paths at head                                      221.6K\n5314.2: number of distinct name-hashes                      72.0K\n5314.3: number of distinct full-name-hashes                221.6K\n5314.4: maximum multiplicity of name-hashes                 14.4K\n5314.5: maximum multiplicity of fullname-hashes                 2\n\nEven in this repository with many more paths at HEAD, the collision rate\nwas low and the maximum number of paths being grouped into a single\nbucket by the full-path-name algorithm was two.\n\nSigned-off-by: Derrick Stolee <stolee@gmail.com>\n---\n Makefile                  |  1 +\n t/helper/test-name-hash.c | 23 ++++++++++++++++++++++\n t/helper/test-tool.c      |  1 +\n t/helper/test-tool.h      |  1 +\n t/perf/p5314-name-hash.sh | 41 +++++++++++++++++++++++++++++++++++++++\n t/t5310-pack-bitmaps.sh   | 26 +++++++++++++++++++++++++\n 6 files changed, 93 insertions(+)\n create mode 100644 t/helper/test-name-hash.c\n create mode 100755 t/perf/p5314-name-hash.sh\n\ndiff --git a/Makefile b/Makefile\nindex 275a5ee3c9f..50797a4e541 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -812,6 +812,7 @@ TEST_BUILTINS_OBJS += test-lazy-init-name-hash.o\n TEST_BUILTINS_OBJS += test-match-trees.o\n TEST_BUILTINS_OBJS += test-mergesort.o\n TEST_BUILTINS_OBJS += test-mktemp.o\n+TEST_BUILTINS_OBJS += test-name-hash.o\n TEST_BUILTINS_OBJS += test-online-cpus.o\n TEST_BUILTINS_OBJS += test-pack-mtimes.o\n TEST_BUILTINS_OBJS += test-parse-options.o\ndiff --git a/t/helper/test-name-hash.c b/t/helper/test-name-hash.c\nnew file mode 100644\nindex 00000000000..15fb8f853c1\n--- /dev/null\n+++ b/t/helper/test-name-hash.c\n@@ -0,0 +1,23 @@\n+/*\n+ * test-name-hash.c: Read a list of paths over stdin and report on their\n+ * name-hash and full name-hash.\n+ */\n+\n+#include \"test-tool.h\"\n+#include \"git-compat-util.h\"\n+#include \"pack-objects.h\"\n+#include \"strbuf.h\"\n+\n+int cmd__name_hash(int argc UNUSED, const char **argv UNUSED)\n+{\n+\tstruct strbuf line = STRBUF_INIT;\n+\n+\twhile (!strbuf_getline(&line, stdin)) {\n+\t\tuint32_t name_hash = pack_name_hash(line.buf);\n+\t\tuint32_t full_hash = pack_full_name_hash(line.buf);\n+\n+\t\tprintf(\"%10\"PRIu32\"\\t%10\"PRIu32\"\\t%s\\n\", name_hash, full_hash, line.buf);\n+\t}\n+\n+\treturn 0;\n+}\ndiff --git a/t/helper/test-tool.c b/t/helper/test-tool.c\nindex 1ebb69a5dc4..e794058ab6d 100644\n--- a/t/helper/test-tool.c\n+++ b/t/helper/test-tool.c\n@@ -44,6 +44,7 @@ static struct test_cmd cmds[] = {\n \t{ \"match-trees\", cmd__match_trees },\n \t{ \"mergesort\", cmd__mergesort },\n \t{ \"mktemp\", cmd__mktemp },\n+\t{ \"name-hash\", cmd__name_hash },\n \t{ \"online-cpus\", cmd__online_cpus },\n \t{ \"pack-mtimes\", cmd__pack_mtimes },\n \t{ \"parse-options\", cmd__parse_options },\ndiff --git a/t/helper/test-tool.h b/t/helper/test-tool.h\nindex 21802ac27da..26ff30a5a9a 100644\n--- a/t/helper/test-tool.h\n+++ b/t/helper/test-tool.h\n@@ -37,6 +37,7 @@ int cmd__lazy_init_name_hash(int argc, const char **argv);\n int cmd__match_trees(int argc, const char **argv);\n int cmd__mergesort(int argc, const char **argv);\n int cmd__mktemp(int argc, const char **argv);\n+int cmd__name_hash(int argc, const char **argv);\n int cmd__online_cpus(int argc, const char **argv);\n int cmd__pack_mtimes(int argc, const char **argv);\n int cmd__parse_options(int argc, const char **argv);\ndiff --git a/t/perf/p5314-name-hash.sh b/t/perf/p5314-name-hash.sh\nnew file mode 100755\nindex 00000000000..9fe26612fac\n--- /dev/null\n+++ b/t/perf/p5314-name-hash.sh\n@@ -0,0 +1,41 @@\n+#!/bin/sh\n+\n+test_description='Tests pack performance using bitmaps'\n+. ./perf-lib.sh\n+\n+GIT_TEST_PASSING_SANITIZE_LEAK=0\n+export GIT_TEST_PASSING_SANITIZE_LEAK\n+\n+test_perf_large_repo\n+\n+test_size 'paths at head' '\n+\tgit ls-tree -r --name-only HEAD >path-list &&\n+\twc -l <path-list\n+'\n+\n+test_size 'number of distinct name-hashes' '\n+\tcat path-list | test-tool name-hash >name-hashes &&\n+\tcat name-hashes | awk \"{ print \\$1; }\" | sort -n | uniq -c >name-hash-count &&\n+\twc -l <name-hash-count\n+'\n+\n+test_size 'number of distinct full-name-hashes' '\n+\tcat name-hashes | awk \"{ print \\$2; }\" | sort -n | uniq -c >full-name-hash-count &&\n+\twc -l <full-name-hash-count\n+'\n+\n+test_size 'maximum multiplicity of name-hashes' '\n+\tcat name-hash-count | \\\n+\t\tsort -nr | \\\n+\t\thead -n 1 | \\\n+\t\tawk \"{ print \\$1; }\"\n+'\n+\n+test_size 'maximum multiplicity of fullname-hashes' '\n+\tcat full-name-hash-count | \\\n+\t\tsort -nr | \\\n+\t\thead -n 1 | \\\n+\t\tawk \"{ print \\$1; }\"\n+'\n+\n+test_done\ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex a6de7c57643..5759710a2cd 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -26,6 +26,32 @@ has_any () {\n \tgrep -Ff \"$1\" \"$2\"\n }\n \n+# Since name-hash values are stored in the .bitmap files, add a test\n+# that checks that the name-hash calculations are stable across versions.\n+# Not exhaustive, but these hashing algorithms would be hard to change\n+# without causing deviations here.\n+test_expect_success 'name-hash value stability' '\n+\tcat >names <<-\\EOF &&\n+\tfirst\n+\tsecond\n+\tthird\n+\tone-long-enough-for-collisions\n+\ttwo-long-enough-for-collisions\n+\tEOF\n+\n+\ttest-tool name-hash <names >out &&\n+\n+\tcat >expect <<-\\EOF &&\n+\t2582249472\t3109209818\tfirst\n+\t2289942528\t3781118409\tsecond\n+\t2300837888\t3028707182\tthird\n+\t2544516325\t3241327563\tone-long-enough-for-collisions\n+\t2544516325\t4207880830\ttwo-long-enough-for-collisions\n+\tEOF\n+\n+\ttest_cmp expect out\n+'\n+\n test_bitmap_cases () {\n \twriteLookupTable=false\n \tfor i in \"$@\"\n-- \ngitgitgadget\n"},{"id":"503041","messageId":"b2ad8d6f-ad66-4ca4-8b27-8e5450306c99@gmail.com","threadId":"62085","inReplyTo":"pull.1785.v2.git.1726692381.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 0/6] pack-objects: create new name-hash algorithm","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-09-18T23:30:42Z","receivedAt":"2024-09-18T23:30:44Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 9/18/24 4:46 PM, Derrick Stolee via GitGitGadget wrote:\n...\n > Other things that have happened include investigations into ways to adapt\n > the full-name hash to improve upon the name-hash. I did some experimenting\n > with increasing the size of 'struct object_entry' by using a 64-bit hash\n > value (name-hash, then full-name-hash) for a single-pass compression or two\n > 32-bit hash values for a two-pass compression process. I include my WIP\n > branch at [3] to show what I tried, though the single-pass option did not\n > present any improvements and the two-pass option seems to be broken to the\n > point that the compression is substantially worse. (I'll try to elaborate on\n > this in a reply to this cover letter.)\n >\n > [3] \nhttps://github.com/derrickstolee/git/compare/full-name...derrickstolee:git:full-name-wip\n\nTo break down what I attempted in [3], let me break down a few things.\n\nFirst, I tried using a 64-bit hash value [1]. This used the standard name-hash\nas the most-significant digits and the full-name-hash as the least-significant\ndigits. The goal here was to still have locality from the name-hash but get a\ngood partition based on full-name-hash within those collisions.\n\nHowever, when sorting this way, the boundaries of the full-name-hash partitions\nare ineffective at getting good delta bases because the largest object from one\nfull-name-hash set is next to the smallest object from the next full-name-hash\nset. Even when a full-name-hash set has size one, it is sorted roughly randomly\namong the other colliding path names instead of grouped nicely with objects of\na similar size. This makes the results nearly identical to the 32-bit\nfull-name-hash implementation.\n\n[1] \nhttps://github.com/derrickstolee/git/commit/aaa6befa3016667ea5eb10fdd6aa2b7fcec3a52e\n\nSecond, I tried storing two 32-bit hashes and doing a two-pass delta search [2].\nIn theory, this should be very similar to the --path-walk feature from the RFC.\nHowever, I failed to make it work. Something about this version of a two-pass\nwalk was hitting some strange behavior. For example, I had to put in this extra\ncondition [4] if a best delta base was not found, or else we could get a\nsegfault.\n\n[2] \nhttps://github.com/derrickstolee/git/commit/bf71271040ab93a624a8cdf5bc8aaff68e9b1b17\n\n[4] \nhttps://github.com/derrickstolee/git/commit/fedc4fc543e50563f4748a5ffc45b51b530023e0\n\nIn fact, the results were not just _bad_ but they were _significantly worse_.\n\nIt took me a long time to report these details because they just didn't make\nsense and I couldn't figure out what was going wrong. I'd be very grateful to\nanyone who could explore these WIP commits and point out what I'm doing wrong\nso I can learn and maybe we can get a boost to the feature.\n\nEven if we had strong data from these examples, I'm not sure that we'd want\nto add four bytes per object to the packing data, especially in a way that\nimpacts users that aren't even using the new feature. We would want to\nexplore options that use some kind of hashtable to map objects to their\n64-bit hash values, perhaps. It also affects the .bitmap file format, which\nwould need modification even for a new 32-bit hash function (though one of\nthe same size could be used by adding an extension saying \"I'm using hash\nfunction v2\" and leave the rest of the structure the same).\n\nI would also like to test the performance against the threaded version of the\n--path-walk feature, which I recently got working in my prototype branch [5].\n\n[5] \nhttps://github.com/derrickstolee/git/pull/28/commits/a9fc233390ae00e3d4b156be64d6b3974e30d8a1\n\nThanks,\n-Stolee\n"},{"id":"503099","messageId":"xmqqh6ab5mvb.fsf@gitster.g","threadId":"62085","inReplyTo":"5f52e2617654946c87fff0744393b984ccaab043.1726692381.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 1/6] pack-objects: add --full-name-hash option","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-09-19T21:56:08Z","receivedAt":"2024-09-19T21:56:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n> +static inline uint32_t pack_full_name_hash(const char *name)\n> +{\n> +\tconst uint32_t bigp = 1234572167U;\n> +\tuint32_t c, hash = bigp;\n> +\n> +\tif (!name)\n> +\t\treturn 0;\n> +\n> +\t/*\n> +\t * Do the simplest thing that will resemble pseduo-randomness: add\n\n\"pseduo\" -> \"pseudo\"\n\n> +\t * random multiples of a large prime number with a binary shift.\n> +\t * The goal is not to be cryptographic, but to be generally\n> +\t * uniformly distributed.\n> +\t */\n\nOther than that, there is no substantial difference since the\nprevious iteration; this step looks good.\n\nThanks.\n"},{"id":"503100","messageId":"xmqqcykz5mrg.fsf@gitster.g","threadId":"62085","inReplyTo":"999b1d094241b0ba8d6924ac6976eafc64c7d4a6.1726692382.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 5/6] p5313: add size comparison test","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-09-19T21:58:27Z","receivedAt":"2024-09-19T21:58:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n> From: Derrick Stolee <stolee@gmail.com>\n>\n> As custom options are added to 'git pack-objects' and 'git repack' to\n> adjust how compression is done, use this new performance test script to\n> demonstrate their effectiveness in performance and size.\n>\n> The recently-added --full-name-hash option swaps the default name-hash\n> algorithm with one that attempts to uniformly distribute the hashes\n> based on the full path name instead of the last 16 characters.\n>\n> This has a dramatic effect on full repacks for repositories with many\n> versions of most paths. It can have a negative impact on cases such as\n> pushing a single change.\n>\n> This can be seen by running pt5313 on the open source fluentui\n> repository [1]. Most commits will have this kind of output for the thin\n> and big pack cases, though certain commits (such as [2]) will have\n> problematic thin pack size for other reasons.\n>\n> [1] https://github.com/microsoft/fluentui\n> [2] a637a06df05360ce5ff21420803f64608226a875\n>\n> Checked out at the parent of [2], I see the following statistics:\n>\n> Test                                           this tree\n> ------------------------------------------------------------------\n> 5313.2: thin pack                              0.02(0.01+0.01)\n> 5313.3: thin pack size                                    1.1K\n> 5313.4: thin pack with --full-name-hash        0.02(0.01+0.00)\n> 5313.5: thin pack size with --full-name-hash              3.0K\n> 5313.6: big pack                               1.65(3.35+0.24)\n> 5313.7: big pack size                                    58.0M\n> 5313.8: big pack with --full-name-hash         1.53(2.52+0.18)\n> 5313.9: big pack size with --full-name-hash              57.6M\n> 5313.10: repack                                176.52(706.60+3.53)\n> 5313.11: repack size                                    446.7K\n> 5313.12: repack with --full-name-hash          37.47(134.18+3.06)\n> 5313.13: repack size with --full-name-hash              183.1K\n>\n> Note that this demonstrates a 3x size _increase_ in the case that\n> simulates a small \"git push\". The size change is neutral on the case of\n> pushing the difference between HEAD and HEAD~1000.\n>\n> However, the full repack case is both faster and more efficient.\n\nNice.\n\n> Signed-off-by: Derrick Stolee <stolee@gmail.com>\n> ---\n>  t/perf/p5313-pack-objects.sh | 71 ++++++++++++++++++++++++++++++++++++\n>  1 file changed, 71 insertions(+)\n>  create mode 100755 t/perf/p5313-pack-objects.sh\n\n\"wc -c\" -> \"test_file_size\" or \"test-tool path-utils file-size\"?\n"},{"id":"503101","messageId":"xmqq7cb75m62.fsf@gitster.g","threadId":"62085","inReplyTo":"48b87cccedb3d7920a3184ca86ca9eec77c0fd01.1726692381.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 2/6] repack: test --full-name-hash option","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-09-19T22:11:17Z","receivedAt":"2024-09-19T22:11:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n> The existing test_subcommand method requires an exact list of arguments\n> for the subcommand. This is too rigid for our needs here, so create a\n> new method, test_subcommand_flex. Use it to check that the\n> --full-name-hash option is passing through.\n\nThis is something I found need for in the past at least a few times.\n\n> +# Check that the given subcommand was run with the given set of\n> +# arguments in order (but with possible extra arguments).\n> +#\n> +#\ttest_subcommand_flex [!] <command> <args>... < <trace>\n> +#\n> +# If the first parameter passed is !, this instead checks that\n> +# the given command was not called.\n> +#\n> +test_subcommand_flex () {\n> +\tlocal negate=\n> +\tif test \"$1\" = \"!\"\n> +\tthen\n> +\t\tnegate=t\n> +\t\tshift\n> +\tfi\n> +\n> +\tlocal expr=\"$(printf '\"%s\".*' \"$@\")\"\n\nOK, so it works exactly like the comment said.  You allow arbigrary\ngarbage in between the given parameters that come in the order\ngiven.  As long as this is used to make sure that the flags are\npassed through, by somebody who knows how the code constructs the\ncommand line, this should be fine, as we won't be permuting the\ncommand line parameters.\n\nLooking good.\n\n\n> +\tif test -n \"$negate\"\n> +\tthen\n> +\t\t! grep \"\\[$expr\\]\"\n> +\telse\n> +\t\tgrep \"\\[$expr\\]\"\n> +\tfi\n> +}\n> +\n>  # Check that the given command was invoked as part of the\n>  # trace2-format trace on stdin.\n>  #\n"},{"id":"503102","messageId":"xmqq34lv5lnn.fsf@gitster.g","threadId":"62085","inReplyTo":"48b3876a10247d2ba65a6e5f1ff8ed3a662813f8.1726692381.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 3/6] pack-objects: add GIT_TEST_FULL_NAME_HASH","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-09-19T22:22:20Z","receivedAt":"2024-09-19T22:22:23Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n> From: Derrick Stolee <stolee@gmail.com>\n>\n> Add a new environment variable to opt-in to the --full-name-hash option\n> in 'git pack-objects'. This allows for extra testing of the feature\n> without repeating all of the test scenarios.\n\nThis also allows the programmer on the C implementation side to be a\nbit lazy, as the --full-name-hash option does not have to be plumbed\nthrough from the end-user facing commands (like \"bundle\") down to\nthe underlying \"pack-objects\" command ;-).\n\nAs an end-user facing tweak mechanism, an environment variable is\nthe most clunky, followed by a configuration variable (which can be\nused via \"git -c\" and exhibits the same clunkiness as an environment\nvariable), and a command line parameter is the most versatile in\nallowing users to customize the behaviour per-invocation of the\ncommands.  So in the longer term, we probably want to plumb through\nthe option, like you did for \"repack -> pack-objects\" call chain,\nfor all end-user visible commands that call into pack-objects.\n\nBut for testing purposes, the solution presented here is of course\ngood enough.\n\n> Second, there are two tests in t5616-partial-clone.sh that I believe are\n> actually broken scenarios. While the client is set up to clone the\n> 'promisor-server' repo via a treeless partial clone filter (tree:0),\n> that filter does not translate to the 'server' repo. Thus, fetching from\n> these repos causes the server to think that the client has all reachable\n> trees and blobs from the commits advertised as 'haves'. This leads the\n> server to providing a thin pack assuming those objects as delta bases.\n\nIn short, the tests are based on broken assumption and checking\nbogus outcome?  Somebody familiar with the partial clone area should\nprobably take a look into it and fix the tests if that is the case.\n\n> -\tif (write_bitmap_index && use_full_name_hash)\n> +\tif (write_bitmap_index && use_full_name_hash > 0)\n>  \t\tdie(_(\"currently, the --full-name-hash option is incompatible with --write-bitmap-index\"));\n> +\tif (use_full_name_hash < 0)\n> +\t\tuse_full_name_hash = git_env_bool(\"GIT_TEST_FULL_NAME_HASH\", 0);\n\nOK.\n"},{"id":"503233","messageId":"9cd3e993-3273-48af-9990-7a18c8bb668b@gmail.com","threadId":"62085","inReplyTo":"xmqq34lv5lnn.fsf@gitster.g","subject":"Re: [PATCH v2 3/6] pack-objects: add GIT_TEST_FULL_NAME_HASH","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-09-23T01:39:44Z","receivedAt":"2024-09-23T01:39:47Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 9/19/24 6:22 PM, Junio C Hamano wrote:\n > \"Derrick Stolee via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n >> Second, there are two tests in t5616-partial-clone.sh that I believe are\n >> actually broken scenarios. While the client is set up to clone the\n >> 'promisor-server' repo via a treeless partial clone filter (tree:0),\n >> that filter does not translate to the 'server' repo. Thus, fetching from\n >> these repos causes the server to think that the client has all reachable\n >> trees and blobs from the commits advertised as 'haves'. This leads the\n >> server to providing a thin pack assuming those objects as delta bases.\n >\n > In short, the tests are based on broken assumption and checking\n > bogus outcome?  Somebody familiar with the partial clone area should\n > probably take a look into it and fix the tests if that is the case.\n\nThat is my understanding, yes. It is a common issue that I've had when\nusing partial clones with multiple remotes and forgetting to modify the\nfilter for each, so is also a usability wart that could use mending\n(say, by adding the existing filter when adding a new remote).\n\nThanks,\n-Stolee\n\n"},{"id":"503234","messageId":"24d266e4-4279-42fa-871e-c843ba6d4f5e@gmail.com","threadId":"62085","inReplyTo":"xmqqcykz5mrg.fsf@gitster.g","subject":"Re: [PATCH v2 5/6] p5313: add size comparison test","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-09-23T01:50:07Z","receivedAt":"2024-09-23T01:50:11Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 9/19/24 5:58 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n>>   t/perf/p5313-pack-objects.sh | 71 ++++++++++++++++++++++++++++++++++++\n>>   1 file changed, 71 insertions(+)\n>>   create mode 100755 t/perf/p5313-pack-objects.sh\n> \n> \"wc -c\" -> \"test_file_size\" or \"test-tool path-utils file-size\"?\n\nThanks. I was unfamiliar with those options.\n\nI will squash this change into the next version. The use of a\nvariable for the packfile name was important at some point while\nI was testing this with various repos on different platforms.\n\n--- >8 ---\n\ndiff --git a/t/perf/p5313-pack-objects.sh b/t/perf/p5313-pack-objects.sh\nindex 5dcf52acb0..bf6f0d69e4 100755\n--- a/t/perf/p5313-pack-objects.sh\n+++ b/t/perf/p5313-pack-objects.sh\n@@ -25,7 +25,7 @@ test_perf 'thin pack' '\n  '\n\n  test_size 'thin pack size' '\n-\twc -c <out\n+\ttest_file_size out\n  '\n\n  test_perf 'thin pack with --full-name-hash' '\n@@ -33,7 +33,7 @@ test_perf 'thin pack with --full-name-hash' '\n  '\n\n  test_size 'thin pack size with --full-name-hash' '\n-\twc -c <out\n+\ttest_file_size out\n  '\n\n  test_perf 'big pack' '\n@@ -41,7 +41,7 @@ test_perf 'big pack' '\n  '\n\n  test_size 'big pack size' '\n-\twc -c <out\n+\ttest_file_size out\n  '\n\n  test_perf 'big pack with --full-name-hash' '\n@@ -49,7 +49,7 @@ test_perf 'big pack with --full-name-hash' '\n  '\n\n  test_size 'big pack size with --full-name-hash' '\n-\twc -c <out\n+\ttest_file_size out\n  '\n\n  test_perf 'repack' '\n@@ -57,7 +57,8 @@ test_perf 'repack' '\n  '\n\n  test_size 'repack size' '\n-\twc -c <.git/objects/pack/pack-*.pack\n+\tpack=$(ls .git/objects/pack/pack-*.pack) &&\n+\ttest_file_size \"$pack\"\n  '\n\n  test_perf 'repack with --full-name-hash' '\n@@ -65,7 +66,8 @@ test_perf 'repack with --full-name-hash' '\n  '\n\n  test_size 'repack size with --full-name-hash' '\n-\twc -c <.git/objects/pack/pack-*.pack\n+\tpack=$(ls .git/objects/pack/pack-*.pack) &&\n+\ttest_file_size \"$pack\"\n  '\n\n  test_done\n\n"},{"id":"503260","messageId":"xmqq4j665ov2.fsf@gitster.g","threadId":"62085","inReplyTo":"24d266e4-4279-42fa-871e-c843ba6d4f5e@gmail.com","subject":"Re: [PATCH v2 5/6] p5313: add size comparison test","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-09-23T16:14:25Z","receivedAt":"2024-09-23T16:14:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee <stolee@gmail.com> writes:\n\n> On 9/19/24 5:58 PM, Junio C Hamano wrote:\n>> \"Derrick Stolee via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n>\n>>>   t/perf/p5313-pack-objects.sh | 71 ++++++++++++++++++++++++++++++++++++\n>>>   1 file changed, 71 insertions(+)\n>>>   create mode 100755 t/perf/p5313-pack-objects.sh\n>> \"wc -c\" -> \"test_file_size\" or \"test-tool path-utils file-size\"?\n>\n> Thanks. I was unfamiliar with those options.\n\nI was, too ;-).  There are a few other test pieces that use \"wc -c\"\nto count bytes, but it made me a bit nervous to use it to count\nbytes in a binary file.\n\n>  test_size 'repack size' '\n> -\twc -c <.git/objects/pack/pack-*.pack\n> +\tpack=$(ls .git/objects/pack/pack-*.pack) &&\n> +\ttest_file_size \"$pack\"\n>  '\n\nI am perfectly fine (and actually even prefer) to pay the cost to\nfork \"ls\" here, but if you really wanted to avoid it, we could do\nsomething like\n\n\tpack=$(\n\t\tset x .git/objects/pack/pack-*.pack &&\n\t\ttest $# = 2 && echo \"$2\" || exit 1\n\t) &&\n\ttest_file_size \"$pack\"\n\n;-)\n\n>  test_perf 'repack with --full-name-hash' '\n> @@ -65,7 +66,8 @@ test_perf 'repack with --full-name-hash' '\n>  '\n>\n>  test_size 'repack size with --full-name-hash' '\n> -\twc -c <.git/objects/pack/pack-*.pack\n> +\tpack=$(ls .git/objects/pack/pack-*.pack) &&\n> +\ttest_file_size \"$pack\"\n>  '\n>\n>  test_done\n"},{"id":"503331","messageId":"ZvJj7PeB52m_1mG9@pks.im","threadId":"62085","inReplyTo":"7e47fc8cb53647ad92c86801204c3089a5dfe8e6.1726692382.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 6/6] test-tool: add helper for name-hash values","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-09-24T07:02:40Z","receivedAt":"2024-09-24T07:02:50Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Wed, Sep 18, 2024 at 08:46:21PM +0000, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee <stolee@gmail.com>\n> diff --git a/t/helper/test-name-hash.c b/t/helper/test-name-hash.c\n> new file mode 100644\n> index 00000000000..15fb8f853c1\n> --- /dev/null\n> +++ b/t/helper/test-name-hash.c\n> @@ -0,0 +1,23 @@\n> +/*\n> + * test-name-hash.c: Read a list of paths over stdin and report on their\n> + * name-hash and full name-hash.\n> + */\n> +\n> +#include \"test-tool.h\"\n> +#include \"git-compat-util.h\"\n> +#include \"pack-objects.h\"\n> +#include \"strbuf.h\"\n> +\n> +int cmd__name_hash(int argc UNUSED, const char **argv UNUSED)\n> +{\n> +\tstruct strbuf line = STRBUF_INIT;\n> +\n> +\twhile (!strbuf_getline(&line, stdin)) {\n> +\t\tuint32_t name_hash = pack_name_hash(line.buf);\n> +\t\tuint32_t full_hash = pack_full_name_hash(line.buf);\n> +\n> +\t\tprintf(\"%10\"PRIu32\"\\t%10\"PRIu32\"\\t%s\\n\", name_hash, full_hash, line.buf);\n> +\t}\n> +\n> +\treturn 0;\n> +}\n\nThis patch breaks t5310 with the leak sanitizer enabled due to the\nleaking `struct strbuf line`. It needs the following diff on top:\n\ndiff --git a/t/helper/test-name-hash.c b/t/helper/test-name-hash.c\nindex 15fb8f853c..e4ecd159b7 100644\n--- a/t/helper/test-name-hash.c\n+++ b/t/helper/test-name-hash.c\n@@ -19,5 +19,6 @@ int cmd__name_hash(int argc UNUSED, const char **argv UNUSED)\n \t\tprintf(\"%10\"PRIu32\"\\t%10\"PRIu32\"\\t%s\\n\", name_hash, full_hash, line.buf);\n \t}\n \n+\tstrbuf_release(&line);\n \treturn 0;\n }\n\nI also plan to eventually have a deeper look at your patch series, but\ndidn't yet find the time to do so until now :(\n\nPatrick\n"},{"id":"503466","messageId":"5bc7ba07-da0f-4a41-8979-e75221a747a7@gmail.com","threadId":"62085","inReplyTo":"ZvJj7PeB52m_1mG9@pks.im","subject":"Re: [PATCH v2 6/6] test-tool: add helper for name-hash values","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-09-25T13:35:25Z","receivedAt":"2024-09-25T13:35:29Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 9/24/24 3:02 AM, Patrick Steinhardt wrote:\n\n> This patch breaks t5310 with the leak sanitizer enabled due to the\n> leaking `struct strbuf line`. It needs the following diff on top:\n> \n> diff --git a/t/helper/test-name-hash.c b/t/helper/test-name-hash.c\n> index 15fb8f853c..e4ecd159b7 100644\n> --- a/t/helper/test-name-hash.c\n> +++ b/t/helper/test-name-hash.c\n> @@ -19,5 +19,6 @@ int cmd__name_hash(int argc UNUSED, const char **argv UNUSED)\n>   \t\tprintf(\"%10\"PRIu32\"\\t%10\"PRIu32\"\\t%s\\n\", name_hash, full_hash, line.buf);\n>   \t}\n>   \n> +\tstrbuf_release(&line);\n>   \treturn 0;\n>   }\n\nThanks! I'll make sure this gets in the next version.\n\n> I also plan to eventually have a deeper look at your patch series, but\n> didn't yet find the time to do so until now :(\nThanks for taking the time, when you have it.\n\n-Stolee\n\n"},{"id":"504114","messageId":"xmqqiku7d0ut.fsf@gitster.g","threadId":"62085","inReplyTo":"pull.1785.v2.git.1726692381.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 0/6] pack-objects: create new name-hash algorithm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-10-04T21:17:30Z","receivedAt":"2024-10-04T21:17:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n> I've been focused recently on understanding and mitigating the growth of a\n> few internal repositories. Some of these are growing much larger than\n> expected for the number of contributors, and there are multiple aspects to\n> why this growth is so large.\n> ...\n> Derrick Stolee (6):\n>   pack-objects: add --full-name-hash option\n>   repack: test --full-name-hash option\n>   pack-objects: add GIT_TEST_FULL_NAME_HASH\n>   git-repack: update usage to match docs\n>   p5313: add size comparison test\n>   test-tool: add helper for name-hash values\n\nRecent CI jobs on 'seen' has been failing the leak-check jobs, e.g.\n\n  https://github.com/git/git/actions/runs/11184876759/job/31096601111#step:4:1886\n\nshows that t5310 and t5334 are having problems.\n\nI randomly picked this topic and ejected it out of 'seen', and the\nresult is fairing a bit better. t5310 that failed 228/228 subtests\nin the above run is now passing.  I didn't run this topic alone\nunder the leak checker, so it is entirely possible that there are\nsome unfortunate interactions with other topics in flight.\n\nt5334 still fails 8/16 subtests just like the above run, exonerating\nthis topic for its breakage.\n\n  https://github.com/git/git/actions/runs/11186737635/job/31102378478#step:4:1880\n\n"},{"id":"504115","messageId":"ZwBsbW5jsFw0mxKk@nand.local","threadId":"62085","inReplyTo":"xmqqiku7d0ut.fsf@gitster.g","subject":"Re: [PATCH v2 0/6] pack-objects: create new name-hash algorithm","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-10-04T22:30:05Z","receivedAt":"2024-10-04T22:30:08Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Oct 04, 2024 at 02:17:30PM -0700, Junio C Hamano wrote:\n> t5334 still fails 8/16 subtests just like the above run, exonerating\n> this topic for its breakage.\n>\n>   https://github.com/git/git/actions/runs/11186737635/job/31102378478#step:4:1880\n\nThis is not all too surprising, since part two of the incremental MIDX\ntopic introduces some new leaks which were not seen by Patrick's recent\nleakfixes. So I expect that this broke with 9d4855eef3 (midx-write: fix\nleaking buffer, 2024-09-30), which marked t5534 as leak-free.\n\nAnd that's true, without the patches from tb/incremental-midx-part-2.\nThe leak stems from the fact that the 'bitmap_index' struct now has a\nnew optional \"base\" pointer, which points to another 'bitmap_index'\ncorresponding to the previous MIDX layer.\n\nThe fix is fairly straightforward, and should be limited to:\n\n--- 8< ---\nSubject: [PATCH] fixup! pack-bitmap.c: open and store incremental bitmap\n layers\n\nThe incremental MIDX bitmap work was done prior to 9d4855eef3\n(midx-write: fix leaking buffer, 2024-09-30), and causes test failures\nin t5334 in a post-9d4855eef3 world.\n\nThe leak looks like:\n\n    Direct leak of 264 byte(s) in 1 object(s) allocated from:\n        #0 0x7f6bcd87eaca in calloc ../../../../src/libsanitizer/lsan/lsan_interceptors.cpp:90\n        #1 0x55ad1428e8a4 in xcalloc wrapper.c:151\n        #2 0x55ad14199e16 in prepare_midx_bitmap_git pack-bitmap.c:742\n        #3 0x55ad14199447 in open_midx_bitmap_1 pack-bitmap.c:507\n        #4 0x55ad14199cca in open_midx_bitmap pack-bitmap.c:704\n        #5 0x55ad14199d44 in open_bitmap pack-bitmap.c:717\n        #6 0x55ad14199dc2 in prepare_bitmap_git pack-bitmap.c:733\n        #7 0x55ad1419e496 in test_bitmap_walk pack-bitmap.c:2698\n        #8 0x55ad14047b0b in cmd_rev_list builtin/rev-list.c:629\n        #9 0x55ad13f71cd6 in run_builtin git.c:487\n        #10 0x55ad13f72132 in handle_builtin git.c:756\n        #11 0x55ad13f72380 in run_argv git.c:826\n        #12 0x55ad13f728f4 in cmd_main git.c:961\n        #13 0x55ad1407d3ae in main common-main.c:64\n        #14 0x7f6bcd5f0c89 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58\n        #15 0x7f6bcd5f0d44 in __libc_start_main_impl ../csu/libc-start.c:360\n        #16 0x55ad13f6ff90 in _start (git+0x1ef90) (BuildId: 3e63cdd415f1d185b21da3035cb48332510dddce)\n\n, and is a result of us not freeing the resources corresponding to the\nbitmap's base layer, if one was present.\n\nRectify that leak by calling the newly-introduced free_bitmap_index()\nfunction on the base layer to ensure that its resources are also freed.\n\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\n pack-bitmap.c | 1 +\n 1 file changed, 1 insertion(+)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 2b4c3972e5..fe0df2b6c3 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -3045,6 +3045,7 @@ void free_bitmap_index(struct bitmap_index *b)\n \t\tclose_midx_revindex(b->midx);\n \t}\n \tfree_pseudo_merge_map(&b->pseudo_merges);\n+\tfree_bitmap_index(b->base);\n \tfree(b);\n }\n\n--\n2.47.0.rc1.154.ge6e38f19f35.dirty\n--- >8 ---\n\nThat should apply on top of 'seen' easily, and will at least fix the\nleak failures you pointed out here.\n\nWhen the integration branches are rewound after 2.47.0 is tagged, I'll\nsend a new version of this topic based on Patrick's work here.\n\nThanks,\nTaylor\n"},{"id":"504116","messageId":"20241004223502.GA580885@coredump.intra.peff.net","threadId":"62085","inReplyTo":"xmqqiku7d0ut.fsf@gitster.g","subject":"Re: [PATCH v2 0/6] pack-objects: create new name-hash algorithm","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-10-04T22:35:02Z","receivedAt":"2024-10-04T22:35:11Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Oct 04, 2024 at 02:17:30PM -0700, Junio C Hamano wrote:\n\n> > Derrick Stolee (6):\n> >   pack-objects: add --full-name-hash option\n> >   repack: test --full-name-hash option\n> >   pack-objects: add GIT_TEST_FULL_NAME_HASH\n> >   git-repack: update usage to match docs\n> >   p5313: add size comparison test\n> >   test-tool: add helper for name-hash values\n> \n> Recent CI jobs on 'seen' has been failing the leak-check jobs, e.g.\n> \n>   https://github.com/git/git/actions/runs/11184876759/job/31096601111#step:4:1886\n> \n> shows that t5310 and t5334 are having problems.\n> \n> I randomly picked this topic and ejected it out of 'seen', and the\n> result is fairing a bit better. t5310 that failed 228/228 subtests\n> in the above run is now passing.  I didn't run this topic alone\n> under the leak checker, so it is entirely possible that there are\n> some unfortunate interactions with other topics in flight.\n\nMaybe squash this into the final patch of that series?\n\ndiff --git a/t/helper/test-name-hash.c b/t/helper/test-name-hash.c\nindex 15fb8f853c..e4ecd159b7 100644\n--- a/t/helper/test-name-hash.c\n+++ b/t/helper/test-name-hash.c\n@@ -19,5 +19,6 @@ int cmd__name_hash(int argc UNUSED, const char **argv UNUSED)\n \t\tprintf(\"%10\"PRIu32\"\\t%10\"PRIu32\"\\t%s\\n\", name_hash, full_hash, line.buf);\n \t}\n \n+\tstrbuf_release(&line);\n \treturn 0;\n }\n\nThat seems to be enough to clear t5310 on \"seen\". It was not noticed in\nthe original topic because t5310 was not yet marked as leak-free in its\nbase. That happened in fa016423c7 (revision: fix leaking parents when\nsimplifying commits, 2024-09-26)\n\n-Peff\n"},{"id":"504470","messageId":"b5c65c3c-ae6d-4b56-aec6-846a1118c59b@gmail.com","threadId":"62085","inReplyTo":"pull.1785.v2.git.1726692381.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 0/6] pack-objects: create new name-hash algorithm","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-10-08T18:32:46Z","receivedAt":"2024-10-08T18:32:49Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 9/18/24 4:46 PM, Derrick Stolee via GitGitGadget wrote:\n> I've been focused recently on understanding and mitigating the growth of a\n> few internal repositories. Some of these are growing much larger than\n> expected for the number of contributors, and there are multiple aspects to\n> why this growth is so large.\n> \n> This is part of the RFC I submitted [1] [2] involving the path-walk API,\n> though this doesn't use the path-walk API directly. In full repack cases, it\n> seems that the --full-name-hash option gets nearly as good compression as\n> the --path-walk option introduced in that series. I continue to work on that\n> feature as well, so we can review it after this series is complete.\nBased on the discussion in this thread, I recommend pulling this branch out\nof 'seen' and instead focus on the --path-walk option which is now available\nat [3]. If we choose to revisit the --full-name-hash option, then that can\nbe done on top of that feature which is probably a higher priority.\n\n[3] https://lore.kernel.org/git/pull.1813.git.1728396723.gitgitgadget@gmail.com\n\nThanks,\n-Stolee\n\n"}]}