[PATCH v3 0/3] pack-bitmap: boundary-based bitmap traversal

[Taylor Blau <me@ttaylorr.com>]

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' '
-- 
2.40.1.479.g8f2b93ade7