Git's new name hash forgets where files moved
When Git packs a repository, it compresses most objects as deltas against similar objects, and it finds candidates by sorting everything by a hash of the file's path. Git 2.49 added a second version of that hash, --name-hash-version=2, to fix a real problem: in monorepos with over a hundred per-package changelog files with the same name, the old hash lumps them all together. On microsoft/fluentui, the repo the new hash was built for, it shrank my full repack from 582 MB to 191 MB. On golang/go it made the pack 4.3% bigger, and on babel 2.3% bigger. Version 2 loses two kinds of locality that version 1 had by accident: files that moved to another directory, and files whose names differ by one character, like versioned releases. The other new option, --path-walk, made the smallest pack on all five repos I tried, including fluentui.
How the hash picks delta bases
git pack-objects sorts objects by type, then by the 32-bit name hash, then by size, and tries each object against the 10 objects before it in that order (the --window). Two versions of a file can only become a delta pair if they sort within 10 of each other. Version 1, unchanged since 2006, is a few lines in pack-objects.h: for each character, hash = (hash >> 2) + (c << 24). Only the last 16 characters survive, and the last ones count most, so all .c files sort together, and a/foo.c and b/foo.c get the same or nearly the same hash. That's deliberate. The commit that added version 2 says the collisions are "somewhat by design" so that "the same file across a directory rename (a/foo.txt to b/foo.txt)" stays together. The catch is that a hundred unrelated files with the same name also stay together, and they crowd each file's real history out of the window.
Version 2 hashes each path component separately and, at every /, XORs the parent's hash, shifted down 6 bits, into the result. It also reverses the bits of every byte, because the low bits of a character vary the most. The commit says this keeps "some amount of hash locality", and the man page says version 2 "has similar locality features as version 1". In the code, the parent directory's hash lands on all but the top 6 of the 32 bits. So a/foo.c and b/foo.c agree only in those top 6 bits, which leaves roughly 1/64 of the repo's paths that could sort between them.
The test
I cloned five public repos and repacked each one from scratch three ways: git pack-objects --all --no-reuse-delta --no-reuse-object with the default hash, with --name-hash-version=2, and with --path-walk, using Git 2.54 with the default window of 10 and depth of 50. I checked a Python port of both hash functions against Git's C code on all 29,111 paths in Go's history; they matched. Repeating the Go runs changed sizes by 0.2% at most.
| Repo | v1 (default) | v2 | --path-walk |
|---|---|---|---|
| git/git | 144.9 MB | 144.9 MB (+0.01%) | 127.9 MB (−11.7%) |
| golang/go | 235.2 MB | 245.4 MB (+4.3%) | 221.2 MB (−6.0%) |
| facebook/react | 301.2 MB | 298.9 MB (−0.8%) | 264.8 MB (−12.1%) |
| babel/babel | 87.6 MB | 89.6 MB (+2.3%) | 78.8 MB (−10.1%) |
| microsoft/fluentui | 581.6 MB | 191.4 MB (−67.1%) | 173.0 MB (−70.3%) |
Version 2 is a large win in exactly one place, about a wash in two, and a loss in two. The authors' own benchmark in the performance-test commit shows the same pattern: fluentui went from 439 MB to 161 MB, and the Git repo got "slight bloat" because it "benefits a lot from cross-path delta pairs".
Loss one: directories that moved
In September 2014, Go moved the standard library from src/pkg/ to src/: 2,097 files changed directory in one commit. Across Go's whole history, 77% of renames keep exactly the same version-1 hash, because the last 16 characters didn't change. Under version 2, 24% do. Where the hash changes, the first copy of a file at its new path no longer sorts next to its old versions, so it can't be stored as a delta against them. Splitting the pack by path, the version-2 pack stored 857 more files from moved directories as whole objects and spent 5.4 MB more on them. A wider window didn't help: at --window=250, the setting git gc --aggressive uses, version 2 was still 5.7% bigger (215.8 MB against 204.1 MB).
Loss two: names that differ by one character
Babel's loss came from somewhere else. Babel commits each Yarn release it uses as its own file, .yarn/releases/yarn-4.1.0.cjs, yarn-4.1.1.cjs and so on, 1.6 to 3 MB each before compression. Version 1 deltified 14 of the 22 release files against each other. Version 2 deltified 3, and those files took 6.1 MB more. That's more than v2's 2.0 MB net loss on the whole pack; it won some of it back on package.json and test fixtures.
The cause is the bit reversal. '0' and '1' differ in their lowest bit. In version 1, that bit ends up low in the hash, so yarn-4.1.0.cjs and yarn-4.1.1.cjs are 65,536 apart. Reversed, it becomes the character's highest bit, and the gap grows to 8,388,608, 128 times as far. When I replayed pack-objects' sort order, version 1 put all the Yarn releases in one unbroken run, so each had up to 10 other releases in its window to choose a base from. Version 2 split them into small groups with unrelated files between them. No file had more than 3 other releases in its window, and 8 had none. Version 2 was designed to scatter names that differ only slightly, and these were names that differ only slightly.
Why path-walk wins both ways
--path-walk (Git 2.51) doesn't need a better hash. It first deltifies each exact path's versions against each other, so one package's changelog never competes with other packages' changelogs for its own history. Then it runs the normal sorted pass over the objects that still aren't deltas, mostly one base object per path, using the version-1 hash. Moved and versioned files get their cross-path chance there, with much less crowding than when every version of every file is in the list. It also helped directory trees a lot: on git/git, tree objects dropped from 36.1 MB to 25.7 MB. Running path-walk with version 2 underneath undid part of that on Go (231.2 MB against 221.2 MB), because the second pass then has the same blind spots.
There's a practical difference too: --write-bitmap-index forces version 1 back on with a warning, so a server that keeps reachability bitmaps can't use version 2 at all. git repack -adbf --path-walk wrote a bitmap without complaint.
What to do
If you're going to repack with a non-default option, use --path-walk (git repack -adf --path-walk, or pack.usePathWalk=true, which feature.experimental also turns on). It matched or beat version 2 on every repo here, including the one version 2 was designed for, and it doesn't cost you on repos with moved or versioned files. Use --name-hash-version=2 only if you've measured it on your own repo.
Versions: Git 2.54.0, with source read at git/git 6de20f6. Full repacks of all reachable objects with --no-reuse-delta --no-reuse-object, 8 threads, on macOS. MB here means 106 bytes of .pack file. Babel repacked with one thread gave the same direction (version 2 +3.6%) and the same Yarn result, so thread splitting isn't the cause. A clone you fetch is packed by the server's own settings, so these numbers apply to repacking, not to clone sizes.