{"thread":{"id":"33208","subject":"Make GIT_USE_LOOKUP default?","startedAt":"2013-03-17T13:25:55Z","lastAt":"2013-03-19T15:55:44Z","messageCount":10,"participants":["Duy Nguyen","Junio C Hamano","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"211518","messageId":"CACsJy8AihriCDfN=cz7FjdHzZAhnPPGML_w8yWcVVrmTQLZyjw@mail.gmail.com","threadId":"33208","inReplyTo":null,"subject":"Make GIT_USE_LOOKUP default?","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-17T13:25:55Z","receivedAt":"2013-03-17T13:25:55Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This env comes from jc/sha1-lookup in 2008 (merge commit e9f9d4f), 5\nyears ago. I wonder if it's good enough to turn on by default and keep\nimproving from there, or is it still experimental?\n-- \nDuy\n"},{"id":"211527","messageId":"7vd2uxrdh7.fsf@alter.siamese.dyndns.org","threadId":"33208","inReplyTo":"CACsJy8AihriCDfN=cz7FjdHzZAhnPPGML_w8yWcVVrmTQLZyjw@mail.gmail.com","subject":"Re: Make GIT_USE_LOOKUP default?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-17T20:13:56Z","receivedAt":"2013-03-17T20:13:56Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Duy Nguyen writes:\n\n> This env comes from jc/sha1-lookup in 2008 (merge commit e9f9d4f), 5\n> years ago. I wonder if it's good enough to turn on by default and keep\n> improving from there, or is it still experimental?\n\nThe algorithm has been used in production in other codepaths like\npatch-ids and replace-object, so correctness-wise it should be fine\nto turn it on. I think nobody has bothered to benchmark with and\nwithout the environment to see if it is really worth the complexity.\n\nIt may be a good idea to try doing so, now you have noticed it ;-).\n"},{"id":"211550","messageId":"20130318073229.GA5551@sigill.intra.peff.net","threadId":"33208","inReplyTo":"7vd2uxrdh7.fsf@alter.siamese.dyndns.org","subject":"Re: Make GIT_USE_LOOKUP default?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-18T07:32:29Z","receivedAt":"2013-03-18T07:32:29Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"[+cc Ingo and Jonathan, as this revisits the \"open-code hashcmp\" thread\n referenced below]\n\nOn Sun, Mar 17, 2013 at 01:13:56PM -0700, Junio C Hamano wrote:\n\n> Duy Nguyen writes:\n> \n> > This env comes from jc/sha1-lookup in 2008 (merge commit e9f9d4f), 5\n> > years ago. I wonder if it's good enough to turn on by default and keep\n> > improving from there, or is it still experimental?\n> \n> The algorithm has been used in production in other codepaths like\n> patch-ids and replace-object, so correctness-wise it should be fine\n> to turn it on. I think nobody has bothered to benchmark with and\n> without the environment to see if it is really worth the complexity.\n> \n> It may be a good idea to try doing so, now you have noticed it ;-).\n\nThe only benchmarking I could find in the list archive (besides the ones\nin the commit itself, showing little change, but fewer page faults) is:\n\n http://article.gmane.org/gmane.comp.version-control.git/123832\n\nwhich actually indicates that GIT_USE_LOOKUP is slower (despite having\nfewer page faults).\n\nBy the way, looking at that made me think for a few minutes about\nhashcmp, and I was surprised to find that we use an open-coded\ncomparison loop. That dates back to this thread by Ingo:\n\n http://article.gmane.org/gmane.comp.version-control.git/172286\n\nI could not replicate his benchmarks at all. In fact, my measurements\nshowed a slight slowdown with 1a812f3 (hashcmp(): inline memcmp() by\nhand to optimize, 2011-04-28).\n\nHere are my best-of-five numbers for running \"git rev-list --objects\n--all >/dev/null\" on linux-2.6.git:\n\n [current master, compiled with -O2]\n real 0m45.612s\n user 0m45.140s\n sys 0m0.300s\n\n [current master, compiled with -O3 for comparison]\n real 0m45.588s\n user 0m45.088s\n sys 0m0.312s\n\n [revert 1a812f3 (i.e., go back to memcmp), -O2]\n real 0m44.358s\n user 0m43.876s\n sys 0m0.316s\n\n [open-code first byte, fall back to memcmp, -O2]\n real 0m43.963s\n user 0m43.568s\n sys 0m0.284s\n\nI wonder why we get such different numbers. Ingo said his tests are on a\nNehalem CPU, as are mine (mine is an i7-840QM). I wonder if we should be\nwrapping the optimization in an #ifdef, but I'm not sure which flag we\nshould be checking.\n\nNote that I didn't run all of my measurements using \"git gc\" as Ingo\ndid, which I think conflates a lot of unrelated performance issues (like\nwriting out a packfile). The interesting bits for hashcmp in \"gc\" are\nthe \"Counting objects\" phase of pack-objects, and \"git prune\"\ndetermining reachability. Those are both basically the same as \"rev-list\n--objects --all\".\n\nI did do a quick check of `git gc`, though, and it showed results that\nmatched my rev-lists above (i.e., a very slight speedup by going back to\nmemcmp).\n\n-Peff\n"},{"id":"211581","messageId":"7vtxo8ody3.fsf@alter.siamese.dyndns.org","threadId":"33208","inReplyTo":"20130318073229.GA5551@sigill.intra.peff.net","subject":"Re: Make GIT_USE_LOOKUP default?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-18T16:44:20Z","receivedAt":"2013-03-18T16:44:20Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> By the way, looking at that made me think for a few minutes about\n> hashcmp, and I was surprised to find that we use an open-coded\n> comparison loop. That dates back to this thread by Ingo:\n>\n> http://article.gmane.org/gmane.comp.version-control.git/172286\n>\n> I could not replicate his benchmarks at all. In fact, my measurements\n> showed a slight slowdown with 1a812f3 (hashcmp(): inline memcmp() by\n> hand to optimize, 2011-04-28).\n>\n> Here are my best-of-five numbers for running \"git rev-list --objects\n> --all >/dev/null\" on linux-2.6.git:\n>\n> [current master, compiled with -O2]\n> real 0m45.612s\n> user 0m45.140s\n> sys 0m0.300s\n> ...\n> [revert 1a812f3 (i.e., go back to memcmp), -O2]\n> real 0m44.358s\n> user 0m43.876s\n> sys 0m0.316s\n> ...\n> I wonder why we get such different numbers. Ingo said his tests are on a\n> Nehalem CPU, as are mine (mine is an i7-840QM). I wonder if we should be\n> wrapping the optimization in an #ifdef, but I'm not sure which flag we\n> should be checking.\n\nFWIW, I am getting something like this on my\n\n$ grep 'model name' /proc/cpuinfo | uniq -c\n 4 model name : Intel(R) Core(TM)2 Quad CPU Q9450 @ 2.66GHz\n\nThe same \"rev-list --objects --all >/dev/null\", best of five:\n\n[current master, compiled with -O2]\nreal 0m39.956s\nuser 0m39.562s\nsys 0m0.396s\n\n[revert 1a812f3 (i.e., go back to memcmp), -O2]\nreal 0m42.161s\nuser 0m41.879s\nsys 0m0.284s\n\nIt could be that the difference may be how well memcmp() is\noptimized, no? My box runs Debian with libc6 2.11.3-4 and gcc\n4.4.5.\n"},{"id":"211582","messageId":"20130318164950.GA14844@sigill.intra.peff.net","threadId":"33208","inReplyTo":"7vtxo8ody3.fsf@alter.siamese.dyndns.org","subject":"Re: Make GIT_USE_LOOKUP default?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-18T16:49:50Z","receivedAt":"2013-03-18T16:49:50Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Mar 18, 2013 at 09:44:20AM -0700, Junio C Hamano wrote:\n\n> FWIW, I am getting something like this on my\n> \n> $ grep 'model name' /proc/cpuinfo | uniq -c\n> 4 model name : Intel(R) Core(TM)2 Quad CPU Q9450 @ 2.66GHz\n> \n> The same \"rev-list --objects --all >/dev/null\", best of five:\n> \n> [current master, compiled with -O2]\n> real 0m39.956s\n> user 0m39.562s\n> sys 0m0.396s\n> \n> [revert 1a812f3 (i.e., go back to memcmp), -O2]\n> real 0m42.161s\n> user 0m41.879s\n> sys 0m0.284s\n> \n> It could be that the difference may be how well memcmp() is\n> optimized, no? My box runs Debian with libc6 2.11.3-4 and gcc\n> 4.4.5.\n\nYeah, that would make sense. I have libc6 2.13-38 and gcc 4.7.2 (debian\nunstable).\n\n-Peff\n"},{"id":"211585","messageId":"7vli9kocuc.fsf@alter.siamese.dyndns.org","threadId":"33208","inReplyTo":"20130318164950.GA14844@sigill.intra.peff.net","subject":"Re: Make GIT_USE_LOOKUP default?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-18T17:08:11Z","receivedAt":"2013-03-18T17:08:11Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Mon, Mar 18, 2013 at 09:44:20AM -0700, Junio C Hamano wrote:\n>\n>> FWIW, I am getting something like this on my\n>> \n>> $ grep 'model name' /proc/cpuinfo | uniq -c\n>> 4 model name : Intel(R) Core(TM)2 Quad CPU Q9450 @ 2.66GHz\n>> \n>> The same \"rev-list --objects --all >/dev/null\", best of five:\n>> \n>> [current master, compiled with -O2]\n>> real 0m39.956s\n>> user 0m39.562s\n>> sys 0m0.396s\n>> \n>> [revert 1a812f3 (i.e., go back to memcmp), -O2]\n>> real 0m42.161s\n>> user 0m41.879s\n>> sys 0m0.284s\n>> \n>> It could be that the difference may be how well memcmp() is\n>> optimized, no? My box runs Debian with libc6 2.11.3-4 and gcc\n>> 4.4.5.\n>\n> Yeah, that would make sense. I have libc6 2.13-38 and gcc 4.7.2 (debian\n> unstable).\n\nJust for fun, here is a totally unrelated comparison, both with\ncurrent master, compiled with -O2 and running on the same box.\n\n[without GIT_USE_LOOKUP]\nreal 0m39.906s\nreal 0m40.020s\nreal 0m40.022s\nreal 0m40.027s\nreal 0m40.146s\n\n[with GIT_USE_LOOKUP]\nreal 0m40.336s\nreal 0m40.376s\nreal 0m40.452s\nreal 0m40.503s\nreal 0m40.572s\n\nMaybe the Newton-Raphson is right as a concept (it does seem to\nresult in fewer minor-faults) but the current code is implemented\npoorly and has a huge room for improvement?\n\n[without GIT_USE_LOOKUP]\n0inputs+0outputs (0major+182895minor)pagefaults 0swaps\n0inputs+0outputs (0major+182920minor)pagefaults 0swaps\n0inputs+0outputs (0major+183004minor)pagefaults 0swaps\n0inputs+0outputs (0major+183006minor)pagefaults 0swaps\n0inputs+0outputs (0major+183036minor)pagefaults 0swaps\n\n[with GIT_USE_LOOKUP]\n0inputs+0outputs (0major+182803minor)pagefaults 0swaps\n0inputs+0outputs (0major+182886minor)pagefaults 0swaps\n0inputs+0outputs (0major+182967minor)pagefaults 0swaps\n0inputs+0outputs (0major+182997minor)pagefaults 0swaps\n0inputs+0outputs (0major+182998minor)pagefaults 0swaps\n"},{"id":"211586","messageId":"20130318171949.GB15924@sigill.intra.peff.net","threadId":"33208","inReplyTo":"7vli9kocuc.fsf@alter.siamese.dyndns.org","subject":"Re: Make GIT_USE_LOOKUP default?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-18T17:19:49Z","receivedAt":"2013-03-18T17:19:49Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Mar 18, 2013 at 10:08:11AM -0700, Junio C Hamano wrote:\n\n> Just for fun, here is a totally unrelated comparison, both with\n> current master, compiled with -O2 and running on the same box.\n> \n> [without GIT_USE_LOOKUP]\n> real 0m39.906s\n> real 0m40.020s\n> real 0m40.022s\n> real 0m40.027s\n> real 0m40.146s\n> \n> [with GIT_USE_LOOKUP]\n> real 0m40.336s\n> real 0m40.376s\n> real 0m40.452s\n> real 0m40.503s\n> real 0m40.572s\n> \n> Maybe the Newton-Raphson is right as a concept (it does seem to\n> result in fewer minor-faults) but the current code is implemented\n> poorly and has a huge room for improvement?\n\nI do not see anything obviously wrong in it, though I did not walk\nthrough all of the ofs calculation to look for any clever speedups.\nHowever, I think it is clear from the other timings and Ingo's thread\nthat glibc 2.11's memcmp does not perform very well on many short reads.\nAnd sha1_entry_pos will do memcmps even smaller than 20 bytes.\n\nWhat happens if you do this?\n\ndiff --git a/sha1-lookup.c b/sha1-lookup.c\nindex c4dc55d..4ea03bd 100644\n--- a/sha1-lookup.c\n+++ b/sha1-lookup.c\n@@ -102,6 +102,17 @@ int sha1_pos(const unsigned char *sha1, void *table, size_t nr,\n \treturn -lo-1;\n }\n \n+static int short_memcmp(const unsigned char *a,\n+\t\t\tconst unsigned char *b,\n+\t\t\tint len)\n+{\n+\tint i;\n+\tfor (i = 0; i < len; i++, a++, b++)\n+\t\tif (*a != *b)\n+\t\t\treturn *a - *b;\n+\treturn 0;\n+}\n+\n /*\n * Conventional binary search loop looks like this:\n *\n@@ -257,7 +268,7 @@ int sha1_entry_pos(const void *table,\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\tcmp = short_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"},{"id":"211591","messageId":"7v38vso8kz.fsf@alter.siamese.dyndns.org","threadId":"33208","inReplyTo":"20130318171949.GB15924@sigill.intra.peff.net","subject":"Re: Make GIT_USE_LOOKUP default?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-18T18:40:12Z","receivedAt":"2013-03-18T18:40:12Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I do not see anything obviously wrong in it, though I did not walk\n> through all of the ofs calculation to look for any clever speedups.\n> However, I think it is clear from the other timings and Ingo's thread\n> that glibc 2.11's memcmp does not perform very well on many short reads.\n> And sha1_entry_pos will do memcmps even smaller than 20 bytes.\n>\n> What happens if you do this?\n\nThe overall trend is the same.\n\n[without GIT_USE_LOOKUP]\nreal 0m40.044s\nreal 0m40.054s\nreal 0m40.072s\nreal 0m40.097s\nreal 0m40.159s\n\n[with GIT_USE_LOOKUP]\nreal 0m40.257s\nreal 0m40.281s\nreal 0m40.311s\nreal 0m40.366s\nreal 0m40.407s\n\nI suspect that after the first few rounds the range shrinks small\nenough that the difference between a simple \"mi = (hi + lo)/2\" and\nconvoluted ofs computation becomes dominant. Perhaps we should only\ndo N-R for the initial midpoint selection and then fall back to a\nstupid binary search?\n"},{"id":"211681","messageId":"CACsJy8BxbJU9-7Q-Ef3cG2VV2cW8YbBGcjNT9wjT+JywDOxyNg@mail.gmail.com","threadId":"33208","inReplyTo":"20130318073229.GA5551@sigill.intra.peff.net","subject":"Re: Make GIT_USE_LOOKUP default?","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-19T15:43:40Z","receivedAt":"2013-03-19T15:43:40Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Mar 18, 2013 at 2:32 PM, Jeff King wrote:\n> By the way, looking at that made me think for a few minutes about\n> hashcmp, and I was surprised to find that we use an open-coded\n> comparison loop. That dates back to this thread by Ingo:\n>\n> http://article.gmane.org/gmane.comp.version-control.git/172286\n>\n> I could not replicate his benchmarks at all. In fact, my measurements\n> showed a slight slowdown with 1a812f3 (hashcmp(): inline memcmp() by\n> hand to optimize, 2011-04-28).\n>\n> Here are my best-of-five numbers for running \"git rev-list --objects\n> --all >/dev/null\" on linux-2.6.git:\n>\n> [current master, compiled with -O2]\n> real 0m45.612s\n> user 0m45.140s\n> sys 0m0.300s\n>\n> [current master, compiled with -O3 for comparison]\n> real 0m45.588s\n> user 0m45.088s\n> sys 0m0.312s\n>\n> [revert 1a812f3 (i.e., go back to memcmp), -O2]\n> real 0m44.358s\n> user 0m43.876s\n> sys 0m0.316s\n>\n> [open-code first byte, fall back to memcmp, -O2]\n> real 0m43.963s\n> user 0m43.568s\n> sys 0m0.284s\n>\n> I wonder why we get such different numbers. Ingo said his tests are on a\n> Nehalem CPU, as are mine (mine is an i7-840QM). I wonder if we should be\n> wrapping the optimization in an #ifdef, but I'm not sure which flag we\n> should be checking.\n\nWhat gcc and glibc versions are you using? With gcc 4.5.3 I got \"repz\ncmpsb\" after reverting the patch, just like what Ingo described\n(although interestingly it ran a bit faster than current master, glibc\n2.11.2 on Atom D510 32 bit). gcc 4.6.3 -O2 (on another machine, 64\nbit) produced a call to libc's memcmp instead of \"repz cmpsb\". I guess\nif \"repz cmpsb\" is what we are against, then we could pass\n-fno-builtin-memcmp (potential impact to other parts of git though).\n-- \nDuy\n"},{"id":"211685","messageId":"20130319155544.GB10010@sigill.intra.peff.net","threadId":"33208","inReplyTo":"CACsJy8BxbJU9-7Q-Ef3cG2VV2cW8YbBGcjNT9wjT+JywDOxyNg@mail.gmail.com","subject":"Re: Make GIT_USE_LOOKUP default?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-19T15:55:44Z","receivedAt":"2013-03-19T15:55:44Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Mar 19, 2013 at 10:43:40PM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> > I could not replicate his benchmarks at all. In fact, my measurements\n> > showed a slight slowdown with 1a812f3 (hashcmp(): inline memcmp() by\n> > hand to optimize, 2011-04-28).\n> [...]\n> \n> What gcc and glibc versions are you using? With gcc 4.5.3 I got \"repz\n> cmpsb\" after reverting the patch, just like what Ingo described\n> (although interestingly it ran a bit faster than current master, glibc\n> 2.11.2 on Atom D510 32 bit). gcc 4.6.3 -O2 (on another machine, 64\n> bit) produced a call to libc's memcmp instead of \"repz cmpsb\". I guess\n> if \"repz cmpsb\" is what we are against, then we could pass\n> -fno-builtin-memcmp (potential impact to other parts of git though).\n\nI have glibc 2.13. And looking at the changelog, there were a ton of\nssse-optimized memcmp implementations that went into 2.13 [1], so I suspect\nthat is what is going on.\n\n-Peff\n\nPS As a side note, you may recall a year or two ago when these went in,\nbecause the initial versions walked backwards, meaning memcpys of\noverlapping regions started to fail (as they are allowed to, but many\nprograms do not properly use memmove).\n"}]}