Re: [PATCH v2 2/2] reftable/block: fix binary search over restart counter

From: Junio C Hamano <gitster@pobox.com>
Date: Mar 7, 2024, 23:29 UTC
Message-ID: <xmqq7cidk4e4.fsf@gitster.g>
In-Reply-To: <370b608f9007abe9c0562d76894e2475d19867a1.1709843663.git.ps@pks.im>

Patrick Steinhardt <ps@pks.im> writes:

Show 11 quoted lines

> The consequence is that `binsearch()` essentially always returns 0,
> indicacting to us that we must start searching right at the beginning of
> the block. This works by chance because we now always do a linear scan
> from the start of the block, and thus we would still end up finding the
> desired record. But needless to say, this makes the optimization quite
> useless.
>
> Fix this bug by returning whether the current key is smaller than the
> searched key. As the current behaviour was correct it is not possible to
> write a test. Furthermore it is also not really possible to demonstrate
> in a benchmark that this fix speeds up seeking records.

This is an amusing bug.

I wonder if we inherited it from the original implementation---this was imported from jgit, right?

Thanks for a detailed write-up.

The "it is a fix, but the breakage is well hidden and cannot be observed only by checking for correctness" aspect of the bug deserves the unusually large "number of paragraphs explaining the change divided by number of changed lines" ratio ;-).

Applied.

Show 18 quoted lines

> Signed-off-by: Patrick Steinhardt <ps@pks.im>
> ---
>  reftable/block.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/reftable/block.c b/reftable/block.c
> index 72eb73b380..1663030386 100644
> --- a/reftable/block.c
> +++ b/reftable/block.c
> @@ -302,7 +302,7 @@ static int restart_key_less(size_t idx, void *args)
>  
>  	result = strbuf_cmp(&a->key, &rkey);
>  	strbuf_release(&rkey);
> -	return result;
> +	return result < 0;
>  }
>  
>  void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)