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

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