{"thread":{"id":"27207","subject":"[PATCH] git gc: Speed it up by 18% via faster hash comparisons","startedAt":"2011-04-27T22:51:14Z","lastAt":"2011-04-29T16:24:08Z","messageCount":45,"participants":["Ingo Molnar","Jonathan Nieder","Junio C Hamano","Ralf Baechle","Bernhard R. Link","Dmitry Potapov","Erik Faye-Lund","Andreas Ericsson","Pekka Enberg","Nguyen Thai Ngoc Duy","Tor Arntsen","H. Peter Anvin","Alex Riesen"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"166569","messageId":"20110427225114.GA16765@elte.hu","threadId":"27207","inReplyTo":null,"subject":"[PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2011-04-27T22:51:14Z","receivedAt":"2011-04-27T22:51:14Z","isPatch":true,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\nLooking at the stalled-cycled profile of a cached 'git gc' i noticed the \nfind_pack_entry_one() entry:\n\n $ perf record -e stalled-cycles -F 10000 ./git gc\n $ perf report\n\n# Events: 26K stalled-cycles\n#\n# Overhead Command Shared Object Symbol\n# ........ .......... ..................... .........................................\n#\n 26.07% git git [.] lookup_object\n 10.22% git libz.so.1.2.5 [.] 0xc43a \n 7.08% git libz.so.1.2.5 [.] inflate\n 6.63% git git [.] find_pack_entry_one\n 5.37% git [kernel.kallsyms] [k] do_raw_spin_lock\n 4.03% git git [.] lookup_blob\n 3.09% git libc-2.13.90.so [.] __strlen_sse42\n 2.81% git libc-2.13.90.so [.] __memcpy_ssse3_back\n\nAnnotation shows:\n\n $ perf annotate find_pack_entry_one\n\n Percent | Source code & Disassembly of git\n------------------------------------------------\n :\n ...\n : int cmp = hashcmp(index + mi * stride, sha1);\n 0.90 : 4b9264: 89 ee mov %ebp,%esi\n 0.45 : 4b9266: 41 0f af f2 imul %r10d,%esi\n 2.86 : 4b926a: 4c 01 de add %r11,%rsi\n 53.34 : 4b926d: f3 a6 repz cmpsb %es:(%rdi),%ds:(%rsi)\n 14.37 : 4b926f: 0f 92 c0 setb %al\n 5.78 : 4b9272: 41 0f 97 c4 seta %r12b\n 1.52 : 4b9276: 41 28 c4 sub %al,%r12b\n\nMost overhead is in hashcmp(), which uses memcmp(), which falls back to \nassembly string operations.\n\nBut we know that hashcmp() compares hashes, which if they do not match, the first byte\nwill differ in 99% of the cases.\n\nSo i tried the patch below: instead of relying on GCC putting in the string \nops, i used an open-coded loop for this relatively short comparison, which does \nnot go beyond the first byte in 99% of the cases.\n\nWhile it at i also open-coded the is_null_sha1() comparison: instead of \ncomparing it to null_sha1[] byte by byte, we can use the sha1 value directly \nand use much more optimal 64-bit and 32-bit comparisons.\n\nThe results were rather surprising:\n\n #\n # Before:\n #\n\n $ perf stat --sync --repeat 10 ./git gc\n\n Performance counter stats for './git gc' (10 runs):\n\n 2771.119892 task-clock # 0.863 CPUs utilized ( +- 0.16% )\n 1,813 context-switches # 0.001 M/sec ( +- 3.06% )\n 167 CPU-migrations # 0.000 M/sec ( +- 2.92% )\n 39,210 page-faults # 0.014 M/sec ( +- 0.26% )\n 8,828,405,654 cycles # 3.186 GHz ( +- 0.13% )\n 2,102,083,909 stalled-cycles # 23.81% of all cycles are idle ( +- 0.52% )\n 8,821,931,740 instructions # 1.00 insns per cycle \n # 0.24 stalled cycles per insn ( +- 0.04% )\n 1,750,408,175 branches # 631.661 M/sec ( +- 0.04% )\n 74,612,120 branch-misses # 4.26% of all branches ( +- 0.07% )\n\n 3.211098537 seconds time elapsed ( +- 1.52% )\n\n[ Note: the --sync option to perf stat emits a sync() before each 'git gc' \n test-run, this reduces the noise of 'elapsed time' numbers enormously. ]\n\n #\n # After:\n #\n\n $ perf stat --sync --repeat 10 ./git gc\n\n Performance counter stats for './git gc' (10 runs):\n\n 2349.498022 task-clock # 0.807 CPUs utilized ( +- 0.15% )\n 1,842 context-switches # 0.001 M/sec ( +- 2.50% )\n 164 CPU-migrations # 0.000 M/sec ( +- 3.67% )\n 39,350 page-faults # 0.017 M/sec ( +- 0.06% )\n 7,484,317,230 cycles # 3.185 GHz ( +- 0.15% )\n 1,577,673,341 stalled-cycles # 21.08% of all cycles are idle ( +- 0.67% )\n 11,067,826,786 instructions # 1.48 insns per cycle \n # 0.14 stalled cycles per insn ( +- 0.02% )\n 2,489,157,909 branches # 1059.442 M/sec ( +- 0.02% )\n 59,384,019 branch-misses # 2.39% of all branches ( +- 0.22% )\n\n 2.910829134 seconds time elapsed ( +- 1.39% )\n\n'git gc' got faster by 18%! Interestingly, 33% of all prior stalled cycles \ndisappeared: most of them turned into actual cycle count savings and speedups.\n\nSo it's rather clear that the string assembly instructions based memcmp is \nsuboptimal for short comparisons like this: there's quite a bit of setup \nlatency in repz cmpsb and the CPU is idling around during that time.\n\n(I ran this on a Nehalem system, so it's a rather fast and modern Intel CPU.)\n\nAlso note another very interesting detail, the number of branch misses went way \ndown, well beyond the measurement noise:\n\n before: 74,612,120 branch-misses # 4.26% of all branches ( +- 0.07% )\n after: 59,384,019 branch-misses # 2.39% of all branches ( +- 0.22% )\n\nOne theory would be that the open-coded loop is easier for the CPU to speculate \nalong, so it produces less branch misses.\n\nThe number of instructions and branches increased - this is mostly because the \nPMU counts a complex 'repz cmpsb' as a single instruction issuing many uops, \nwhile the open-coded loop consists of separate instructions - but roughly the \nsame amount of uops.\n\nI suspect 'git fsck' got faster as well, but i have not measured that.\n\nThere's more string op use in the Git sha1 code, but this was the lowest \nhanging fruit.\n\nThanks,\n\n\tIngo\n\nSigned-off-by: Ingo Molnar \n\ndiff --git a/cache.h b/cache.h\nindex 2674f4c..c5a54fb 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -675,14 +675,33 @@ extern char *sha1_pack_name(const unsigned char *sha1);\n extern char *sha1_pack_index_name(const unsigned char *sha1);\n extern const char *find_unique_abbrev(const unsigned char *sha1, int);\n extern const unsigned char null_sha1[20];\n-static inline int is_null_sha1(const unsigned char *sha1)\n+\n+static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n {\n-\treturn !memcmp(sha1, null_sha1, 20);\n+\tint i;\n+\n+\tfor (i = 0; i < 20; i++, sha1++, sha2++) {\n+\t\tif (*sha1 != *sha2) {\n+\t\t\tif (*sha1 < *sha2)\n+\t\t\t\treturn -1;\n+\t\t\treturn +1;\n+\t\t}\n+\t}\n+\n+\treturn 0;\n }\n-static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n+\n+static inline int is_null_sha1(const unsigned char *sha1)\n {\n-\treturn memcmp(sha1, sha2, 20);\n+\tconst unsigned long long *sha1_64 = (void *)sha1;\n+\tconst unsigned int *sha1_32 = (void *)sha1;\n+\n+\tif (sha1_64[0] || sha1_64[1] || sha1_32[4])\n+\t\treturn 0;\n+\n+\treturn 1;\n }\n+\n static inline void hashcpy(unsigned char *sha_dst, const unsigned char *sha_src)\n {\n \tmemcpy(sha_dst, sha_src, 20);\n"},{"id":"166571","messageId":"20110427231012.GA17807@elte.hu","threadId":"27207","inReplyTo":"20110427225114.GA16765@elte.hu","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2011-04-27T23:10:12Z","receivedAt":"2011-04-27T23:10:12Z","isPatch":true,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Ingo Molnar wrote:\n\n> I suspect 'git fsck' got faster as well, but i have not measured that.\n\nIt got faster a bit:\n\n #\n # Before:\n #\n\n $ perf stat --sync --repeat 5 ./git fsck >/dev/null\n\n Performance counter stats for './git fsck' (5 runs):\n\n 32011.163574 task-clock # 0.998 CPUs utilized ( +- 0.08% )\n 46 context-switches # 0.000 M/sec ( +- 2.77% )\n 0 CPU-migrations # 0.000 M/sec ( +- 0.00% )\n 60,279 page-faults # 0.002 M/sec ( +- 12.21% )\n 102,597,312,322 cycles # 3.205 GHz ( +- 0.08% )\n 27,303,254,781 stalled-cycles # 26.61% of all cycles are idle ( +- 2.51% )\n 152,359,589,474 instructions # 1.49 insns per cycle \n # 0.18 stalled cycles per insn ( +- 0.03% )\n 13,225,673,730 branches # 413.158 M/sec ( +- 0.06% )\n 1,226,749,384 branch-misses # 9.28% of all branches ( +- 0.08% )\n\n 32.083499222 seconds time elapsed ( +- 0.07% )\n\n #\n # After:\n #\n\n Performance counter stats for './git fsck' (5 runs):\n\n 31605.868825 task-clock # 0.998 CPUs utilized ( +- 0.08% )\n 42 context-switches # 0.000 M/sec ( +- 3.92% )\n 0 CPU-migrations # 0.000 M/sec ( +-100.00% )\n 62,979 page-faults # 0.002 M/sec ( +- 14.72% )\n 101,297,181,916 cycles # 3.205 GHz ( +- 0.08% )\n 27,173,614,721 stalled-cycles # 26.83% of all cycles are idle ( +- 0.49% )\n 155,074,859,385 instructions # 1.53 insns per cycle \n # 0.18 stalled cycles per insn ( +- 0.01% )\n 14,132,018,558 branches # 447.133 M/sec ( +- 0.02% )\n 1,207,054,592 branch-misses # 8.54% of all branches ( +- 0.03% )\n\n 31.675135938 seconds time elapsed ( +- 0.08% )\n\nso there's a +1.3% speedup.\n\nBut git fsck stalls are dominated by libz and other external libraries:\n\n# Events: 30K stalled-cycles\n#\n# Overhead Command Shared Object Symbol\n# ........ ....... ..................... ............................\n#\n 36.13% git libz.so.1.2.5 [.] 0x90be \n 18.27% git libc-2.13.90.so [.] __memcpy_ssse3_back\n 13.68% git libcrypto.so.1.0.0d [.] sha1_block_data_order\n 5.85% git libz.so.1.2.5 [.] inflate\n 4.69% git git [.] lookup_object\n 4.58% git libz.so.1.2.5 [.] adler32\n 4.30% git libz.so.1.2.5 [.] 0xc280 \n 2.19% git libc-2.13.90.so [.] _int_malloc\n\nSo those dominate execution time.\n\n\tIngo\n"},{"id":"166572","messageId":"20110427231748.GA26632@elie","threadId":"27207","inReplyTo":"20110427225114.GA16765@elte.hu","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-04-27T23:18:12Z","receivedAt":"2011-04-27T23:18:12Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Ingo Molnar wrote:\n\n> Most overhead is in hashcmp(), which uses memcmp(), which falls back to \n> assembly string operations.\n>\n> But we know that hashcmp() compares hashes, which if they do not match, the first byte\n> will differ in 99% of the cases.\n>\n> So i tried the patch below: instead of relying on GCC putting in the string \n> ops, i used an open-coded loop for this relatively short comparison, which does \n> not go beyond the first byte in 99% of the cases.\n[...]\n> --- a/cache.h\n> +++ b/cache.h\n> @@ -675,14 +675,33 @@ extern char *sha1_pack_name(const unsigned char *sha1);\n[...]\n> +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n> {\n> -\treturn memcmp(sha1, sha2, 20);\n> +\tint i;\n> +\n> +\tfor (i = 0; i < 20; i++, sha1++, sha2++) {\n\nHm. This would be very sensitive to the compiler, since a too-smart\noptimizer could take this loop and rewrite it back to memcmp! So I\nwonder if it's possible to convey this to the compiler more precisely:\n\n\treturn memcmp_probably_differs_early(sha1, sha2, 20);\n\nE.g., how would something like\n\n\tconst unsigned int *start1 = (const unsigned int *) sha1;\n\tconst unsigned int *start2 = (const unsigned int *) sha2;\n\n\tif (likely(*start1 != *start2)) {\n\t\tif (*start1 < *start2)\n\t\t\treturn -1;\n\t\treturn +1;\n\t}\n\treturn memcmp(sha1 + 4, sha2 + 4, 16);\n\nperform?\n\nI suspect we don't have to worry about endianness as long as hashcmp\nyields a consistent ordering, but I haven't checked.\n\nThanks, that was interesting.\n\nRegards,\nJonathan\n"},{"id":"166574","messageId":"7voc3r5kzn.fsf@alter.siamese.dyndns.org","threadId":"27207","inReplyTo":"20110427225114.GA16765@elte.hu","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-04-27T23:32:12Z","receivedAt":"2011-04-27T23:32:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ingo Molnar writes:\n\n> +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n> {\n> -\treturn !memcmp(sha1, null_sha1, 20);\n> +\tint i;\n> +\n> +\tfor (i = 0; i < 20; i++, sha1++, sha2++) {\n> +\t\tif (*sha1 != *sha2) {\n> +\t\t\tif (*sha1 < *sha2)\n> +\t\t\t\treturn -1;\n> +\t\t\treturn +1;\n> +\t\t}\n> +\t}\n> +\n> +\treturn 0;\n\nThis is very unfortunate, as it is so trivially correct and we shouldn't\nhave to do it. If the compiler does not use a good inlined memcmp(), this\npatch may fly, but I fear it may hurt other compilers, no?\n\n> +static inline int is_null_sha1(const unsigned char *sha1)\n> {\n> -\treturn memcmp(sha1, sha2, 20);\n> +\tconst unsigned long long *sha1_64 = (void *)sha1;\n> +\tconst unsigned int *sha1_32 = (void *)sha1;\n\nCan everybody do unaligned accesses just fine?\n"},{"id":"166579","messageId":"20110428003541.GA18382@linux-mips.org","threadId":"27207","inReplyTo":"7voc3r5kzn.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Ralf Baechle","fromEmail":"ralf@linux-mips.org","sentAt":"2011-04-28T00:35:41Z","receivedAt":"2011-04-28T00:35:41Z","isPatch":true,"sender":{"key":"ralf@linux-mips.org","avatar":null},"body":"On Wed, Apr 27, 2011 at 04:32:12PM -0700, Junio C Hamano wrote:\n\n> > +static inline int is_null_sha1(const unsigned char *sha1)\n> > {\n> > -\treturn memcmp(sha1, sha2, 20);\n> > +\tconst unsigned long long *sha1_64 = (void *)sha1;\n> > +\tconst unsigned int *sha1_32 = (void *)sha1;\n> \n> Can everybody do unaligned accesses just fine?\n\nMisaligned accesses cause exceptions on some architectures which then\nare fixed up in software making these accesses _very_ slow. You can\nuse __attribute__((packed)) to work around that but that will on the\naffected architectures make gcc generate code pessimistically that is\nslower than not using __attribute__((packed)) in case of proper\nalignment. And __attribute__((packed)) only works with GCC.\n\n Ralf\n"},{"id":"166600","messageId":"20110428062717.GA952@elte.hu","threadId":"27207","inReplyTo":"7voc3r5kzn.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2011-04-28T06:27:17Z","receivedAt":"2011-04-28T06:27:17Z","isPatch":true,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Junio C Hamano wrote:\n\n> Ingo Molnar writes:\n> \n> > +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n> > {\n> > -\treturn !memcmp(sha1, null_sha1, 20);\n> > +\tint i;\n> > +\n> > +\tfor (i = 0; i < 20; i++, sha1++, sha2++) {\n> > +\t\tif (*sha1 != *sha2) {\n> > +\t\t\tif (*sha1 < *sha2)\n> > +\t\t\t\treturn -1;\n> > +\t\t\treturn +1;\n> > +\t\t}\n> > +\t}\n> > +\n> > +\treturn 0;\n> \n> This is very unfortunate, as it is so trivially correct and we shouldn't\n> have to do it. If the compiler does not use a good inlined memcmp(), this\n> patch may fly, but I fear it may hurt other compilers, no?\n\nWell, i used a very fresh GCC version:\n\n gcc version 4.6.0 20110419 (Red Hat 4.6.0-5) (GCC)\n\nAnd used a relatively fresh CPU as well. So given how compiler and CPU versions \ntrickle down to users and how long they live there Git will live with this \ncombination for years to come.\n\nSecondly, the combined speedup of the cached case with my two patches appears \nto be more than 30% on my testbox so it's a very nifty win from two relatively \nsimple changes.\n\nShould a compiler ever turn this into suboptimal code again we can revisit the \nissue once more - it's not like we *can* keep the compiler from messing up the \nassembly output! :-) ...\n\n> > +static inline int is_null_sha1(const unsigned char *sha1)\n> > {\n> > -\treturn memcmp(sha1, sha2, 20);\n> > +\tconst unsigned long long *sha1_64 = (void *)sha1;\n> > +\tconst unsigned int *sha1_32 = (void *)sha1;\n> \n> Can everybody do unaligned accesses just fine?\n\nI have added some quick debug code and none of the sha1 pointers (in my \nadmittedly very limited) testing showed misaligned pointers on 64-bit systems.\n\nOn 32-bit systems the pointer might be 32-bit aligned only - the patch below \nimplements the function 32-bit comparisons.\n\nBut is_null_sha1() is not called that often in the tests i've done so we could \nkeep it untouched as well.\n\nThanks,\n\n\tIngo\n\ndiff --git a/cache.h b/cache.h\nindex 2674f4c..427ad5a 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -675,14 +675,32 @@ extern char *sha1_pack_name(const unsigned char *sha1);\n extern char *sha1_pack_index_name(const unsigned char *sha1);\n extern const char *find_unique_abbrev(const unsigned char *sha1, int);\n extern const unsigned char null_sha1[20];\n-static inline int is_null_sha1(const unsigned char *sha1)\n+\n+static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n {\n-\treturn !memcmp(sha1, null_sha1, 20);\n+\tint i;\n+\n+\tfor (i = 0; i < 20; i++, sha1++, sha2++) {\n+\t\tif (*sha1 != *sha2) {\n+\t\t\tif (*sha1 < *sha2)\n+\t\t\t\treturn -1;\n+\t\t\treturn +1;\n+\t\t}\n+\t}\n+\n+\treturn 0;\n }\n-static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n+\n+static inline int is_null_sha1(const unsigned char *sha1)\n {\n-\treturn memcmp(sha1, sha2, 20);\n+\tconst unsigned int *sha1_32 = (void *)sha1;\n+\n+\tif (sha1_32[0] || sha1_32[1] || sha1_32[2] || sha1_32[3] || sha1_32[4])\n+\t\treturn 0;\n+\n+\treturn 1;\n }\n+\n static inline void hashcpy(unsigned char *sha_dst, const unsigned char *sha_src)\n {\n \tmemcpy(sha_dst, sha_src, 20);\n"},{"id":"166601","messageId":"20110428063625.GB952@elte.hu","threadId":"27207","inReplyTo":"20110427231748.GA26632@elie","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2011-04-28T06:36:25Z","receivedAt":"2011-04-28T06:36:25Z","isPatch":true,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Jonathan Nieder wrote:\n\n> Ingo Molnar wrote:\n> \n> > Most overhead is in hashcmp(), which uses memcmp(), which falls back to \n> > assembly string operations.\n> >\n> > But we know that hashcmp() compares hashes, which if they do not match, the first byte\n> > will differ in 99% of the cases.\n> >\n> > So i tried the patch below: instead of relying on GCC putting in the string \n> > ops, i used an open-coded loop for this relatively short comparison, which does \n> > not go beyond the first byte in 99% of the cases.\n> [...]\n> > --- a/cache.h\n> > +++ b/cache.h\n> > @@ -675,14 +675,33 @@ extern char *sha1_pack_name(const unsigned char *sha1);\n> [...]\n> > +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n> > {\n> > -\treturn memcmp(sha1, sha2, 20);\n> > +\tint i;\n> > +\n> > +\tfor (i = 0; i < 20; i++, sha1++, sha2++) {\n> \n> Hm. This would be very sensitive to the compiler, since a too-smart \n> optimizer could take this loop and rewrite it back to memcmp! So I wonder if \n> it's possible to convey this to the compiler more precisely:\n> \n> \treturn memcmp_probably_differs_early(sha1, sha2, 20);\n> \n> E.g., how would something like\n> \n> \tconst unsigned int *start1 = (const unsigned int *) sha1;\n> \tconst unsigned int *start2 = (const unsigned int *) sha2;\n> \n> \tif (likely(*start1 != *start2)) {\n> \t\tif (*start1 < *start2)\n> \t\t\treturn -1;\n> \t\treturn +1;\n> \t}\n> \treturn memcmp(sha1 + 4, sha2 + 4, 16);\n>\n> perform?\n\nNote that this function wont work on like 99% of the systems out there due to \nendianness assumptions in Git.\n\nAlso, your hypothetical smart compiler would recognize the above as equivalent \nto memcmp(sha1, sha2, 20) and could rewrite it again - so we'd be back to \nsquare 1.\n\nAs i argued in my other mail in this thread, it's hard to keep a compiler from \nmessing up its assembly output if it really wants to mess up - we'll deal with \nit when that happens. I used a very fresh compiler and a modern CPU for my \ntesting - so even if very, very new compilers improve this problem somehow it \nwill stay with us for a long, long time.\n\nHaving said that, it would be nice if someone could test these two patches on a \nmodern AMD box, using the perf stat from here:\n\n http://people.redhat.com/mingo/tip.git/README\n\n cd tools/perf/\n make -j install\n\nand do something like this to test git gc's performance:\n\n $ perf stat --sync --repeat 10 ./git gc\n\n... to see whether these speedups are generic, or somehow Intel CPU specific.\n\n> I suspect we don't have to worry about endianness as long as hashcmp\n> yields a consistent ordering, but I haven't checked.\n\nWell i messed up endianness in an early version of this patch and 'git gc' was \neminently unhappy about it! I have not figured out which part of Git relies on \nthe comparison result though - most places seem to use the result as a boolean.\n\nThanks,\n\n\tIngo\n"},{"id":"166605","messageId":"20110428081817.GA29344@pcpool00.mathematik.uni-freiburg.de","threadId":"27207","inReplyTo":"20110428003541.GA18382@linux-mips.org","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Bernhard R. Link","fromEmail":"brl+ccmadness@pcpool00.mathematik.uni-freiburg.de","sentAt":"2011-04-28T08:18:17Z","receivedAt":"2011-04-28T08:18:17Z","isPatch":true,"sender":{"key":"brl+ccmadness@pcpool00.mathematik.uni-freiburg.de","avatar":null},"body":"* Ralf Baechle [110428 02:35]:\n> On Wed, Apr 27, 2011 at 04:32:12PM -0700, Junio C Hamano wrote:\n> \n> > > +static inline int is_null_sha1(const unsigned char *sha1)\n> > > {\n> > > -\treturn memcmp(sha1, sha2, 20);\n> > > +\tconst unsigned long long *sha1_64 = (void *)sha1;\n> > > +\tconst unsigned int *sha1_32 = (void *)sha1;\n> > \n> > Can everybody do unaligned accesses just fine?\n> \n> Misaligned accesses cause exceptions on some architectures which then\n> are fixed up in software making these accesses _very_ slow. You can\n> use __attribute__((packed)) to work around that but that will on the\n> affected architectures make gcc generate code pessimistically that is\n> slower than not using __attribute__((packed)) in case of proper\n> alignment. And __attribute__((packed)) only works with GCC.\n\nEven __attribute__((packed)) usually does not allow arbitrary aligned\ndata, but can intruct the code to generate code to access code\nmisaligned in a special way. (I have already seen code where thus\naccessing a properly aligned long caused a SIGBUS, because it was\naligned because being in a misaligned packed struct).\n\nIn short: misaligning stuff works on x86, everywhere else it is disaster\nwaiting to happen. (And people claiming compiler bugs or broken\narchitectures, just because they do not know the basic rules of C).\n\n\tBernhard R. Link\n"},{"id":"166606","messageId":"BANLkTim7bbFiSsj3PRr-_yM5gh1txYQR5w@mail.gmail.com","threadId":"27207","inReplyTo":"20110427225114.GA16765@elte.hu","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Dmitry Potapov","fromEmail":"dpotapov@gmail.com","sentAt":"2011-04-28T08:52:16Z","receivedAt":"2011-04-28T08:52:16Z","isPatch":true,"sender":{"key":"dpotapov@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6568595?v=4"},"body":"2011/4/28 Ingo Molnar :\n> +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n>  {\n> -       return !memcmp(sha1, null_sha1, 20);\n> +       int i;\n> +\n> +       for (i = 0; i < 20; i++, sha1++, sha2++) {\n> +               if (*sha1 != *sha2) {\n\nAt the very least, you may want to put 'likely' in this 'if'\ncondition, otherwise the compiler may optimize this loop in\nthe same way as with memcmp. So, it may work well now, but\nit may not work much slower with future versions or different\nlevel of optimization. (AFAIK, -O3 is far more aggressive in\noptimizing of loops).\n\nAnother thing is that so far this optimization was only with\nGCC, and we do not know whether it helps or harms to compilers.\nSo, maybe placing this code under 'ifdef __GNUC__' makes more\nsense than pushing this change on other compilers too.\n\n\nDmitry\n"},{"id":"166608","messageId":"20110428091110.GA14431@elte.hu","threadId":"27207","inReplyTo":"BANLkTim7bbFiSsj3PRr-_yM5gh1txYQR5w@mail.gmail.com","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2011-04-28T09:11:10Z","receivedAt":"2011-04-28T09:11:10Z","isPatch":true,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Dmitry Potapov wrote:\n\n> 2011/4/28 Ingo Molnar :\n> > +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n> >  {\n> > -       return !memcmp(sha1, null_sha1, 20);\n> > +       int i;\n> > +\n> > +       for (i = 0; i < 20; i++, sha1++, sha2++) {\n> > +               if (*sha1 != *sha2) {\n> \n> At the very least, you may want to put 'likely' in this 'if'\n> condition, otherwise the compiler may optimize this loop in\n> the same way as with memcmp. So, it may work well now, but\n> it may not work much slower with future versions or different\n> level of optimization. (AFAIK, -O3 is far more aggressive in\n> optimizing of loops).\n\nthe main difference is between the string assembly instructions and the loop. \nModern CPUs will hardly notice this loop being emitted with slight variations \nby the compiler. So i do not share this concern.\n\n> Another thing is that so far this optimization was only with\n> GCC, and we do not know whether it helps or harms to compilers.\n> So, maybe placing this code under 'ifdef __GNUC__' makes more\n> sense than pushing this change on other compilers too.\n\nWell, given that 90%+ of Git development is done with GCC (and probably the \nuser share is similarly high as well):\n\n aldebaran:~/git> git log --pretty=oneline -i --grep gcc | wc -l\n 127\n aldebaran:~/git> git log --pretty=oneline -i --grep llvm | wc -l\n 1\n\nand given that these two patches speed up 'git gc' by 30%+, i doubt we'd want \nto litter core Git code with #ifdef __GNUC__ uglinesses.\n\nThanks,\n\n\tIngo\n"},{"id":"166611","messageId":"BANLkTik_2sHZ0OTgQeHpRnpmNsAmT=sAcA@mail.gmail.com","threadId":"27207","inReplyTo":"20110428062717.GA952@elte.hu","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Erik Faye-Lund","fromEmail":"kusmabite@gmail.com","sentAt":"2011-04-28T09:17:26Z","receivedAt":"2011-04-28T09:17:26Z","isPatch":true,"sender":{"key":"kusmabite@gmail.com","avatar":"https://avatars.githubusercontent.com/u/47073?v=4"},"body":"2011/4/28 Ingo Molnar :\n>\n> * Junio C Hamano wrote:\n>\n>> Ingo Molnar writes:\n>>\n>> > +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n>> >  {\n>> > -   return !memcmp(sha1, null_sha1, 20);\n>> > +   int i;\n>> > +\n>> > +   for (i = 0; i < 20; i++, sha1++, sha2++) {\n>> > +           if (*sha1 != *sha2) {\n>> > +                   if (*sha1 < *sha2)\n>> > +                           return -1;\n>> > +                   return +1;\n>> > +           }\n\nWhy not just:\n\nif (*sha1 != *sha2)\n return *sha2 - *sha1;\n\nmemcmp isn't guaranteed to return onlt the values -1, 0, +1, it can\nreturn any value, just as long as it's sign of a non-zero return\nexpress the relationship between the first mis-matching byte.\n\n>> > +   }\n>> > +\n>> > +   return 0;\n>>\n>> This is very unfortunate, as it is so trivially correct and we shouldn't\n>> have to do it.  If the compiler does not use a good inlined memcmp(), this\n>> patch may fly, but I fear it may hurt other compilers, no?\n\nIf the common case is that the hashes are random (as the assumption in\nthis patch is), then this patch should give very close to ideal\nperformance, no? A good memcmp might be faster when there's a match;\nbut how often do we really compare SHA-1's that are identical?\n\nI see your worry, but if the assumption is correct, I doubt it'd turn\nout to be a real problem. ~99.6% of the time we'd early-out on the\nfirst byte, which is ideal.\n\nIf comparing identical SHA-1's are important, perhaps just having a\nearly-out just on the first byte and then doing memcmp is a good\nsolution (similar to what Jonathan Nieder proposed, but without\nalignment problems)?\n\n> Secondly, the combined speedup of the cached case with my two patches appears\n> to be more than 30% on my testbox so it's a very nifty win from two relatively\n> simple changes.\n\nThat speed-up was on ONE test vector, no? There are a lot of other\nuses of hash-comparisons in Git, did you measure those?\n\n>> > +static inline int is_null_sha1(const unsigned char *sha1)\n>> >  {\n>> > -   return memcmp(sha1, sha2, 20);\n>> > +   const unsigned long long *sha1_64 = (void *)sha1;\n>> > +   const unsigned int *sha1_32 = (void *)sha1;\n>>\n>> Can everybody do unaligned accesses just fine?\n>\n> I have added some quick debug code and none of the sha1 pointers (in my\n> admittedly very limited) testing showed misaligned pointers on 64-bit systems.\n>\n> On 32-bit systems the pointer might be 32-bit aligned only - the patch below\n> implements the function 32-bit comparisons.\n\nThat's simply wrong. Unsigned char arrays can and will be unaligned,\nand this causes exceptions on most architectures (x86 is pretty much\nthe exception here). While some systems for these architectures\nsupport unaligned reads from the exception handler, others doesn't. So\nthis patch is pretty much guaranteed to cause a crash in some setups.\n"},{"id":"166613","messageId":"20110428093120.GA377@elie","threadId":"27207","inReplyTo":"20110428063625.GB952@elte.hu","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-04-28T09:31:21Z","receivedAt":"2011-04-28T09:31:21Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Ingo Molnar wrote:\n> * Jonathan Nieder wrote:\n\n>> E.g., how would something like\n>>\n>> \tconst unsigned int *start1 = (const unsigned int *) sha1;\n>> \tconst unsigned int *start2 = (const unsigned int *) sha2;\n>>\n>> \tif (likely(*start1 != *start2)) {\n>> \t\tif (*start1 < *start2)\n>> \t\t\treturn -1;\n>> \t\treturn +1;\n>> \t}\n>> \treturn memcmp(sha1 + 4, sha2 + 4, 16);\n>>\n>> perform?\n>\n> Note that this function wont work on like 99% of the systems out there due to \n> endianness assumptions in Git.\n\nYes, I was greedy and broke the semantics, and my suggestion was\nnonsensical for other reasons (e.g., alignment), too. I should have\nwritten something like:\n\n\tif (likely(*sha1 != *sha2)) {\n\t\tif (*sha1 < *sha2)\n\t\t\treturn -1;\n\t\treturn +1;\n\t}\n\treturn memcmp(sha1, sha2, 20);\n\nsince speeding it up 255/256 times seems good enough already.\n\n> Also, your hypothetical smart compiler would recognize the above as equivalent \n> to memcmp(sha1, sha2, 20) and could rewrite it again - so we'd be back to \n> square 1.\n\nTrue. The real point is a \"likely\" to explain to human readers what\nis happening.\n\n> Having said that, it would be nice if someone could test these two patches on a \n> modern AMD box, using the perf stat from here:\n>\n> http://people.redhat.com/mingo/tip.git/README\n>\n> cd tools/perf/\n> make -j install\n>\n> and do something like this to test git gc's performance:\n>\n> $ perf stat --sync --repeat 10 ./git gc\n>\n> ... to see whether these speedups are generic, or somehow Intel CPU specific.\n\nSounds like fun. Will try to find time to play around with this in\nthe next few days.\n\n> Well i messed up endianness in an early version of this patch and 'git gc' was\n> eminently unhappy about it! I have not figured out which part of Git relies on\n> the comparison result though - most places seem to use the result as a boolean.\n\nI think hashcmp is used to run binary searches within a packfile\nindex. Thanks for explaining.\n\nRegards,\nJonathan\n"},{"id":"166614","messageId":"BANLkTikWd8=1RbY78tPFMVhuV05eKVzjkg@mail.gmail.com","threadId":"27207","inReplyTo":"20110428091110.GA14431@elte.hu","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Dmitry Potapov","fromEmail":"dpotapov@gmail.com","sentAt":"2011-04-28T09:31:53Z","receivedAt":"2011-04-28T09:31:53Z","isPatch":true,"sender":{"key":"dpotapov@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6568595?v=4"},"body":"2011/4/28 Ingo Molnar :\n>\n> * Dmitry Potapov wrote:\n>\n>> 2011/4/28 Ingo Molnar :\n>> > +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n>> >  {\n>> > -       return !memcmp(sha1, null_sha1, 20);\n>> > +       int i;\n>> > +\n>> > +       for (i = 0; i < 20; i++, sha1++, sha2++) {\n>> > +               if (*sha1 != *sha2) {\n>>\n>> At the very least, you may want to put 'likely' in this 'if'\n>> condition, otherwise the compiler may optimize this loop in\n>> the same way as with memcmp. So, it may work well now, but\n>> it may not work much slower with future versions or different\n>> level of optimization. (AFAIK, -O3 is far more aggressive in\n>> optimizing of loops).\n>\n> the main difference is between the string assembly instructions and the loop.\n> Modern CPUs will hardly notice this loop being emitted with slight variations\n> by the compiler. So i do not share this concern.\n\nHere you make an assumption what kind of optimization the compiler\ncan do. As Jonathan noticed above, theoretically a smart compiler\ncan turn this loop into memcmp (or code very similar to memcmp).\n\nThe reason why memcmp does not work well is that it is optimized\nfor the worst case scenario (where beginning of two strings is\nthe same), while _we_ know that with a hash it very unlikely,\nand we want to conduct this knowledge to the compiler in some\nway. Just re-writing memcmp as explicit loop does not conduct\nthis knowledge.\n\nTherefore, I believe it makes sense to add 'likely'. I have not\ntested this code, but in the past, I had a very similar code\nwhich was compiled with -O3, and just putting likely turned out\nto 40% speed-up for that comparison function.\n\n\nDmitry\n"},{"id":"166615","messageId":"BANLkTin+qb6j8p+kOTEkQ2iK29ZWOsRk-g@mail.gmail.com","threadId":"27207","inReplyTo":"20110427231748.GA26632@elie","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Dmitry Potapov","fromEmail":"dpotapov@gmail.com","sentAt":"2011-04-28T09:32:56Z","receivedAt":"2011-04-28T09:32:56Z","isPatch":true,"sender":{"key":"dpotapov@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6568595?v=4"},"body":"2011/4/28 Jonathan Nieder :\n>\n> Hm.  This would be very sensitive to the compiler, since a too-smart\n> optimizer could take this loop and rewrite it back to memcmp!  So I\n> wonder if it's possible to convey this to the compiler more precisely:\n>\n>        return memcmp_probably_differs_early(sha1, sha2, 20);\n>\n> E.g., how would something like\n>\n>        const unsigned int *start1 = (const unsigned int *) sha1;\n>        const unsigned int *start2 = (const unsigned int *) sha2;\n>\n>        if (likely(*start1 != *start2)) {\n>                if (*start1 < *start2)\n\nIt can be a problem with unalligned access. So, IMHO, it is\nbetter to use get_be32 here:\n\n        unsigned start1 = get_be32(sha1);\n        unsigned start2 = get_be32(sha2);\n\n        if (likely(start1 != start2)) {\n                if (start1 < start2)\n\n...\n\nDmitry\n"},{"id":"166616","messageId":"20110428093307.GA15349@elte.hu","threadId":"27207","inReplyTo":"BANLkTik_2sHZ0OTgQeHpRnpmNsAmT=sAcA@mail.gmail.com","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2011-04-28T09:33:07Z","receivedAt":"2011-04-28T09:33:07Z","isPatch":true,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Erik Faye-Lund wrote:\n\n> 2011/4/28 Ingo Molnar :\n> >\n> > * Junio C Hamano wrote:\n> >\n> >> Ingo Molnar writes:\n> >>\n> >> > +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n> >> >  {\n> >> > -   return !memcmp(sha1, null_sha1, 20);\n> >> > +   int i;\n> >> > +\n> >> > +   for (i = 0; i < 20; i++, sha1++, sha2++) {\n> >> > +           if (*sha1 != *sha2) {\n> >> > +                   if (*sha1 < *sha2)\n> >> > +                           return -1;\n> >> > +                   return +1;\n> >> > +           }\n> \n> Why not just:\n> \n> if (*sha1 != *sha2)\n> return *sha2 - *sha1;\n\nYou mean \"*sha1 - *sha2\", right?\n\n> memcmp isn't guaranteed to return onlt the values -1, 0, +1, it can\n> return any value, just as long as it's sign of a non-zero return\n> express the relationship between the first mis-matching byte.\n\nYeah, agreed, updated patch below. Seems to work fine here.\n\n\tIngo\n\nSigned-off-by: Ingo Molnar \n\ndiff --git a/cache.h b/cache.h\nindex 2674f4c..574c948 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -675,14 +675,30 @@ extern char *sha1_pack_name(const unsigned char *sha1);\n extern char *sha1_pack_index_name(const unsigned char *sha1);\n extern const char *find_unique_abbrev(const unsigned char *sha1, int);\n extern const unsigned char null_sha1[20];\n-static inline int is_null_sha1(const unsigned char *sha1)\n+\n+static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n {\n-\treturn !memcmp(sha1, null_sha1, 20);\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+\t}\n+\n+\treturn 0;\n }\n-static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n+\n+static inline int is_null_sha1(const unsigned char *sha1)\n {\n-\treturn memcmp(sha1, sha2, 20);\n+\tconst unsigned long long *sha1_64 = (void *)sha1;\n+\tconst unsigned int *sha1_32 = (void *)sha1;\n+\n+\tif (sha1_64[0] || sha1_64[1] || sha1_32[4])\n+\t\treturn 0;\n+\n+\treturn 1;\n }\n+\n static inline void hashcpy(unsigned char *sha_dst, const unsigned char *sha_src)\n {\n \tmemcpy(sha_dst, sha_src, 20);\n"},{"id":"166618","messageId":"20110428093703.GB15349@elte.hu","threadId":"27207","inReplyTo":"BANLkTik_2sHZ0OTgQeHpRnpmNsAmT=sAcA@mail.gmail.com","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2011-04-28T09:37:03Z","receivedAt":"2011-04-28T09:37:03Z","isPatch":true,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Erik Faye-Lund wrote:\n\n> > Secondly, the combined speedup of the cached case with my two patches \n> > appears to be more than 30% on my testbox so it's a very nifty win from two \n> > relatively simple changes.\n> \n> That speed-up was on ONE test vector, no? There are a lot of other uses of \n> hash-comparisons in Git, did you measure those?\n\nI picked this hash function because it showed up in the profile (see the \nprofile i posted). There's one other hash that mattered as well in the profile, \nsee the lookup_object() patch i sent yesterday.\n\n> > I have added some quick debug code and none of the sha1 pointers (in my \n> > admittedly very limited) testing showed misaligned pointers on 64-bit \n> > systems.\n> >\n> > On 32-bit systems the pointer might be 32-bit aligned only - the patch \n> > below implements the function 32-bit comparisons.\n> \n> That's simply wrong. Unsigned char arrays can and will be unaligned, and this \n> causes exceptions on most architectures (x86 is pretty much the exception \n> here). While some systems for these architectures support unaligned reads \n> from the exception handler, others doesn't. So this patch is pretty much \n> guaranteed to cause a crash in some setups.\n\nIf unsigned char arrays are allocated unaligned then that's another bug i \nsuspect that should be fixed. Unaligned access on x86 is not free either - \nthere's cycle penalties.\n\nAlas, i have not seen these sha1 hash buffers being allocated unaligned (in my \nvery limited testing). In which spots are they allocated unaligned?\n\nThanks,\n\n\tIngo\n"},{"id":"166617","messageId":"20110428093837.GA15847@elte.hu","threadId":"27207","inReplyTo":"20110428091110.GA14431@elte.hu","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2011-04-28T09:38:37Z","receivedAt":"2011-04-28T09:38:37Z","isPatch":true,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Ingo Molnar wrote:\n\n> > Another thing is that so far this optimization was only with\n> > GCC, and we do not know whether it helps or harms to compilers.\n> > So, maybe placing this code under 'ifdef __GNUC__' makes more\n> > sense than pushing this change on other compilers too.\n> \n> Well, given that 90%+ of Git development is done with GCC (and probably the \n> user share is similarly high as well):\n> \n> aldebaran:~/git> git log --pretty=oneline -i --grep gcc | wc -l\n> 127\n> aldebaran:~/git> git log --pretty=oneline -i --grep llvm | wc -l\n> 1\n\nI left out:\n\n aldebaran:~/git> git log --pretty=oneline -i --grep clang | wc -l\n 5\n\nStill well within the 90%+ figure.\n\nThanks,\n\n\tIngo\n"},{"id":"166619","messageId":"4DB9367B.2050607@op5.se","threadId":"27207","inReplyTo":"20110428081817.GA29344@pcpool00.mathematik.uni-freiburg.de","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2011-04-28T09:42:19Z","receivedAt":"2011-04-28T09:42:19Z","isPatch":true,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"On 04/28/2011 10:18 AM, Bernhard R. Link wrote:\n> * Ralf Baechle [110428 02:35]:\n>> On Wed, Apr 27, 2011 at 04:32:12PM -0700, Junio C Hamano wrote:\n>>\n>>>> +static inline int is_null_sha1(const unsigned char *sha1)\n>>>> {\n>>>> -\treturn memcmp(sha1, sha2, 20);\n>>>> +\tconst unsigned long long *sha1_64 = (void *)sha1;\n>>>> +\tconst unsigned int *sha1_32 = (void *)sha1;\n>>>\n>>> Can everybody do unaligned accesses just fine?\n>>\n>> Misaligned accesses cause exceptions on some architectures which then\n>> are fixed up in software making these accesses _very_ slow. You can\n>> use __attribute__((packed)) to work around that but that will on the\n>> affected architectures make gcc generate code pessimistically that is\n>> slower than not using __attribute__((packed)) in case of proper\n>> alignment. And __attribute__((packed)) only works with GCC.\n> \n> Even __attribute__((packed)) usually does not allow arbitrary aligned\n> data, but can intruct the code to generate code to access code\n> misaligned in a special way. (I have already seen code where thus\n> accessing a properly aligned long caused a SIGBUS, because it was\n> aligned because being in a misaligned packed struct).\n> \n> In short: misaligning stuff works on x86, everywhere else it is disaster\n> waiting to happen. (And people claiming compiler bugs or broken\n> architectures, just because they do not know the basic rules of C).\n> \n\nGiven that the vast majority of user systems are x86 style ones, it's\nprobably worth using this patch on such systems and stick to a\npartially unrolled byte-by-byte comparison that finishes early on\nthe rest of them. Properly pipelined, it will just mean that the early\nreturn undoes the fetch steps for the 3-4 unrolled bytes that it\ncomputes in advance, so if the diff comes in the first 10-12 bytes,\nit will still be a win.\n\nFor bonus points, check if both bytestrings are equally (un)aligned\nfirst and, if they are, half-Duff it out with a fallthrough switch\nstatement (without the while() loop) to compare byte-by-byte first\nand then word-for-word on the rest of it. The setup and complexity\nis probably not worth it for our meager 20-byte strings though.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n\nConsidering the successes of the wars on alcohol, poverty, drugs and\nterror, I think we should give some serious thought to declaring war\non peace.\n"},{"id":"166621","messageId":"20110428094459.GA15952@elte.hu","threadId":"27207","inReplyTo":"BANLkTikWd8=1RbY78tPFMVhuV05eKVzjkg@mail.gmail.com","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2011-04-28T09:44:59Z","receivedAt":"2011-04-28T09:44:59Z","isPatch":true,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Dmitry Potapov wrote:\n\n> 2011/4/28 Ingo Molnar :\n> >\n> > * Dmitry Potapov wrote:\n> >\n> >> 2011/4/28 Ingo Molnar :\n> >> > +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n> >> >  {\n> >> > -       return !memcmp(sha1, null_sha1, 20);\n> >> > +       int i;\n> >> > +\n> >> > +       for (i = 0; i < 20; i++, sha1++, sha2++) {\n> >> > +               if (*sha1 != *sha2) {\n> >>\n> >> At the very least, you may want to put 'likely' in this 'if'\n> >> condition, otherwise the compiler may optimize this loop in\n> >> the same way as with memcmp. So, it may work well now, but\n> >> it may not work much slower with future versions or different\n> >> level of optimization. (AFAIK, -O3 is far more aggressive in\n> >> optimizing of loops).\n> >\n> > the main difference is between the string assembly instructions and the loop.\n> > Modern CPUs will hardly notice this loop being emitted with slight variations\n> > by the compiler. So i do not share this concern.\n> \n> Here you make an assumption what kind of optimization the compiler\n> can do. [...]\n\nI make no assumption there because rule #1 is that the compiler can pretty well \ndo what it wants and we have little control over that.\n\n> [...] As Jonathan noticed above, theoretically a smart compiler can turn this \n> loop into memcmp (or code very similar to memcmp).\n\nYes, and in practice it does not, and in practice we can speed up git gc \nmeasurably.\n\n> The reason why memcmp does not work well is that it is optimized\n> for the worst case scenario (where beginning of two strings is\n> the same), while _we_ know that with a hash it very unlikely,\n> and we want to conduct this knowledge to the compiler in some\n> way. Just re-writing memcmp as explicit loop does not conduct\n> this knowledge.\n> \n> Therefore, I believe it makes sense to add 'likely'. I have not\n> tested this code, but in the past, I had a very similar code\n> which was compiled with -O3, and just putting likely turned out\n> to 40% speed-up for that comparison function.\n\nYou guys can certainly add the 'likely()' if you want to (it likely wont hurt) \n- but note that the compiler can *still* turn it into a memcpy() - see rule #1 \nabove.\n\nNote that Git does not have a likely() facility at the moment and \n__builtin_expect() is a GNU extension. Should be a separate patch.\n\nThanks,\n\n\tIngo\n"},{"id":"166623","messageId":"BANLkTim+Kk_ah_4+pQKCi8bXtA8thRVRjQ@mail.gmail.com","threadId":"27207","inReplyTo":"20110428093703.GB15349@elte.hu","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Erik Faye-Lund","fromEmail":"kusmabite@gmail.com","sentAt":"2011-04-28T09:50:06Z","receivedAt":"2011-04-28T09:50:06Z","isPatch":true,"sender":{"key":"kusmabite@gmail.com","avatar":"https://avatars.githubusercontent.com/u/47073?v=4"},"body":"2011/4/28 Ingo Molnar :\n>\n> * Erik Faye-Lund wrote:\n>\n>> > Secondly, the combined speedup of the cached case with my two patches\n>> > appears to be more than 30% on my testbox so it's a very nifty win from two\n>> > relatively simple changes.\n>>\n>> That speed-up was on ONE test vector, no? There are a lot of other uses of\n>> hash-comparisons in Git, did you measure those?\n>\n> I picked this hash function because it showed up in the profile (see the\n> profile i posted). There's one other hash that mattered as well in the profile,\n> see the lookup_object() patch i sent yesterday.\n>\n\nMy point was that the 30% improvement was in \"git gc\", which is not\nthe only important use-case. How does this affect other git commands?\n\nMy suspicion is that it's generally an improvement, but I don't know\nfor sure. I think something like this might be an acceptable\ntrade-off, though:\n\ndiff --git a/cache.h b/cache.h\nindex c730c58..50b6f55 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -687,6 +687,10 @@ static inline int is_null_sha1(const unsigned char *sha1)\n }\n static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n {\n+\t/* early out for fast mis-match */\n+\tif (*sha1 != *sha2)\n+\t\treturn *sha2 - *sha1;\n+\n \treturn memcmp(sha1, sha2, 20);\n }\n static inline void hashcpy(unsigned char *sha_dst, const unsigned\nchar *sha_src)\n\n>> > I have added some quick debug code and none of the sha1 pointers (in my\n>> > admittedly very limited) testing showed misaligned pointers on 64-bit\n>> > systems.\n>> >\n>> > On 32-bit systems the pointer might be 32-bit aligned only - the patch\n>> > below implements the function 32-bit comparisons.\n>>\n>> That's simply wrong. Unsigned char arrays can and will be unaligned, and this\n>> causes exceptions on most architectures (x86 is pretty much the exception\n>> here). While some systems for these architectures support unaligned reads\n>> from the exception handler, others doesn't. So this patch is pretty much\n>> guaranteed to cause a crash in some setups.\n>\n> If unsigned char arrays are allocated unaligned then that's another bug i\n> suspect that should be fixed.\n\nWe can't. The compiler decides the alignment of variables on the\nstack. Some compilers / compiler-setting pairs might align\nchar-arrays, while others might not.\n\n> Unaligned access on x86 is not free either -\n> there's cycle penalties.\n>\n> Alas, i have not seen these sha1 hash buffers being allocated unaligned (in my\n> very limited testing). In which spots are they allocated unaligned?\n\nLike I said above, it can happen when allocated on the stack. But it\ncan also happen in malloc'ed structs, or in global variables. An array\nis aligned to the size of it's base member type. But malloc does\nworst-case-allignment, because it happens at run-time without\ntype-information.\n"},{"id":"166622","messageId":"BANLkTikU3evfo86WmQeVS_Z41s3xSK1DJw@mail.gmail.com","threadId":"27207","inReplyTo":"4DB9367B.2050607@op5.se","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Erik Faye-Lund","fromEmail":"kusmabite@gmail.com","sentAt":"2011-04-28T09:55:57Z","receivedAt":"2011-04-28T09:55:57Z","isPatch":true,"sender":{"key":"kusmabite@gmail.com","avatar":"https://avatars.githubusercontent.com/u/47073?v=4"},"body":"On Thu, Apr 28, 2011 at 11:42 AM, Andreas Ericsson wrote:\n> On 04/28/2011 10:18 AM, Bernhard R. Link wrote:\n>> * Ralf Baechle  [110428 02:35]:\n>>> On Wed, Apr 27, 2011 at 04:32:12PM -0700, Junio C Hamano wrote:\n>>>\n>>>>> +static inline int is_null_sha1(const unsigned char *sha1)\n>>>>>   {\n>>>>> -  return memcmp(sha1, sha2, 20);\n>>>>> +  const unsigned long long *sha1_64 = (void *)sha1;\n>>>>> +  const unsigned int *sha1_32 = (void *)sha1;\n>>>>\n>>>> Can everybody do unaligned accesses just fine?\n>>>\n>>> Misaligned accesses cause exceptions on some architectures which then\n>>> are fixed up in software making these accesses _very_ slow.  You can\n>>> use __attribute__((packed)) to work around that but that will on the\n>>> affected architectures make gcc generate code pessimistically that is\n>>> slower than not using __attribute__((packed)) in case of proper\n>>> alignment.  And __attribute__((packed)) only works with GCC.\n>>\n>> Even __attribute__((packed)) usually does not allow arbitrary aligned\n>> data, but can intruct the code to generate code to access code\n>> misaligned in a special way. (I have already seen code where thus\n>> accessing a properly aligned long caused a SIGBUS, because it was\n>> aligned because being in a misaligned packed struct).\n>>\n>> In short: misaligning stuff works on x86, everywhere else it is disaster\n>> waiting to happen. (And people claiming compiler bugs or broken\n>> architectures, just because they do not know the basic rules of C).\n>>\n>\n> Given that the vast majority of user systems are x86 style ones, it's\n> probably worth using this patch on such systems and stick to a\n> partially unrolled byte-by-byte comparison that finishes early on\n> the rest of them.\n\nI disagree. We have no guarantee that the SHA-1s are aligned on x86\neither, and unaligned accesses are slow on x86.\n\nI think it's much much cleaner to add an early-out on the first byte,\nand hope that memcmp is optimized properly. If it's not, those\nplatforms can add an override to memcmp in git-compat-util and/or\ncompat/*.\n"},{"id":"166626","messageId":"4DB93D16.4000603@cs.helsinki.fi","threadId":"27207","inReplyTo":"BANLkTim+Kk_ah_4+pQKCi8bXtA8thRVRjQ@mail.gmail.com","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Pekka Enberg","fromEmail":"penberg@cs.helsinki.fi","sentAt":"2011-04-28T10:10:30Z","receivedAt":"2011-04-28T10:10:30Z","isPatch":true,"sender":{"key":"penberg@cs.helsinki.fi","avatar":"https://gravatar.com/avatar/85c22f5836e27e3fa9136f0ba21ea177570fa170ef60ab3dd1c1a36b4d63e516?d=mp&s=160"},"body":"On 4/28/11 12:50 PM, Erik Faye-Lund wrote:\n>> Alas, i have not seen these sha1 hash buffers being allocated unaligned (in my\n>> very limited testing). In which spots are they allocated unaligned?\n>\n> Like I said above, it can happen when allocated on the stack. But it\n> can also happen in malloc'ed structs, or in global variables. An array\n> is aligned to the size of it's base member type. But malloc does\n> worst-case-allignment, because it happens at run-time without\n> type-information.\n\nI'd be very surprised if malloc() did \"worst case alignment\" - that'd \nsuck pretty badly from performance point of view. However, if you want \n*guarantees* about the alignment, there's memalign() for heap allocations.\n\nStack allocation alignment is a harder issue but I doubt it's as bad as \nyou make it out to be. On x86, for example, stack pointer is almost \nalways 8 or 16 byte aligned with compilers whose writers have spent any \ntime reading the Intel optimization manuals.\n\nSo yes, your statements are absolutely correct but I strongly doubt it \nmatters that much in practice unless you're using a really crappy \ncompiler...\n\n\t\t\tPekka\n"},{"id":"166628","messageId":"20110428101902.GA17257@elte.hu","threadId":"27207","inReplyTo":"BANLkTim+Kk_ah_4+pQKCi8bXtA8thRVRjQ@mail.gmail.com","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2011-04-28T10:19:02Z","receivedAt":"2011-04-28T10:19:02Z","isPatch":true,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Erik Faye-Lund wrote:\n\n> 2011/4/28 Ingo Molnar :\n> >\n> > * Erik Faye-Lund wrote:\n> >\n> >> > Secondly, the combined speedup of the cached case with my two patches\n> >> > appears to be more than 30% on my testbox so it's a very nifty win from two\n> >> > relatively simple changes.\n> >>\n> >> That speed-up was on ONE test vector, no? There are a lot of other uses of\n> >> hash-comparisons in Git, did you measure those?\n> >\n> > I picked this hash function because it showed up in the profile (see the\n> > profile i posted). There's one other hash that mattered as well in the profile,\n> > see the lookup_object() patch i sent yesterday.\n> \n> My point was that the 30% improvement was in \"git gc\", which is not\n> the only important use-case. How does this affect other git commands?\n\nIn a followup mail i measured git fsck, which showed a speedup too. (despite \nbeing mostly dependent on external libraries to do most of the processing)\n\nIf you'd like to see other things tested please suggest a testcase that you \nthink uses these hashes extensively, i don't really know what the slowest (and \naffected) Git commands are - git gc is the one *i* notice as being pretty slow \n(for good reasons).\n\n> >> from the exception handler, others doesn't. So this patch is pretty much\n> >> guaranteed to cause a crash in some setups.\n> >\n> > If unsigned char arrays are allocated unaligned then that's another bug i\n> > suspect that should be fixed.\n> \n> We can't. The compiler decides the alignment of variables on the stack. Some \n> compilers / compiler-setting pairs might align char-arrays, while others \n> might not.\n\nEven if that were true it can be solved: you'd need to declare the sha1 not as \na char array but as a u32 * array or so. We do have control over the alignment \nof data structures, obviously.\n\n> > Unaligned access on x86 is not free either - there's cycle penalties.\n> >\n> > Alas, i have not seen these sha1 hash buffers being allocated unaligned (in \n> > my very limited testing). In which spots are they allocated unaligned?\n> \n> Like I said above, it can happen when allocated on the stack. But it can also \n> happen in malloc'ed structs, or in global variables. An array is aligned to \n> the size of it's base member type. But malloc does worst-case-allignment, \n> because it happens at run-time without type-information.\n\nWell, should we ready be ready to throw up our hands as if we didnt have \ncontrol over the alignment of objects and have to accept suboptimal code as a \nresult? We do have control over that.\n\nIn any case, i'll retract the null case as it really isnt called that often in \nthe tests i've done - updated patch below - it simply falls back on to hashcmp.\n\nThanks,\n\n\tIngo\n\nSigned-off-by: Ingo Molnar \n\ndiff --git a/cache.h b/cache.h\nindex 2674f4c..39fa9cd 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -675,14 +675,24 @@ extern char *sha1_pack_name(const unsigned char *sha1);\n extern char *sha1_pack_index_name(const unsigned char *sha1);\n extern const char *find_unique_abbrev(const unsigned char *sha1, int);\n extern const unsigned char null_sha1[20];\n-static inline int is_null_sha1(const unsigned char *sha1)\n+\n+static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n {\n-\treturn !memcmp(sha1, null_sha1, 20);\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+\t}\n+\n+\treturn 0;\n }\n-static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n+\n+static inline int is_null_sha1(const unsigned char *sha1)\n {\n-\treturn memcmp(sha1, sha2, 20);\n+\treturn !hashcmp(sha1, null_sha1);\n }\n+\n static inline void hashcpy(unsigned char *sha_dst, const unsigned char *sha_src)\n {\n \tmemcpy(sha_dst, sha_src, 20);\n"},{"id":"166627","messageId":"BANLkTimD7KZz4fS0QynPui7-JQS10AkLtg@mail.gmail.com","threadId":"27207","inReplyTo":"4DB93D16.4000603@cs.helsinki.fi","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Erik Faye-Lund","fromEmail":"kusmabite@gmail.com","sentAt":"2011-04-28T10:19:17Z","receivedAt":"2011-04-28T10:19:17Z","isPatch":true,"sender":{"key":"kusmabite@gmail.com","avatar":"https://avatars.githubusercontent.com/u/47073?v=4"},"body":"On Thu, Apr 28, 2011 at 12:10 PM, Pekka Enberg wrote:\n> On 4/28/11 12:50 PM, Erik Faye-Lund wrote:\n>>>\n>>> Alas, i have not seen these sha1 hash buffers being allocated unaligned\n>>> (in my\n>>> very limited testing). In which spots are they allocated unaligned?\n>>\n>> Like I said above, it can happen when allocated on the stack. But it\n>> can also happen in malloc'ed structs, or in global variables. An array\n>> is aligned to the size of it's base member type. But malloc does\n>> worst-case-allignment, because it happens at run-time without\n>> type-information.\n>\n> I'd be very surprised if malloc() did \"worst case alignment\" - that'd suck\n> pretty badly from performance point of view.\n\n>From POSIX (I don't have K&R at hand, but it's also specified there):\n\"The pointer returned if the allocation succeeds shall be suitably\naligned so that it may be assigned to a pointer to any type of object\nand then used to access such an object in the space allocated (until\nthe space is explicitly freed or reallocated).\"\n\nI put it in quotes because it's not the worst-case alignment you can\never think of, but rather the worst case alignment of your CPUs\nalignment requirements. This is 4 bytes for most CPUs.\n\n> Stack allocation alignment is a harder issue but I doubt it's as bad as you\n> make it out to be. On x86, for example, stack pointer is almost always 8 or\n> 16 byte aligned with compilers whose writers have spent any time reading the\n> Intel optimization manuals.\n>\n> So yes, your statements are absolutely correct but I strongly doubt it\n> matters that much in practice unless you're using a really crappy\n> compiler...\n\nI'm sorry, but the the fact of the matter is that we don't write code\nfor one compiler, we try to please many. Crappy compilers are very\nmuch out there in the wild, and we have to deal with it. So, we can't\ndepend on char-arrays being aligned to 32-bytes. This code WILL break\non GCC for ARM, so it's not a theoretical issue at all. It will also\nmost likely break on GCC for x86 when optimizations are disabled.\n"},{"id":"166629","messageId":"4DB941CD.2050403@cs.helsinki.fi","threadId":"27207","inReplyTo":"BANLkTimD7KZz4fS0QynPui7-JQS10AkLtg@mail.gmail.com","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Pekka Enberg","fromEmail":"penberg@cs.helsinki.fi","sentAt":"2011-04-28T10:30:37Z","receivedAt":"2011-04-28T10:30:37Z","isPatch":true,"sender":{"key":"penberg@cs.helsinki.fi","avatar":"https://gravatar.com/avatar/85c22f5836e27e3fa9136f0ba21ea177570fa170ef60ab3dd1c1a36b4d63e516?d=mp&s=160"},"body":"Hi,\n\nOn 4/28/11 1:19 PM, Erik Faye-Lund wrote:\n> On Thu, Apr 28, 2011 at 12:10 PM, Pekka Enberg wrote:\n>> On 4/28/11 12:50 PM, Erik Faye-Lund wrote:\n>>>>\n>>>> Alas, i have not seen these sha1 hash buffers being allocated unaligned\n>>>> (in my\n>>>> very limited testing). In which spots are they allocated unaligned?\n>>>\n>>> Like I said above, it can happen when allocated on the stack. But it\n>>> can also happen in malloc'ed structs, or in global variables. An array\n>>> is aligned to the size of it's base member type. But malloc does\n>>> worst-case-allignment, because it happens at run-time without\n>>> type-information.\n>>\n>> I'd be very surprised if malloc() did \"worst case alignment\" - that'd suck\n>> pretty badly from performance point of view.\n>\n> From POSIX (I don't have K&R at hand, but it's also specified there):\n> \"The pointer returned if the allocation succeeds shall be suitably\n> aligned so that it may be assigned to a pointer to any type of object\n> and then used to access such an object in the space allocated (until\n> the space is explicitly freed or reallocated).\"\n>\n> I put it in quotes because it's not the worst-case alignment you can\n> ever think of, but rather the worst case alignment of your CPUs\n> alignment requirements. This is 4 bytes for most CPUs.\n\nThat's just the minimum guarantee! Why do you think modern malloc() \nimplementations don't try *very* hard to provide best possible alignment?\n\n>> Stack allocation alignment is a harder issue but I doubt it's as bad as you\n>> make it out to be. On x86, for example, stack pointer is almost always 8 or\n>> 16 byte aligned with compilers whose writers have spent any time reading the\n>> Intel optimization manuals.\n>>\n>> So yes, your statements are absolutely correct but I strongly doubt it\n>> matters that much in practice unless you're using a really crappy\n>> compiler...\n>\n> I'm sorry, but the the fact of the matter is that we don't write code\n> for one compiler, we try to please many. Crappy compilers are very\n> much out there in the wild, and we have to deal with it. So, we can't\n> depend on char-arrays being aligned to 32-bytes. This code WILL break\n> on GCC for ARM, so it's not a theoretical issue at all. It will also\n> most likely break on GCC for x86 when optimizations are disabled.\n\nYes, ARM is a problem and I didn't try to claim otherwise. However, it's \nnot \"impossible to fix\" as you say with memalign().\n\nBut my comment was mostly about your claim that \"we have no guarantee \nthat the SHA-1s are aligned on x86 either, and unaligned accesses are \nslow on x86\" which only matters in practice if you have a crappy \ncompiler. And arguing for performance if you don't have a reasonable \ncompiler is pretty uninteresting.\n\n\t\t\tPekka\n"},{"id":"166630","messageId":"20110428103650.GA18530@elte.hu","threadId":"27207","inReplyTo":"20110428063625.GB952@elte.hu","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2011-04-28T10:36:50Z","receivedAt":"2011-04-28T10:36:50Z","isPatch":true,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Ingo Molnar wrote:\n\n> Having said that, it would be nice if someone could test these two patches on a \n> modern AMD box, using the perf stat from here:\n> \n> http://people.redhat.com/mingo/tip.git/README\n> \n> cd tools/perf/\n> make -j install\n> \n> and do something like this to test git gc's performance:\n> \n> $ perf stat --sync --repeat 10 ./git gc\n> \n> ... to see whether these speedups are generic, or somehow Intel CPU specific.\n\nTo follow up on this angle, i've now tested both 'git gc' performance \nimprovement patches on an Opteron box:\n\n #\n # Before:\n #\n\n Performance counter stats for './git gc' (10 runs):\n\n 6400.903957 task-clock # 0.977 CPUs utilized ( +- 0.09% )\n 1,537 context-switches # 0.000 M/sec ( +- 3.12% )\n 118 CPU-migrations # 0.000 M/sec ( +- 7.08% )\n 40,879 page-faults # 0.006 M/sec ( +- 0.03% )\n 14,768,724,649 cycles # 2.307 GHz ( +- 0.09% )\n 9,185,135,676 instructions # 0.62 insns per cycle ( +- 0.08% )\n 1,883,860,739 branches # 294.312 M/sec ( +- 0.16% )\n 99,800,253 branch-misses # 5.30% of all branches ( +- 0.34% )\n\n 6.548348691 seconds time elapsed ( +- 1.01% )\n\n #\n # After:\n #\n\n Performance counter stats for './git gc' (10 runs):\n\n 6078.191492 task-clock # 0.979 CPUs utilized ( +- 0.09% )\n 1,511 context-switches # 0.000 M/sec ( +- 2.85% )\n 104 CPU-migrations # 0.000 M/sec ( +- 6.29% )\n 41,410 page-faults # 0.007 M/sec ( +- 0.04% )\n 14,024,602,415 cycles # 2.307 GHz ( +- 0.09% )\n stalled-cycles \n 11,364,757,635 instructions # 0.81 insns per cycle ( +- 0.06% )\n 2,612,173,056 branches # 429.762 M/sec ( +- 0.09% )\n 109,257,789 branch-misses # 4.18% of all branches ( +- 0.74% )\n\n 6.209749362 seconds time elapsed ( +- 0.51% )\n\nSo they bring an about +5.3% improvement.\n\nThanks,\n\n\tIngo\n"},{"id":"166636","messageId":"BANLkTik-uk-mpdHZxcz8Nem=nEzED_tuJg@mail.gmail.com","threadId":"27207","inReplyTo":"4DB941CD.2050403@cs.helsinki.fi","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Erik Faye-Lund","fromEmail":"kusmabite@gmail.com","sentAt":"2011-04-28T11:59:54Z","receivedAt":"2011-04-28T11:59:54Z","isPatch":true,"sender":{"key":"kusmabite@gmail.com","avatar":"https://avatars.githubusercontent.com/u/47073?v=4"},"body":"On Thu, Apr 28, 2011 at 12:30 PM, Pekka Enberg wrote:\n> Hi,\n>\n> On 4/28/11 1:19 PM, Erik Faye-Lund wrote:\n>>\n>> On Thu, Apr 28, 2011 at 12:10 PM, Pekka Enberg\n>>  wrote:\n>>>\n>>> On 4/28/11 12:50 PM, Erik Faye-Lund wrote:\n>>>>>\n>>>>> Alas, i have not seen these sha1 hash buffers being allocated unaligned\n>>>>> (in my\n>>>>> very limited testing). In which spots are they allocated unaligned?\n>>>>\n>>>> Like I said above, it can happen when allocated on the stack. But it\n>>>> can also happen in malloc'ed structs, or in global variables. An array\n>>>> is aligned to the size of it's base member type. But malloc does\n>>>> worst-case-allignment, because it happens at run-time without\n>>>> type-information.\n>>>\n>>> I'd be very surprised if malloc() did \"worst case alignment\" - that'd\n>>> suck\n>>> pretty badly from performance point of view.\n>>\n>>  From POSIX (I don't have K&R at hand, but it's also specified there):\n>> \"The pointer returned if the allocation succeeds shall be suitably\n>> aligned so that it may be assigned to a pointer to any type of object\n>> and then used to access such an object in the space allocated (until\n>> the space is explicitly freed or reallocated).\"\n>>\n>> I put it in quotes because it's not the worst-case alignment you can\n>> ever think of, but rather the worst case alignment of your CPUs\n>> alignment requirements. This is 4 bytes for most CPUs.\n>\n> That's just the minimum guarantee! Why do you think modern malloc()\n> implementations don't try *very* hard to provide best possible alignment?\n>\n\nYes, it's the minimum alignment requirement. And yes, malloc\nimplementations try to keep the alignment. I don't think there's any\ncontradiction between what you and I said.\n\n>>> Stack allocation alignment is a harder issue but I doubt it's as bad as\n>>> you\n>>> make it out to be. On x86, for example, stack pointer is almost always 8\n>>> or\n>>> 16 byte aligned with compilers whose writers have spent any time reading\n>>> the\n>>> Intel optimization manuals.\n>>>\n>>> So yes, your statements are absolutely correct but I strongly doubt it\n>>> matters that much in practice unless you're using a really crappy\n>>> compiler...\n>>\n>> I'm sorry, but the the fact of the matter is that we don't write code\n>> for one compiler, we try to please many. Crappy compilers are very\n>> much out there in the wild, and we have to deal with it. So, we can't\n>> depend on char-arrays being aligned to 32-bytes. This code WILL break\n>> on GCC for ARM, so it's not a theoretical issue at all. It will also\n>> most likely break on GCC for x86 when optimizations are disabled.\n>\n> Yes, ARM is a problem and I didn't try to claim otherwise. However, it's not\n> \"impossible to fix\" as you say with memalign().\n\nTrue, it's not impossible. It's just an insane thing to try to do, for\na very small gain. The important change was the early-out, and we can\nget that while still using a platform-optimized memcmp.\n\n> But my comment was mostly about your claim that \"we have no guarantee that\n> the SHA-1s are aligned on x86 either, and unaligned accesses are slow on\n> x86\" which only matters in practice if you have a crappy compiler. And\n> arguing for performance if you don't have a reasonable compiler is pretty\n> uninteresting.\n\nI agree that not aligning arrays when optimizations are disabled isn't\na big problem on x86. But I don't think that assuming that every\nreasonable compiler/compiler-setting pair for x86 align all char-array\nmakes sense. Aligning short arrays on the stack can lead to\nsub-optimal caching for local variables, for instance. Alignment isn't\nthe only thing that matters.\n\nBut that point aside, we need an implementation that is both fast and\ncorrect on all platforms; type-punning arrays is not the way to do it.\n\nSo my preference is still something like this. Call me conservative ;)\n\ndiff --git a/cache.h b/cache.h\nindex c730c58..8bc03c6 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -681,13 +681,17 @@ extern char *sha1_pack_name(const unsigned char *sha1);\n extern char *sha1_pack_index_name(const unsigned char *sha1);\n extern const char *find_unique_abbrev(const unsigned char *sha1, int);\n extern const unsigned char null_sha1[20];\n-static inline int is_null_sha1(const unsigned char *sha1)\n+static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n {\n-\treturn !memcmp(sha1, null_sha1, 20);\n+\t/* early out for fast mis-match */\n+\tif (*sha1 != *sha2)\n+\t\treturn *sha1 - *sha2;\n+\n+\treturn memcmp(sha1 + 1, sha2 + 1, 19);\n }\n-static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n+static inline int is_null_sha1(const unsigned char *sha1)\n {\n-\treturn memcmp(sha1, sha2, 20);\n+\treturn !hashcmp(sha1, null_sha1);\n }\n static inline void hashcpy(unsigned char *sha_dst, const unsigned\nchar *sha_src)\n {\n"},{"id":"166637","messageId":"BANLkTikf2Q81otJxOWoAs+EFA5_4wf7fyQ@mail.gmail.com","threadId":"27207","inReplyTo":"20110428101902.GA17257@elte.hu","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-04-28T12:02:22Z","receivedAt":"2011-04-28T12:02:22Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"2011/4/28 Ingo Molnar :\n> If you'd like to see other things tested please suggest a testcase that you\n> think uses these hashes extensively, i don't really know what the slowest (and\n> affected) Git commands are - git gc is the one *i* notice as being pretty slow\n> (for good reasons).\n\ngit clone\n-- \nDuy\n"},{"id":"166638","messageId":"4DB9599D.3010208@cs.helsinki.fi","threadId":"27207","inReplyTo":"BANLkTik-uk-mpdHZxcz8Nem=nEzED_tuJg@mail.gmail.com","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Pekka Enberg","fromEmail":"penberg@cs.helsinki.fi","sentAt":"2011-04-28T12:12:13Z","receivedAt":"2011-04-28T12:12:13Z","isPatch":true,"sender":{"key":"penberg@cs.helsinki.fi","avatar":"https://gravatar.com/avatar/85c22f5836e27e3fa9136f0ba21ea177570fa170ef60ab3dd1c1a36b4d63e516?d=mp&s=160"},"body":"On 4/28/11 2:59 PM, Erik Faye-Lund wrote:\n> So my preference is still something like this. Call me conservative ;)\n>\n> diff --git a/cache.h b/cache.h\n> index c730c58..8bc03c6 100644\n> --- a/cache.h\n> +++ b/cache.h\n> @@ -681,13 +681,17 @@ extern char *sha1_pack_name(const unsigned char *sha1);\n> extern char *sha1_pack_index_name(const unsigned char *sha1);\n> extern const char *find_unique_abbrev(const unsigned char *sha1, int);\n> extern const unsigned char null_sha1[20];\n> -static inline int is_null_sha1(const unsigned char *sha1)\n> +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n> {\n> -\treturn !memcmp(sha1, null_sha1, 20);\n> +\t/* early out for fast mis-match */\n> +\tif (*sha1 != *sha2)\n> +\t\treturn *sha1 - *sha2;\n> +\n> +\treturn memcmp(sha1 + 1, sha2 + 1, 19);\n> }\n> -static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n> +static inline int is_null_sha1(const unsigned char *sha1)\n> {\n> -\treturn memcmp(sha1, sha2, 20);\n> +\treturn !hashcmp(sha1, null_sha1);\n> }\n> static inline void hashcpy(unsigned char *sha_dst, const unsigned\n> char *sha_src)\n> {\n\nYup, might be the most reasonable thing to do if it still speeds things up.\n\n\t\t\tPekka\n"},{"id":"166640","messageId":"BANLkTikKUuBMDR2-OBYXw7jzs_+1wGacuA@mail.gmail.com","threadId":"27207","inReplyTo":"4DB941CD.2050403@cs.helsinki.fi","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Tor Arntsen","fromEmail":"tor@spacetec.no","sentAt":"2011-04-28T12:16:20Z","receivedAt":"2011-04-28T12:16:20Z","isPatch":true,"sender":{"key":"tor@spacetec.no","avatar":null},"body":"On Thu, Apr 28, 2011 at 12:30, Pekka Enberg wrote:\n> Hi,\n>\n> On 4/28/11 1:19 PM, Erik Faye-Lund wrote:\n[alignment issues]\n>\n> Yes, ARM is a problem and I didn't try to claim otherwise. However, it's not\n> \"impossible to fix\" as you say with memalign().\n\nMIPS (e.g. SGI machines) also bus-errors on non-aligned data.\n\n-Tor\n"},{"id":"166641","messageId":"4DB95AEF.5060609@op5.se","threadId":"27207","inReplyTo":"4DB941CD.2050403@cs.helsinki.fi","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2011-04-28T12:17:51Z","receivedAt":"2011-04-28T12:17:51Z","isPatch":true,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"On 04/28/2011 12:30 PM, Pekka Enberg wrote:\n> Hi,\n> \n> On 4/28/11 1:19 PM, Erik Faye-Lund wrote:\n>> On Thu, Apr 28, 2011 at 12:10 PM, Pekka Enberg wrote:\n>>> On 4/28/11 12:50 PM, Erik Faye-Lund wrote:\n>>>>>\n>>>>> Alas, i have not seen these sha1 hash buffers being allocated unaligned\n>>>>> (in my\n>>>>> very limited testing). In which spots are they allocated unaligned?\n>>>>\n>>>> Like I said above, it can happen when allocated on the stack. But it\n>>>> can also happen in malloc'ed structs, or in global variables. An array\n>>>> is aligned to the size of it's base member type. But malloc does\n>>>> worst-case-allignment, because it happens at run-time without\n>>>> type-information.\n>>>\n>>> I'd be very surprised if malloc() did \"worst case alignment\" - that'd suck\n>>> pretty badly from performance point of view.\n>>\n>> From POSIX (I don't have K&R at hand, but it's also specified there):\n>> \"The pointer returned if the allocation succeeds shall be suitably\n>> aligned so that it may be assigned to a pointer to any type of object\n>> and then used to access such an object in the space allocated (until\n>> the space is explicitly freed or reallocated).\"\n>>\n>> I put it in quotes because it's not the worst-case alignment you can\n>> ever think of, but rather the worst case alignment of your CPUs\n>> alignment requirements. This is 4 bytes for most CPUs.\n> \n> That's just the minimum guarantee! Why do you think modern malloc() implementations don't try *very* hard to provide best possible alignment?\n> \n>>> Stack allocation alignment is a harder issue but I doubt it's as bad as you\n>>> make it out to be. On x86, for example, stack pointer is almost always 8 or\n>>> 16 byte aligned with compilers whose writers have spent any time reading the\n>>> Intel optimization manuals.\n>>>\n>>> So yes, your statements are absolutely correct but I strongly doubt it\n>>> matters that much in practice unless you're using a really crappy\n>>> compiler...\n>>\n>> I'm sorry, but the the fact of the matter is that we don't write code\n>> for one compiler, we try to please many. Crappy compilers are very\n>> much out there in the wild, and we have to deal with it. So, we can't\n>> depend on char-arrays being aligned to 32-bytes. This code WILL break\n>> on GCC for ARM, so it's not a theoretical issue at all. It will also\n>> most likely break on GCC for x86 when optimizations are disabled.\n> \n> Yes, ARM is a problem and I didn't try to claim otherwise. However, it's not \"impossible to fix\" as you say with memalign().\n> \n\n#define is_aligned(ptr) (ptr & (sizeof(void *) - 1))\nif (is_aligned(sha1) && is_aligned(sha2))\n\treturn aligned_and_fast_hashcmp(sha1, sha2);\n\nreturn memcmp(sha1, sha2, 20);\n\nProblem solved for all architectures. Not as fast as the original\npatch when we're lucky with alignment, but we cater to sucky\ncompilers and make the good ones go a lot faster. The really good\ncompilers that recognizes \"is it aligned?\" checks will optimize the\nis_aligned() checks away or at least hint at the branch prediction\nwhich path it should prefer.\n\nOnce again; Bear in mind that x86 style architectures with gcc is\nalmost certainly the most common combo for git users by a very wide\nmargin, so a 25-30% speedup for those users is pretty worthwhile.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n\nConsidering the successes of the wars on alcohol, poverty, drugs and\nterror, I think we should give some serious thought to declaring war\non peace.\n"},{"id":"166642","messageId":"BANLkTikq=oZ4uk-MN_zOXmdKNq7O3XtJhQ@mail.gmail.com","threadId":"27207","inReplyTo":"20110428101902.GA17257@elte.hu","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Erik Faye-Lund","fromEmail":"kusmabite@gmail.com","sentAt":"2011-04-28T12:18:51Z","receivedAt":"2011-04-28T12:18:51Z","isPatch":true,"sender":{"key":"kusmabite@gmail.com","avatar":"https://avatars.githubusercontent.com/u/47073?v=4"},"body":"2011/4/28 Ingo Molnar :\n>\n> * Erik Faye-Lund wrote:\n>\n>> 2011/4/28 Ingo Molnar :\n>> >\n>> > * Erik Faye-Lund wrote:\n>> >\n>> >> > Secondly, the combined speedup of the cached case with my two patches\n>> >> > appears to be more than 30% on my testbox so it's a very nifty win from two\n>> >> > relatively simple changes.\n>> >>\n>> >> That speed-up was on ONE test vector, no? There are a lot of other uses of\n>> >> hash-comparisons in Git, did you measure those?\n>> >\n>> > I picked this hash function because it showed up in the profile (see the\n>> > profile i posted). There's one other hash that mattered as well in the profile,\n>> > see the lookup_object() patch i sent yesterday.\n>>\n>> My point was that the 30% improvement was in \"git gc\", which is not\n>> the only important use-case. How does this affect other git commands?\n>\n> In a followup mail i measured git fsck, which showed a speedup too. (despite\n> being mostly dependent on external libraries to do most of the processing)\n>\n> If you'd like to see other things tested please suggest a testcase that you\n> think uses these hashes extensively, i don't really know what the slowest (and\n> affected) Git commands are - git gc is the one *i* notice as being pretty slow\n> (for good reasons).\n>\n\nYou only seem to test cases that iterate through the entire repo, and\nI suspect that they might not be representative for all affected\nuse-cases.\n\nSo I'd love to see something like just timing of something like \"git\ndiff > /dev/null\" (and some other goodies) in a hot-cache repo with\nand without your patch. Perhaps even timing of running the test-suite,\nas this touches most git-commands...\n\n>> We can't. The compiler decides the alignment of variables on the stack. Some\n>> compilers / compiler-setting pairs might align char-arrays, while others\n>> might not.\n>\n> Even if that were true it can be solved: you'd need to declare the sha1 not as\n> a char array but as a u32 * array or so. We do have control over the alignment\n> of data structures, obviously.\n\nTrue, but that's a very intrusive change. And it's not a bug-fix as\nyou indicated :)\n\n>> Like I said above, it can happen when allocated on the stack. But it can also\n>> happen in malloc'ed structs, or in global variables. An array is aligned to\n>> the size of it's base member type. But malloc does worst-case-allignment,\n>> because it happens at run-time without type-information.\n>\n> Well, should we ready be ready to throw up our hands as if we didnt have\n> control over the alignment of objects and have to accept suboptimal code as a\n> result? We do have control over that.\n\nYes, but it's better to pick low-hanging fruits and see if we can get\n99% of the performance increase without having to change all of the\ncode. See my previous e-mail (Message-ID:\n) for what I\nsuspect will do the trick without causing problems.\n\n> In any case, i'll retract the null case as it really isnt called that often in\n> the tests i've done - updated patch below - it simply falls back on to hashcmp.\n\nNice, I think this makes sense. I already stole that hunk and\nincorporated that in the diff I posted ;)\n"},{"id":"166643","messageId":"BANLkTi=B4nQPC7CrLkpmn4AhwjOAvs82qw@mail.gmail.com","threadId":"27207","inReplyTo":"4DB95AEF.5060609@op5.se","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Erik Faye-Lund","fromEmail":"kusmabite@gmail.com","sentAt":"2011-04-28T12:28:03Z","receivedAt":"2011-04-28T12:28:03Z","isPatch":true,"sender":{"key":"kusmabite@gmail.com","avatar":"https://avatars.githubusercontent.com/u/47073?v=4"},"body":"On Thu, Apr 28, 2011 at 2:17 PM, Andreas Ericsson wrote:\n>>>> Stack allocation alignment is a harder issue but I doubt it's as bad as you\n>>>> make it out to be. On x86, for example, stack pointer is almost always 8 or\n>>>> 16 byte aligned with compilers whose writers have spent any time reading the\n>>>> Intel optimization manuals.\n>>>>\n>>>> So yes, your statements are absolutely correct but I strongly doubt it\n>>>> matters that much in practice unless you're using a really crappy\n>>>> compiler...\n>>>\n>>> I'm sorry, but the the fact of the matter is that we don't write code\n>>> for one compiler, we try to please many. Crappy compilers are very\n>>> much out there in the wild, and we have to deal with it. So, we can't\n>>> depend on char-arrays being aligned to 32-bytes. This code WILL break\n>>> on GCC for ARM, so it's not a theoretical issue at all. It will also\n>>> most likely break on GCC for x86 when optimizations are disabled.\n>>\n>> Yes, ARM is a problem and I didn't try to claim otherwise. However, it's not \"impossible to fix\" as you say with memalign().\n>>\n>\n> #define is_aligned(ptr) (ptr & (sizeof(void *) - 1))\n> if (is_aligned(sha1) && is_aligned(sha2))\n>        return aligned_and_fast_hashcmp(sha1, sha2);\n>\n> return memcmp(sha1, sha2, 20);\n>\n> Problem solved for all architectures. Not as fast as the original\n> patch when we're lucky with alignment, but we cater to sucky\n> compilers and make the good ones go a lot faster. The really good\n> compilers that recognizes \"is it aligned?\" checks will optimize the\n> is_aligned() checks away or at least hint at the branch prediction\n> which path it should prefer.\n\nI'd rather go with the do-not-introduce-the-problem-in-the-first-place\napproach. As I've pointed out many times already, the vast majority of\nthe performance increase comes from the early-out in the first\niteration. Why not just special case that ONE check, and do memcmp as\nusual for the rest? The first iteration should affect 99.6% of all\nmismatches, so it should have nice performance even for the unaligned\ncase. This gives us both speed and portability.\n\n> Once again; Bear in mind that x86 style architectures with gcc is\n> almost certainly the most common combo for git users by a very wide\n> margin, so a 25-30% speedup for those users is pretty worthwhile.\n\nAgain, I never argued against speed. I argued against going a route\nthat is tricky to get right. Very reasonable alternatives were posted,\nincluding Ingo's last patch.\n"},{"id":"166644","messageId":"20110428123617.GA2062@elie","threadId":"27207","inReplyTo":"BANLkTik-uk-mpdHZxcz8Nem=nEzED_tuJg@mail.gmail.com","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-04-28T12:36:17Z","receivedAt":"2011-04-28T12:36:17Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi,\n\nA side note for amusement.\n\nErik Faye-Lund wrote:\n\n> --- a/cache.h\n> +++ b/cache.h\n> @@ -681,13 +681,17 @@ extern char *sha1_pack_name(const unsigned char *sha1);\n> extern char *sha1_pack_index_name(const unsigned char *sha1);\n> extern const char *find_unique_abbrev(const unsigned char *sha1, int);\n> extern const unsigned char null_sha1[20];\n> -static inline int is_null_sha1(const unsigned char *sha1)\n> +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n> {\n> -\treturn !memcmp(sha1, null_sha1, 20);\n> +\t/* early out for fast mis-match */\n> +\tif (*sha1 != *sha2)\n> +\t\treturn *sha1 - *sha2;\n> +\n> +\treturn memcmp(sha1 + 1, sha2 + 1, 19);\n> }\n\nOn the off-chance that sha1 and sha2 are nicely aligned, a more\nredundant\n\n\tif (*sha1 != *sha2)\n\t\treturn *sha1 - *sha2;\n\n\treturn memcmp(sha1, sha2, 20);\n\nwould take advantage of that (yes, this is just superstition, but it\nsomehow seems comforting anyway).\n\nAnyway, assuming it does not kill performance for some reason, the\nabove sounds good to me. Thanks for spelling it out.\n\nJonathan\n"},{"id":"166645","messageId":"BANLkTi=6zzW41OagqAQfifHfQ4Mvy+BwsA@mail.gmail.com","threadId":"27207","inReplyTo":"20110428123617.GA2062@elie","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Erik Faye-Lund","fromEmail":"kusmabite@gmail.com","sentAt":"2011-04-28T12:40:16Z","receivedAt":"2011-04-28T12:40:16Z","isPatch":true,"sender":{"key":"kusmabite@gmail.com","avatar":"https://avatars.githubusercontent.com/u/47073?v=4"},"body":"On Thu, Apr 28, 2011 at 2:36 PM, Jonathan Nieder wrote:\n> Hi,\n>\n> A side note for amusement.\n>\n> Erik Faye-Lund wrote:\n>\n>> --- a/cache.h\n>> +++ b/cache.h\n>> @@ -681,13 +681,17 @@ extern char *sha1_pack_name(const unsigned char *sha1);\n>>  extern char *sha1_pack_index_name(const unsigned char *sha1);\n>>  extern const char *find_unique_abbrev(const unsigned char *sha1, int);\n>>  extern const unsigned char null_sha1[20];\n>> -static inline int is_null_sha1(const unsigned char *sha1)\n>> +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n>>  {\n>> -     return !memcmp(sha1, null_sha1, 20);\n>> +     /* early out for fast mis-match */\n>> +     if (*sha1 != *sha2)\n>> +             return *sha1 - *sha2;\n>> +\n>> +     return memcmp(sha1 + 1, sha2 + 1, 19);\n>>  }\n>\n> On the off-chance that sha1 and sha2 are nicely aligned, a more\n> redundant\n>\n>        if (*sha1 != *sha2)\n>                return *sha1 - *sha2;\n>\n>        return memcmp(sha1, sha2, 20);\n>\n> would take advantage of that (yes, this is just superstition, but it\n> somehow seems comforting anyway).\n\nGood point, I think that's an improvement.\n\n> Anyway, assuming it does not kill performance for some reason, the\n> above sounds good to me.  Thanks for spelling it out.\n\nIf it does, then we haven't fully understood where it came from in the\nfirst place, no? :P\n"},{"id":"166646","messageId":"20110428133708.GA31383@elte.hu","threadId":"27207","inReplyTo":"20110428123617.GA2062@elie","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2011-04-28T13:37:08Z","receivedAt":"2011-04-28T13:37:08Z","isPatch":true,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Jonathan Nieder wrote:\n\n> Hi,\n> \n> A side note for amusement.\n> \n> Erik Faye-Lund wrote:\n> \n> > --- a/cache.h\n> > +++ b/cache.h\n> > @@ -681,13 +681,17 @@ extern char *sha1_pack_name(const unsigned char *sha1);\n> > extern char *sha1_pack_index_name(const unsigned char *sha1);\n> > extern const char *find_unique_abbrev(const unsigned char *sha1, int);\n> > extern const unsigned char null_sha1[20];\n> > -static inline int is_null_sha1(const unsigned char *sha1)\n> > +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n> > {\n> > -\treturn !memcmp(sha1, null_sha1, 20);\n> > +\t/* early out for fast mis-match */\n> > +\tif (*sha1 != *sha2)\n> > +\t\treturn *sha1 - *sha2;\n> > +\n> > +\treturn memcmp(sha1 + 1, sha2 + 1, 19);\n> > }\n> \n> On the off-chance that sha1 and sha2 are nicely aligned, a more\n> redundant\n> \n> \tif (*sha1 != *sha2)\n> \t\treturn *sha1 - *sha2;\n> \n> \treturn memcmp(sha1, sha2, 20);\n> \n> would take advantage of that (yes, this is just superstition, but it\n> somehow seems comforting anyway).\n\nYour variant also makes the code slightly more compact as the sha1+1 and sha2+1 \naddresses do not have to be computed. I'll re-test and resend this variant.\n\nThanks,\n\n\tIngo\n"},{"id":"166648","messageId":"20110428151409.GA32025@elte.hu","threadId":"27207","inReplyTo":"20110428133708.GA31383@elte.hu","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2011-04-28T15:14:09Z","receivedAt":"2011-04-28T15:14:09Z","isPatch":true,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Ingo Molnar wrote:\n\n> * Jonathan Nieder wrote:\n> \n> > Hi,\n> > \n> > A side note for amusement.\n> > \n> > Erik Faye-Lund wrote:\n> > \n> > > --- a/cache.h\n> > > +++ b/cache.h\n> > > @@ -681,13 +681,17 @@ extern char *sha1_pack_name(const unsigned char *sha1);\n> > > extern char *sha1_pack_index_name(const unsigned char *sha1);\n> > > extern const char *find_unique_abbrev(const unsigned char *sha1, int);\n> > > extern const unsigned char null_sha1[20];\n> > > -static inline int is_null_sha1(const unsigned char *sha1)\n> > > +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n> > > {\n> > > -\treturn !memcmp(sha1, null_sha1, 20);\n> > > +\t/* early out for fast mis-match */\n> > > +\tif (*sha1 != *sha2)\n> > > +\t\treturn *sha1 - *sha2;\n> > > +\n> > > +\treturn memcmp(sha1 + 1, sha2 + 1, 19);\n> > > }\n> > \n> > On the off-chance that sha1 and sha2 are nicely aligned, a more\n> > redundant\n> > \n> > \tif (*sha1 != *sha2)\n> > \t\treturn *sha1 - *sha2;\n> > \n> > \treturn memcmp(sha1, sha2, 20);\n> > \n> > would take advantage of that (yes, this is just superstition, but it\n> > somehow seems comforting anyway).\n> \n> Your variant also makes the code slightly more compact as the sha1+1 and sha2+1 \n> addresses do not have to be computed. I'll re-test and resend this variant.\n\nSeems to perform measurably worse:\n\n #\n # Open-coded loop:\n #\n Performance counter stats for './git gc' (10 runs):\n\n 2358.560100 task-clock # 0.763 CPUs utilized ( +- 0.06% )\n 1,870 context-switches # 0.001 M/sec ( +- 3.09% )\n 170 CPU-migrations # 0.000 M/sec ( +- 3.54% )\n 38,230 page-faults # 0.016 M/sec ( +- 0.03% )\n 7,513,529,543 cycles # 3.186 GHz ( +- 0.06% )\n 1,634,103,128 stalled-cycles # 21.75% of all cycles are idle ( +- 0.28% )\n 11,068,971,207 instructions # 1.47 insns per cycle \n # 0.15 stalled cycles per insn ( +- 0.04% )\n 2,487,656,519 branches # 1054.735 M/sec ( +- 0.03% )\n 59,233,604 branch-misses # 2.38% of all branches ( +- 0.09% )\n\n 3.092183093 seconds time elapsed ( +- 3.49% )\n\n #\n # Front test + memcmp:\n #\n Performance counter stats for './git gc' (10 runs):\n\n 2723.468639 task-clock # 0.833 CPUs utilized ( +- 0.22% )\n 1,751 context-switches # 0.001 M/sec ( +- 2.02% )\n 167 CPU-migrations # 0.000 M/sec ( +- 1.23% )\n 38,230 page-faults # 0.014 M/sec ( +- 0.03% )\n 8,684,682,538 cycles # 3.189 GHz ( +- 0.21% )\n 2,062,906,208 stalled-cycles # 23.75% of all cycles are idle ( +- 0.60% )\n 9,019,624,641 instructions # 1.04 insns per cycle \n # 0.23 stalled cycles per insn ( +- 0.04% )\n 1,771,179,402 branches # 650.340 M/sec ( +- 0.04% )\n 75,026,810 branch-misses # 4.24% of all branches ( +- 0.04% )\n\n 3.271415104 seconds time elapsed ( +- 1.97% )\n\nSo i think the open-coded loop variant i posted is faster.\n\nThe key observation is that there's two cases that matter to performance:\n\n - the hashes are different: in this case the front test catches 99% of the cases\n - the hashes are *equal*: in this case the open-coded loop performs better than the memcmp\n\nMy patch addresses both cases.\n\nThanks,\n\n\tIngo\n"},{"id":"166650","messageId":"BANLkTim90XOLRBPtVCXFb1ptkmUvHGRqeg@mail.gmail.com","threadId":"27207","inReplyTo":"20110428151409.GA32025@elte.hu","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Erik Faye-Lund","fromEmail":"kusmabite@gmail.com","sentAt":"2011-04-28T16:00:19Z","receivedAt":"2011-04-28T16:00:19Z","isPatch":true,"sender":{"key":"kusmabite@gmail.com","avatar":"https://avatars.githubusercontent.com/u/47073?v=4"},"body":"On Thu, Apr 28, 2011 at 5:14 PM, Ingo Molnar wrote:\n>\n> * Ingo Molnar wrote:\n>\n>> * Jonathan Nieder wrote:\n>>\n>> > Hi,\n>> >\n>> > A side note for amusement.\n>> >\n>> > Erik Faye-Lund wrote:\n>> >\n>> > > --- a/cache.h\n>> > > +++ b/cache.h\n>> > > @@ -681,13 +681,17 @@ extern char *sha1_pack_name(const unsigned char *sha1);\n>> > >  extern char *sha1_pack_index_name(const unsigned char *sha1);\n>> > >  extern const char *find_unique_abbrev(const unsigned char *sha1, int);\n>> > >  extern const unsigned char null_sha1[20];\n>> > > -static inline int is_null_sha1(const unsigned char *sha1)\n>> > > +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n>> > >  {\n>> > > - return !memcmp(sha1, null_sha1, 20);\n>> > > + /* early out for fast mis-match */\n>> > > + if (*sha1 != *sha2)\n>> > > +         return *sha1 - *sha2;\n>> > > +\n>> > > + return memcmp(sha1 + 1, sha2 + 1, 19);\n>> > >  }\n>> >\n>> > On the off-chance that sha1 and sha2 are nicely aligned, a more\n>> > redundant\n>> >\n>> >     if (*sha1 != *sha2)\n>> >             return *sha1 - *sha2;\n>> >\n>> >     return memcmp(sha1, sha2, 20);\n>> >\n>> > would take advantage of that (yes, this is just superstition, but it\n>> > somehow seems comforting anyway).\n>>\n>> Your variant also makes the code slightly more compact as the sha1+1 and sha2+1\n>> addresses do not have to be computed. I'll re-test and resend this variant.\n>\n> Seems to perform measurably worse:\n>\n>  #\n>  # Open-coded loop:\n>  #\n>  Performance counter stats for './git gc' (10 runs):\n>\n>       2358.560100 task-clock               #    0.763 CPUs utilized            ( +-  0.06% )\n>             1,870 context-switches         #    0.001 M/sec                    ( +-  3.09% )\n>               170 CPU-migrations           #    0.000 M/sec                    ( +-  3.54% )\n>            38,230 page-faults              #    0.016 M/sec                    ( +-  0.03% )\n>     7,513,529,543 cycles                   #    3.186 GHz                      ( +-  0.06% )\n>     1,634,103,128 stalled-cycles           #   21.75% of all cycles are idle   ( +-  0.28% )\n>    11,068,971,207 instructions             #    1.47  insns per cycle\n>                                            #    0.15  stalled cycles per insn  ( +-  0.04% )\n>     2,487,656,519 branches                 # 1054.735 M/sec                    ( +-  0.03% )\n>        59,233,604 branch-misses            #    2.38% of all branches          ( +-  0.09% )\n>\n>        3.092183093  seconds time elapsed  ( +-  3.49% )\n>\n>  #\n>  # Front test + memcmp:\n>  #\n>  Performance counter stats for './git gc' (10 runs):\n>\n>       2723.468639 task-clock               #    0.833 CPUs utilized            ( +-  0.22% )\n>             1,751 context-switches         #    0.001 M/sec                    ( +-  2.02% )\n>               167 CPU-migrations           #    0.000 M/sec                    ( +-  1.23% )\n>            38,230 page-faults              #    0.014 M/sec                    ( +-  0.03% )\n>     8,684,682,538 cycles                   #    3.189 GHz                      ( +-  0.21% )\n>     2,062,906,208 stalled-cycles           #   23.75% of all cycles are idle   ( +-  0.60% )\n>     9,019,624,641 instructions             #    1.04  insns per cycle\n>                                            #    0.23  stalled cycles per insn  ( +-  0.04% )\n>     1,771,179,402 branches                 #  650.340 M/sec                    ( +-  0.04% )\n>        75,026,810 branch-misses            #    4.24% of all branches          ( +-  0.04% )\n>\n>        3.271415104  seconds time elapsed  ( +-  1.97% )\n>\n> So i think the open-coded loop variant i posted is faster.\n>\n> The key observation is that there's two cases that matter to performance:\n>\n>  - the hashes are different: in this case the front test catches 99% of the cases\n>  - the hashes are *equal*: in this case the open-coded loop performs better than the memcmp\n>\n> My patch addresses both cases.\n>\n\nThanks. I also timed on my end (on Windows), and I came to the same\nconclusion (but the improvements of your original was somewhat smaller\nin my end; could be due to the test-case). It seems like the early-out\nwasn't the only reason your original patch performed faster. It could\nbe that memcmp (probably) didn't get inlined, and the extra function\ncall outweighs the complexity. Or there's something else going on that\nboth affects glibc and msvcrt.dll.\n"},{"id":"166657","messageId":"BANLkTinfc9J4vhWd9V+ZpXb5tumtZM1jZA@mail.gmail.com","threadId":"27207","inReplyTo":"20110428093703.GB15349@elte.hu","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Dmitry Potapov","fromEmail":"dpotapov@gmail.com","sentAt":"2011-04-28T16:36:27Z","receivedAt":"2011-04-28T16:36:27Z","isPatch":true,"sender":{"key":"dpotapov@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6568595?v=4"},"body":"2011/4/28 Ingo Molnar :\n>\n> If unsigned char arrays are allocated unaligned then that's another bug i\n> suspect that should be fixed. Unaligned access on x86 is not free either -\n> there's cycle penalties.\n\nUnsigned char arrays can be stored unaligned. Basically, it depends on\nthe context in what they were declared. If a preceding field in some\nstructure ended unaligned then the byte array will start unaligned.\nFor example:\n\nstruct foo\n{\n char ch;\n unsigned char sha1[20];\n};\n\nThe same on the stack, except the compiler may pack them as it wishes.\nSo, you have no guarantee here. If you want to make sure all SHA-1 are\naligned properly, sha1 should be declared as ui32: 'uint32_t sha1[5]'.\n\n\nDmitry\n"},{"id":"166683","messageId":"4DB9CBB8.8050605@zytor.com","threadId":"27207","inReplyTo":"BANLkTikU3evfo86WmQeVS_Z41s3xSK1DJw@mail.gmail.com","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2011-04-28T20:19:04Z","receivedAt":"2011-04-28T20:19:04Z","isPatch":true,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"On 04/28/2011 02:55 AM, Erik Faye-Lund wrote:\n> \n> I disagree. We have no guarantee that the SHA-1s are aligned on x86\n> either, and unaligned accesses are slow on x86.\n> \n\nNot particularly, especially not statistically. Furthermore, for a\nsizable chunk like a SHA-1, not all accesses will have the cross-grain\npenalities that you sometimes can have.\n\n> I think it's much much cleaner to add an early-out on the first byte,\n> and hope that memcmp is optimized properly. If it's not, those\n> platforms can add an override to memcmp in git-compat-util and/or\n> compat/*.\n\nOverall, doing an architecture optimization library especially for\nwidely used architectures like x86 is not a bad idea.\n\n\t-hpa\n"},{"id":"166682","messageId":"7v8vuu3z6h.fsf@alter.siamese.dyndns.org","threadId":"27207","inReplyTo":"20110428101902.GA17257@elte.hu","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-04-28T20:20:54Z","receivedAt":"2011-04-28T20:20:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ingo Molnar writes:\n\n> In any case, i'll retract the null case as it really isnt called that often in \n> the tests i've done - updated patch below - it simply falls back on to hashcmp.\n>\n> Thanks,\n>\n> \tIngo\n>\n> Signed-off-by: Ingo Molnar \n\nThanks, will queue this version.\n\n> diff --git a/cache.h b/cache.h\n> index 2674f4c..39fa9cd 100644\n> --- a/cache.h\n> +++ b/cache.h\n> @@ -675,14 +675,24 @@ extern char *sha1_pack_name(const unsigned char *sha1);\n> extern char *sha1_pack_index_name(const unsigned char *sha1);\n> extern const char *find_unique_abbrev(const unsigned char *sha1, int);\n> extern const unsigned char null_sha1[20];\n> -static inline int is_null_sha1(const unsigned char *sha1)\n> +\n> +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n> {\n> -\treturn !memcmp(sha1, null_sha1, 20);\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> +\t}\n> +\n> +\treturn 0;\n> }\n> -static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n> +\n> +static inline int is_null_sha1(const unsigned char *sha1)\n> {\n> -\treturn memcmp(sha1, sha2, 20);\n> +\treturn !hashcmp(sha1, null_sha1);\n> }\n> +\n> static inline void hashcpy(unsigned char *sha_dst, const unsigned char *sha_src)\n> {\n> \tmemcpy(sha_dst, sha_src, 20);\n"},{"id":"166685","messageId":"4DB9CCD8.6090701@zytor.com","threadId":"27207","inReplyTo":"BANLkTikKUuBMDR2-OBYXw7jzs_+1wGacuA@mail.gmail.com","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2011-04-28T20:23:52Z","receivedAt":"2011-04-28T20:23:52Z","isPatch":true,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"On 04/28/2011 05:16 AM, Tor Arntsen wrote:\n> On Thu, Apr 28, 2011 at 12:30, Pekka Enberg wrote:\n>> Hi,\n>>\n>> On 4/28/11 1:19 PM, Erik Faye-Lund wrote:\n> [alignment issues]\n>>\n>> Yes, ARM is a problem and I didn't try to claim otherwise. However, it's not\n>> \"impossible to fix\" as you say with memalign().\n> \n> MIPS (e.g. SGI machines) also bus-errors on non-aligned data.\n\nOn the other hand, MIPS has efficient instructions for accessing\nknown-unaligned data.\n\n\t-hpa\n"},{"id":"166686","messageId":"20110428203205.GD24755@elte.hu","threadId":"27207","inReplyTo":"BANLkTim90XOLRBPtVCXFb1ptkmUvHGRqeg@mail.gmail.com","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2011-04-28T20:32:05Z","receivedAt":"2011-04-28T20:32:05Z","isPatch":true,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Erik Faye-Lund wrote:\n\n> Thanks. I also timed on my end (on Windows), and I came to the same \n> conclusion (but the improvements of your original was somewhat smaller in my \n> end; could be due to the test-case). It seems like the early-out wasn't the \n> only reason your original patch performed faster. It could be that memcmp \n> (probably) didn't get inlined, and the extra function call outweighs the \n> complexity. [...]\n\nFunction calls arent that heavy really. My measurements identified the \nfollowing effects:\n\n - profiling of stalled cycles clearly pinpointed the REP MOV string \n instruction.\n\n - the patched code had less branch-misses - the clearer and inlined open-coded \n loop is probably easier for the CPU to speculate along - while REP MOV \n string ops are 'opaque' and the result might be harder to speculate.\n\nSo i think the main benefit of my patch is that it avoids the REP MOV \ninstruction.\n\nThanks,\n\n\tIngo\n"},{"id":"166712","messageId":"BANLkTikt0CU87maPs65WGi0oopD+g0uVDA@mail.gmail.com","threadId":"27207","inReplyTo":"BANLkTik-uk-mpdHZxcz8Nem=nEzED_tuJg@mail.gmail.com","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2011-04-29T07:05:46Z","receivedAt":"2011-04-29T07:05:46Z","isPatch":true,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On Thu, Apr 28, 2011 at 13:59, Erik Faye-Lund wrote:\n> diff --git a/cache.h b/cache.h\n> index c730c58..8bc03c6 100644\n> --- a/cache.h\n> +++ b/cache.h\n> @@ -681,13 +681,17 @@ extern char *sha1_pack_name(const unsigned char *sha1);\n>  extern char *sha1_pack_index_name(const unsigned char *sha1);\n>  extern const char *find_unique_abbrev(const unsigned char *sha1, int);\n>  extern const unsigned char null_sha1[20];\n> -static inline int is_null_sha1(const unsigned char *sha1)\n> +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n>  {\n> -       return !memcmp(sha1, null_sha1, 20);\n> +       /* early out for fast mis-match */\n> +       if (*sha1 != *sha2)\n> +               return *sha1 - *sha2;\n\nCan one take advantage of common expression optimization here?\nLike this:\n\n+ if (*sha1 - *sha2)\n+ return *sha1 - *sha2;\n"},{"id":"166745","messageId":"4DBAE628.4080501@zytor.com","threadId":"27207","inReplyTo":"BANLkTikt0CU87maPs65WGi0oopD+g0uVDA@mail.gmail.com","subject":"Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2011-04-29T16:24:08Z","receivedAt":"2011-04-29T16:24:08Z","isPatch":true,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"On 04/29/2011 12:05 AM, Alex Riesen wrote:\n> \n> Can one take advantage of common expression optimization here?\n> Like this:\n> \n> + if (*sha1 - *sha2)\n> + return *sha1 - *sha2;\n> \n\nOr even clue the compiler in explicitly:\n\n\tdelta = *sha1 - *sha2;\n\tif (delta)\n\t\treturn delta;\n\nFor newer x86-specific optimization there are a bunch of newer SSE\ninstructions which can be used to do bulk compares which may be faster\nif optimized for the fixed length compare; of course it requires a new\nenough processor.\n\n\t-hpa\n\n-- \nH. Peter Anvin, Intel Open Source Technology Center\nI work for Intel. I don't speak on their behalf.\n"}]}