{"thread":{"id":"20588","subject":"Re: [PATCH] block-sha1: more good unaligned memory access candidates","startedAt":"2009-08-13T20:15:42Z","lastAt":"2009-08-13T21:28:18Z","messageCount":2,"participants":["George Spelvin","Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"120574","messageId":"20090813201542.25431.qmail@science.horizon.com","threadId":"20588","inReplyTo":null,"subject":"Re: [PATCH] block-sha1: more good unaligned memory access candidates","fromName":"George Spelvin","fromEmail":"linux@horizon.com","sentAt":"2009-08-13T20:15:42Z","receivedAt":"2009-08-13T20:15:42Z","isPatch":true,"sender":{"key":"linux@horizon.com","avatar":null},"body":"> Wow.  Is it now faster than the arm/ and ppc/ hand-tweaked assembly?\n\nIt's probably faster than the ARM, which was tuned for size rather\nthan speed, but if you want to rework the assembly for speed, the ARM's\nrotate-and-add operations allow tricks which I doubt GCC can pick up on.\n(You have to notice that the F(b,c,d) function is bitwise, so you can\ndo it on rotated data and do the rotate when you add the result to e.)\n\nI'd be surprised if it were faster than PPC code, especially on the\nin-order G3 and G4 cores where careful scheduling really pays off.\nBut maybe I just get to be surprised...\n\nFor automatic assembly tuning, I was thinking of having a .c file that\nhas a bunch of #ifdef __PPC__ statements that gets run through $(CC) -E.\nThat should be a fairly portable way to \n\n\nThe other question about unaligned access is whether it's beneficial\nto make the fetch loop work like this:\n\n\tchar const *in;\n\tuint32_t *out\n\tunsigned lsb = (unsigned)p & 3;\n\tuint32_t const *p32 = (uint32_t const *)(in - lsb);\n\tuint32_t t = ntohl(*p32);\n\n\tswitch (lsb) {\n\n\tcase 0:\n\t\t*out++ = t;\n\t\tfor (i = 1; i < 16; i++)\n\t\t\t*out++ = ntohl(*++p32);\n\t\tbreak;\n\tcase 1:\n\t\tfor (i = 0; i < 16; i++) {\n\t\t\tuint32_t s = t << 8;\n\t\t\tt = ntohl(*++p32);\n\t\t\t*out++ = s | t >> 24;\n\t\t}\n\t\tbreak;\n\tcase 1:\n\t\tfor (i = 0; i < 16; i++) {\n\t\t\tuint32_t s = t << 16;\n\t\t\tt = ntohl(*++p32);\n\t\t\t*out++ = s | t >> 16;\n\t\t}\n\t\tbreak;\n\tcase 1:\n\t\tfor (i = 0; i < 16; i++) {\n\t\t\tuint32_t s = t << 24;\n\t\t\tt = ntohl(*++p32);\n\t\t\t*out++ = s | t >> 8;\n\t\t}\n\t\tbreak;\n\t}\n\nOn the ARM, at least, ntohl() isn't particularly cheap, so loading 4\nbytes and assembling them turns out to be cheaper.  But it's a thought.\n"},{"id":"120585","messageId":"alpine.LFD.2.00.0908131651110.10633@xanadu.home","threadId":"20588","inReplyTo":"20090813201542.25431.qmail@science.horizon.com","subject":"Re: [PATCH] block-sha1: more good unaligned memory access candidates","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-08-13T21:28:18Z","receivedAt":"2009-08-13T21:28:18Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 13 Aug 2009, George Spelvin wrote:\n\n> > Wow.  Is it now faster than the arm/ and ppc/ hand-tweaked assembly?\n> \n> It's probably faster than the ARM, which was tuned for size rather\n> than speed, but if you want to rework the assembly for speed, the ARM's\n> rotate-and-add operations allow tricks which I doubt GCC can pick up on.\n> (You have to notice that the F(b,c,d) function is bitwise, so you can\n> do it on rotated data and do the rotate when you add the result to e.)\n\ngcc is not too bad at merging ALU and shift/rotate operations into the \nsame instruction.  However, to make a really optimal ARM version, some \ncustom SHA_ROUND macros with inline assembly could be made.  I suspect \nthat wouldn't gain much though, as the pure shift/rotate mov \ninstructions really aren't that many in the generated code.\n\n> I'd be surprised if it were faster than PPC code, especially on the\n> in-order G3 and G4 cores where careful scheduling really pays off.\n> But maybe I just get to be surprised...\n\nGiven that PPC has enough register to hold the entire state, it is then \nonly a matter of proper instruction scheduling which modern gcc ought to \ndo right.  If not then this is a good test case for gcc people to fix \nthe PPC machine pipeline description.\n\n> For automatic assembly tuning, I was thinking of having a .c file that\n> has a bunch of #ifdef __PPC__ statements that gets run through $(CC) -E.\n> That should be a fairly portable way to \n\n??\n\n> The other question about unaligned access is whether it's beneficial\n> to make the fetch loop work like this:\n> \n> \tchar const *in;\n> \tuint32_t *out\n> \tunsigned lsb = (unsigned)p & 3;\n> \tuint32_t const *p32 = (uint32_t const *)(in - lsb);\n> \tuint32_t t = ntohl(*p32);\n> \n> \tswitch (lsb) {\n> \n> \tcase 0:\n> \t\t*out++ = t;\n> \t\tfor (i = 1; i < 16; i++)\n> \t\t\t*out++ = ntohl(*++p32);\n> \t\tbreak;\n> \tcase 1:\n> \t\tfor (i = 0; i < 16; i++) {\n> \t\t\tuint32_t s = t << 8;\n> \t\t\tt = ntohl(*++p32);\n> \t\t\t*out++ = s | t >> 24;\n> \t\t}\n> \t\tbreak;\n> \tcase 1:\n> \t\tfor (i = 0; i < 16; i++) {\n> \t\t\tuint32_t s = t << 16;\n> \t\t\tt = ntohl(*++p32);\n> \t\t\t*out++ = s | t >> 16;\n> \t\t}\n> \t\tbreak;\n> \tcase 1:\n> \t\tfor (i = 0; i < 16; i++) {\n> \t\t\tuint32_t s = t << 24;\n> \t\t\tt = ntohl(*++p32);\n> \t\t\t*out++ = s | t >> 8;\n> \t\t}\n> \t\tbreak;\n> \t}\n> \n> On the ARM, at least, ntohl() isn't particularly cheap, so loading 4\n> bytes and assembling them turns out to be cheaper.  But it's a thought.\n\nWell, that would have to be tested.  This could possibly only be a gain \nif you have a fast ntohl() though.\n\nAnd the other question is also to decide when this is good enough for a \ngeneric version.  Gaining 5% speedup on raw SHA1 throughput with ugly \ncode might not be worth the maintenance hassle.  At that point you might \nas well go back to a purely asm version if you really want to get the \nextra edge.\n\n\nNicolas\n"}]}