Re: [PATCH] sha1_file: avoid comparison if no packed hash matches the first byte

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

René Scharfe <l.s.r@web.de> writes:

> find_pack_entry_one() uses the fan-out table of pack indexes to find out
> which entries match the first byte of the searched hash and does a
> binary search on this subset of the main index table.
>
> If there are no matching entries then lo and hi will have the same
> value.  The binary search still starts and compares the hash of the
> following entry (which has a non-matching first byte, so won't cause any
> trouble), or whatever comes after the sorted list of entries.
>
> The probability of that stray comparison matching by mistake is low, but
> let's not take any chances and check when entering the binary search
> loop if we're actually done already.
>
> Signed-off-by: Rene Scharfe <l.s.r@web.de>
> ---
>  sha1_file.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/sha1_file.c b/sha1_file.c
> index b60ae15f70..11ee69a99d 100644
> --- a/sha1_file.c
> +++ b/sha1_file.c
> @@ -2799,7 +2799,7 @@ off_t find_pack_entry_one(const unsigned char *sha1,
>  		return nth_packed_object_offset(p, pos);
>  	}
>  
> -	do {
> +	while (lo < hi) {
>  		unsigned mi = (lo + hi) / 2;
>  		int cmp = hashcmp(index + mi * stride, sha1);
>  
> @@ -2812,7 +2812,7 @@ off_t find_pack_entry_one(const unsigned char *sha1,
>  			hi = mi;
>  		else
>  			lo = mi+1;
> -	} while (lo < hi);
> +	}
>  	return 0;
>  }

Interesting.  I see that we still have the conditional code to call
out to sha1-lookup.c::sha1_entry_pos().  Do we need a similar change
over there, I wonder?  Alternatively, as we have had the experimental
sha1-lookup.c::sha1_entry_pos() long enough without anybody using it,
perhaps we should write it off as a failed experiment and retire it?