| Message ID | cover.1683567065.git.me@ttaylorr.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | pack-bitmap: boundary-based bitmap traversal | expand |
Taylor Blau <me@ttaylorr.com> writes: > Here is another small reroll of my series to implement a boundary-based > bitmap traversal algorithm that I worked on towards the end of 2021 with > Peff. > > The algorithm is the same as in the last round, though I cleaned up a > few things throughout thanks to another very helpful review from Stolee. > > One significant change from last time is that the new algorithm is > opt-in behind feature.experimental, giving users a way to try out the > new implementation while still being able to switch back to the > known-good traversal in case anything goes wrong. It seems that the comments the topic received on the previous round have all been addressed adequately? Does everybody feel comfortable merging this topic to 'next'? Thanks.
On Wed, May 10, 2023 at 03:55:54PM -0700, Junio C Hamano wrote: > Taylor Blau <me@ttaylorr.com> writes: > > > Here is another small reroll of my series to implement a boundary-based > > bitmap traversal algorithm that I worked on towards the end of 2021 with > > Peff. > > > > The algorithm is the same as in the last round, though I cleaned up a > > few things throughout thanks to another very helpful review from Stolee. > > > > One significant change from last time is that the new algorithm is > > opt-in behind feature.experimental, giving users a way to try out the > > new implementation while still being able to switch back to the > > known-good traversal in case anything goes wrong. > > It seems that the comments the topic received on the previous round > have all been addressed adequately? Does everybody feel comfortable > merging this topic to 'next'? Thanks. I agree and think that this is ready to merge down. Even though it is changing the traversal algorithm, it should be relatively safe to merge since the new behavior is hidden behind an opt-in configuration option. Thanks, Taylor
On 5/10/2023 7:10 PM, Taylor Blau wrote: > On Wed, May 10, 2023 at 03:55:54PM -0700, Junio C Hamano wrote: >> Taylor Blau <me@ttaylorr.com> writes: >> >>> Here is another small reroll of my series to implement a boundary-based >>> bitmap traversal algorithm that I worked on towards the end of 2021 with >>> Peff. >>> >>> The algorithm is the same as in the last round, though I cleaned up a >>> few things throughout thanks to another very helpful review from Stolee. >>> >>> One significant change from last time is that the new algorithm is >>> opt-in behind feature.experimental, giving users a way to try out the >>> new implementation while still being able to switch back to the >>> known-good traversal in case anything goes wrong. >> >> It seems that the comments the topic received on the previous round >> have all been addressed adequately? Does everybody feel comfortable >> merging this topic to 'next'? > > Thanks. I agree and think that this is ready to merge down. Even though > it is changing the traversal algorithm, it should be relatively safe to > merge since the new behavior is hidden behind an opt-in configuration > option. Yes, I'm happy with this version. Thanks, -Stolee
Here is another small reroll of my series to implement a boundary-based bitmap traversal algorithm that I worked on towards the end of 2021 with Peff. The algorithm is the same as in the last round, though I cleaned up a few things throughout thanks to another very helpful review from Stolee. One significant change from last time is that the new algorithm is opt-in behind feature.experimental, giving users a way to try out the new implementation while still being able to switch back to the known-good traversal in case anything goes wrong. Hopefully after a version or two we can safely remove the conditional and drop the existing algorithm. Thanks in advance for your review. Taylor Blau (3): object: add object_array initializer helper function pack-bitmap.c: extract `fill_in_bitmap()` pack-bitmap.c: use commit boundary during bitmap traversal Documentation/config/feature.txt | 3 + Documentation/config/pack.txt | 17 +++ ci/run-build-and-tests.sh | 1 + object.c | 6 + object.h | 2 + pack-bitmap.c | 241 ++++++++++++++++++++++++++----- pack-bitmap.h | 4 + repo-settings.c | 7 +- repository.h | 1 + t/README | 4 + t/t5310-pack-bitmaps.sh | 38 +++++ 11 files changed, 284 insertions(+), 40 deletions(-) Range-diff against v2: -: ---------- > 1: c31508ac4a object: add object_array initializer helper function 1: a3a1522439 = 2: e7b30490da pack-bitmap.c: extract `fill_in_bitmap()` 2: 1993af00cb ! 3: 8a8f41e0c4 pack-bitmap.c: use commit boundary during bitmap traversal @@ Commit message the true number of objects in a similar fashion as the non-bitmap traversal): - # (Computing objects unique to 'master' among all branches, not - # using bitmaps). - $ time git rev-list --count --objects master --not --exclude=master --branches - 43 + # (Computing the number of tagged objects not on any branches + # without bitmaps). + $ time git rev-list --count --objects --tags --not --branches + 20 - real 0m0.346s - user 0m0.231s - sys 0m0.115s + real 0m1.388s + user 0m1.092s + sys 0m0.296s - # (Computing the same uniqueness query using the old bitmap - # traversal algorithm.) - $ time git rev-list --use-bitmap-index --count --objects master --not --exclude=master --branches - 41 + # (Computing the same query using the old bitmap traversal). + $ time git rev-list --count --objects --tags --not --branches --use-bitmap-index + 19 - real 0m20.007s - user 0m19.045s - sys 0m0.960s + real 0m22.709s + user 0m21.628s + sys 0m1.076s - # (Computing the same uniqueness query using the new bitmap - # traversal algorithm.) - $ time git.compile rev-list --use-bitmap-index --count --objects master --not --exclude=master --branches - 41 + # (this commit) + $ time git.compile rev-list --count --objects --tags --not --branches --use-bitmap-index + 19 - real 0m1.748s - user 0m1.428s - sys 0m0.320s + real 0m1.518s + user 0m1.234s + sys 0m0.284s The new algorithm is still slower than not using bitmaps at all, but it - is nearly a 11-fold improvement over the existing traversal. + is nearly a 15-fold improvement over the existing traversal. In a more realistic setting (using my local copy of git.git), I can observe a similar (if more modest) speed-up: - $ ours="$(git branch --show-current)" - argv="--count --objects $ours --not --exclude=$ours --branches" - hyperfine \ - -n 'no bitmaps' "git.compile rev-list $argv" \ - -n 'existing bitmap traversal' "git rev-list --use-bitmap-index $argv" \ - -n 'this commit' "git.compile rev-list --use-bitmap-index $argv" + $ argv="--count --objects --branches --not --tags" + hyperfine \ + -n 'no bitmaps' "git.compile rev-list $argv" \ + -n 'existing traversal' "git.compile rev-list --use-bitmap-index $argv" \ + -n 'boundary traversal' "git.compile -c pack.useBitmapBoundaryTraversal=true rev-list --use-bitmap-index $argv" Benchmark 1: no bitmaps - Time (mean ± σ): 5.8 ms ± 0.2 ms [User: 3.3 ms, System: 2.4 ms] - Range (min … max): 5.4 ms … 7.0 ms 409 runs + Time (mean ± σ): 124.6 ms ± 2.1 ms [User: 103.7 ms, System: 20.8 ms] + Range (min … max): 122.6 ms … 133.1 ms 22 runs - Benchmark 2: existing bitmap traversal - Time (mean ± σ): 65.3 ms ± 0.6 ms [User: 49.3 ms, System: 15.8 ms] - Range (min … max): 64.1 ms … 66.9 ms 45 runs + Benchmark 2: existing traversal + Time (mean ± σ): 368.6 ms ± 3.0 ms [User: 325.3 ms, System: 43.1 ms] + Range (min … max): 365.1 ms … 374.8 ms 10 runs - Benchmark 3: this commit - Time (mean ± σ): 19.8 ms ± 0.3 ms [User: 12.9 ms, System: 6.8 ms] - Range (min … max): 19.1 ms … 20.8 ms 150 runs + Benchmark 3: boundary traversal + Time (mean ± σ): 167.6 ms ± 0.9 ms [User: 139.5 ms, System: 27.9 ms] + Range (min … max): 166.1 ms … 169.2 ms 17 runs Summary 'no bitmaps' ran - 3.43 ± 0.14 times faster than 'this commit' - 11.34 ± 0.45 times faster than 'existing bitmap traversal' + 1.34 ± 0.02 times faster than 'boundary traversal' + 2.96 ± 0.05 times faster than 'existing traversal' Here, the new algorithm is also still slower than not using bitmaps, but - represents a more than 3-fold improvement over the existing traversal in + represents a more than 2-fold improvement over the existing traversal in a more modest example. Since this algorithm was originally written (nearly a year and a half @@ Commit message Helped-by: Derrick Stolee <derrickstolee@github.com> Signed-off-by: Taylor Blau <me@ttaylorr.com> + ## Documentation/config/feature.txt ## +@@ Documentation/config/feature.txt: feature.experimental:: + + + * `fetch.negotiationAlgorithm=skipping` may improve fetch negotiation times by + skipping more commits at a time, reducing the number of round trips. +++ ++* `pack.useBitmapBoundaryTraversal=true` may improve bitmap traversal times by ++walking fewer objects. + + feature.manyFiles:: + Enable config options that optimize for repos with many files in the + + ## Documentation/config/pack.txt ## +@@ Documentation/config/pack.txt: pack.useBitmaps:: + true. You should not generally need to turn this off unless + you are debugging pack bitmaps. + ++pack.useBitmapBoundaryTraversal:: ++ When true, Git will use an experimental algorithm for computing ++ reachability queries with bitmaps. Instead of building up ++ complete bitmaps for all of the negated tips and then OR-ing ++ them together, consider negated tips with existing bitmaps as ++ additive (i.e. OR-ing them into the result if they exist, ++ ignoring them otherwise), and build up a bitmap at the boundary ++ instead. +++ ++When using this algorithm, Git may include too many objects as a result ++of not opening up trees belonging to certain UNINTERESTING commits. This ++inexactness matches the non-bitmap traversal algorithm. +++ ++In many cases, this can provide a speed-up over the exact algorithm, ++particularly when there is poor bitmap coverage of the negated side of ++the query. ++ + pack.useSparse:: + When true, git will default to using the '--sparse' option in + 'git pack-objects' when the '--revs' option is present. This + + ## ci/run-build-and-tests.sh ## +@@ ci/run-build-and-tests.sh: linux-TEST-vars) + export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=master + export GIT_TEST_NO_WRITE_REV_INDEX=1 + export GIT_TEST_CHECKOUT_WORKERS=2 ++ export GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 + ;; + linux-clang) + export GIT_TEST_DEFAULT_HASH=sha1 + ## pack-bitmap.c ## @@ pack-bitmap.c: static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_git, return base; } -+static int obj_in_bitmap(struct bitmap_index *bitmap_git, -+ struct object *obj, struct bitmap *bitmap) -+{ -+ int pos; -+ -+ if (!bitmap) -+ return 0; -+ pos = bitmap_position(bitmap_git, &obj->oid); -+ if (pos < 0) -+ return 0; -+ return bitmap_get(bitmap, pos); -+} -+ +struct bitmap_boundary_cb { + struct bitmap_index *bitmap_git; + struct bitmap *base; @@ pack-bitmap.c: static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_ + add_object_array(&commit->object, "", &data->boundary); + + if (commit->object.flags & UNINTERESTING) { -+ if (obj_in_bitmap(data->bitmap_git, &commit->object, -+ data->base)) ++ if (bitmap_walk_contains(data->bitmap_git, data->base, ++ &commit->object.oid)) + return; + + add_commit_to_bitmap(data->bitmap_git, &data->base, commit); @@ pack-bitmap.c: static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_ + struct rev_info *revs, + struct object_list *roots) +{ -+ struct bitmap_boundary_cb cb = { .bitmap_git = bitmap_git }; ++ struct bitmap_boundary_cb cb; ++ struct object_list *root; + unsigned int i; + unsigned int tmp_blobs, tmp_trees, tmp_tags; + int any_missing = 0; + ++ cb.bitmap_git = bitmap_git; ++ cb.base = bitmap_new(); ++ object_array_init(&cb.boundary); ++ + revs->ignore_missing_links = 1; + + /* -+ * OR in any existing reachability bitmaps among `roots` into `base`. ++ * OR in any existing reachability bitmaps among `roots` into ++ * `cb.base`. + */ -+ while (roots) { -+ struct object *object = roots->item; -+ roots = roots->next; ++ for (root = roots; root; root = root->next) { ++ struct object *object = root->item; ++ if (object->type != OBJ_COMMIT || ++ bitmap_walk_contains(bitmap_git, cb.base, &object->oid)) ++ continue; + -+ if (object->type == OBJ_COMMIT && -+ !obj_in_bitmap(bitmap_git, object, cb.base) && -+ add_commit_to_bitmap(bitmap_git, &cb.base, -+ (struct commit *)object)) { -+ object->flags |= SEEN; ++ if (add_commit_to_bitmap(bitmap_git, &cb.base, ++ (struct commit *)object)) + continue; -+ } + + any_missing = 1; + } @@ pack-bitmap.c: static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_ + show_boundary_object, + &cb, NULL); + revs->boundary = 0; ++ trace2_region_leave("pack-bitmap", "boundary-traverse", the_repository); ++ + revs->blob_objects = tmp_blobs; + revs->tree_objects = tmp_trees; + revs->tag_objects = tmp_tags; + + reset_revision_walk(); + clear_object_flags(UNINTERESTING); -+ trace2_region_leave("pack-bitmap", "boundary-traverse", the_repository); + + /* + * Then add the boundary commit(s) as fill-in traversal tips. + */ + trace2_region_enter("pack-bitmap", "boundary-fill-in", the_repository); -+ if (cb.boundary.nr) { -+ struct object *obj; -+ int needs_walk = 0; -+ -+ for (i = 0; i < cb.boundary.nr; i++) { -+ obj = cb.boundary.objects[i].item; -+ -+ if (obj_in_bitmap(bitmap_git, obj, cb.base)) { -+ obj->flags |= SEEN; -+ } else { -+ add_pending_object(revs, obj, ""); -+ needs_walk = 1; -+ } -+ } -+ -+ if (needs_walk) -+ cb.base = fill_in_bitmap(bitmap_git, revs, cb.base, NULL); ++ for (i = 0; i < cb.boundary.nr; i++) { ++ struct object *obj = cb.boundary.objects[i].item; ++ if (bitmap_walk_contains(bitmap_git, cb.base, &obj->oid)) ++ obj->flags |= SEEN; ++ else ++ add_pending_object(revs, obj, ""); + } ++ if (revs->pending.nr) ++ cb.base = fill_in_bitmap(bitmap_git, revs, cb.base, NULL); + trace2_region_leave("pack-bitmap", "boundary-fill-in", the_repository); + -+ +cleanup: ++ object_array_clear(&cb.boundary); + revs->ignore_missing_links = 0; + + return cb.base; @@ pack-bitmap.c: static struct bitmap *find_objects(struct bitmap_index *bitmap_gi return base; } -@@ pack-bitmap.c: static void show_objects_for_type( - } - } +@@ pack-bitmap.c: struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs, + int filter_provided_objects) + { + unsigned int i; ++ int use_boundary_traversal; --static int in_bitmapped_pack(struct bitmap_index *bitmap_git, -- struct object_list *roots) --{ -- while (roots) { -- struct object *object = roots->item; -- roots = roots->next; -- -- if (bitmap_is_midx(bitmap_git)) { -- if (bsearch_midx(&object->oid, bitmap_git->midx, NULL)) -- return 1; -- } else { -- if (find_pack_entry_one(object->oid.hash, bitmap_git->pack) > 0) -- return 1; -- } -- } -- -- return 0; --} -- - static struct bitmap *find_tip_objects(struct bitmap_index *bitmap_git, - struct object_list *tip_objects, - enum object_type type) + struct object_list *wants = NULL; + struct object_list *haves = NULL; @@ pack-bitmap.c: struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs, object_list_insert(object, &wants); } @@ pack-bitmap.c: struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs, - */ - if (haves && !in_bitmapped_pack(bitmap_git, haves)) - goto cleanup; -- ++ use_boundary_traversal = git_env_bool(GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL, -1); ++ if (use_boundary_traversal < 0) { ++ prepare_repo_settings(revs->repo); ++ use_boundary_traversal = revs->repo->settings.pack_use_bitmap_boundary_traversal; ++ } ++ ++ if (!use_boundary_traversal) { ++ /* ++ * if we have a HAVES list, but none of those haves is contained ++ * in the packfile that has a bitmap, we don't have anything to ++ * optimize here ++ */ ++ if (haves && !in_bitmapped_pack(bitmap_git, haves)) ++ goto cleanup; ++ } + /* if we don't want anything, we're done here */ if (!wants) - goto cleanup; @@ pack-bitmap.c: struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs, if (load_bitmap(revs->repo, bitmap_git) < 0) goto cleanup; - object_array_clear(&revs->pending); -- ++ if (!use_boundary_traversal) ++ object_array_clear(&revs->pending); + if (haves) { - revs->ignore_missing_links = 1; - haves_bitmap = find_objects(bitmap_git, revs, haves, NULL); - reset_revision_walk(); - revs->ignore_missing_links = 0; -- -+ haves_bitmap = find_boundary_objects(bitmap_git, revs, haves); ++ if (use_boundary_traversal) { ++ trace2_region_enter("pack-bitmap", "haves/boundary", the_repository); ++ haves_bitmap = find_boundary_objects(bitmap_git, revs, haves); ++ trace2_region_leave("pack-bitmap", "haves/boundary", the_repository); ++ } else { ++ trace2_region_enter("pack-bitmap", "haves/classic", the_repository); ++ revs->ignore_missing_links = 1; ++ haves_bitmap = find_objects(bitmap_git, revs, haves, NULL); ++ reset_revision_walk(); ++ revs->ignore_missing_links = 0; ++ trace2_region_leave("pack-bitmap", "haves/classic", the_repository); ++ } + if (!haves_bitmap) BUG("failed to perform bitmap walk"); } -+ object_array_clear(&revs->pending); -+ reset_revision_walk(); ++ if (use_boundary_traversal) { ++ object_array_clear(&revs->pending); ++ reset_revision_walk(); ++ } + wants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap); if (!wants_bitmap) + + ## pack-bitmap.h ## +@@ pack-bitmap.h: void traverse_bitmap_commit_list(struct bitmap_index *, + void test_bitmap_walk(struct rev_info *revs); + int test_bitmap_commits(struct repository *r); + int test_bitmap_hashes(struct repository *r); ++ ++#define GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL \ ++ "GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL" ++ + struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs, + int filter_provided_objects); + uint32_t midx_preferred_pack(struct bitmap_index *bitmap_git); + + ## repo-settings.c ## +@@ repo-settings.c: void prepare_repo_settings(struct repository *r) + repo_cfg_bool(r, "feature.experimental", &experimental, 0); + + /* Defaults modified by feature.* */ +- if (experimental) ++ if (experimental) { + r->settings.fetch_negotiation_algorithm = FETCH_NEGOTIATION_SKIPPING; ++ r->settings.pack_use_bitmap_boundary_traversal = 1; ++ } + if (manyfiles) { + r->settings.index_version = 4; + r->settings.index_skip_hash = 1; +@@ repo-settings.c: void prepare_repo_settings(struct repository *r) + repo_cfg_bool(r, "index.sparse", &r->settings.sparse_index, 0); + repo_cfg_bool(r, "index.skiphash", &r->settings.index_skip_hash, r->settings.index_skip_hash); + repo_cfg_bool(r, "pack.readreverseindex", &r->settings.pack_read_reverse_index, 1); ++ repo_cfg_bool(r, "pack.usebitmapboundarytraversal", ++ &r->settings.pack_use_bitmap_boundary_traversal, ++ r->settings.pack_use_bitmap_boundary_traversal); + + /* + * The GIT_TEST_MULTI_PACK_INDEX variable is special in that + + ## repository.h ## +@@ repository.h: struct repo_settings { + int command_requires_full_index; + int sparse_index; + int pack_read_reverse_index; ++ int pack_use_bitmap_boundary_traversal; + + struct fsmonitor_settings *fsmonitor; /* lazily loaded */ + + + ## t/README ## +@@ t/README: GIT_TEST_INDEX_VERSION=<n> exercises the index read/write code path + for the index version specified. Can be set to any valid version + (currently 2, 3, or 4). + ++GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=<boolean> if enabled will ++use the boundary-based bitmap traversal algorithm. See the documentation ++of `pack.useBitmapBoundaryTraversal` for more details. ++ + GIT_TEST_PACK_SPARSE=<boolean> if disabled will default the pack-objects + builtin to use the non-sparse object walk. This can still be overridden by + the --sparse command-line argument. + + ## t/t5310-pack-bitmaps.sh ## +@@ t/t5310-pack-bitmaps.sh: test_description='exercise basic bitmap functionality' + # their place. + GIT_TEST_MULTI_PACK_INDEX_WRITE_BITMAP=0 + ++# Likewise, allow individual tests to control whether or not they use ++# the boundary-based traversal. ++sane_unset GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL ++ + objpath () { + echo ".git/objects/$(echo "$1" | sed -e 's|\(..\)|\1/|')" + } +@@ t/t5310-pack-bitmaps.sh: test_bitmap_cases () { + + test_bitmap_cases + ++GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 ++export GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL ++ ++test_bitmap_cases ++ ++sane_unset GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL ++ + test_expect_success 'incremental repack fails when bitmaps are requested' ' + test_commit more-1 && + test_must_fail git repack -d 2>err && +@@ t/t5310-pack-bitmaps.sh: test_expect_success 'incremental repack can disable bitmaps' ' + git repack -d --no-write-bitmap-index + ' + ++test_expect_success 'boundary-based traversal is used when requested' ' ++ git repack -a -d --write-bitmap-index && ++ ++ for argv in \ ++ "git -c pack.useBitmapBoundaryTraversal=true" \ ++ "git -c feature.experimental=true" \ ++ "GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 git" ++ do ++ eval "GIT_TRACE2_EVENT=1 $argv rev-list --objects \ ++ --use-bitmap-index second..other 2>perf" && ++ grep "\"region_enter\".*\"label\":\"haves/boundary\"" perf || ++ return 1 ++ done && ++ ++ for argv in \ ++ "git -c pack.useBitmapBoundaryTraversal=false" \ ++ "git -c feature.experimental=true -c pack.useBitmapBoundaryTraversal=false" \ ++ "GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=0 git -c pack.useBitmapBoundaryTraversal=true" \ ++ "GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=0 git -c feature.experimental=true" ++ do ++ eval "GIT_TRACE2_EVENT=1 $argv rev-list --objects \ ++ --use-bitmap-index second..other 2>perf" && ++ grep "\"region_enter\".*\"label\":\"haves/classic\"" perf || ++ return 1 ++ done ++' ++ + test_bitmap_cases "pack.writeBitmapLookupTable" + + test_expect_success 'verify writing bitmap lookup table when enabled' '