threads / discuss / 27582

Sha1 lookup and GIT_USE_LOOKUP

Subject: Sha1 lookup and GIT_USE_LOOKUP

## tl;dr

4 messages between Jun 8, 2011 and Jun 9, 2011.

replies: 3people: 3as markdown or json

Marc Pegon· Jun 8, 2011, 18:31 UTC · lore

Hi, I noticed in find_pack_entry_one the use of the environment variable GIT_USE_LOOKUP, which does not seem to be used anywhere else in git or even in the tests.

Obviously, it determines whether or not a simple binary search or the sha1_entry_pos method (which is apparently some kind of improved binary search) should be used to retrieve the offset of an object (given its sha1) in a pack. Since this environment variable is not set by default, git will always use a simple binary search, won't it ?

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 ?

Thanks

-- Marc Pegon

Junio C Hamano· Jun 8, 2011, 18:55 UTC · re: Marc Pegon · lore

Re: Sha1 lookup and GIT_USE_LOOKUP

Marc Pegon <pegon.marc@gmail.com> 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.

Thanks.

Marc Pegon· Jun 9, 2011, 09:24 UTC · re: Junio C Hamano · lore

Re: Sha1 lookup and GIT_USE_LOOKUP

On Wed, Jun 8, 2011 at 8:55 PM, Junio C Hamano <gitster@pobox.com> wrote:

Show 19 quoted lines

> Marc Pegon <pegon.marc@gmail.com> 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 ?

> Thanks.
>

Michael Schubert· Jun 9, 2011, 22:51 UTC · re: Marc Pegon · lore

Re: Sha1 lookup and GIT_USE_LOOKUP

On 06/09/2011 11:24 AM, Marc Pegon wrote:

Show 27 quoted lines

> On Wed, Jun 8, 2011 at 8:55 PM, Junio C Hamano <gitster@pobox.com> wrote:
>> Marc Pegon <pegon.marc@gmail.com> 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:

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

dd453c