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

[Junio C Hamano <gitster@pobox.com>]

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

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

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