{"thread":{"id":"37164","subject":"[PATCH] fast-import: use hashcmp() for SHA1 hash comparison","startedAt":"2014-07-18T16:00:51Z","lastAt":"2014-07-19T17:53:04Z","messageCount":7,"participants":["René Scharfe","Jonathan Nieder","Jeff King","brian m. carlson"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"246315","messageId":"53C944B3.5080106@web.de","threadId":"37164","inReplyTo":null,"subject":"[PATCH] fast-import: use hashcmp() for SHA1 hash comparison","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2014-07-18T16:00:51Z","receivedAt":"2014-07-18T16:00:51Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Signed-off-by: Rene Scharfe <l.s.r@web.de>\n---\n fast-import.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex fa635f7..d73f58c 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -2324,7 +2324,7 @@ static void file_change_m(const char *p, struct branch *b)\n \t}\n \n \t/* Git does not track empty, non-toplevel directories. */\n-\tif (S_ISDIR(mode) && !memcmp(sha1, EMPTY_TREE_SHA1_BIN, 20) && *p) {\n+\tif (S_ISDIR(mode) && !hashcmp(sha1, EMPTY_TREE_SHA1_BIN) && *p) {\n \t\ttree_content_remove(&b->branch_tree, p, NULL, 0);\n \t\treturn;\n \t}\n-- \n2.0.2\n"},{"id":"246327","messageId":"20140718184246.GS12427@google.com","threadId":"37164","inReplyTo":"53C944B3.5080106@web.de","subject":"Re: [PATCH] fast-import: use hashcmp() for SHA1 hash comparison","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2014-07-18T18:42:46Z","receivedAt":"2014-07-18T18:42:46Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"René Scharfe wrote:\n\n> Signed-off-by: Rene Scharfe <l.s.r@web.de>\n> ---\n>  fast-import.c | 2 +-\n>  1 file changed, 1 insertion(+), 1 deletion(-)\n\nBefore:\n\n  $ size git-fast-import\n     text    data     bss     dec     hex filename\n   804138    6768  754160 1565066  17e18a git-fast-import\n\nAfter:\n\n  $ size git-fast-import\n     text    data     bss     dec     hex filename\n   804154    6768  754160 1565082  17e19a git-fast-import\n\nSo this makes the text size worse on this machine (amd64, building\nwith gcc 4.8.2 -O2).  That's probably because the old code does 'call\nmemcmp', while the new code inlines it.  Inlining is presumably the\nbetter choice.\n\nMore importantly, the new code is more readable.\n\nFor what it's worth,\nReviewed-by: Jonathan Nieder <jrnieder@gmail.com>\n"},{"id":"246331","messageId":"53C971FD.6040500@web.de","threadId":"37164","inReplyTo":"20140718184246.GS12427@google.com","subject":"Re: [PATCH] fast-import: use hashcmp() for SHA1 hash comparison","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2014-07-18T19:14:05Z","receivedAt":"2014-07-18T19:14:05Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 18.07.2014 20:42, schrieb Jonathan Nieder:\n> René Scharfe wrote:\n>\n>> Signed-off-by: Rene Scharfe <l.s.r@web.de>\n>> ---\n>>   fast-import.c | 2 +-\n>>   1 file changed, 1 insertion(+), 1 deletion(-)\n>\n> Before:\n>\n>    $ size git-fast-import\n>       text    data     bss     dec     hex filename\n>     804138    6768  754160 1565066  17e18a git-fast-import\n>\n> After:\n>\n>    $ size git-fast-import\n>       text    data     bss     dec     hex filename\n>     804154    6768  754160 1565082  17e19a git-fast-import\n>\n> So this makes the text size worse on this machine (amd64, building\n> with gcc 4.8.2 -O2).  That's probably because the old code does 'call\n> memcmp', while the new code inlines it.  Inlining is presumably the\n> better choice.\n>\n> More importantly, the new code is more readable.\n\nYes, the latter point is the important one.\n\nIf inlining is really better is another matter; I don't understand how \n1a812f3a (hashcmp(): inline memcmp() by hand to optimize) could have \nmade git gc 18% faster, as it claimed.  I would expect memcmp(), which \ncan compare more than a byte at a time, to be significantly faster -- or \nat least just as fast as whatever the compiler does with the inlined \nversion.\n\nRené\n"},{"id":"246349","messageId":"20140718235706.GA11192@peff.net","threadId":"37164","inReplyTo":"53C971FD.6040500@web.de","subject":"Re: [PATCH] fast-import: use hashcmp() for SHA1 hash comparison","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-07-18T23:57:08Z","receivedAt":"2014-07-18T23:57:08Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jul 18, 2014 at 09:14:05PM +0200, René Scharfe wrote:\n\n> If inlining is really better is another matter; I don't understand how\n> 1a812f3a (hashcmp(): inline memcmp() by hand to optimize) could have made\n> git gc 18% faster, as it claimed.  I would expect memcmp(), which can\n> compare more than a byte at a time, to be significantly faster -- or at\n> least just as fast as whatever the compiler does with the inlined version.\n\nI looked into this a while ago[1]. I think with glibc 2.13 and up, the\nmemcmp is a win. We should consider switching back if that is what is\ncommon now.\n\n-Peff\n\n[1] http://article.gmane.org/gmane.comp.version-control.git/218396\n"},{"id":"246365","messageId":"53CA6072.8000009@web.de","threadId":"37164","inReplyTo":"20140718235706.GA11192@peff.net","subject":"Re: [PATCH] fast-import: use hashcmp() for SHA1 hash comparison","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2014-07-19T12:11:30Z","receivedAt":"2014-07-19T12:11:30Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 19.07.2014 01:57, schrieb Jeff King:\n> On Fri, Jul 18, 2014 at 09:14:05PM +0200, René Scharfe wrote:\n> \n>> If inlining is really better is another matter; I don't understand how\n>> 1a812f3a (hashcmp(): inline memcmp() by hand to optimize) could have made\n>> git gc 18% faster, as it claimed.  I would expect memcmp(), which can\n>> compare more than a byte at a time, to be significantly faster -- or at\n>> least just as fast as whatever the compiler does with the inlined version.\n> \n> I looked into this a while ago[1]. I think with glibc 2.13 and up, the\n> memcmp is a win. We should consider switching back if that is what is\n> common now.\n> \n> -Peff\n> \n> [1] http://article.gmane.org/gmane.comp.version-control.git/218396\n\nOn Linux this seems to improve rev-list performance by ca. 10% for me, but\non on FreeBSD it slows it down by ca. 25%.  That's less surprising after\nlooking at their memcmp() implementation:\n\nhttp://svnweb.freebsd.org/base/release/10.0.0/lib/libc/string/memcmp.c?revision=260789&view=co\n\nIt's basically our one-byte-at-a-time inlined version, sans inlining.\n\nI'd say if a platform doesn't bother optimizing memcmp() then they\ndeserve the resulting performance.  And it's probably not too bad a\npenalty because such comparisons probably won't make up a significant\npart of most applications.\n\nBut perhaps we can do better.  First, here are the numbers I got for\n\"/usr/bin/time git rev-list --all --objects v2.0.0 >/dev/null\" (best\nof five runs):\n\nDebian testing amd64 with gcc 4.9.0 and libc 2.19 on Hyper-V on Intel i5-4670:\n\n  master (398dd4bd)\n  2.14user 0.02system 0:02.16elapsed 99%CPU (0avgtext+0avgdata 71004maxresident)k\n  0inputs+0outputs (0major+21985minor)pagefaults 0swaps\n\n  using memcmp\n  1.92user 0.02system 0:01.95elapsed 99%CPU (0avgtext+0avgdata 71032maxresident)k\n  0inputs+0outputs (0major+21987minor)pagefaults 0swaps\n\n  four bytes at a time\n  1.93user 0.03system 0:01.97elapsed 99%CPU (0avgtext+0avgdata 71240maxresident)k\n  0inputs+0outputs (0major+22024minor)pagefaults 0swaps\n\nDebian testing amd64 with clang 3.3 and libc 2.19 on Hyper-V on Intel i5-4670:\n\n  master (398dd4bd)\n  2.12user 0.04system 0:02.17elapsed 99%CPU (0avgtext+0avgdata 70976maxresident)k\n  0inputs+0outputs (0major+21995minor)pagefaults 0swaps\n\n  memcmp\n  1.94user 0.01system 0:01.95elapsed 100%CPU (0avgtext+0avgdata 71012maxresident)k\n  0inputs+0outputs (0major+21952minor)pagefaults 0swaps\n\n  four bytes at a time\n  1.86user 0.01system 0:01.88elapsed 99%CPU (0avgtext+0avgdata 70788maxresident)k\n  0inputs+0outputs (0major+21909minor)pagefaults 0swaps\n\nFreeBSD 10 amd64 with clang 3.3 on Hyper-V on Intel i5-4670c:\n\n  master (398dd4bd)\n        1.83 real         1.80 user         0.03 sys\n\n  using memcmp\n        2.32 real         2.32 user         0.00 sys\n\n  four bytes at a time\n        1.56 real         1.53 user         0.03 sys\n\nPerformance measurements in virtual machines are not very accurate, so\ntake them with a bag of salt, but the numbers were relatively stable\naccross runs.\n\nHow come rev-list runs so much faster on FreeBSD?  Would it make sense\nto apply the four-bytes-at-a-time patch?  How would it on other\nplatforms, especially ARM?  Can we do even better?  And more\nimportantly: Does it matter in the first place?\n\nThe memcmp version just replaces the body of hashcmp() with\n\"return memcmp(sha1, sha2, 20);\".  Here's the four-bytes-at-a-time\npatch:\n---\n cache.h | 13 +++++++++----\n 1 file changed, 9 insertions(+), 4 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 92fc9f1..c6cd28e 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -732,13 +732,18 @@ extern const unsigned char null_sha1[20];\n \n static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n {\n+\tconst uint32_t *p1 = (const uint32_t *)sha1;\n+\tconst uint32_t *p2 = (const uint32_t *)sha2;\n \tint i;\n \n-\tfor (i = 0; i < 20; i++, sha1++, sha2++) {\n-\t\tif (*sha1 != *sha2)\n-\t\t\treturn *sha1 - *sha2;\n+\tfor (i = 0; i < 20 / sizeof(uint32_t); i++, p1++, p2++) {\n+\t\tuint32_t v1 = htonl(*p1);\n+\t\tuint32_t v2 = htonl(*p2);\n+\t\tif (v1 < v2)\n+\t\t\treturn -1;\n+\t\tif (v1 > v2)\n+\t\t\treturn 1;\n \t}\n-\n \treturn 0;\n }\n \n-- \n2.0.2\n"},{"id":"246386","messageId":"20140719164324.GA5616@vauxhall.crustytoothpaste.net","threadId":"37164","inReplyTo":"53CA6072.8000009@web.de","subject":"Re: [PATCH] fast-import: use hashcmp() for SHA1 hash comparison","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2014-07-19T16:43:25Z","receivedAt":"2014-07-19T16:43:25Z","isPatch":true,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On Sat, Jul 19, 2014 at 02:11:30PM +0200, René Scharfe wrote:\n> I'd say if a platform doesn't bother optimizing memcmp() then they\n> deserve the resulting performance.  And it's probably not too bad a\n> penalty because such comparisons probably won't make up a significant\n> part of most applications.\n\nI tend to agree with this.  On many modern versions of GCC, the compiler\ncan generate an appropriately optimized inline version when it sees a\nmemcmp call, so it's more of a compiler issue then, since no actual call\nto the function will be emitted.\n\n>  static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n>  {\n> +\tconst uint32_t *p1 = (const uint32_t *)sha1;\n> +\tconst uint32_t *p2 = (const uint32_t *)sha2;\n\nYou can't make this cast.  The guaranteed alignment for sha1 and sha2 is\n1, and for p1 and p2, it's 4.  If sha1 and sha2 are not suitably\naligned, this will get a SIGBUS on sparc and possibly a wrong value on\nARM[0].\n\n[0] http://www.aleph1.co.uk/chapter-10-arm-structured-alignment-faq\n\n-- \nbrian m. carlson / brian with sandals: Houston, Texas, US\n+1 832 623 2791 | http://www.crustytoothpaste.net/~bmc | My opinion only\nOpenPGP: RSA v4 4096b: 88AC E9B2 9196 305B A994 7552 F1BA 225C 0223 B187\n"},{"id":"246389","messageId":"53CAB080.8060005@web.de","threadId":"37164","inReplyTo":"20140719164324.GA5616@vauxhall.crustytoothpaste.net","subject":"Re: [PATCH] fast-import: use hashcmp() for SHA1 hash comparison","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2014-07-19T17:53:04Z","receivedAt":"2014-07-19T17:53:04Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 19.07.2014 18:43, schrieb brian m. carlson:\n> On Sat, Jul 19, 2014 at 02:11:30PM +0200, René Scharfe wrote:\n>> I'd say if a platform doesn't bother optimizing memcmp() then they\n>> deserve the resulting performance.  And it's probably not too bad a\n>> penalty because such comparisons probably won't make up a significant\n>> part of most applications.\n>\n> I tend to agree with this.  On many modern versions of GCC, the compiler\n> can generate an appropriately optimized inline version when it sees a\n> memcmp call, so it's more of a compiler issue then, since no actual call\n> to the function will be emitted.\n\nI just found this open GCC bug entry about glibc memcmp being faster \nthan the inlined version of the compiler: \nhttps://gcc.gnu.org/bugzilla/show_bug.cgi?id=43052.\n\n(Found through \nhttp://randomascii.wordpress.com/2012/10/31/comparing-memory-is-still-tricky/, \nwhich says that the compilers coming with Microsoft Visual Studio 2010 \nand 2012 are not optimizing memcmp() as much as they could as well.)\n\n>>   static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n>>   {\n>> +\tconst uint32_t *p1 = (const uint32_t *)sha1;\n>> +\tconst uint32_t *p2 = (const uint32_t *)sha2;\n>\n> You can't make this cast.  The guaranteed alignment for sha1 and sha2 is\n> 1, and for p1 and p2, it's 4.  If sha1 and sha2 are not suitably\n> aligned, this will get a SIGBUS on sparc and possibly a wrong value on\n> ARM[0].\n>\n> [0] http://www.aleph1.co.uk/chapter-10-arm-structured-alignment-faq\n\nYeah, it was just a test balloon that happens to work on amd64.  We \ncould invent a hash type with correct alignment (a struct with a \nuint32_t[5] member?) and replace all those unsigned char pointers if we \nwanted to go with such a \"vectorized\" hashcmp, but that would be \nmaximally invasive.\n\nRené\n"}]}