Back in e37d0b8730 (builtin/index-pack.c: write reverse indexes, 2021-01-25), Git learned how to read and write a pack's reverse index from a file instead of in-memory. A pack's reverse index is a mapping from pack position (that is, the order that objects appear together in a ".pack") to their position in lexical order (that is, the order that objects are listed in an ".idx" file). Reverse indexes are consulted often during pack-objects, as well as during auxiliary operations that require mapping between pack offsets, pack order, and index index. They are useful in GitHub's infrastructure, where we have seen a dramatic increase in performance when writing ".rev" files[1]. In particular: - an ~80% reduction in the time it takes to serve fetches on a popular repository, Homebrew/homebrew-core. - a ~60% reduction in the peak memory usage to serve fetches on that same repository. - a collective savings of ~35% in CPU time across all pack-objects invocations serving fetches across all repositories in a single datacenter. Reverse indexes are also beneficial to end-users as well as forges. For example, the time it takes to generate a pack containing the objects for the 10 most recent commits in linux.git (representing a typical push) is significantly faster when on-disk reverse indexes are available: $ { git rev-parse HEAD && printf '^' && git rev-parse HEAD~10 } >in $ hyperfine -L v false,true 'git.compile -c pack.readReverseIndex={v} pack-objects --delta-base-offset --revs --stdout <in >/dev/null' Benchmark 1: git.compile -c pack.readReverseIndex=false pack-objects --delta-base-offset --revs --stdout <in >/dev/null Time (mean ± σ): 543.0 ms ± 20.3 ms [User: 616.2 ms, System: 58.8 ms] Range (min … max): 521.0 ms … 577.9 ms 10 runs Benchmark 2: git.compile -c pack.readReverseIndex=true pack-objects --delta-base-offset --revs --stdout <in >/dev/null Time (mean ± σ): 245.0 ms ± 11.4 ms [User: 335.6 ms, System: 31.3 ms] Range (min … max): 226.0 ms … 259.6 ms 13 runs Summary 'git.compile -c pack.readReverseIndex=true pack-objects --delta-base-offset --revs --stdout <in >/dev/null' ran 2.22 ± 0.13 times faster than 'git.compile -c pack.readReverseIndex=false pack-objects --delta-base-offset --revs --stdout <in >/dev/null' The same is true of writing a pack containing the objects for the 30 most-recent commits: $ { git rev-parse HEAD && printf '^' && git rev-parse HEAD~30 } >in $ hyperfine -L v false,true 'git.compile -c pack.readReverseIndex={v} pack-objects --delta-base-offset --revs --stdout <in >/dev/null' Benchmark 1: git.compile -c pack.readReverseIndex=false pack-objects --delta-base-offset --revs --stdout <in >/dev/null Time (mean ± σ): 866.5 ms ± 16.2 ms [User: 1414.5 ms, System: 97.0 ms] Range (min … max): 839.3 ms … 886.9 ms 10 runs Benchmark 2: git.compile -c pack.readReverseIndex=true pack-objects --delta-base-offset --revs --stdout <in >/dev/null Time (mean ± σ): 581.6 ms ± 10.2 ms [User: 1181.7 ms, System: 62.6 ms] Range (min … max): 567.5 ms … 599.3 ms 10 runs Summary 'git.compile -c pack.readReverseIndex=true pack-objects --delta-base-offset --revs --stdout <in >/dev/null' ran 1.49 ± 0.04 times faster than 'git.compile -c pack.readReverseIndex=false pack-objects --delta-base-offset --revs --stdout <in >/dev/null' ...and savings on trivial operations like computing the on-disk size of a single (packed) object are even more dramatic: $ git rev-parse HEAD >in $ hyperfine -L v false,true 'git.compile -c pack.readReverseIndex={v} cat-file --batch-check="%(objectsize:disk)" <in' Benchmark 1: git.compile -c pack.readReverseIndex=false cat-file --batch-check="%(objectsize:disk)" <in Time (mean ± σ): 305.8 ms ± 11.4 ms [User: 264.2 ms, System: 41.4 ms] Range (min … max): 290.3 ms … 331.1 ms 10 runs Benchmark 2: git.compile -c pack.readReverseIndex=true cat-file --batch-check="%(objectsize:disk)" <in Time (mean ± σ): 4.0 ms ± 0.3 ms [User: 1.7 ms, System: 2.3 ms] Range (min … max): 1.6 ms … 4.6 ms 1155 runs Summary 'git.compile -c pack.readReverseIndex=true cat-file --batch-check="%(objectsize:disk)" <in' ran 76.96 ± 6.25 times faster than 'git.compile -c pack.readReverseIndex=false cat-file --batch-check="%(objectsize:disk)" <in' In the more than two years since e37d0b8730 was merged, Git's implementation of on-disk reverse indexes has been thoroughly tested, both from users enabling `pack.writeReverseIndexes`, and from GitHub's deployment of the feature. The latter has been running without incident for more than two years. This patch changes Git's behavior to write on-disk reverse indexes by default when indexing a pack, which should make the above operations faster for everybody's Git installation after a repack. (The previous commit explains some potential drawbacks of using on-disk reverse indexes in certain limited circumstances, that essentially boil down to a trade-off between time to generate, and time to access. For those limited cases, the `pack.readReverseIndex` escape hatch can be used). [1]: https://github.blog/2021-04-29-scaling-monorepo-maintenance/#reverse-indexes Signed-off-by: Taylor Blau <me@xxxxxxxxxxxx> --- Documentation/config/pack.txt | 2 +- builtin/index-pack.c | 1 + builtin/pack-objects.c | 1 + t/perf/p5312-pack-bitmaps-revs.sh | 3 +-- t/t5325-reverse-index.sh | 1 + 5 files changed, 5 insertions(+), 3 deletions(-) diff --git a/Documentation/config/pack.txt b/Documentation/config/pack.txt index 7db7fed466..d4c7c9d4e4 100644 --- a/Documentation/config/pack.txt +++ b/Documentation/config/pack.txt @@ -182,4 +182,4 @@ pack.writeReverseIndex:: linkgit:gitformat-pack[5]) for each new packfile that it writes in all places except for linkgit:git-fast-import[1] and in the bulk checkin mechanism. - Defaults to false. + Defaults to true. diff --git a/builtin/index-pack.c b/builtin/index-pack.c index b17e79cd40..323c063f9d 100644 --- a/builtin/index-pack.c +++ b/builtin/index-pack.c @@ -1753,6 +1753,7 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix) fsck_options.walk = mark_link; reset_pack_idx_option(&opts); + opts.flags |= WRITE_REV; git_config(git_index_pack_config, &opts); if (prefix && chdir(prefix)) die(_("Cannot come back to cwd")); diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c index 77d88f85b0..dbaa04482f 100644 --- a/builtin/pack-objects.c +++ b/builtin/pack-objects.c @@ -4293,6 +4293,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix) } reset_pack_idx_option(&pack_idx_opts); + pack_idx_opts.flags |= WRITE_REV; git_config(git_pack_config, NULL); if (git_env_bool(GIT_TEST_WRITE_REV_INDEX, 0)) pack_idx_opts.flags |= WRITE_REV; diff --git a/t/perf/p5312-pack-bitmaps-revs.sh b/t/perf/p5312-pack-bitmaps-revs.sh index 0684b690af..ceec60656b 100755 --- a/t/perf/p5312-pack-bitmaps-revs.sh +++ b/t/perf/p5312-pack-bitmaps-revs.sh @@ -12,8 +12,7 @@ test_lookup_pack_bitmap () { test_perf_large_repo test_expect_success 'setup bitmap config' ' - git config pack.writebitmaps true && - git config pack.writeReverseIndex true + git config pack.writebitmaps true ' # we need to create the tag up front such that it is covered by the repack and diff --git a/t/t5325-reverse-index.sh b/t/t5325-reverse-index.sh index 66171c1d67..149dcf5193 100755 --- a/t/t5325-reverse-index.sh +++ b/t/t5325-reverse-index.sh @@ -14,6 +14,7 @@ packdir=.git/objects/pack test_expect_success 'setup' ' test_commit base && + test_config pack.writeReverseIndex false && pack=$(git pack-objects --all $packdir/pack) && rev=$packdir/pack-$pack.rev && -- 2.40.0.323.g9c80379958