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

From: Junio C Hamano <gitster@pobox.com>
Date: Mar 8, 2024, 00:40 UTC
Message-ID: <xmqq34t1k12p.fsf@gitster.g>
In-Reply-To: <xmqq7cidk4e4.fsf@gitster.g>

Junio C Hamano <gitster@pobox.com> writes:

Show 8 quoted lines

> Patrick Steinhardt <ps@pks.im> writes:
>
>> 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.

Show 6 quoted lines

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

Having said all that.

I have to wonder if it is the custom implementation of binsearch() the reftable/basic.c file has, not this particular comparison callback. It makes an unusual expectation on the comparison function, unlike bsearch(3) whose compar(a,b) is expected to return an answer with the same sign as "a - b".

I just checked the binary search loops we have in the core part of the system, like the one in hash-lookup.c (which takes advantage of the random and uniform nature of hashed values to converge faster than log2) and ones in builtin/pack-objects.c (both of which are absolute bog-standard). Luckily, we do not use such an unusual convention (well, we avoid overhead of compar callbacks to begin with, so it is a bit of apples-to-oranges comparison).