Re: [PATCH v2 09/15] rev-list: allow commit-only bitmap traversals

From: Derrick Stolee <stolee@gmail.com>
To: Jeff King <peff@peff.net>, git@vger.kernel.org
Cc: Junio C Hamano <gitster@pobox.com>
Subject: Re: [PATCH v2 09/15] rev-list: allow commit-only bitmap traversals
Date: Tue, 18 Feb 2020 13:18:21 -0500	[thread overview]
Message-ID: <967821c8-aca4-52ff-8eb9-01a74f5a8144@gmail.com> (raw)
In-Reply-To: <20200214182227.GI150965@coredump.intra.peff.net>

On 2/14/2020 1:22 PM, Jeff King wrote:
> Here are numbers for linux.git:
> 
>   Test                         HEAD^               HEAD
>   ------------------------------------------------------------------------
>   5310.7: rev-list (commits)   8.29(8.10+0.19)       1.76(1.72+0.04) -78.8%
>   5310.8: rev-list (objects)   8.06(7.94+0.12)       8.14(7.94+0.13) +1.0%

Nice.

> That run was cheating a little, as I didn't have any commit-graph in the
> repository, and we'd built it by default these days when running git-gc.
> Here are numbers with a commit-graph:
> 
>   Test                         HEAD^               HEAD
>   ------------------------------------------------------------------------
>   5310.7: rev-list (commits)   0.70(0.58+0.12)     0.51(0.46+0.04) -27.1%
>   5310.8: rev-list (objects)   6.20(6.09+0.10)     6.27(6.16+0.11) +1.1%
> 
> Still an improvement, but a lot less impressive.

I think this is still impressive, because you are still allocating the
object structs and writing data to the output. The commit-graph code allows
cheating and doing very little work when navigating from one commit to
another. I suppose the biggest difference between these two approaches is
that the object cache contains "parsed" commits at the end (with allocated
parents and initialized commit times) and we needed a priority queue for
the commit walk. I'm impressed that this is still 27% improvement!

> diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh
> index b8645ae070..2c64d0c441 100755
> --- a/t/t5310-pack-bitmaps.sh
> +++ b/t/t5310-pack-bitmaps.sh
> @@ -80,6 +80,12 @@ rev_list_tests() {
>  		test_cmp expect actual
>  	'
>  
> +	test_expect_success "enumerate commits ($state)" '
> +		git rev-list --use-bitmap-index HEAD >actual &&
> +		git rev-list HEAD >expect &&
> +		test_bitmap_traversal --no-confirm-bitmaps expect actual
> +	'
> +

I was wondering if there is anything we could add to the "expect"
command that could better guarantee these commits show up in a
different order than the bitmap order, allowing us to drop the
"--no-confirm-bitmaps". Perhaps the issue is the merge structure
of the repository, and how it will cause these orders to always
agree?

I suppose "--topo-order" may actually present an order _even closer_
to the bitmap order.

Thanks,
-Stolee