{"thread":{"id":"27582","subject":"Sha1 lookup and GIT_USE_LOOKUP","startedAt":"2011-06-08T18:31:15Z","lastAt":"2011-06-09T22:51:41Z","messageCount":4,"participants":["Marc Pegon","Junio C Hamano","Michael Schubert"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"169657","messageId":"BANLkTintTECbO5X3VMvzHdGgyKmLKe65YE=0mX6Ahj5wutCJ0Q@mail.gmail.com","threadId":"27582","inReplyTo":null,"subject":"Sha1 lookup and GIT_USE_LOOKUP","fromName":"Marc Pegon","fromEmail":"pegon.marc@gmail.com","sentAt":"2011-06-08T18:31:15Z","receivedAt":"2011-06-08T18:31:15Z","isPatch":false,"sender":{"key":"pegon.marc@gmail.com","avatar":null},"body":"Hi,\nI noticed in find_pack_entry_one the use of the environment variable\nGIT_USE_LOOKUP, which does not seem to be used anywhere else in git or\neven in the tests.\n\nObviously, it determines whether or not a simple binary search or the\nsha1_entry_pos method (which is apparently some kind of improved\nbinary search) should be used to retrieve the offset of an object\n(given its sha1) in a pack.\nSince this environment variable is not set by default, git will always\nuse a simple binary search, won't it ?\n\nAlso, when searching for a sha1 given a sha1 prefix, among packed\nobjects, find_short_packed_object also does a simple binary search.\nWouldn't it be simpler to just use the sha1_entry_pos method ?\n\nThanks\n\n--\nMarc Pegon\n"},{"id":"169679","messageId":"7v62og2lw1.fsf@alter.siamese.dyndns.org","threadId":"27582","inReplyTo":"BANLkTintTECbO5X3VMvzHdGgyKmLKe65YE=0mX6Ahj5wutCJ0Q@mail.gmail.com","subject":"Re: Sha1 lookup and GIT_USE_LOOKUP","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-06-08T18:55:42Z","receivedAt":"2011-06-08T18:55:42Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Marc Pegon writes:\n\n> Since this environment variable is not set by default, git will always\n> use a simple binary search, won't it ?\n\nYes.\n\n> Also, when searching for a sha1 given a sha1 prefix, among packed\n> objects, find_short_packed_object also does a simple binary search.\n> Wouldn't it be simpler to just use the sha1_entry_pos method ?\n\nUnknown ;-).\n\nThe environment variable is there exactly for people like you who are\ninterested in finding out which one yields better performance by\nbenchmarking. Once we can get a convincing result, we can either\ndeprecate the more involved sha1_entry_pos() if it turns out to be not\nworth it, or we can always use it if it turns out to be significantly\nbetter.\n\nThanks.\n"},{"id":"169749","messageId":"BANLkTi=b+WKy2_9VeEw5B0QqodHfVJs2XQ@mail.gmail.com","threadId":"27582","inReplyTo":"7v62og2lw1.fsf@alter.siamese.dyndns.org","subject":"Re: Sha1 lookup and GIT_USE_LOOKUP","fromName":"Marc Pegon","fromEmail":"pegon.marc@gmail.com","sentAt":"2011-06-09T09:24:15Z","receivedAt":"2011-06-09T09:24:15Z","isPatch":false,"sender":{"key":"pegon.marc@gmail.com","avatar":null},"body":"On Wed, Jun 8, 2011 at 8:55 PM, Junio C Hamano wrote:\n> Marc Pegon writes:\n>\n>> Since this environment variable is not set by default, git will always\n>> use a simple binary search, won't it ?\n>\n> Yes.\n>\n>> Also, when searching for a sha1 given a sha1 prefix, among packed\n>> objects, find_short_packed_object also does a simple binary search.\n>> Wouldn't it be simpler to just use the sha1_entry_pos method ?\n>\n> Unknown ;-).\n>\n> The environment variable is there exactly for people like you who are\n> interested in finding out which one yields better performance by\n> benchmarking.  Once we can get a convincing result, we can either\n> deprecate the more involved sha1_entry_pos() if it turns out to be not\n> worth it, or we can always use it if it turns out to be significantly\n> better.\n\nPerhaps we could compare the two methods by counting for each one the\naverage number of iterations it takes to find an object in a pack.\nBut anyways, I guess GIT_USE_LOOKUP should also have an influence on\nthe method used to find an object given a sha1 prefix, and the code\nthat does a simple binary search should not be duplicated as it is\nnow, right ?\n\n> Thanks.\n>\n"},{"id":"169823","messageId":"4DF14E7D.50809@elegosoft.com","threadId":"27582","inReplyTo":"BANLkTi=b+WKy2_9VeEw5B0QqodHfVJs2XQ@mail.gmail.com","subject":"Re: Sha1 lookup and GIT_USE_LOOKUP","fromName":"Michael Schubert","fromEmail":"mschub@elegosoft.com","sentAt":"2011-06-09T22:51:41Z","receivedAt":"2011-06-09T22:51:41Z","isPatch":false,"sender":{"key":"mschub@elegosoft.com","avatar":null},"body":"On 06/09/2011 11:24 AM, Marc Pegon wrote:\n> On Wed, Jun 8, 2011 at 8:55 PM, Junio C Hamano wrote:\n>> Marc Pegon writes:\n>>\n>>> Since this environment variable is not set by default, git will always\n>>> use a simple binary search, won't it ?\n>>\n>> Yes.\n>>\n>>> Also, when searching for a sha1 given a sha1 prefix, among packed\n>>> objects, find_short_packed_object also does a simple binary search.\n>>> Wouldn't it be simpler to just use the sha1_entry_pos method ?\n>>\n>> Unknown ;-).\n>>\n>> The environment variable is there exactly for people like you who are\n>> interested in finding out which one yields better performance by\n>> benchmarking. Once we can get a convincing result, we can either\n>> deprecate the more involved sha1_entry_pos() if it turns out to be not\n>> worth it, or we can always use it if it turns out to be significantly\n>> better.\n> \n> Perhaps we could compare the two methods by counting for each one the\n> average number of iterations it takes to find an object in a pack.\n> But anyways, I guess GIT_USE_LOOKUP should also have an influence on\n> the method used to find an object given a sha1 prefix, and the code\n> that does a simple binary search should not be duplicated as it is\n> now, right ?\n\nThe commit introducing sha1_entry_pos() comes with some reasoning:\n\n628522\n\nlibgit2 dropped \"old and boring binary search\" some days ago:\n\ndd453c\n"}]}