Subject: Re: Sha1 lookup and GIT_USE_LOOKUP

From: Michael Schubert <[email-masked]>
Date: Fri, 10 Jun 2011 00:51:41 +0200

On 06/09/2011 11:24 AM, Marc Pegon wrote:
> On Wed, Jun 8, 2011 at 8:55 PM, Junio C Hamano <[email-masked]> wrote:
>> Marc Pegon <[email-masked]> writes:
>>
>>> Since this environment variable is not set by default, git will always
>>> use a simple binary search, won't it ?
>>
>> Yes.
>>
>>> Also, when searching for a sha1 given a sha1 prefix, among packed
>>> objects, find_short_packed_object also does a simple binary search.
>>> Wouldn't it be simpler to just use the sha1_entry_pos method ?
>>
>> Unknown ;-).
>>
>> The environment variable is there exactly for people like you who are
>> interested in finding out which one yields better performance by
>> benchmarking.  Once we can get a convincing result, we can either
>> deprecate the more involved sha1_entry_pos() if it turns out to be not
>> worth it, or we can always use it if it turns out to be significantly
>> better.
> 
> Perhaps we could compare the two methods by counting for each one the
> average number of iterations it takes to find an object in a pack.
> But anyways, I guess GIT_USE_LOOKUP should also have an influence on
> the method used to find an object given a sha1 prefix, and the code
> that does a simple binary search should not be duplicated as it is
> now, right ?

The commit introducing sha1_entry_pos() comes with some reasoning:

628522

libgit2 dropped "old and boring binary search" some days ago:

dd453c