# Sha1 lookup and GIT_USE_LOOKUP 4 messages from 2011-06-08 to 2011-06-09. Participants: Marc Pegon, Junio C Hamano, Michael Schubert. Thread: https://gitlist.dev/t/27582 ## Marc Pegon, 2011-06-08 18:31 Subject: Sha1 lookup and GIT_USE_LOOKUP Message-ID: URL: https://gitlist.dev/e/BANLkTintTECbO5X3VMvzHdGgyKmLKe65YE%3D0mX6Ahj5wutCJ0Q%40mail.gmail.com ``` 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, 2011-06-08 18:55 Subject: Re: Sha1 lookup and GIT_USE_LOOKUP Message-ID: <7v62og2lw1.fsf@alter.siamese.dyndns.org> URL: https://gitlist.dev/e/7v62og2lw1.fsf%40alter.siamese.dyndns.org In-Reply-To: ``` Marc Pegon 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, 2011-06-09 09:24 Subject: Re: Sha1 lookup and GIT_USE_LOOKUP Message-ID: URL: https://gitlist.dev/e/BANLkTi%3Db%2BWKy2_9VeEw5B0QqodHfVJs2XQ%40mail.gmail.com In-Reply-To: <7v62og2lw1.fsf@alter.siamese.dyndns.org> ``` On Wed, Jun 8, 2011 at 8:55 PM, Junio C Hamano wrote: > Marc Pegon 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, 2011-06-09 22:51 Subject: Re: Sha1 lookup and GIT_USE_LOOKUP Message-ID: <4DF14E7D.50809@elegosoft.com> URL: https://gitlist.dev/e/4DF14E7D.50809%40elegosoft.com In-Reply-To: ``` On 06/09/2011 11:24 AM, Marc Pegon wrote: > On Wed, Jun 8, 2011 at 8:55 PM, Junio C Hamano wrote: >> Marc Pegon 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 ```