{"thread":{"id":"46544","subject":"[PATCH] sha1_file: avoid comparison if no packed hash matches the first byte","startedAt":"2017-08-08T22:07:43Z","lastAt":"2017-08-09T21:09:54Z","messageCount":14,"participants":["René Scharfe","Jonathan Nieder","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"325865","messageId":"0c1f898c-46c4-033d-001b-114b17d7d36f@web.de","threadId":"46544","inReplyTo":null,"subject":"[PATCH] sha1_file: avoid comparison if no packed hash matches the first byte","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-08-08T22:07:30Z","receivedAt":"2017-08-08T22:07:43Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"find_pack_entry_one() uses the fan-out table of pack indexes to find out\nwhich entries match the first byte of the searched hash and does a\nbinary search on this subset of the main index table.\n\nIf there are no matching entries then lo and hi will have the same\nvalue. The binary search still starts and compares the hash of the\nfollowing entry (which has a non-matching first byte, so won't cause any\ntrouble), or whatever comes after the sorted list of entries.\n\nThe probability of that stray comparison matching by mistake is low, but\nlet's not take any chances and check when entering the binary search\nloop if we're actually done already.\n\nSigned-off-by: Rene Scharfe \n---\n sha1_file.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex b60ae15f70..11ee69a99d 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -2799,7 +2799,7 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \t\treturn nth_packed_object_offset(p, pos);\n \t}\n \n-\tdo {\n+\twhile (lo < hi) {\n \t\tunsigned mi = (lo + hi) / 2;\n \t\tint cmp = hashcmp(index + mi * stride, sha1);\n \n@@ -2812,7 +2812,7 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \t\t\thi = mi;\n \t\telse\n \t\t\tlo = mi+1;\n-\t} while (lo < hi);\n+\t}\n \treturn 0;\n }\n \n-- \n2.14.0\n\n"},{"id":"325875","messageId":"20170808224114.GD169894@aiede.mtv.corp.google.com","threadId":"46544","inReplyTo":"0c1f898c-46c4-033d-001b-114b17d7d36f@web.de","subject":"Re: [PATCH] sha1_file: avoid comparison if no packed hash matches the first byte","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2017-08-08T22:41:14Z","receivedAt":"2017-08-08T22:41:51Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"René Scharfe wrote:\n\n> find_pack_entry_one() uses the fan-out table of pack indexes to find out\n> which entries match the first byte of the searched hash and does a\n> binary search on this subset of the main index table.\n>\n> If there are no matching entries then lo and hi will have the same\n> value. The binary search still starts and compares the hash of the\n> following entry (which has a non-matching first byte, so won't cause any\n> trouble), or whatever comes after the sorted list of entries.\n>\n> The probability of that stray comparison matching by mistake is low, but\n> let's not take any chances and check when entering the binary search\n> loop if we're actually done already.\n>\n> Signed-off-by: Rene Scharfe \n> ---\n> sha1_file.c | 4 ++--\n> 1 file changed, 2 insertions(+), 2 deletions(-)\n\nThanks for a clear explanation.\n\nSanity checking: is this correct in the sha1[0] == 0 case? In that\ncase, we have lo = 0, hi = the 0th offset from the fanout table. The\noffsets in the fanout table are defined as \"the number of objects in\nthe corresponding pack, the first byte of whose object name is less\nthan or equal to N.\" So hi == lo would mean there are no objects with\nid starting with 0, as hoped.\n\nOr in other words, the [lo, hi) interval we're trying to search is\nindeed a half-open interval.\n\nReviewed-by: Jonathan Nieder \n"},{"id":"325876","messageId":"xmqq3791adfi.fsf@gitster.mtv.corp.google.com","threadId":"46544","inReplyTo":"0c1f898c-46c4-033d-001b-114b17d7d36f@web.de","subject":"Re: [PATCH] sha1_file: avoid comparison if no packed hash matches the first byte","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-08-08T22:43:13Z","receivedAt":"2017-08-08T22:43:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> find_pack_entry_one() uses the fan-out table of pack indexes to find out\n> which entries match the first byte of the searched hash and does a\n> binary search on this subset of the main index table.\n>\n> If there are no matching entries then lo and hi will have the same\n> value. The binary search still starts and compares the hash of the\n> following entry (which has a non-matching first byte, so won't cause any\n> trouble), or whatever comes after the sorted list of entries.\n>\n> The probability of that stray comparison matching by mistake is low, but\n> let's not take any chances and check when entering the binary search\n> loop if we're actually done already.\n>\n> Signed-off-by: Rene Scharfe \n> ---\n> sha1_file.c | 4 ++--\n> 1 file changed, 2 insertions(+), 2 deletions(-)\n>\n> diff --git a/sha1_file.c b/sha1_file.c\n> index b60ae15f70..11ee69a99d 100644\n> --- a/sha1_file.c\n> +++ b/sha1_file.c\n> @@ -2799,7 +2799,7 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n> \t\treturn nth_packed_object_offset(p, pos);\n> \t}\n> \n> -\tdo {\n> +\twhile (lo < hi) {\n> \t\tunsigned mi = (lo + hi) / 2;\n> \t\tint cmp = hashcmp(index + mi * stride, sha1);\n> \n> @@ -2812,7 +2812,7 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n> \t\t\thi = mi;\n> \t\telse\n> \t\t\tlo = mi+1;\n> -\t} while (lo < hi);\n> +\t}\n> \treturn 0;\n> }\n\nInteresting. I see that we still have the conditional code to call\nout to sha1-lookup.c::sha1_entry_pos(). Do we need a similar change\nover there, I wonder? Alternatively, as we have had the experimental\nsha1-lookup.c::sha1_entry_pos() long enough without anybody using it,\nperhaps we should write it off as a failed experiment and retire it?\n\n"},{"id":"325877","messageId":"20170808225231.3l7gyoxxvghsvtv7@sigill.intra.peff.net","threadId":"46544","inReplyTo":"xmqq3791adfi.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] sha1_file: avoid comparison if no packed hash matches the first byte","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-08-08T22:52:31Z","receivedAt":"2017-08-08T22:52:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Aug 08, 2017 at 03:43:13PM -0700, Junio C Hamano wrote:\n\n> > @@ -2812,7 +2812,7 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n> > \t\t\thi = mi;\n> > \t\telse\n> > \t\t\tlo = mi+1;\n> > -\t} while (lo < hi);\n> > +\t}\n> > \treturn 0;\n> > }\n> \n> Interesting. I see that we still have the conditional code to call\n> out to sha1-lookup.c::sha1_entry_pos(). Do we need a similar change\n> over there, I wonder? Alternatively, as we have had the experimental\n> sha1-lookup.c::sha1_entry_pos() long enough without anybody using it,\n> perhaps we should write it off as a failed experiment and retire it?\n\nThere is also sha1_pos(), which seems to have the same problem (and is\nused in several places).\n\n-Peff\n"},{"id":"325878","messageId":"20170808225851.kgbyrlqrtlurzc73@sigill.intra.peff.net","threadId":"46544","inReplyTo":"20170808225231.3l7gyoxxvghsvtv7@sigill.intra.peff.net","subject":"Re: [PATCH] sha1_file: avoid comparison if no packed hash matches the first byte","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-08-08T22:58:51Z","receivedAt":"2017-08-08T22:58:58Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Aug 08, 2017 at 06:52:31PM -0400, Jeff King wrote:\n\n> > Interesting. I see that we still have the conditional code to call\n> > out to sha1-lookup.c::sha1_entry_pos(). Do we need a similar change\n> > over there, I wonder? Alternatively, as we have had the experimental\n> > sha1-lookup.c::sha1_entry_pos() long enough without anybody using it,\n> > perhaps we should write it off as a failed experiment and retire it?\n> \n> There is also sha1_pos(), which seems to have the same problem (and is\n> used in several places).\n\nActually, I take it back. The problem happens when we enter the loop\nwith no entries to look at. But both sha1_pos() and sha1_entry_pos()\nreturn early before hitting their do-while loops in that case.\n\n-Peff\n"},{"id":"325916","messageId":"xmqqpoc58fq6.fsf@gitster.mtv.corp.google.com","threadId":"46544","inReplyTo":"20170808225851.kgbyrlqrtlurzc73@sigill.intra.peff.net","subject":"Re: [PATCH] sha1_file: avoid comparison if no packed hash matches the first byte","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-08-09T05:36:33Z","receivedAt":"2017-08-09T05:36:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Tue, Aug 08, 2017 at 06:52:31PM -0400, Jeff King wrote:\n>\n>> > Interesting. I see that we still have the conditional code to call\n>> > out to sha1-lookup.c::sha1_entry_pos(). Do we need a similar change\n>> > over there, I wonder? Alternatively, as we have had the experimental\n>> > sha1-lookup.c::sha1_entry_pos() long enough without anybody using it,\n>> > perhaps we should write it off as a failed experiment and retire it?\n>> \n>> There is also sha1_pos(), which seems to have the same problem (and is\n>> used in several places).\n>\n> Actually, I take it back. The problem happens when we enter the loop\n> with no entries to look at. But both sha1_pos() and sha1_entry_pos()\n> return early before hitting their do-while loops in that case.\n\nAh, I was not looking at that part of the code. Thanks.\n\nI still wonder if we want to retire that conditional invocation of\nsha1_entry_pos(), though.\n"},{"id":"325928","messageId":"20170809092005.tnazbnbgn4piv76r@sigill.intra.peff.net","threadId":"46544","inReplyTo":"xmqqpoc58fq6.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] sha1_file: avoid comparison if no packed hash matches the first byte","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-08-09T09:20:05Z","receivedAt":"2017-08-09T09:20:15Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Aug 08, 2017 at 10:36:33PM -0700, Junio C Hamano wrote:\n\n> > Actually, I take it back. The problem happens when we enter the loop\n> > with no entries to look at. But both sha1_pos() and sha1_entry_pos()\n> > return early before hitting their do-while loops in that case.\n> \n> Ah, I was not looking at that part of the code. Thanks.\n> \n> I still wonder if we want to retire that conditional invocation of\n> sha1_entry_pos(), though.\n\nI think so. Digging in the list for it, almost every mention is either\nsomebody asking \"should we scrap this?\" or somebody showing benchmarks\nin which it is slower than the normal lookup (and then somebody asking\n\"should we scrap this\" :) ).\n\nI just re-ran a simple benchmark and it is indeed slower. I also came\nacross the hashcmp open-code-versus-memcmp discussion, which shows that\nthe memcmp in recent glibc is much faster. That has been around long\nenough that it's probably worth switching to.\n\n-Peff\n"},{"id":"325930","messageId":"20170809101106.p45y34uk6wcruqxv@sigill.intra.peff.net","threadId":"46544","inReplyTo":"20170809092005.tnazbnbgn4piv76r@sigill.intra.peff.net","subject":"Re: [PATCH] sha1_file: avoid comparison if no packed hash matches the first byte","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-08-09T10:11:07Z","receivedAt":"2017-08-09T10:11:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 09, 2017 at 05:20:05AM -0400, Jeff King wrote:\n\n> > I still wonder if we want to retire that conditional invocation of\n> > sha1_entry_pos(), though.\n> \n> I think so. Digging in the list for it, almost every mention is either\n> somebody asking \"should we scrap this?\" or somebody showing benchmarks\n> in which it is slower than the normal lookup (and then somebody asking\n> \"should we scrap this\" :) ).\n> \n> I just re-ran a simple benchmark and it is indeed slower. I also came\n> across the hashcmp open-code-versus-memcmp discussion, which shows that\n> the memcmp in recent glibc is much faster. That has been around long\n> enough that it's probably worth switching to.\n\nSo here are two patches (on top of René's since there is otherwise a\nminor textual conflict).\n\n [1/2]: sha1_file: drop experimental GIT_USE_LOOKUP search\n [2/2]: hashcmp: use memcmp instead of open-coded loop\n\n cache.h | 9 +-\n sha1-lookup.c | 216 --------------------------------------\n sha1_file.c | 11 --\n t/t5308-pack-detect-duplicates.sh | 11 +-\n t/test-lib.sh | 1 -\n 5 files changed, 2 insertions(+), 246 deletions(-)\n\n-Peff\n"},{"id":"325931","messageId":"20170809101432.6jquwmev423o56pb@sigill.intra.peff.net","threadId":"46544","inReplyTo":"20170809101106.p45y34uk6wcruqxv@sigill.intra.peff.net","subject":"[PATCH 1/2] sha1_file: drop experimental GIT_USE_LOOKUP search","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-08-09T10:14:32Z","receivedAt":"2017-08-09T10:14:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Long ago in 628522ec14 (sha1-lookup: more memory efficient\nsearch in sorted list of SHA-1, 2007-12-29) we added\nsha1_entry_pos(), a binary search that uses the uniform\ndistribution of sha1s to scale the selection of mid-points.\nAs this was a performance experiment, we tied it to the\nGIT_USE_LOOKUP environment variable and never enabled it by\ndefault.\n\nThis code was successful in reducing the number of steps in\neach search. But the overhead of the scaling ends up making\nit slower when the cache is warm. Here are best-of-five\ntimings for running rev-list on linux.git, which will have\nto look up every object:\n\n $ time git rev-list --objects --all >/dev/null\n real\t0m35.357s\n user\t0m35.016s\n sys\t0m0.340s\n\n $ time GIT_USE_LOOKUP=1 git rev-list --objects --all >/dev/null\n real\t0m37.364s\n user\t0m37.045s\n sys\t0m0.316s\n\nThe USE_LOOKUP version might have more benefit on a cold\ncache, as the time to fault in each page would dominate. But\nthat would be for a single lookup. In practice, most\noperations tend to look up many objects, and the whole pack\n.idx will end up warm.\n\nIt's possible that the code could be better optimized to\ncompete with a naive binary search for the warm-cache case,\nand we could have the best of both worlds. But over the\nyears nobody has done so, and this is largely dead code that\nis rarely run outside of the test suite. Let's drop it in\nthe name of simplicity.\n\nThis lets us remove sha1_entry_pos() entirely, as the .idx\nlookup code was the only caller. Note that sha1-lookup.c\nstill contains sha1_pos(), which differs from\nsha1_entry_pos() in two ways:\n\n - it has a different interface; it uses a function pointer\n to access sha1 entries rather than a size/offset pair\n describing the table's memory layout\n\n - it only scales the initial selection of \"mi\", rather\n than each iteration of the search\n\nWe can't get rid of this function, as it's called from\nseveral places. It may be that we could replace it with a\nsimple binary search, but that's out of scope for this patch\n(and would need benchmarking).\n\nSigned-off-by: Jeff King \n---\n sha1-lookup.c | 216 --------------------------------------\n sha1_file.c | 11 --\n t/t5308-pack-detect-duplicates.sh | 11 +-\n t/test-lib.sh | 1 -\n 4 files changed, 1 insertion(+), 238 deletions(-)\n\ndiff --git a/sha1-lookup.c b/sha1-lookup.c\nindex 5f069214d9..2552b7902c 100644\n--- a/sha1-lookup.c\n+++ b/sha1-lookup.c\n@@ -99,219 +99,3 @@ int sha1_pos(const unsigned char *sha1, void *table, size_t nr,\n \t} while (lo < hi);\n \treturn -lo-1;\n }\n-\n-/*\n- * Conventional binary search loop looks like this:\n- *\n- *\tunsigned lo, hi;\n- * do {\n- * unsigned mi = (lo + hi) / 2;\n- * int cmp = \"entry pointed at by mi\" minus \"target\";\n- * if (!cmp)\n- * return (mi is the wanted one)\n- * if (cmp > 0)\n- * hi = mi; \"mi is larger than target\"\n- * else\n- * lo = mi+1; \"mi is smaller than target\"\n- * } while (lo < hi);\n- *\n- * The invariants are:\n- *\n- * - When entering the loop, lo points at a slot that is never\n- * above the target (it could be at the target), hi points at a\n- * slot that is guaranteed to be above the target (it can never\n- * be at the target).\n- *\n- * - We find a point 'mi' between lo and hi (mi could be the same\n- * as lo, but never can be as same as hi), and check if it hits\n- * the target. There are three cases:\n- *\n- * - if it is a hit, we are happy.\n- *\n- * - if it is strictly higher than the target, we set it to hi,\n- * and repeat the search.\n- *\n- * - if it is strictly lower than the target, we update lo to\n- * one slot after it, because we allow lo to be at the target.\n- *\n- * If the loop exits, there is no matching entry.\n- *\n- * When choosing 'mi', we do not have to take the \"middle\" but\n- * anywhere in between lo and hi, as long as lo <= mi < hi is\n- * satisfied. When we somehow know that the distance between the\n- * target and lo is much shorter than the target and hi, we could\n- * pick mi that is much closer to lo than the midway.\n- *\n- * Now, we can take advantage of the fact that SHA-1 is a good hash\n- * function, and as long as there are enough entries in the table, we\n- * can expect uniform distribution. An entry that begins with for\n- * example \"deadbeef...\" is much likely to appear much later than in\n- * the midway of the table. It can reasonably be expected to be near\n- * 87% (222/256) from the top of the table.\n- *\n- * However, we do not want to pick \"mi\" too precisely. If the entry at\n- * the 87% in the above example turns out to be higher than the target\n- * we are looking for, we would end up narrowing the search space down\n- * only by 13%, instead of 50% we would get if we did a simple binary\n- * search. So we would want to hedge our bets by being less aggressive.\n- *\n- * The table at \"table\" holds at least \"nr\" entries of \"elem_size\"\n- * bytes each. Each entry has the SHA-1 key at \"key_offset\". The\n- * table is sorted by the SHA-1 key of the entries. The caller wants\n- * to find the entry with \"key\", and knows that the entry at \"lo\" is\n- * not higher than the entry it is looking for, and that the entry at\n- * \"hi\" is higher than the entry it is looking for.\n- */\n-int sha1_entry_pos(const void *table,\n-\t\t size_t elem_size,\n-\t\t size_t key_offset,\n-\t\t unsigned lo, unsigned hi, unsigned nr,\n-\t\t const unsigned char *key)\n-{\n-\tconst unsigned char *base = table;\n-\tconst unsigned char *hi_key, *lo_key;\n-\tunsigned ofs_0;\n-\tstatic int debug_lookup = -1;\n-\n-\tif (debug_lookup < 0)\n-\t\tdebug_lookup = !!getenv(\"GIT_DEBUG_LOOKUP\");\n-\n-\tif (!nr || lo >= hi)\n-\t\treturn -1;\n-\n-\tif (nr == hi)\n-\t\thi_key = NULL;\n-\telse\n-\t\thi_key = base + elem_size * hi + key_offset;\n-\tlo_key = base + elem_size * lo + key_offset;\n-\n-\tofs_0 = 0;\n-\tdo {\n-\t\tint cmp;\n-\t\tunsigned ofs, mi, range;\n-\t\tunsigned lov, hiv, kyv;\n-\t\tconst unsigned char *mi_key;\n-\n-\t\trange = hi - lo;\n-\t\tif (hi_key) {\n-\t\t\tfor (ofs = ofs_0; ofs < 20; ofs++)\n-\t\t\t\tif (lo_key[ofs] != hi_key[ofs])\n-\t\t\t\t\tbreak;\n-\t\t\tofs_0 = ofs;\n-\t\t\t/*\n-\t\t\t * byte 0 thru (ofs-1) are the same between\n-\t\t\t * lo and hi; ofs is the first byte that is\n-\t\t\t * different.\n-\t\t\t *\n-\t\t\t * If ofs==20, then no bytes are different,\n-\t\t\t * meaning we have entries with duplicate\n-\t\t\t * keys. We know that we are in a solid run\n-\t\t\t * of this entry (because the entries are\n-\t\t\t * sorted, and our lo and hi are the same,\n-\t\t\t * there can be nothing but this single key\n-\t\t\t * in between). So we can stop the search.\n-\t\t\t * Either one of these entries is it (and\n-\t\t\t * we do not care which), or we do not have\n-\t\t\t * it.\n-\t\t\t *\n-\t\t\t * Furthermore, we know that one of our\n-\t\t\t * endpoints must be the edge of the run of\n-\t\t\t * duplicates. For example, given this\n-\t\t\t * sequence:\n-\t\t\t *\n-\t\t\t * idx 0 1 2 3 4 5\n-\t\t\t * key A C C C C D\n-\t\t\t *\n-\t\t\t * If we are searching for \"B\", we might\n-\t\t\t * hit the duplicate run at lo=1, hi=3\n-\t\t\t * (e.g., by first mi=3, then mi=0). But we\n-\t\t\t * can never have lo > 1, because B < C.\n-\t\t\t * That is, if our key is less than the\n-\t\t\t * run, we know that \"lo\" is the edge, but\n-\t\t\t * we can say nothing of \"hi\". Similarly,\n-\t\t\t * if our key is greater than the run, we\n-\t\t\t * know that \"hi\" is the edge, but we can\n-\t\t\t * say nothing of \"lo\".\n-\t\t\t *\n-\t\t\t * Therefore if we do not find it, we also\n-\t\t\t * know where it would go if it did exist:\n-\t\t\t * just on the far side of the edge that we\n-\t\t\t * know about.\n-\t\t\t */\n-\t\t\tif (ofs == 20) {\n-\t\t\t\tmi = lo;\n-\t\t\t\tmi_key = base + elem_size * mi + key_offset;\n-\t\t\t\tcmp = memcmp(mi_key, key, 20);\n-\t\t\t\tif (!cmp)\n-\t\t\t\t\treturn mi;\n-\t\t\t\tif (cmp < 0)\n-\t\t\t\t\treturn -1 - hi;\n-\t\t\t\telse\n-\t\t\t\t\treturn -1 - lo;\n-\t\t\t}\n-\n-\t\t\thiv = hi_key[ofs_0];\n-\t\t\tif (ofs_0 < 19)\n-\t\t\t\thiv = (hiv << 8) | hi_key[ofs_0+1];\n-\t\t} else {\n-\t\t\thiv = 256;\n-\t\t\tif (ofs_0 < 19)\n-\t\t\t\thiv <<= 8;\n-\t\t}\n-\t\tlov = lo_key[ofs_0];\n-\t\tkyv = key[ofs_0];\n-\t\tif (ofs_0 < 19) {\n-\t\t\tlov = (lov << 8) | lo_key[ofs_0+1];\n-\t\t\tkyv = (kyv << 8) | key[ofs_0+1];\n-\t\t}\n-\t\tassert(lov < hiv);\n-\n-\t\tif (kyv < lov)\n-\t\t\treturn -1 - lo;\n-\t\tif (hiv < kyv)\n-\t\t\treturn -1 - hi;\n-\n-\t\t/*\n-\t\t * Even if we know the target is much closer to 'hi'\n-\t\t * than 'lo', if we pick too precisely and overshoot\n-\t\t * (e.g. when we know 'mi' is closer to 'hi' than to\n-\t\t * 'lo', pick 'mi' that is higher than the target), we\n-\t\t * end up narrowing the search space by a smaller\n-\t\t * amount (i.e. the distance between 'mi' and 'hi')\n-\t\t * than what we would have (i.e. about half of 'lo'\n-\t\t * and 'hi'). Hedge our bets to pick 'mi' less\n-\t\t * aggressively, i.e. make 'mi' a bit closer to the\n-\t\t * middle than we would otherwise pick.\n-\t\t */\n-\t\tkyv = (kyv * 6 + lov + hiv) / 8;\n-\t\tif (lov < hiv - 1) {\n-\t\t\tif (kyv == lov)\n-\t\t\t\tkyv++;\n-\t\t\telse if (kyv == hiv)\n-\t\t\t\tkyv--;\n-\t\t}\n-\t\tmi = (range - 1) * (kyv - lov) / (hiv - lov) + lo;\n-\n-\t\tif (debug_lookup) {\n-\t\t\tprintf(\"lo %u hi %u rg %u mi %u \", lo, hi, range, mi);\n-\t\t\tprintf(\"ofs %u lov %x, hiv %x, kyv %x\\n\",\n-\t\t\t ofs_0, lov, hiv, kyv);\n-\t\t}\n-\t\tif (!(lo <= mi && mi < hi))\n-\t\t\tdie(\"assertion failure lo %u mi %u hi %u %s\",\n-\t\t\t lo, mi, hi, sha1_to_hex(key));\n-\n-\t\tmi_key = base + elem_size * mi + key_offset;\n-\t\tcmp = memcmp(mi_key + ofs_0, key + ofs_0, 20 - ofs_0);\n-\t\tif (!cmp)\n-\t\t\treturn mi;\n-\t\tif (cmp > 0) {\n-\t\t\thi = mi;\n-\t\t\thi_key = mi_key;\n-\t\t} else {\n-\t\t\tlo = mi + 1;\n-\t\t\tlo_key = mi_key + elem_size;\n-\t\t}\n-\t} while (lo < hi);\n-\treturn -lo-1;\n-}\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 11ee69a99d..607b34ea53 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -2759,7 +2759,6 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \tconst uint32_t *level1_ofs = p->index_data;\n \tconst unsigned char *index = p->index_data;\n \tunsigned hi, lo, stride;\n-\tstatic int use_lookup = -1;\n \tstatic int debug_lookup = -1;\n \n \tif (debug_lookup < 0)\n@@ -2789,16 +2788,6 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \t\tprintf(\"%02x%02x%02x... lo %u hi %u nr %\"PRIu32\"\\n\",\n \t\t sha1[0], sha1[1], sha1[2], lo, hi, p->num_objects);\n \n-\tif (use_lookup < 0)\n-\t\tuse_lookup = !!getenv(\"GIT_USE_LOOKUP\");\n-\tif (use_lookup) {\n-\t\tint pos = sha1_entry_pos(index, stride, 0,\n-\t\t\t\t\t lo, hi, p->num_objects, sha1);\n-\t\tif (pos < 0)\n-\t\t\treturn 0;\n-\t\treturn nth_packed_object_offset(p, pos);\n-\t}\n-\n \twhile (lo < hi) {\n \t\tunsigned mi = (lo + hi) / 2;\n \t\tint cmp = hashcmp(index + mi * stride, sha1);\ndiff --git a/t/t5308-pack-detect-duplicates.sh b/t/t5308-pack-detect-duplicates.sh\nindex 9c5a8766ab..156ae9e9d3 100755\n--- a/t/t5308-pack-detect-duplicates.sh\n+++ b/t/t5308-pack-detect-duplicates.sh\n@@ -56,20 +56,11 @@ test_expect_success 'create batch-check test vectors' '\n \tEOF\n '\n \n-test_expect_success 'lookup in duplicated pack (binary search)' '\n+test_expect_success 'lookup in duplicated pack' '\n \tgit cat-file --batch-check actual &&\n \ttest_cmp expect actual\n '\n \n-test_expect_success 'lookup in duplicated pack (GIT_USE_LOOKUP)' '\n-\t(\n-\t\tGIT_USE_LOOKUP=1 &&\n-\t\texport GIT_USE_LOOKUP &&\n-\t\tgit cat-file --batch-check actual\n-\t) &&\n-\ttest_cmp expect actual\n-'\n-\n test_expect_success 'index-pack can reject packs with duplicates' '\n \tclear_packs &&\n \tcreate_pack dups.pack 2 &&\ndiff --git a/t/test-lib.sh b/t/test-lib.sh\nindex 1b6e53f78a..5e3ca30ab3 100644\n--- a/t/test-lib.sh\n+++ b/t/test-lib.sh\n@@ -99,7 +99,6 @@ unset VISUAL EMAIL LANGUAGE COLUMNS $(\"$PERL_PATH\" -e '\n \tmy $ok = join(\"|\", qw(\n \t\tTRACE\n \t\tDEBUG\n-\t\tUSE_LOOKUP\n \t\tTEST\n \t\t.*_TEST\n \t\tPROVE\n-- \n2.14.0.609.gd2d1f7ddf\n\n"},{"id":"325932","messageId":"20170809101645.7wv4mcsmnejxzhvs@sigill.intra.peff.net","threadId":"46544","inReplyTo":"20170809101106.p45y34uk6wcruqxv@sigill.intra.peff.net","subject":"[PATCH 2/2] hashcmp: use memcmp instead of open-coded loop","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-08-09T10:16:45Z","receivedAt":"2017-08-09T10:16:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"In 1a812f3a70 (hashcmp(): inline memcmp() by hand to\noptimize, 2011-04-28), it was reported that an open-coded\nloop outperformed memcmp() for comparing sha1s.\n\nDiscussion[1] a few years later in 2013 showed that this\ndepends on your libc's version of memcmp(). In particular,\nglibc 2.13 optimized their memcmp around 2011. Here are\ncurrent timings with glibc 2.24 (best-of-five, on\nlinux.git):\n\n [before this patch, open-coded]\n $ time git rev-list --objects --all\n real\t0m35.357s\n user\t0m35.016s\n sys\t0m0.340s\n\n [after this patch, memcmp]\n real\t0m32.930s\n user\t0m32.630s\n sys\t0m0.300s\n\nNow that we've had 6 years for that version of glibc to\nmake its way onto people's machines, it's worth revisiting\nour benchmarks and switching to memcmp().\n\nIt may be that there are other non-glibc systems where\nmemcmp() isn't as well optimized. But since our single data\npoint in favor of open-coding was on a now-ancient glibc, we\nshould probably assume the system memcmp is good unless\nproven otherwise. We may end up with a SLOW_MEMCMP Makefile\nknob, but we can hold off on that until we actually find\nsuch a system in practice.\n\n[1] https://public-inbox.org/git/20130318073229.GA5551@sigill.intra.peff.net/\n\nSigned-off-by: Jeff King \n---\nI also wondered if using memcmp() could be a hint to the compiler to use\nan intrinsic or some other trick, especially because the \"len\" here is a\nconstant. But in a toy function compiled with \"gcc -S\", it looks like we\ndo keep the call to memcmp (so the speedup really is glibc, and not some\ncompiler magic).\n\n cache.h | 9 +--------\n 1 file changed, 1 insertion(+), 8 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 71fe092644..46af4ecddb 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -939,14 +939,7 @@ extern const struct object_id null_oid;\n \n static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n {\n-\tint i;\n-\n-\tfor (i = 0; i < GIT_SHA1_RAWSZ; i++, sha1++, sha2++) {\n-\t\tif (*sha1 != *sha2)\n-\t\t\treturn *sha1 - *sha2;\n-\t}\n-\n-\treturn 0;\n+\treturn memcmp(sha1, sha2, GIT_SHA1_RAWSZ);\n }\n \n static inline int oidcmp(const struct object_id *oid1, const struct object_id *oid2)\n-- \n2.14.0.609.gd2d1f7ddf\n"},{"id":"325959","messageId":"2b111a78-dea4-85ff-3d8f-94d2eee0ca26@web.de","threadId":"46544","inReplyTo":"20170809101645.7wv4mcsmnejxzhvs@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] hashcmp: use memcmp instead of open-coded loop","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-08-09T14:55:43Z","receivedAt":"2017-08-09T14:56:15Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 09.08.2017 um 12:16 schrieb Jeff King:\n> In 1a812f3a70 (hashcmp(): inline memcmp() by hand to\n> optimize, 2011-04-28), it was reported that an open-coded\n> loop outperformed memcmp() for comparing sha1s.\n> \n> Discussion[1] a few years later in 2013 showed that this\n> depends on your libc's version of memcmp(). In particular,\n> glibc 2.13 optimized their memcmp around 2011. Here are\n> current timings with glibc 2.24 (best-of-five, on\n> linux.git):\n> \n> [before this patch, open-coded]\n> $ time git rev-list --objects --all\n> real\t0m35.357s\n> user\t0m35.016s\n> sys\t0m0.340s\n> \n> [after this patch, memcmp]\n> real\t0m32.930s\n> user\t0m32.630s\n> sys\t0m0.300s\n\nNice. And here's the size of the git executable in my build:\n\n unstripped stripped\n before 8048176 2082416\n after 8006064 2037360\n\n> I also wondered if using memcmp() could be a hint to the compiler to use\n> an intrinsic or some other trick, especially because the \"len\" here is a\n> constant. But in a toy function compiled with \"gcc -S\", it looks like we\n> do keep the call to memcmp (so the speedup really is glibc, and not some\n> compiler magic).\n\nGCC 7 inlines memcmp() if we only need a binary result:\n\n\thttps://godbolt.org/g/iZ11Ne\n\nRené\n"},{"id":"325960","messageId":"20170809150644.ny565zdhki5zgdzr@sigill.intra.peff.net","threadId":"46544","inReplyTo":"2b111a78-dea4-85ff-3d8f-94d2eee0ca26@web.de","subject":"Re: [PATCH 2/2] hashcmp: use memcmp instead of open-coded loop","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-08-09T15:06:45Z","receivedAt":"2017-08-09T15:06:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 09, 2017 at 04:55:43PM +0200, René Scharfe wrote:\n\n> > I also wondered if using memcmp() could be a hint to the compiler to use\n> > an intrinsic or some other trick, especially because the \"len\" here is a\n> > constant. But in a toy function compiled with \"gcc -S\", it looks like we\n> > do keep the call to memcmp (so the speedup really is glibc, and not some\n> > compiler magic).\n> \n> GCC 7 inlines memcmp() if we only need a binary result:\n> \n> \thttps://godbolt.org/g/iZ11Ne\n\nCute. It turns it into a series of 8-byte xors. The original open-coded\nloop doesn't end up nearly as optimized with gcc-7.\n\nI suspect many calls in practice are of the binary-result type. So some\nof the speedup I saw may have been from compiler improvements and not\nlibc improvements. Still, I think the general argument is the same,\nreplacing \"if your libc memcmp is fast\" with \"if your libc/compiler\nmakes memcmp fast\".\n\n-Peff\n"},{"id":"325977","messageId":"xmqqshh06264.fsf@gitster.mtv.corp.google.com","threadId":"46544","inReplyTo":"20170809101432.6jquwmev423o56pb@sigill.intra.peff.net","subject":"Re: [PATCH 1/2] sha1_file: drop experimental GIT_USE_LOOKUP search","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-08-09T18:12:19Z","receivedAt":"2017-08-09T18:12:26Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> This lets us remove sha1_entry_pos() entirely, as the .idx\n> lookup code was the only caller. Note that sha1-lookup.c\n> still contains sha1_pos(), which differs from\n> sha1_entry_pos() in two ways:\n>\n> - it has a different interface; it uses a function pointer\n> to access sha1 entries rather than a size/offset pair\n> describing the table's memory layout\n>\n> - it only scales the initial selection of \"mi\", rather\n> than each iteration of the search\n>\n> We can't get rid of this function, as it's called from\n> several places. It may be that we could replace it with a\n> simple binary search, but that's out of scope for this patch\n> (and would need benchmarking).\n\nThanks for reducing the count of binary search functions by one.\n\nI think the \"just one round of newton-raphson\" in sha1_pos() comes\nfrom [*1*]; I agree that it needs benchmarking before tweaking it.\n\nWe may want to tell libgit2 folks about this change, though [*2*].\nI think they too are carrying dead code that is only used under CPP\nmacro GIT_USE_LOOKUP, which they do not seem to define.\n\n\n[Reference]\n\n*1* https://public-inbox.org/git/7v38vso8kz.fsf@alter.siamese.dyndns.org/\n*2* https://github.com/libgit2/libgit2/commit/dd453c4dbf9a1fa38530b1f51e079852736b8f66\n"},{"id":"325985","messageId":"20170809210946.2pzz5rze4u57c4lr@sigill.intra.peff.net","threadId":"46544","inReplyTo":"xmqqshh06264.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 1/2] sha1_file: drop experimental GIT_USE_LOOKUP search","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-08-09T21:09:47Z","receivedAt":"2017-08-09T21:09:54Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 09, 2017 at 11:12:19AM -0700, Junio C Hamano wrote:\n\n> Thanks for reducing the count of binary search functions by one.\n> \n> I think the \"just one round of newton-raphson\" in sha1_pos() comes\n> from [*1*]; I agree that it needs benchmarking before tweaking it.\n\nActually, it's weirder than that. You mentioned it in that thread, but\nthe code dates back much further. It was moved to the file in 96beef8,\nbut that was just a copy from patch-ids.c. The original seems to be from\n5d23e133d2 (Refactor patch-id filtering out of git-cherry and\ngit-format-patch., 2007-04-09), which predates the sha1_entry_pos()\nexperiment.\n\nI always thought those two sha1-lookup functions came in the opposite\norder, but I guess was wrong. Or possibly you are a time traveler.\n\n> We may want to tell libgit2 folks about this change, though [*2*].\n> I think they too are carrying dead code that is only used under CPP\n> macro GIT_USE_LOOKUP, which they do not seem to define.\n\nGood thinking. It looks like they could use all three of the patches\nunder discussion. I opened some PRs:\n\n https://github.com/libgit2/libgit2/pull/4326\n https://github.com/libgit2/libgit2/pull/4327\n https://github.com/libgit2/libgit2/pull/4328\n\n-Peff\n"}]}