Re: [PATCH v3 3/3] pack-bitmap.c: use commit boundary during bitmap traversal

From: Derrick Stolee <derrickstolee@github.com>
Date: May 8, 2023, 20:53 UTC
Message-ID: <673a2b60-0556-fc2b-edf7-f2a19ef5dcbe@github.com>
In-Reply-To: <8a8f41e0c410f9160b8ff922333c13ed68f7334b.1683567065.git.me@ttaylorr.com>

On 5/8/2023 1:38 PM, Taylor Blau wrote:

Show 22 quoted lines

> -	/*
> -	 * 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;
> +	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;
> +	}

I was reading along, nodding my head, until I came across this comment. I recognize that it's moved from an existing place, but this seems very strange and incorrect.

Is this implying that if the 'haves' are not in the bitmapped pack, then we _can't_ construct a bitmap representing the objects they can reach?

Do we not have the ability to extend the object order beyond the bitmapped pack in-memory in a way that allows us to provide bit positions for the objects not in the bitmapped pack?

I can understand saying "it might be more expensive to construct a bitmap here, because we need to walk into the bitmapped pack before we have a hope of hitting a bitmap." However, that's far from "we don't have anything to optimize".

This comment is from fff42755efc (pack-bitmap: add support for bitmap indexes, 2013-12-21), and perhaps at that time we didn't have the ability to construct a reachability bitmap across the non-bitmapped pack.

Something to think about removing in the future, but not a blocker for
this series. Getting it out of the way for the boundary-based walk makes
even more sense because the commits to check are those in the boundary,
not the haves themselves.

Show 19 quoted lines

> +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"

This ordering (GIT_TEST_*=0 overrides config) seems backwards to me, but it doesn't really matter since it's a GIT_TEST_* variable. Thanks for including tests so the order is documented.

Show 5 quoted lines

> +	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

nit: you should be able to use 'test_region' here. Probably not worth a re-roll, as everything else looks good to me.

Thanks, -Stolee