{"thread":{"id":"20527","subject":"block-sha1: improve code on large-register-set machines","startedAt":"2009-08-10T23:52:07Z","lastAt":"2009-08-12T02:26:58Z","messageCount":16,"participants":["Linus Torvalds","Nicolas Pitre","Brandon Casey","Artur Skawina"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"120210","messageId":"alpine.LFD.2.01.0908101637440.3417@localhost.localdomain","threadId":"20527","inReplyTo":null,"subject":"block-sha1: improve code on large-register-set machines","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-10T23:52:07Z","receivedAt":"2009-08-10T23:52:07Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nFor x86 performance (especially in 32-bit mode) I added that hack to write \nthe SHA1 internal temporary hash using a volatile pointer, in order to get \ngcc to not try to cache the array contents. Because gcc will do all the \nwrong things, and then spill things in insane random ways.\n\nBut on architectures like PPC, where you have 32 registers, it's actually \nperfectly reasonable to put the whole temporary array[] into the register \nset, and gcc can do so.\n\nSo make the 'volatile unsigned int *' cast be dependent on a \nSMALL_REGISTER_SET preprocessor symbol, and enable it (currently) on just \nx86 and x86-64. With that, the routine is fairly reasonable even when \ncompared to the hand-scheduled PPC version. Ben Herrenschmidt reports on \na G5:\n\n * Paulus asm version: about 3.67s\n * Yours with no change: about 5.74s\n * Yours without \"volatile\": about 3.78s\n\nso with this the C version is within about 3% of the asm one.\n\nAnd add a lot of commentary on what the heck is going on.\n\nSigned-off-by: Linus Torvalds \n---\n\nI also asked David Miller to test the non-volatile version on Sparc, but I \nsuspect it will have the same pattern. ia64 likewise (but I have not asked \nanybody to test).\n\nOf the other architectures, ARM probably would wants SMALL_REGISTER_SET, \nbut I suspect the problem there is the htonl() (on little-endian), and \npossibly the unaligned loads - at least on older ARM. The latter is \nsomething gcc could be taught about, though (the SHA_SRC macro would just \nneed to use a pointer that goes through a packed struct member or \nsomething).\n\n block-sha1/sha1.c | 25 ++++++++++++++++++++++++-\n 1 files changed, 24 insertions(+), 1 deletions(-)\n\ndiff --git a/block-sha1/sha1.c b/block-sha1/sha1.c\nindex 36da763..9bc8b8a 100644\n--- a/block-sha1/sha1.c\n+++ b/block-sha1/sha1.c\n@@ -82,6 +82,7 @@ void blk_SHA1_Final(unsigned char hashout[20], blk_SHA_CTX *ctx)\n #define SHA_ASM(op, x, n) ({ unsigned int __res; asm(op \" %1,%0\":\"=r\" (__res):\"i\" (n), \"0\" (x)); __res; })\n #define SHA_ROL(x,n)\tSHA_ASM(\"rol\", x, n)\n #define SHA_ROR(x,n)\tSHA_ASM(\"ror\", x, n)\n+#define SMALL_REGISTER_SET\n \n #else\n \n@@ -93,7 +94,29 @@ void blk_SHA1_Final(unsigned char hashout[20], blk_SHA_CTX *ctx)\n \n /* This \"rolls\" over the 512-bit array */\n #define W(x) (array[(x)&15])\n-#define setW(x, val) (*(volatile unsigned int *)&W(x) = (val))\n+\n+/*\n+ * If you have 32 registers or more, the compiler can (and should)\n+ * try to change the array[] accesses into registers. However, on\n+ * machines with less than ~25 registers, that won't really work,\n+ * and at least gcc will make an unholy mess of it.\n+ *\n+ * So to avoid that mess which just slows things down, we force\n+ * the stores to memory to actually happen (we might be better off\n+ * with a 'W(t)=(val);asm(\"\":\"+m\" (W(t))' there instead, as\n+ * suggested by Artur Skawina - that will also make gcc unable to\n+ * try to do the silly \"optimize away loads\" part because it won't\n+ * see what the value will be).\n+ *\n+ * Ben Herrenschmidt reports that on PPC, the C version comes close\n+ * to the optimized asm with this (ie on PPC you don't want that\n+ * 'volatile', since there are lots of registers).\n+ */\n+#ifdef SMALL_REGISTER_SET\n+ #define setW(x, val) (*(volatile unsigned int *)&W(x) = (val))\n+#else\n+ #define setW(x, val) (W(x) = (val))\n+#endif\n \n /*\n * Where do we get the source from? The first 16 iterations get it from\n"},{"id":"120278","messageId":"alpine.LFD.2.00.0908102246210.10633@xanadu.home","threadId":"20527","inReplyTo":"alpine.LFD.2.01.0908101637440.3417@localhost.localdomain","subject":"Re: block-sha1: improve code on large-register-set machines","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-08-11T06:15:50Z","receivedAt":"2009-08-11T06:15:50Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 10 Aug 2009, Linus Torvalds wrote:\n\n> \n> For x86 performance (especially in 32-bit mode) I added that hack to write \n> the SHA1 internal temporary hash using a volatile pointer, in order to get \n> gcc to not try to cache the array contents. Because gcc will do all the \n> wrong things, and then spill things in insane random ways.\n> \n> But on architectures like PPC, where you have 32 registers, it's actually \n> perfectly reasonable to put the whole temporary array[] into the register \n> set, and gcc can do so.\n> \n> So make the 'volatile unsigned int *' cast be dependent on a \n> SMALL_REGISTER_SET preprocessor symbol, and enable it (currently) on just \n> x86 and x86-64. With that, the routine is fairly reasonable even when \n> compared to the hand-scheduled PPC version. Ben Herrenschmidt reports on \n> a G5:\n> \n> * Paulus asm version: about 3.67s\n> * Yours with no change: about 5.74s\n> * Yours without \"volatile\": about 3.78s\n> \n> so with this the C version is within about 3% of the asm one.\n> \n> And add a lot of commentary on what the heck is going on.\n> \n> Signed-off-by: Linus Torvalds \n> ---\n> \n> I also asked David Miller to test the non-volatile version on Sparc, but I \n> suspect it will have the same pattern. ia64 likewise (but I have not asked \n> anybody to test).\n> \n> Of the other architectures, ARM probably would wants SMALL_REGISTER_SET, \n> but I suspect the problem there is the htonl() (on little-endian), and \n> possibly the unaligned loads - at least on older ARM. The latter is \n> something gcc could be taught about, though (the SHA_SRC macro would just \n> need to use a pointer that goes through a packed struct member or \n> something).\n\nThe \"older\" ARM (those that don't perform unaligned accesses in \nhardware) are still the majority by far in the field.\n\nHere some numbers on ARM for 203247018 bytes.\n\nMOZILLA_SHA1:\t14.520s\nARM_SHA1:\t 5.600s\nOPENSSL:\t 5.530s\n\nBLK_SHA1:\t 5.280s\t\t[original]\nBLK_SHA1:\t 7.410s\t\t[with SMALL_REGISTER_SET defined]\nBLK_SHA1:\t 7.480s\t\t[with 'W(x)=(val);asm(\"\":\"+m\" (W(x)))']\nBLK_SHA1:\t 4.980s\t\t[with 'W(x)=(val);asm(\"\":::\"memory\")']\n\nAt this point the generated assembly is pretty slick. I bet the full \nmemory barrier might help on x86 as well.\n\nHowever the above BLK_SHA1 works only for aligned source buffers. So \nlet's define our own SHA_SRC to replace the htonl() (which should \nprobably be ntohl() by the way) like this:\n\n#define SHA_SRC(t) \\\n ({ unsigned char *__d = (unsigned char *)&data[t]; \\\n (__d[0] << 24) | (__d[1] << 16) | (__d[2] << 8) | (__d[3] << 0); })\n\nAnd this provides the exact same performance as the ntohl() based \nversion (4.980s) except that this now cope with unaligned buffers too.\n\nOf course the BLK_SHA1 version is a pig since it is totally unrolled\n\n text data bss dec hex filename\n 1220 0 0 1220 4c4 mozilla-sha1/sha1.o\n 852 0 0 852 354 arm/sha1_arm.o\n 6292 0 0 6292 1894 block-sha1/sha1.o\n\nso the speed advantage has a significant (but relative) code size cost.\n\n\nNicolas\n"},{"id":"120276","messageId":"alpine.LFD.2.01.0908110758160.3417@localhost.localdomain","threadId":"20527","inReplyTo":"alpine.LFD.2.00.0908102246210.10633@xanadu.home","subject":"Re: block-sha1: improve code on large-register-set machines","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-11T15:04:29Z","receivedAt":"2009-08-11T15:04:29Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 11 Aug 2009, Nicolas Pitre wrote:\n> \n> #define SHA_SRC(t) \\\n> ({ unsigned char *__d = (unsigned char *)&data[t]; \\\n> (__d[0] << 24) | (__d[1] << 16) | (__d[2] << 8) | (__d[3] << 0); })\n> \n> And this provides the exact same performance as the ntohl() based \n> version (4.980s) except that this now cope with unaligned buffers too.\n\nIs it better to do a (conditional) memcpy up front? Or is the byte-based \none better just because you always end up doing the shifting anyway due to \nmost ARM situations being little-endian?\n\nI _suspect_ that most large SHA1 calls from git are pre-aligned. The big \nSHA1 calls are for pack-file verification in fsck, which should all be \naligned. Same goes for index file integrity checking.\n\nThe actual object SHA1 calculations are likely not aligned (we do that \nobject header thing), and if you can't do the htonl() any better way I \nguess the byte-based thing is the way to go..\n\n\t\tLinus\n\n---\n block-sha1/sha1.c | 13 ++++++++++++-\n 1 files changed, 12 insertions(+), 1 deletions(-)\n\ndiff --git a/block-sha1/sha1.c b/block-sha1/sha1.c\nindex 9bc8b8a..df27e66 100644\n--- a/block-sha1/sha1.c\n+++ b/block-sha1/sha1.c\n@@ -25,6 +25,12 @@ void blk_SHA1_Init(blk_SHA_CTX *ctx)\n \tctx->H[4] = 0xc3d2e1f0;\n }\n \n+#ifdef REALLY_SLOW_UNALIGNED\n+ #define is_unaligned(ptr) (3 & (unsigned long)(ptr))\n+#else\n+ #define is_unaligned(ptr) 0\n+#endif\n+\n \n void blk_SHA1_Update(blk_SHA_CTX *ctx, const void *data, unsigned long len)\n {\n@@ -47,7 +53,12 @@ void blk_SHA1_Update(blk_SHA_CTX *ctx, const void *data, unsigned long len)\n \t\tblk_SHA1Block(ctx, ctx->W);\n \t}\n \twhile (len >= 64) {\n-\t\tblk_SHA1Block(ctx, data);\n+\t\tconst unsigned int *block = data;\n+\t\tif (is_unaligned(data)) {\n+\t\t\tmemcpy(ctx->W, data, 64);\n+\t\t\tblock = ctx->W;\n+\t\t}\n+\t\tblk_SHA1Block(ctx, block);\n \t\tdata += 64;\n \t\tlen -= 64;\n \t}\n"},{"id":"120281","messageId":"alpine.LFD.2.01.0908110810410.3417@localhost.localdomain","threadId":"20527","inReplyTo":"alpine.LFD.2.00.0908102246210.10633@xanadu.home","subject":"Re: block-sha1: improve code on large-register-set machines","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-11T15:43:21Z","receivedAt":"2009-08-11T15:43:21Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 11 Aug 2009, Nicolas Pitre wrote:\n> \n> BLK_SHA1:\t 5.280s\t\t[original]\n> BLK_SHA1:\t 7.410s\t\t[with SMALL_REGISTER_SET defined]\n> BLK_SHA1:\t 7.480s\t\t[with 'W(x)=(val);asm(\"\":\"+m\" (W(x)))']\n> BLK_SHA1:\t 4.980s\t\t[with 'W(x)=(val);asm(\"\":::\"memory\")']\n> \n> At this point the generated assembly is pretty slick. I bet the full \n> memory barrier might help on x86 as well.\n\nNo, I had tested that earlier - single-word memory barrier for some reason \ngets _much_ better numbers at least on x86-64. We're talking\n\n\tlinus 1.46 418.2\nvs\n\tlinus 2.004 304.6\n\nkind of differences. With the \"+m\" it outperforms openssl (375-380MB/s).\n\nThe \"volatile unsigned int *\" cast looks pretty much like the \"+m\" version \nto me, but Arthur got a speedup from whatever gcc code generation \ndifferences on his P4.\n\nThe really fundamental and basic problem with gcc on this code is that gcc \ndoes not see _any_ difference what-so-ever between the five variables \ndeclared with\n\n\tunsigned int A, B, C, D, E;\n\nand the sixteen variables declared with\n\n\tunsigned int array[16];\n\nand considers those all to be 21 local variables. It really seems to think \nthat they are all 100% equivalent, and gcc totally ignores me doing things \nlike adding \"register\" to the A-E ones etc.\n\nAnd if you are a compiler, and think that the routine has 21 equal \nregister variables, you're going to do crazy reload sh*t when you have \nonly 7 (or 15) GP registers. So doing that full memory barrier seems to \njust take that random situation, and force some random variable to be \nspilled (this is all from looking at the generated code, not from looking \nat gcc).\n\nIn contrast, with the _targeted_ thing (\"you'd better write back into \narray[]\") we force gcc to spill the array[16] values, and not the A-E \nones, and that's why it seems to make such a big difference.\n\nAnd no, I'm not sure why ARM apparently doesn't show the same behavior. Or \nmaybe it does, but with an in-order core it doesn't matter as much which \nregisters you keep reloading - you'll be serialized all the time _anyway_. \n\n\t\t\tLinus\n"},{"id":"120292","messageId":"alpine.LFD.2.00.0908111254290.10633@xanadu.home","threadId":"20527","inReplyTo":"alpine.LFD.2.01.0908110758160.3417@localhost.localdomain","subject":"Re: block-sha1: improve code on large-register-set machines","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-08-11T18:00:09Z","receivedAt":"2009-08-11T18:00:09Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 11 Aug 2009, Linus Torvalds wrote:\n\n> On Tue, 11 Aug 2009, Nicolas Pitre wrote:\n> > \n> > #define SHA_SRC(t) \\\n> > ({ unsigned char *__d = (unsigned char *)&data[t]; \\\n> > (__d[0] << 24) | (__d[1] << 16) | (__d[2] << 8) | (__d[3] << 0); })\n> > \n> > And this provides the exact same performance as the ntohl() based \n> > version (4.980s) except that this now cope with unaligned buffers too.\n> \n> Is it better to do a (conditional) memcpy up front? Or is the byte-based \n> one better just because you always end up doing the shifting anyway due to \n> most ARM situations being little-endian?\n\nThe vast majority of ARM processors where git might be run are using a \nLE environment.\n\n> I _suspect_ that most large SHA1 calls from git are pre-aligned. The big \n> SHA1 calls are for pack-file verification in fsck, which should all be \n> aligned. Same goes for index file integrity checking.\n> \n> The actual object SHA1 calculations are likely not aligned (we do that \n> object header thing), and if you can't do the htonl() any better way I \n> guess the byte-based thing is the way to go..\n\nLet's see. The default ntohl() provided by glibc generates this code:\n\n ldr r3, [r0, #0]\n mov r0, r3, lsr #24\n and r2, r3, #0x00ff0000\n orr r0, r0, r3, asl #24\n orr r0, r0, r2, lsr #8\n and r3, r3, #0x0000ff00\n orr r0, r0, r3, asl #8\n\nIgnoring the load result delay that gcc should properly schedule anyway, \nthat makes for 7 cycles.\n\nUsing the smarter ARM swab32 implementation from Linux we get:\n\n ldr r3, [r0, #0]\n eor r0, r3, r3, ror #16\n bic r0, r0, #0x00ff0000\n mov r0, r0, lsr #8\n eor r0, r0, r3, ror #8\n\nSo we're down to 5 cycles. And the SHA1 test is a bit faster too: \n4.570s down from 4.980s. However this is still using purely aligned \nbuffers.\n\nAdding your patch using memcpy() to align the data in the unaligned case \ngives me wild results. Sometimes it is 4.930s, sometimes it is 5.560s. \nI suspect the icache starts to get tight and sometimes the SHA1 code \nand/or the special unaligned memcpy path get evicted sometimes.\n\nUsing the byte access version we get:\n\n ldrb r3, [r0, #3]\n ldrb r2, [r0, #0]\n ldrb r1, [r0, #1]\n orr r3, r3, r2, asl #24\n ldrb r0, [r0, #2]\n orr r3, r3, r1, asl #16\n orr r0, r3, r0, asl #8\n\nAgain 7 cycles, like the ntohl() based version, which is coherent with \nthe fact that they both make for 4.980s.. However this time any buffer \nalignment is supported. And in fact the extra 2 cycles over the \nswab32() version should actually be less overhead per word than the \nunaligned memcpy which is around 4 cycles per word.\n\n\nNicolas\n"},{"id":"120293","messageId":"alpine.LFD.2.00.0908111517390.10633@xanadu.home","threadId":"20527","inReplyTo":"alpine.LFD.2.00.0908111254290.10633@xanadu.home","subject":"Re: block-sha1: improve code on large-register-set machines","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-08-11T19:31:50Z","receivedAt":"2009-08-11T19:31:50Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 11 Aug 2009, Nicolas Pitre wrote:\n\n> On Tue, 11 Aug 2009, Linus Torvalds wrote:\n> \n> > On Tue, 11 Aug 2009, Nicolas Pitre wrote:\n> > > \n> > > #define SHA_SRC(t) \\\n> > > ({ unsigned char *__d = (unsigned char *)&data[t]; \\\n> > > (__d[0] << 24) | (__d[1] << 16) | (__d[2] << 8) | (__d[3] << 0); })\n> > > \n> > > And this provides the exact same performance as the ntohl() based \n> > > version (4.980s) except that this now cope with unaligned buffers too.\n> > \n> > The actual object SHA1 calculations are likely not aligned (we do that \n> > object header thing), and if you can't do the htonl() any better way I \n> > guess the byte-based thing is the way to go..\n\nOK, even better: 4.400s.\n\nThis is with this instead of the above:\n\n#define SHA_SRC(t) \\\n ({ unsigned char *__d = (unsigned char *)data; \\\n (__d[(t)*4 + 0] << 24) | (__d[(t)*4 + 1] << 16) | \\\n (__d[(t)*4 + 2] << 8) | (__d[(t)*4 + 3] << 0); })\n\nThe previous version would allocate a new register for __d and then \nindex it with an offset of 0, 1, 2 or 3. This version always uses the \nregister containing the data pointer with absolute offsets. The binary \nis a bit smaller too.\n\n\nNicolas\n"},{"id":"120294","messageId":"alpine.LFD.2.00.0908111437160.10633@xanadu.home","threadId":"20527","inReplyTo":"alpine.LFD.2.01.0908110810410.3417@localhost.localdomain","subject":"Re: block-sha1: improve code on large-register-set machines","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-08-11T20:03:58Z","receivedAt":"2009-08-11T20:03:58Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 11 Aug 2009, Linus Torvalds wrote:\n\n> On Tue, 11 Aug 2009, Nicolas Pitre wrote:\n> > \n> > BLK_SHA1:\t 5.280s\t\t[original]\n> > BLK_SHA1:\t 7.410s\t\t[with SMALL_REGISTER_SET defined]\n> > BLK_SHA1:\t 7.480s\t\t[with 'W(x)=(val);asm(\"\":\"+m\" (W(x)))']\n> > BLK_SHA1:\t 4.980s\t\t[with 'W(x)=(val);asm(\"\":::\"memory\")']\n> > \n> > At this point the generated assembly is pretty slick. I bet the full \n> > memory barrier might help on x86 as well.\n> \n> No, I had tested that earlier - single-word memory barrier for some reason \n> gets _much_ better numbers at least on x86-64. We're talking\n> \n> \tlinus 1.46 418.2\n> vs\n> \tlinus 2.004 304.6\n> \n> kind of differences. With the \"+m\" it outperforms openssl (375-380MB/s).\n> \n> The \"volatile unsigned int *\" cast looks pretty much like the \"+m\" version \n> to me, but Arthur got a speedup from whatever gcc code generation \n> differences on his P4.\n\nThe volatile pointer forces a write to memory but the cached value in \nthe processor's register remains valid, whereas the \"+m\" forces gcc to \nassume the register copy is not valid anymore. That certainly gives the \ncompiler a different clue about register availability, etc.\n\n> The really fundamental and basic problem with gcc on this code is that gcc \n> does not see _any_ difference what-so-ever between the five variables \n> declared with\n> \n> \tunsigned int A, B, C, D, E;\n> \n> and the sixteen variables declared with\n> \n> \tunsigned int array[16];\n> \n> and considers those all to be 21 local variables. It really seems to think \n> that they are all 100% equivalent, and gcc totally ignores me doing things \n> like adding \"register\" to the A-E ones etc.\n> \n> And if you are a compiler, and think that the routine has 21 equal \n> register variables, you're going to do crazy reload sh*t when you have \n> only 7 (or 15) GP registers. So doing that full memory barrier seems to \n> just take that random situation, and force some random variable to be \n> spilled (this is all from looking at the generated code, not from looking \n> at gcc).\n> \n> In contrast, with the _targeted_ thing (\"you'd better write back into \n> array[]\") we force gcc to spill the array[16] values, and not the A-E \n> ones, and that's why it seems to make such a big difference.\n> \n> And no, I'm not sure why ARM apparently doesn't show the same behavior. Or \n> maybe it does, but with an in-order core it doesn't matter as much which \n> registers you keep reloading - you'll be serialized all the time _anyway_. \n\nWell... gcc is really strange in this case (and similar other ones) with \nARM compilation. A good indicator of the quality of the code is the \nsize of the stack frame. When using the \"+m\" then gcc creates a 816 \nbyte stack frame, the generated binary grows by approx 3000 bytes, and \nperformances is almost halved (7.600s). Looking at the assembly result \nI just can't figure out all the crazy moves taking place. Even the \nversion with no barrier what so ever produces better assembly with a \nstack frame of 560 bytes.\n\nThe volatile version is second to worst with a 808 byte stack frame with \nsimilar bad performances.\n\nWith the full \"memory\" the stack frame shrinks to 280 bytes and best \nperformances so far is obtained. And none of the A B C D E or data \nvariables are ever spilled onto the stack either, only the array[16] \ngets allocated stack slots, and the TEMP variable.\n\n\nNicolas\n"},{"id":"120308","messageId":"fLYKSyures_wcvAvAV9-MgKQlhk959HJpx-pKz7T1n-Mel7f2RBkMw@cipher.nrlssc.navy.mil","threadId":"20527","inReplyTo":"alpine.LFD.2.00.0908111517390.10633@xanadu.home","subject":"Re: block-sha1: improve code on large-register-set machines","fromName":"Brandon Casey","fromEmail":"brandon.casey.ctr@nrlssc.navy.mil","sentAt":"2009-08-11T21:20:57Z","receivedAt":"2009-08-11T21:20:57Z","isPatch":false,"sender":{"key":"brandon.casey.ctr@nrlssc.navy.mil","avatar":null},"body":"Nicolas Pitre wrote:\n> On Tue, 11 Aug 2009, Nicolas Pitre wrote:\n> \n>> On Tue, 11 Aug 2009, Linus Torvalds wrote:\n>>\n>>> On Tue, 11 Aug 2009, Nicolas Pitre wrote:\n>>>> #define SHA_SRC(t) \\\n>>>> ({ unsigned char *__d = (unsigned char *)&data[t]; \\\n>>>> (__d[0] << 24) | (__d[1] << 16) | (__d[2] << 8) | (__d[3] << 0); })\n>>>>\n>>>> And this provides the exact same performance as the ntohl() based \n>>>> version (4.980s) except that this now cope with unaligned buffers too.\n>>> The actual object SHA1 calculations are likely not aligned (we do that \n>>> object header thing), and if you can't do the htonl() any better way I \n>>> guess the byte-based thing is the way to go..\n> \n> OK, even better: 4.400s.\n> \n> This is with this instead of the above:\n> \n> #define SHA_SRC(t) \\\n> ({ unsigned char *__d = (unsigned char *)data; \\\n> (__d[(t)*4 + 0] << 24) | (__d[(t)*4 + 1] << 16) | \\\n> (__d[(t)*4 + 2] << 8) | (__d[(t)*4 + 3] << 0); })\n> \n> The previous version would allocate a new register for __d and then \n> index it with an offset of 0, 1, 2 or 3. This version always uses the \n> register containing the data pointer with absolute offsets. The binary \n> is a bit smaller too.\n\nIn that case, why not change the interface of blk_SHA1Block() so that its\nsecond argument is const unsigned char* and get rid of __d and the { } ?\n\nThen it will look like this:\n\n static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned char *data);\n\n ...\n\n #define SHA_SRC(t) \\\n ( (data[(t)*4 + 0] << 24) | (data[(t)*4 + 1] << 16) | \\\n (data[(t)*4 + 2] << 8) | (data[(t)*4 + 3] << 0) )\n\n\nPlus, we need something like the following to handle storing the hash to\nan unaligned buffer (warning copy/pasted):\n\n@@ -73,8 +74,12 @@ void blk_SHA1_Final(unsigned char hashout[20], blk_SHA_CTX *c\n \n /* Output hash\n */\n- for (i = 0; i < 5; i++)\n- ((unsigned int *)hashout)[i] = htonl(ctx->H[i]);\n+ for (i = 0; i < 5; i++) {\n+ *hashout++ = (unsigned char) (ctx->H[i] >> 24);\n+ *hashout++ = (unsigned char) (ctx->H[i] >> 16);\n+ *hashout++ = (unsigned char) (ctx->H[i] >> 8);\n+ *hashout++ = (unsigned char) (ctx->H[i] >> 0);\n+ }\n }\n \n #if defined(__i386__) || defined(__x86_64__)\n\n\nWith these two changes plus a few other minor tweaks, the block-sha1 code compiles\nand passes the test suite on sparc (solaris 7) and mips (irix 6.5).\n\n-brandon\n"},{"id":"120311","messageId":"alpine.LFD.2.00.0908111735010.10633@xanadu.home","threadId":"20527","inReplyTo":"fLYKSyures_wcvAvAV9-MgKQlhk959HJpx-pKz7T1n-Mel7f2RBkMw@cipher.nrlssc.navy.mil","subject":"Re: block-sha1: improve code on large-register-set machines","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-08-11T21:36:58Z","receivedAt":"2009-08-11T21:36:58Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 11 Aug 2009, Brandon Casey wrote:\n\n> Nicolas Pitre wrote:\n> > On Tue, 11 Aug 2009, Nicolas Pitre wrote:\n> > \n> >> On Tue, 11 Aug 2009, Linus Torvalds wrote:\n> >>\n> >>> On Tue, 11 Aug 2009, Nicolas Pitre wrote:\n> >>>> #define SHA_SRC(t) \\\n> >>>> ({ unsigned char *__d = (unsigned char *)&data[t]; \\\n> >>>> (__d[0] << 24) | (__d[1] << 16) | (__d[2] << 8) | (__d[3] << 0); })\n> >>>>\n> >>>> And this provides the exact same performance as the ntohl() based \n> >>>> version (4.980s) except that this now cope with unaligned buffers too.\n> >>> The actual object SHA1 calculations are likely not aligned (we do that \n> >>> object header thing), and if you can't do the htonl() any better way I \n> >>> guess the byte-based thing is the way to go..\n> > \n> > OK, even better: 4.400s.\n> > \n> > This is with this instead of the above:\n> > \n> > #define SHA_SRC(t) \\\n> > ({ unsigned char *__d = (unsigned char *)data; \\\n> > (__d[(t)*4 + 0] << 24) | (__d[(t)*4 + 1] << 16) | \\\n> > (__d[(t)*4 + 2] << 8) | (__d[(t)*4 + 3] << 0); })\n> > \n> > The previous version would allocate a new register for __d and then \n> > index it with an offset of 0, 1, 2 or 3. This version always uses the \n> > register containing the data pointer with absolute offsets. The binary \n> > is a bit smaller too.\n> \n> In that case, why not change the interface of blk_SHA1Block() so that its\n> second argument is const unsigned char* and get rid of __d and the { } ?\n\nBecause not all architectures care to access the data bytewise. Please \nsee the original SHA_SRC definition.\n\n\nNicolas\n"},{"id":"120314","messageId":"s9lHCuz3Fo2GHgUzqSTJyqRY3NBYsra0Ko9LbHd8rN_WaAwuc7IUfw@cipher.nrlssc.navy.mil","threadId":"20527","inReplyTo":"alpine.LFD.2.00.0908111735010.10633@xanadu.home","subject":"Re: block-sha1: improve code on large-register-set machines","fromName":"Brandon Casey","fromEmail":"brandon.casey.ctr@nrlssc.navy.mil","sentAt":"2009-08-11T21:49:12Z","receivedAt":"2009-08-11T21:49:12Z","isPatch":false,"sender":{"key":"brandon.casey.ctr@nrlssc.navy.mil","avatar":null},"body":"Nicolas Pitre wrote:\n> On Tue, 11 Aug 2009, Brandon Casey wrote:\n> \n>> Nicolas Pitre wrote:\n>>> On Tue, 11 Aug 2009, Nicolas Pitre wrote:\n>>>\n>>>> On Tue, 11 Aug 2009, Linus Torvalds wrote:\n>>>>\n>>>>> On Tue, 11 Aug 2009, Nicolas Pitre wrote:\n>>>>>> #define SHA_SRC(t) \\\n>>>>>> ({ unsigned char *__d = (unsigned char *)&data[t]; \\\n>>>>>> (__d[0] << 24) | (__d[1] << 16) | (__d[2] << 8) | (__d[3] << 0); })\n>>>>>>\n>>>>>> And this provides the exact same performance as the ntohl() based \n>>>>>> version (4.980s) except that this now cope with unaligned buffers too.\n>>>>> The actual object SHA1 calculations are likely not aligned (we do that \n>>>>> object header thing), and if you can't do the htonl() any better way I \n>>>>> guess the byte-based thing is the way to go..\n>>> OK, even better: 4.400s.\n>>>\n>>> This is with this instead of the above:\n>>>\n>>> #define SHA_SRC(t) \\\n>>> ({ unsigned char *__d = (unsigned char *)data; \\\n>>> (__d[(t)*4 + 0] << 24) | (__d[(t)*4 + 1] << 16) | \\\n>>> (__d[(t)*4 + 2] << 8) | (__d[(t)*4 + 3] << 0); })\n>>>\n>>> The previous version would allocate a new register for __d and then \n>>> index it with an offset of 0, 1, 2 or 3. This version always uses the \n>>> register containing the data pointer with absolute offsets. The binary \n>>> is a bit smaller too.\n>> In that case, why not change the interface of blk_SHA1Block() so that its\n>> second argument is const unsigned char* and get rid of __d and the { } ?\n> \n> Because not all architectures care to access the data bytewise. Please \n> see the original SHA_SRC definition.\n\nYou mean this:\n\n #define SHA_SRC(t) htonl(data[t])\n\n? Or was there a definition before this one?\n\nI don't follow what you are saying. Are you saying that the following two\nexamples are different?\n\n unsigned int *data;\n\n #define SHA_SRC(t) \\\n ({ unsigned char *__d = (unsigned char *)data; \\\n (__d[(t)*4 + 0] << 24) | (__d[(t)*4 + 1] << 16) | \\\n (__d[(t)*4 + 2] << 8) | (__d[(t)*4 + 3] << 0); })\n\nand\n\n unsigned char *data;\n\n #define SHA_SRC(t) \\\n ( (data[(t)*4 + 0] << 24) | (data[(t)*4 + 1] << 16) | \\\n (data[(t)*4 + 2] << 8) | (data[(t)*4 + 3] << 0) )\n\n-brandon\n"},{"id":"120319","messageId":"alpine.LFD.2.01.0908111550470.28882@localhost.localdomain","threadId":"20527","inReplyTo":"alpine.LFD.2.00.0908111437160.10633@xanadu.home","subject":"Re: block-sha1: improve code on large-register-set machines","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-11T22:53:28Z","receivedAt":"2009-08-11T22:53:28Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 11 Aug 2009, Nicolas Pitre wrote:\n> \n> Well... gcc is really strange in this case (and similar other ones) with \n> ARM compilation. A good indicator of the quality of the code is the \n> size of the stack frame. When using the \"+m\" then gcc creates a 816 \n> byte stack frame, the generated binary grows by approx 3000 bytes, and \n> performances is almost halved (7.600s). Looking at the assembly result \n> I just can't figure out all the crazy moves taking place. Even the \n> version with no barrier what so ever produces better assembly with a \n> stack frame of 560 bytes.\n\nOk, that's just crazy. That function has a required stack size of exactly \n64 bytes, and anything more than that is just spilling. And if you end up \nwith a stack frame of 560 bytes, that means that gcc is doing some _crazy_ \nspilling.\n\nOne thing that strikes me is that I've been just testing with gcc-4.4, and \nBenH (who did some tests on PPC where SHA1 is just _trivial_ because it \nall fits in the normal register space) noticed that older versions of gcc \nthat he tested did much worse on this.\n\nI think Artur also posted (x86) numbers with older gcc versions doing \nworse. Maybe you're seeing some of that?\n\n\t\t\tLinus\n"},{"id":"120320","messageId":"alpine.LFD.2.01.0908111553460.28882@localhost.localdomain","threadId":"20527","inReplyTo":"fLYKSyures_wcvAvAV9-MgKQlhk959HJpx-pKz7T1n-Mel7f2RBkMw@cipher.nrlssc.navy.mil","subject":"Re: block-sha1: improve code on large-register-set machines","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-11T22:57:10Z","receivedAt":"2009-08-11T22:57:10Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 11 Aug 2009, Brandon Casey wrote:\n> \n> In that case, why not change the interface of blk_SHA1Block() so that its\n> second argument is const unsigned char* and get rid of __d and the { } ?\n\nBecause on big-endian, or on architectures like x86 that have an efficient \nbyte swap, that would be horrible.\n\nYou absoluetoy MUST NOT do things a byte at a time in those cases. The \nmemory operations and the shifting just kills you.\n\nThe reason you want to do things a byte at a time on ARM is that ARM \ncannot do unaligned accesses well (very modern cores are better, but \nrare), and that ARM has no bswap instruction and has fairly cheap shifts.\n\nOn no sane architecture is that true. Unaligned loads are fast (and quite \nfrankly, hardware where unaliged loads aren't fast is just crazy sh*t), \nand doing 'bswap' is way faster than doing many shifts and masks.\n\nSo everything should be fundamentally word-oriented. Then, broken \narchitectures that can't handle it should split up the words, not the \nother way around.\n\n\t\t\tLinus\n"},{"id":"120325","messageId":"64Kyx_w-_2GgXIdUn26ky9qHnuvHBH2QTe9tAj1uuLv-1YDZNVLNKA@cipher.nrlssc.navy.mil","threadId":"20527","inReplyTo":"alpine.LFD.2.01.0908111553460.28882@localhost.localdomain","subject":"Re: block-sha1: improve code on large-register-set machines","fromName":"Brandon Casey","fromEmail":"brandon.casey.ctr@nrlssc.navy.mil","sentAt":"2009-08-11T23:13:16Z","receivedAt":"2009-08-11T23:13:16Z","isPatch":false,"sender":{"key":"brandon.casey.ctr@nrlssc.navy.mil","avatar":null},"body":"Linus Torvalds wrote:\n> \n> On Tue, 11 Aug 2009, Brandon Casey wrote:\n>> In that case, why not change the interface of blk_SHA1Block() so that its\n>> second argument is const unsigned char* and get rid of __d and the { } ?\n> \n> Because on big-endian, or on architectures like x86 that have an efficient \n> byte swap, that would be horrible.\n\nSorry, I missed Nicolas's first message where he said his SHA_SRC macro was\nfor arm only.\n\nI started at your reply to him which only has the snippet which says\n\"...this provides the exact same performance as the ntohl() based version\nexcept that this now cope with unaligned buffers too\".\n\nMy mistake.\n\n-brandon\n"},{"id":"120326","messageId":"alpine.LFD.2.01.0908111602020.28882@localhost.localdomain","threadId":"20527","inReplyTo":"alpine.LFD.2.01.0908111550470.28882@localhost.localdomain","subject":"Re: block-sha1: improve code on large-register-set machines","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-11T23:14:19Z","receivedAt":"2009-08-11T23:14:19Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 11 Aug 2009, Linus Torvalds wrote:\n\n> \n> \n> On Tue, 11 Aug 2009, Nicolas Pitre wrote:\n> > \n> > Well... gcc is really strange in this case (and similar other ones) with \n> > ARM compilation. A good indicator of the quality of the code is the \n> > size of the stack frame. When using the \"+m\" then gcc creates a 816 \n> > byte stack frame, the generated binary grows by approx 3000 bytes, and \n> > performances is almost halved (7.600s). Looking at the assembly result \n> > I just can't figure out all the crazy moves taking place. Even the \n> > version with no barrier what so ever produces better assembly with a \n> > stack frame of 560 bytes.\n> \n> Ok, that's just crazy. That function has a required stack size of exactly \n> 64 bytes, and anything more than that is just spilling. And if you end up \n> with a stack frame of 560 bytes, that means that gcc is doing some _crazy_ \n> spilling.\n\nBtw, what I think happens is:\n\n - gcc turns all those array accesses into pseudo's \n\n So now the 'array[16]' is seen as just another 16 variables rather than \n an array.\n\n - gcc then turns it into SSA, where each assignment basically creates a \n new variable. So the 16 array variables (and 5 regular variables) are \n now expanded to 80 SSA asignments (one array assignment per SHA1 round) \n plus an additional 2 assignments to the \"regular\" variables per round \n (B and E are changed each round). So in SSA form, you actually end up \n having 240 pseudo's associated with the actual variables. Plus all \n the temporaries of course.\n\n - the thing then goes crazy and tries to generate great code from that \n internal SSA model. And since there are never more than ~25 things \n _live_ at any particular point, it works fine with lots of registers, \n but on small-register machines gcc just goes crazy and has to spill. \n And it doesn't spill 'array[x]' entries - it spills the _pseudo's_ it \n has created - hundreds of them.\n\n - End result: if the spill code doesn't share slots, it's going to create \n a totally unholy mess of crap.\n\nThat's what the whole 'volatile unsigned int *' game tried to avoid. But \nit really sounds like it's not working too well for you. And the _big_ \nmemory barrier ends up helping just because with that in place, you end up \nbeing almost entirely unable to schedule _anything_ between the different \nSHA rounds, so you end up with only six or seven variables \"live\" in \nbetween those barriers, and the stupid register allocator/spill logic \ndoesn't break down too badly.\n\nThe thing is, if you do full memory barriers, then you're probably better \noff making both the loads and the stores be \"volatile\". That should have \nsimilar effects.\n\nThe downside with that is that it really limits the loads. So (like the \nfull memory barrier) it's a big hammer approach. But it probably generates \nbetter code for you, because it avoids the mental breakdown of gcc \nspilling its pseudo's.\n\n\t\t\tLinus\n"},{"id":"120330","messageId":"4A8202B0.9080608@gmail.com","threadId":"20527","inReplyTo":"alpine.LFD.2.01.0908111550470.28882@localhost.localdomain","subject":"Re: block-sha1: improve code on large-register-set machines","fromName":"Artur Skawina","fromEmail":"art.08.09@gmail.com","sentAt":"2009-08-11T23:45:52Z","receivedAt":"2009-08-11T23:45:52Z","isPatch":false,"sender":{"key":"art.08.09@gmail.com","avatar":null},"body":"Linus Torvalds wrote:\n> \n> One thing that strikes me is that I've been just testing with gcc-4.4, and \n> BenH (who did some tests on PPC where SHA1 is just _trivial_ because it \n> all fits in the normal register space) noticed that older versions of gcc \n> that he tested did much worse on this.\n> \n> I think Artur also posted (x86) numbers with older gcc versions doing \n> worse. Maybe you're seeing some of that?\n\nFWIW, this is how it looks here. On 32-bit x86 gcc4.4 makes a large\ndifference[1], but your code does fairly well w/ most gccs, relatively\nto all the other C implementations.\n\nartur\n\nP4: [linusv is the recent one w/ the volatile stores]\n\n### sha1bench-gcc295: GCCVER 2.95.4 20030502 (prerelease)\nrfc3174 0.9438 64.67\nlinus 0.9081 67.21\nlinusv 0.4155 146.9\nlinusp4 0.8761 69.66\nlinusas 0.9619 63.45\nlinusas2 1.025 59.52\nmozilla 1.314 46.46\nmozillaas 1.132 53.92\n\n### sha1bench-gcc31: GCCVER 3.2 2002-07-26 (prerelease)\nrfc3174 0.8582 71.12\nlinus 0.7943 76.84\nlinusv 0.5667 107.7\nlinusp4 0.7224 84.48\nlinusas 0.7127 85.64\nlinusas2 0.5109 119.5\nmozilla 1.251 48.79\nmozillaas 1.239 49.27\n\n### sha1bench-gcc32: GCCVER 3.2.3\nrfc3174 0.9062 67.35\nlinus 0.5555 109.9\nlinusv 0.3647 167.4\nlinusp4 0.5337 114.4\nlinusas 0.7126 85.66\nlinusas2 0.5089 119.9\nmozilla 1.138 53.64\nmozillaas 1.075 56.78\n\n### sha1bench-gcc33: GCCVER 3.3.6\nrfc3174 0.9029 67.6\nlinus 0.6059 100.7\nlinusv 0.3734 163.4\nlinusp4 0.6695 91.16\nlinusas 0.7832 77.93\nlinusas2 0.571 106.9\nmozilla 1.083 56.36\nmozillaas 1.078 56.62\n\n### sha1bench-gcc34: GCCVER 3.4.6 20060121 (prerelease)\nrfc3174 0.9277 65.79\nlinus 0.6583 92.71\nlinusv 0.6096 100.1\nlinusp4 0.7326 83.31\nlinusas 0.7383 82.67\nlinusas2 0.6264 97.44\nmozilla 1.398 43.67\nmozillaas 1.392 43.84\n\n### sha1bench-gcc40: GCCVER 4.0.4 20061113 (prerelease)\nrfc3174 0.9889 61.72\nlinus 0.7508 81.29\nlinusv 0.7752 78.73\nlinusp4 0.6548 93.21\nlinusas 0.4904 124.5\nlinusas2 0.6378 95.7\nmozilla 1.528 39.93\nmozillaas 1.596 38.24\n\n### sha1bench-gcc41: GCCVER 4.1.3 20080704 (prerelease)\nrfc3174 0.9798 62.29\nlinus 0.6993 87.28\nlinusv 0.767 79.57\nlinusp4 0.6785 89.95\nlinusas 0.6555 93.11\nlinusas2 0.691 88.32\nmozilla 1.594 38.3\nmozillaas 1.566 38.98\n\n### sha1bench-gcc42: GCCVER 4.2.5 20090330 (prerelease)\nrfc3174 1.138 53.63\nlinus 0.7772 78.53\nlinusv 0.6138 99.43\nlinusp4 0.7018 86.97\nlinusas 0.8164 74.76\nlinusas2 0.7038 86.73\nmozilla 1.697 35.97\nmozillaas 1.491 40.94\n\n### sha1bench-gcc43: GCCVER 4.3.5 20090810 (prerelease)\nrfc3174 1.148 53.15\nlinus 0.7085 86.14\nlinusv 0.5474 111.5\nlinusp4 0.5399 113\nlinusas 0.7522 81.14\nlinusas2 0.5341 114.3\nmozilla 1.723 35.43\nmozillaas 1.502 40.64\n\n### sha1bench-gcc44: GCCVER 4.4.2 20090809 (prerelease)\nrfc3174 1.451 42.06\nlinus 0.5871 104\nlinusv 0.3713 164.4\nlinusp4 0.4367 139.8\nlinusas 0.4083 149.5\nlinusas2 0.4372 139.6\nmozilla 1.104 55.27\nmozillaas 1.314 46.44\n\n\nAnd on Atom:\n\n### sha1bench-gcc295: GCCVER 2.95.4 20030502 (prerelease)\nrfc3174 1.905 32.04\nlinus 1.089 56.06\nlinusv 0.8134 75.04\nlinusp4 1.086 56.19\nlinusas 1.009 60.52\nlinusas2 1.255 48.63\nmozilla 2.663 22.92\n\n### sha1bench-gcc31: GCCVER 3.2 2002-07-26 (prerelease)\nrfc3174 2.141 28.51\nlinus 1.022 59.75\nlinusv 0.8323 73.34\nlinusp4 1.061 57.54\nlinusas 0.9889 61.72\nlinusas2 0.9204 66.32\nmozilla 2.573 23.72\n\n### sha1bench-gcc32: GCCVER 3.2.3\nrfc3174 2.155 28.32\nlinus 0.9031 67.58\nlinusv 0.7849 77.76\nlinusp4 0.847 72.06\nlinusas 0.9888 61.73\nlinusas2 0.912 66.93\nmozilla 2.485 24.56\n\n### sha1bench-gcc33: GCCVER 3.3.6\nrfc3174 2.178 28.02\nlinus 0.9489 64.32\nlinusv 0.8642 70.63\nlinusp4 0.8784 69.48\nlinusas 1.017 60.03\nlinusas2 0.906 67.37\nmozilla 2.541 24.02\n\n### sha1bench-gcc34: GCCVER 3.4.6 20060121 (prerelease)\nrfc3174 2.157 28.3\nlinus 0.9481 64.37\nlinusv 0.8383 72.8\nlinusp4 0.965 63.25\nlinusas 0.9852 61.95\nlinusas2 0.9809 62.22\nmozilla 3.143 19.42\n\n### sha1bench-gcc40: GCCVER 4.0.4 20061113 (prerelease)\nrfc3174 2.088 29.24\nlinus 0.9706 62.89\nlinusv 0.928 65.77\nlinusp4 1.003 60.85\nlinusas 0.9478 64.4\nlinusas2 0.9475 64.42\nmozilla 2.742 22.26\n\n### sha1bench-gcc41: GCCVER 4.1.3 20080704 (prerelease)\nrfc3174 2.047 29.81\nlinus 0.9778 62.42\nlinusv 1.051 58.06\nlinusp4 1.062 57.46\nlinusas 1.052 58.01\nlinusas2 1.069 57.12\nmozilla 2.6 23.47\n\n### sha1bench-gcc42: GCCVER 4.2.5 20090330 (prerelease)\nrfc3174 2.025 30.14\nlinus 0.9622 63.43\nlinusv 0.7984 76.44\nlinusp4 0.8967 68.07\nlinusas 1.018 59.94\nlinusas2 0.9048 67.46\nmozilla 2.748 22.21\n\n### sha1bench-gcc43: GCCVER 4.3.5 20090810 (prerelease)\nrfc3174 2.043 29.88\nlinus 0.9436 64.69\nlinusv 0.8532 71.54\nlinusp4 0.8531 71.54\nlinusas 1.04 58.71\nlinusas2 0.8495 71.85\nmozilla 2.678 22.79\n\n### sha1bench-gcc44: GCCVER 4.4.2 20090809 (prerelease)\nrfc3174 2.119 28.8\nlinus 0.9132 66.84\nlinusv 0.8632 70.71\nlinusp4 0.9842 62.02\nlinusas 1.027 59.45\nlinusas2 0.9844 62\nmozilla 2.214 27.57\n"},{"id":"120350","messageId":"alpine.LFD.2.00.0908112140020.10633@xanadu.home","threadId":"20527","inReplyTo":"alpine.LFD.2.01.0908111602020.28882@localhost.localdomain","subject":"Re: block-sha1: improve code on large-register-set machines","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-08-12T02:26:58Z","receivedAt":"2009-08-12T02:26:58Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 11 Aug 2009, Linus Torvalds wrote:\n\n> \n> \n> On Tue, 11 Aug 2009, Linus Torvalds wrote:\n> \n> > \n> > \n> > On Tue, 11 Aug 2009, Nicolas Pitre wrote:\n> > > \n> > > Well... gcc is really strange in this case (and similar other ones) with \n> > > ARM compilation. A good indicator of the quality of the code is the \n> > > size of the stack frame. When using the \"+m\" then gcc creates a 816 \n> > > byte stack frame, the generated binary grows by approx 3000 bytes, and \n> > > performances is almost halved (7.600s). Looking at the assembly result \n> > > I just can't figure out all the crazy moves taking place. Even the \n> > > version with no barrier what so ever produces better assembly with a \n> > > stack frame of 560 bytes.\n> > \n> > Ok, that's just crazy. That function has a required stack size of exactly \n> > 64 bytes, and anything more than that is just spilling. And if you end up \n> > with a stack frame of 560 bytes, that means that gcc is doing some _crazy_ \n> > spilling.\n> \n> Btw, what I think happens is:\n> \n> - gcc turns all those array accesses into pseudo's \n> \n> So now the 'array[16]' is seen as just another 16 variables rather than \n> an array.\n> \n> - gcc then turns it into SSA, where each assignment basically creates a \n> new variable. So the 16 array variables (and 5 regular variables) are \n> now expanded to 80 SSA asignments (one array assignment per SHA1 round) \n> plus an additional 2 assignments to the \"regular\" variables per round \n> (B and E are changed each round). So in SSA form, you actually end up \n> having 240 pseudo's associated with the actual variables. Plus all \n> the temporaries of course.\n> \n> - the thing then goes crazy and tries to generate great code from that \n> internal SSA model. And since there are never more than ~25 things \n> _live_ at any particular point, it works fine with lots of registers, \n> but on small-register machines gcc just goes crazy and has to spill. \n> And it doesn't spill 'array[x]' entries - it spills the _pseudo's_ it \n> has created - hundreds of them.\n> \n> - End result: if the spill code doesn't share slots, it's going to create \n> a totally unholy mess of crap.\n> \n> That's what the whole 'volatile unsigned int *' game tried to avoid. But \n> it really sounds like it's not working too well for you. And the _big_ \n> memory barrier ends up helping just because with that in place, you end up \n> being almost entirely unable to schedule _anything_ between the different \n> SHA rounds, so you end up with only six or seven variables \"live\" in \n> between those barriers, and the stupid register allocator/spill logic \n> doesn't break down too badly.\n> \n> The thing is, if you do full memory barriers, then you're probably better \n> off making both the loads and the stores be \"volatile\". That should have \n> similar effects.\n\nIf the loads are volatile then gcc has less flexibility when scheduling \nthem.\n\n> The downside with that is that it really limits the loads. So (like the \n> full memory barrier) it's a big hammer approach. But it probably generates \n> better code for you, because it avoids the mental breakdown of gcc \n> spilling its pseudo's.\n\nActually, all my previous tests were done with gcc-4.3.2. I now have \ninstalled Fedora 11 which has gcc-4.4.0. And now the stack frame is a \nnice 64 bytes. ;-)\n\nThat's with the \"memory\" though. With the volatile, stack frame goes up \nto 224 bytes and performance, although not as bad as before, is like \n5.160s instead of 4.410s. The \"+m\" version is not much better: 208 byte \nstack frame and similar performance.\n\nThe version with no barrier what so ever runs in 4.580s and uses a 88 \nbyte stack frame. The generated assembly contains stupid things, but \nthis is still the second best version, even better than the \"+m\" and \nvolatile ptr ones.\n\nConclusion: the full \"memory\" barrier remains the best choice on ARM.\n\n\nNicolas\n"}]}