{"thread":{"id":"20601","subject":"Linus' sha1 is much faster!","startedAt":"2009-08-14T23:25:36Z","lastAt":"2017-04-20T21:38:53Z","messageCount":21,"participants":["Pádraig Brady","Bryan Donlan","John Tapsell","Linus Torvalds","Theodore Tso","Giuseppe Scrivano","Nicolas Pitre","Andreas Ericsson","Steven Noonan","galt"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"120674","messageId":"4A85F270.20703@draigBrady.com","threadId":"20601","inReplyTo":null,"subject":"Linus' sha1 is much faster!","fromName":"Pádraig Brady","fromEmail":"p@draigbrady.com","sentAt":"2009-08-14T23:25:36Z","receivedAt":"2009-08-14T23:25:36Z","isPatch":false,"sender":{"key":"p@draigbrady.com","avatar":"https://gravatar.com/avatar/6d16c619bfc08087da3aa2baf6e69e438044a3dd657f0a31637d8de065ef5b27?d=mp&s=160"},"body":"I've noticed before that coreutils hashing utils\nwere a little behind in performance, but was prompted\nto look at it again when I noticed the recently\nupdated sha1 implementation in git:\nhttp://git.kernel.org/?p=git/git.git;a=history;f=block-sha1;h=d3121f7;hb=pu\n\nTesting that with the attached program which I wrote\nin a couple of mins to try and match sha1sum's system calls\nshows that it's around 33% faster, as shown below:\n\n$ gcc $(rpm -q --qf=\"%{OPTFLAGS}\\n\" coreutils) linus-sha1.c sha1.c -o linus-sha1\n\n$ time ./linus-sha1 300MB_file\ndf1e19e245fee4f53087b50ef953ca2c8d1644d7 300MB_file\nreal 0m2.742s\nuser 0m2.516s\nsys 0m0.206s\n\n$ time ~/git/coreutils/src/sha1sum 300MB_file\ndf1e19e245fee4f53087b50ef953ca2c8d1644d7 300MB_file\n\nreal 0m4.166s\nuser 0m3.846s\nsys 0m0.298s\n\nSo, could we use that code in coreutils?\nThink of all the dead fish it would save.\n\nI've also attached a trivial block-sha1 patch which doesn't\naffect performance, but does suppress a signed unsigned\ncomparison warning which occurs with -Wextra for example.\n\ncheers,\nPádraig.\n\n\n/* gcc -O2 -Wall linus-sha1.c sha1.c -o linus-sha1 */\n#include \n#include \n#include \"sha1.h\"\n\nint main(int argc, char** argv)\n{\n if (argc != 2) return 1;\n const char* filename = argv[1];\n FILE *fp = fopen (filename, \"r\");\n if (!fp) return 1;\n\n #define BS 4096 /* match coreutils */\n\n blk_SHA_CTX ctx;\n blk_SHA1_Init(&ctx);\n size_t nr;\n char buf[BS];\n while ((nr=fread_unlocked(buf, 1, sizeof(buf), fp)))\n blk_SHA1_Update(&ctx, buf, nr);\n unsigned char hash[20];\n blk_SHA1_Final(hash, &ctx);\n int i;\n for (i=0; iFrom fa75e818836f763357ff9b7bbde3327e1aabbe47 Mon Sep 17 00:00:00 2001\nFrom: =?utf-8?q?P=C3=A1draig=20Brady?= \nDate: Sat, 15 Aug 2009 00:17:30 +0100\nSubject: [PATCH] block-sha1: suppress signed unsigned comparison warning\n\n* block-sha1/sha1.c: Use unsigned ints as the values\nwill never go negative.\n---\n block-sha1/sha1.c | 4 ++--\n 1 files changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/block-sha1/sha1.c b/block-sha1/sha1.c\nindex d3121f7..be763d8 100644\n--- a/block-sha1/sha1.c\n+++ b/block-sha1/sha1.c\n@@ -231,13 +231,13 @@ void blk_SHA1_Init(blk_SHA_CTX *ctx)\n \n void blk_SHA1_Update(blk_SHA_CTX *ctx, const void *data, unsigned long len)\n {\n-\tint lenW = ctx->size & 63;\n+\tunsigned int lenW = ctx->size & 63;\n \n \tctx->size += len;\n \n \t/* Read the data into W and process blocks as they get full */\n \tif (lenW) {\n-\t\tint left = 64 - lenW;\n+\t\tunsigned int left = 64 - lenW;\n \t\tif (len < left)\n \t\t\tleft = len;\n \t\tmemcpy(lenW + (char *)ctx->W, data, left);\n-- \n1.6.2.5\n\n"},{"id":"120729","messageId":"3e8340490908151302y33a97d50t38ad0a8a788f1cee@mail.gmail.com","threadId":"20601","inReplyTo":"4A85F270.20703@draigBrady.com","subject":"Re: Linus' sha1 is much faster!","fromName":"Bryan Donlan","fromEmail":"bdonlan@gmail.com","sentAt":"2009-08-15T20:02:12Z","receivedAt":"2009-08-15T20:02:12Z","isPatch":false,"sender":{"key":"bdonlan@gmail.com","avatar":null},"body":"2009/8/14 Pádraig Brady :\n> I've noticed before that coreutils hashing utils\n> were a little behind in performance, but was prompted\n> to look at it again when I noticed the recently\n> updated sha1 implementation in git:\n> http://git.kernel.org/?p=git/git.git;a=history;f=block-sha1;h=d3121f7;hb=pu\n>\n> Testing that with the attached program which I wrote\n> in a couple of mins to try and match sha1sum's system calls\n> shows that it's around 33% faster, as shown below:\n>\n> $ gcc $(rpm -q --qf=\"%{OPTFLAGS}\\n\" coreutils) linus-sha1.c sha1.c -o linus-sha1\n>\n> $ time ./linus-sha1 300MB_file\n> df1e19e245fee4f53087b50ef953ca2c8d1644d7  300MB_file\n> real    0m2.742s\n> user    0m2.516s\n> sys     0m0.206s\n>\n> $ time ~/git/coreutils/src/sha1sum 300MB_file\n> df1e19e245fee4f53087b50ef953ca2c8d1644d7  300MB_file\n>\n> real    0m4.166s\n> user    0m3.846s\n> sys     0m0.298s\n>\n> So, could we use that code in coreutils?\n> Think of all the dead fish it would save.\n\ncoreutils is licensed under GPLv3, and git under GPLv2 (only), so\nyou'd need permission from all contributors to the implementation in\norder to relicense under GPLv3. A quick grep of the history suggests\nthese contributors to be:\n\nBrandon Casey \nJunio C Hamano \nLinus Torvalds \nNicolas Pitre \n(adding these people to the CC list)\n\nAdditionally, it was originally based on the code in\nmozilla-sha1/sha1.c, but that contains a license grant allowing it to\nbe used under GPLv2 /or later/, so if GPLv3 relicensing is enough it\nshouldn't be necessary to get in contact with the original author.\nHowever if the FSF requires copyright assignment to accept the new\nimplementation, it will be necessary to track down contributors to the\noriginal mozilla-sha1/sha1.c as well.\n\nNote that I'm not a lawyer, so there might be other roadblocks etc to\nthis as well, etc :)\n"},{"id":"120730","messageId":"43d8ce650908151312o6a43416el27965c4b0ab8d83d@mail.gmail.com","threadId":"20601","inReplyTo":"3e8340490908151302y33a97d50t38ad0a8a788f1cee@mail.gmail.com","subject":"Re: Linus' sha1 is much faster!","fromName":"John Tapsell","fromEmail":"johnflux@gmail.com","sentAt":"2009-08-15T20:12:58Z","receivedAt":"2009-08-15T20:12:58Z","isPatch":false,"sender":{"key":"johnflux@gmail.com","avatar":"https://gravatar.com/avatar/25f70d4c0f96396b84a2e34bcd9bdc233462c7b4be29b5fdca8266fc53f30b0c?d=mp&s=160"},"body":"2009/8/15 Bryan Donlan :\n> coreutils is licensed under GPLv3, and git under GPLv2 (only), so\n> you'd need permission from all contributors to the implementation in\n> order to relicense under GPLv3. A quick grep of the history suggests\n> these contributors to be:\n\n\nX11 also requires a fast SHA1 implementation. It uses this to check\nif two pixmaps are the same. So it would be really nice to relicense\nunder a liberal enough license that xorg can use it.\n\nJohn\n"},{"id":"120733","messageId":"alpine.LFD.2.01.0908151315400.3162@localhost.localdomain","threadId":"20601","inReplyTo":"43d8ce650908151312o6a43416el27965c4b0ab8d83d@mail.gmail.com","subject":"Re: Linus' sha1 is much faster!","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-15T20:23:41Z","receivedAt":"2009-08-15T20:23:41Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 15 Aug 2009, John Tapsell wrote:\n\n> 2009/8/15 Bryan Donlan :\n> > coreutils is licensed under GPLv3, and git under GPLv2 (only), so\n> > you'd need permission from all contributors to the implementation in\n> > order to relicense under GPLv3. A quick grep of the history suggests\n> > these contributors to be:\n> \n> X11 also requires a fast SHA1 implementation. It uses this to check\n> if two pixmaps are the same. So it would be really nice to relicense\n> under a liberal enough license that xorg can use it.\n\nI'm personally ok with retaining the mozilla-sha1 license.\n\nThere's not really anything _remaining_ of the mozilla code, but hey, I \nstarted from it. In retrospect I probably should have started from the PPC \nasm code that already did the blocking sanely - but that's a \"20/20 \nhindsight\" kind of thing.\n\nPlus hey, the mozilla code being a horrid pile of crud was why I was so \nconvinced that I could improve on things. So that's a kind of source for \nit, even if it's more about the motivational side than any actual \nremaining code ;)\n\nThat said, I don't know if the MPL is ok for X11. I've not looked at \ncompatibility issues with MPL. For git, we could just ignore the MPL, \nsince the GPLv2 was acceptable regardless of it.\n\n\t\t\tLinus\n"},{"id":"120735","messageId":"alpine.LFD.2.01.0908151336530.3162@localhost.localdomain","threadId":"20601","inReplyTo":"alpine.LFD.2.01.0908151315400.3162@localhost.localdomain","subject":"Re: Linus' sha1 is much faster!","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-15T20:54:23Z","receivedAt":"2009-08-15T20:54:23Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 15 Aug 2009, Linus Torvalds wrote:\n> \n> That said, I don't know if the MPL is ok for X11. I've not looked at \n> compatibility issues with MPL. For git, we could just ignore the MPL, \n> since the GPLv2 was acceptable regardless of it.\n\nIf MPL isn't ok for X11, then we'd need to make sure that even the \nsilliest Mozilla crud has been rewritten. There really isn't much, but \nhey, the _history_ is based on the mozilla code, and who knows - the \n'blk_SHA_CTX' struct has things like the fields in the same order as the \nMozilla equivalent, for all those historical reasons.\n\n(Heh. Looking at that, I probably should move the 'size' field first, \nsince that would have different alignment rules, and the struct would be \nmore tightly packed that way, and initialize better).\n\nAfaik, none of the actual code remains (the mozilla SHA1 thing did the \nwrong thing for performance even for just the final bytes, and did those a \nbyte at a time etc, so I rewrote even the trivial SHA1_Final parts).\n\nOf course, maybe the Mozilla people would be interested in taking my \nfaster version, and say that the new-BSD license is ok, and make everybody \nhappy. The only listed author for the Mozilla SHA1 is Paul Kocher. I added \nhim to the Cc.\n\nPaul, for your information, we're talking about a faster rewritten \"mostly \nportable\" SHA1 routines that you can find at\n\n\thttp://git.kernel.org/?p=git/git.git;a=tree;f=block-sha1;hb=pu\n\n(follow the \"blob\" pointers to see sha1.c and sha1.h). I don't know if \nyou're active with Mozilla/Firefox or whether you even care, but you seem \nto be the logical choice of person to ask.\n\n\t\t\tLinus\n"},{"id":"120752","messageId":"20090816000640.GA7554@mit.edu","threadId":"20601","inReplyTo":"43d8ce650908151312o6a43416el27965c4b0ab8d83d@mail.gmail.com","subject":"Re: Linus' sha1 is much faster!","fromName":"Theodore Tso","fromEmail":"tytso@mit.edu","sentAt":"2009-08-16T00:06:40Z","receivedAt":"2009-08-16T00:06:40Z","isPatch":false,"sender":{"key":"tytso@mit.edu","avatar":"https://avatars.githubusercontent.com/u/51416?v=4"},"body":"On Sat, Aug 15, 2009 at 09:12:58PM +0100, John Tapsell wrote:\n> 2009/8/15 Bryan Donlan :\n> > coreutils is licensed under GPLv3, and git under GPLv2 (only), so\n> > you'd need permission from all contributors to the implementation in\n> > order to relicense under GPLv3. A quick grep of the history suggests\n> > these contributors to be:\n> \n> X11 also requires a fast SHA1 implementation. It uses this to check\n> if two pixmaps are the same. So it would be really nice to relicense\n> under a liberal enough license that xorg can use it.\n\nIf the checksum isn't being exposed in the protocol (i.e., it's just\ninternal to the X server), one possibility for X11 is to consider to\nuse the SHA-3 candidate Skein instead. After receiving a large amount\nof evaluation by cryptographic experts, it was one of the 18\nalgorithms (our of an original 64 entries) that have made it the 2nd\nround of the NIST competition. It's also *substantially* faster than\nSHA:\n\n One exception to this is Skein, created by several well-known\n cryptographers and noted pundit Bruce Schneier. It was designed\n specifically to exploit all three of the Core 2 execution units\n and to run at a full 64-bits. This gives it roughly four to 10\n times the logic density of competing submissions.\n\n This is what I meant by the Matrix quote above. They didn't bend\n the spoon; they bent the crypto algorithm. They moved the logic\n operations around in a way that wouldn't weaken the crypto, but\n would strengthen its speed on the Intel Core 2.\n\n In their paper (PDF), the authors of Skein express surprise that a\n custom silicon ASIC implementation is not any faster than the\n software implementation. They shouldn't be surprised. Every time\n you can redefine a problem to run optimally in software, you will\n reach the same speeds you get with optimized ASIC hardware. The\n reason software has a reputation of being slow is because people\n don't redefine the original problem.\n\n http://www.darkreading.com/blog/archives/2008/11/bending_skein_c.html\n\nFor more information and some optimized implementation, see:\n\n\thttp://www.skein-hash.info/\n\n\t\t\t\t\t\t\t- Ted\n"},{"id":"120775","messageId":"87eirbef3c.fsf@master.homenet","threadId":"20601","inReplyTo":"4A85F270.20703@draigBrady.com","subject":"Re: Linus' sha1 is much faster!","fromName":"Giuseppe Scrivano","fromEmail":"gscrivano@gnu.org","sentAt":"2009-08-16T19:25:11Z","receivedAt":"2009-08-16T19:25:11Z","isPatch":false,"sender":{"key":"gscrivano@gnu.org","avatar":"https://avatars.githubusercontent.com/u/67430?v=4"},"body":"Hi Pádraig,\n\nI tried to reproduce your results but I wasn't able to do it. The\nbiggest difference on a 300MB file I noticed was approximately 15% using\non both implementations -O2, and 5% using -O3.\nMy GCC version is \"gcc (Debian 4.3.3-14) 4.3.3\" and the CPU is: Intel(R)\nPentium(R) D CPU 3.20GHz.\n\nI also spent some time trying to improve the gnulib SHA1 implementation\nand it seems a lookup table can improve things a bit.\n\nCan you please try the patch that I have attached and tell me which\nperformance difference (if any) you get?\n\nThanks,\nGiuseppe\n\n\n\n\n>From b975a5e0849eaa46e5cf410c5bf6e2308f044d61 Mon Sep 17 00:00:00 2001\nFrom: Giuseppe Scrivano \nDate: Sun, 16 Aug 2009 20:53:54 +0200\nSubject: [PATCH] SHA1: use a lookup table for faster hashing\n\n* lib/sha1.c (struct sha1_pre): New member.\n* lib/sha1.c (sha1_process_block): Use the lookup table to quickly find\nindices to use in the current round.\n---\n lib/sha1.c | 160 ++++++++++++++++++++++++++++++++++-------------------------\n 1 files changed, 92 insertions(+), 68 deletions(-)\n\ndiff --git a/lib/sha1.c b/lib/sha1.c\nindex 9c6c7ae..ec18ba7 100644\n--- a/lib/sha1.c\n+++ b/lib/sha1.c\n@@ -283,6 +283,32 @@ sha1_process_bytes (const void *buffer, size_t len, struct sha1_ctx *ctx)\n #define F3(B,C,D) ( ( B & C ) | ( D & ( B | C ) ) )\n #define F4(B,C,D) (B ^ C ^ D)\n \n+struct lookup_t\n+{\n+ unsigned char l1 : 4;\n+ unsigned char l2 : 4;\n+ unsigned char l3 : 4;\n+ unsigned char l4 : 4;\n+};\n+\n+const static struct lookup_t\n+sha1_pre[16] = {{(0 - 3) & 0x0f, (0 - 8) & 0x0f, (0 - 14) & 0x0f},\n+ {(1 - 3) & 0x0f, (1 - 8) & 0x0f, (1 - 14) & 0x0f},\n+ {(2 - 3) & 0x0f, (2 - 8) & 0x0f, (2 - 14) & 0x0f},\n+ {(3 - 3) & 0x0f, (3 - 8) & 0x0f, (3 - 14) & 0x0f},\n+ {(4 - 3) & 0x0f, (4 - 8) & 0x0f, (4 - 14) & 0x0f},\n+ {(5 - 3) & 0x0f, (5 - 8) & 0x0f, (5 - 14) & 0x0f},\n+ {(6 - 3) & 0x0f, (6 - 8) & 0x0f, (6 - 14) & 0x0f},\n+ {(7 - 3) & 0x0f, (7 - 8) & 0x0f, (7 - 14) & 0x0f},\n+ {(8 - 3) & 0x0f, (8 - 8) & 0x0f, (8 - 14) & 0x0f},\n+ {(9 - 3) & 0x0f, (9 - 8) & 0x0f, (9 - 14) & 0x0f},\n+ {(10 - 3) & 0x0f, (10 - 8) & 0x0f, (10 - 14) & 0x0f},\n+ {(11 - 3) & 0x0f, (11 - 8) & 0x0f, (11 - 14) & 0x0f},\n+ {(12 - 3) & 0x0f, (12 - 8) & 0x0f, (12 - 14) & 0x0f},\n+ {(13 - 3) & 0x0f, (13 - 8) & 0x0f, (13 - 14) & 0x0f},\n+ {(14 - 3) & 0x0f, (14 - 8) & 0x0f, (14 - 14) & 0x0f},\n+ {(15 - 3) & 0x0f, (15 - 8) & 0x0f, (15 - 14) & 0x0f}};\n+\n /* Process LEN bytes of BUFFER, accumulating context into CTX.\n It is assumed that LEN % 64 == 0.\n Most of this code comes from GnuPG's cipher/sha1.c. */\n@@ -309,9 +335,8 @@ sha1_process_block (const void *buffer, size_t len, struct sha1_ctx *ctx)\n \n #define rol(x, n) (((x) << (n)) | ((uint32_t) (x) >> (32 - (n))))\n \n-#define M(I) ( tm = x[I&0x0f] ^ x[(I-14)&0x0f] \\\n-\t\t ^ x[(I-8)&0x0f] ^ x[(I-3)&0x0f] \\\n-\t , (x[I&0x0f] = rol(tm, 1)) )\n+#define M(I) (x[I] = rol (x[sha1_pre[I].l1] ^ x[sha1_pre[I].l2] \\\n+ ^ x[sha1_pre[I].l3] ^ x[I], 1))\n \n #define R(A,B,C,D,E,F,K,M) do { E += rol( A, 5 ) \\\n \t\t\t\t + F( B, C, D ) \\\n@@ -322,7 +347,6 @@ sha1_process_block (const void *buffer, size_t len, struct sha1_ctx *ctx)\n \n while (words < endp)\n {\n- uint32_t tm;\n int t;\n for (t = 0; t < 16; t++)\n \t{\n@@ -346,70 +370,70 @@ sha1_process_block (const void *buffer, size_t len, struct sha1_ctx *ctx)\n R( c, d, e, a, b, F1, K1, x[13] );\n R( b, c, d, e, a, F1, K1, x[14] );\n R( a, b, c, d, e, F1, K1, x[15] );\n- R( e, a, b, c, d, F1, K1, M(16) );\n- R( d, e, a, b, c, F1, K1, M(17) );\n- R( c, d, e, a, b, F1, K1, M(18) );\n- R( b, c, d, e, a, F1, K1, M(19) );\n- R( a, b, c, d, e, F2, K2, M(20) );\n- R( e, a, b, c, d, F2, K2, M(21) );\n- R( d, e, a, b, c, F2, K2, M(22) );\n- R( c, d, e, a, b, F2, K2, M(23) );\n- R( b, c, d, e, a, F2, K2, M(24) );\n- R( a, b, c, d, e, F2, K2, M(25) );\n- R( e, a, b, c, d, F2, K2, M(26) );\n- R( d, e, a, b, c, F2, K2, M(27) );\n- R( c, d, e, a, b, F2, K2, M(28) );\n- R( b, c, d, e, a, F2, K2, M(29) );\n- R( a, b, c, d, e, F2, K2, M(30) );\n- R( e, a, b, c, d, F2, K2, M(31) );\n- R( d, e, a, b, c, F2, K2, M(32) );\n- R( c, d, e, a, b, F2, K2, M(33) );\n- R( b, c, d, e, a, F2, K2, M(34) );\n- R( a, b, c, d, e, F2, K2, M(35) );\n- R( e, a, b, c, d, F2, K2, M(36) );\n- R( d, e, a, b, c, F2, K2, M(37) );\n- R( c, d, e, a, b, F2, K2, M(38) );\n- R( b, c, d, e, a, F2, K2, M(39) );\n- R( a, b, c, d, e, F3, K3, M(40) );\n- R( e, a, b, c, d, F3, K3, M(41) );\n- R( d, e, a, b, c, F3, K3, M(42) );\n- R( c, d, e, a, b, F3, K3, M(43) );\n- R( b, c, d, e, a, F3, K3, M(44) );\n- R( a, b, c, d, e, F3, K3, M(45) );\n- R( e, a, b, c, d, F3, K3, M(46) );\n- R( d, e, a, b, c, F3, K3, M(47) );\n- R( c, d, e, a, b, F3, K3, M(48) );\n- R( b, c, d, e, a, F3, K3, M(49) );\n- R( a, b, c, d, e, F3, K3, M(50) );\n- R( e, a, b, c, d, F3, K3, M(51) );\n- R( d, e, a, b, c, F3, K3, M(52) );\n- R( c, d, e, a, b, F3, K3, M(53) );\n- R( b, c, d, e, a, F3, K3, M(54) );\n- R( a, b, c, d, e, F3, K3, M(55) );\n- R( e, a, b, c, d, F3, K3, M(56) );\n- R( d, e, a, b, c, F3, K3, M(57) );\n- R( c, d, e, a, b, F3, K3, M(58) );\n- R( b, c, d, e, a, F3, K3, M(59) );\n- R( a, b, c, d, e, F4, K4, M(60) );\n- R( e, a, b, c, d, F4, K4, M(61) );\n- R( d, e, a, b, c, F4, K4, M(62) );\n- R( c, d, e, a, b, F4, K4, M(63) );\n- R( b, c, d, e, a, F4, K4, M(64) );\n- R( a, b, c, d, e, F4, K4, M(65) );\n- R( e, a, b, c, d, F4, K4, M(66) );\n- R( d, e, a, b, c, F4, K4, M(67) );\n- R( c, d, e, a, b, F4, K4, M(68) );\n- R( b, c, d, e, a, F4, K4, M(69) );\n- R( a, b, c, d, e, F4, K4, M(70) );\n- R( e, a, b, c, d, F4, K4, M(71) );\n- R( d, e, a, b, c, F4, K4, M(72) );\n- R( c, d, e, a, b, F4, K4, M(73) );\n- R( b, c, d, e, a, F4, K4, M(74) );\n- R( a, b, c, d, e, F4, K4, M(75) );\n- R( e, a, b, c, d, F4, K4, M(76) );\n- R( d, e, a, b, c, F4, K4, M(77) );\n- R( c, d, e, a, b, F4, K4, M(78) );\n- R( b, c, d, e, a, F4, K4, M(79) );\n+ R( e, a, b, c, d, F1, K1, M( 0) );\n+ R( d, e, a, b, c, F1, K1, M( 1) );\n+ R( c, d, e, a, b, F1, K1, M( 2) );\n+ R( b, c, d, e, a, F1, K1, M( 3) );\n+ R( a, b, c, d, e, F2, K2, M( 4) );\n+ R( e, a, b, c, d, F2, K2, M( 5) );\n+ R( d, e, a, b, c, F2, K2, M( 6) );\n+ R( c, d, e, a, b, F2, K2, M( 7) );\n+ R( b, c, d, e, a, F2, K2, M( 8) );\n+ R( a, b, c, d, e, F2, K2, M( 9) );\n+ R( e, a, b, c, d, F2, K2, M(10) );\n+ R( d, e, a, b, c, F2, K2, M(11) );\n+ R( c, d, e, a, b, F2, K2, M(12) );\n+ R( b, c, d, e, a, F2, K2, M(13) );\n+ R( a, b, c, d, e, F2, K2, M(14) );\n+ R( e, a, b, c, d, F2, K2, M(15) );\n+ R( d, e, a, b, c, F2, K2, M( 0) );\n+ R( c, d, e, a, b, F2, K2, M( 1) );\n+ R( b, c, d, e, a, F2, K2, M( 2) );\n+ R( a, b, c, d, e, F2, K2, M( 3) );\n+ R( e, a, b, c, d, F2, K2, M( 4) );\n+ R( d, e, a, b, c, F2, K2, M( 5) );\n+ R( c, d, e, a, b, F2, K2, M( 6) );\n+ R( b, c, d, e, a, F2, K2, M( 7) );\n+ R( a, b, c, d, e, F3, K3, M( 8) );\n+ R( e, a, b, c, d, F3, K3, M( 9) );\n+ R( d, e, a, b, c, F3, K3, M(10) );\n+ R( c, d, e, a, b, F3, K3, M(11) );\n+ R( b, c, d, e, a, F3, K3, M(12) );\n+ R( a, b, c, d, e, F3, K3, M(13) );\n+ R( e, a, b, c, d, F3, K3, M(14) );\n+ R( d, e, a, b, c, F3, K3, M(15) );\n+ R( c, d, e, a, b, F3, K3, M( 0) );\n+ R( b, c, d, e, a, F3, K3, M( 1) );\n+ R( a, b, c, d, e, F3, K3, M( 2) );\n+ R( e, a, b, c, d, F3, K3, M( 3) );\n+ R( d, e, a, b, c, F3, K3, M( 4) );\n+ R( c, d, e, a, b, F3, K3, M( 5) );\n+ R( b, c, d, e, a, F3, K3, M( 6) );\n+ R( a, b, c, d, e, F3, K3, M( 7) );\n+ R( e, a, b, c, d, F3, K3, M( 8) );\n+ R( d, e, a, b, c, F3, K3, M( 9) );\n+ R( c, d, e, a, b, F3, K3, M(10) );\n+ R( b, c, d, e, a, F3, K3, M(11) );\n+ R( a, b, c, d, e, F4, K4, M(12) );\n+ R( e, a, b, c, d, F4, K4, M(13) );\n+ R( d, e, a, b, c, F4, K4, M(14) );\n+ R( c, d, e, a, b, F4, K4, M(15) );\n+ R( b, c, d, e, a, F4, K4, M( 0) );\n+ R( a, b, c, d, e, F4, K4, M( 1) );\n+ R( e, a, b, c, d, F4, K4, M( 2) );\n+ R( d, e, a, b, c, F4, K4, M( 3) );\n+ R( c, d, e, a, b, F4, K4, M( 4) );\n+ R( b, c, d, e, a, F4, K4, M( 5) );\n+ R( a, b, c, d, e, F4, K4, M( 6) );\n+ R( e, a, b, c, d, F4, K4, M( 7) );\n+ R( d, e, a, b, c, F4, K4, M( 8) );\n+ R( c, d, e, a, b, F4, K4, M( 9) );\n+ R( b, c, d, e, a, F4, K4, M(10) );\n+ R( a, b, c, d, e, F4, K4, M(11) );\n+ R( e, a, b, c, d, F4, K4, M(12) );\n+ R( d, e, a, b, c, F4, K4, M(13) );\n+ R( c, d, e, a, b, F4, K4, M(14) );\n+ R( b, c, d, e, a, F4, K4, M(15) );\n \n a = ctx->A += a;\n b = ctx->B += b;\n-- \n1.6.3.3\n\n"},{"id":"120778","messageId":"alpine.LFD.2.01.0908161306340.3162@localhost.localdomain","threadId":"20601","inReplyTo":"87eirbef3c.fsf@master.homenet","subject":"Re: Linus' sha1 is much faster!","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-16T20:10:20Z","receivedAt":"2009-08-16T20:10:20Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 16 Aug 2009, Giuseppe Scrivano wrote:\n> \n> My GCC version is \"gcc (Debian 4.3.3-14) 4.3.3\" and the CPU is: Intel(R)\n> Pentium(R) D CPU 3.20GHz.\n\nNetburst is very sensitive to random spill effects, and you can basically \ntune things by just code shuffling that just has random effects on the \ngenerated asm code.\n\n> I also spent some time trying to improve the gnulib SHA1 implementation\n> and it seems a lookup table can improve things a bit.\n\nI pretty much can guarantee you that it improves things only because it \nmakes gcc generate crap code, which then hides some of the P4 issues.\n\nI'd also suggest you try gcc-4.4, since that apparently fixes some of the \noddest spill issues.\n\n\t\t\tLinus\n"},{"id":"120791","messageId":"87ab1ze76y.fsf@master.homenet","threadId":"20601","inReplyTo":"alpine.LFD.2.01.0908161306340.3162@localhost.localdomain","subject":"Re: Linus' sha1 is much faster!","fromName":"Giuseppe Scrivano","fromEmail":"gscrivano@gnu.org","sentAt":"2009-08-16T22:15:49Z","receivedAt":"2009-08-16T22:15:49Z","isPatch":false,"sender":{"key":"gscrivano@gnu.org","avatar":"https://avatars.githubusercontent.com/u/67430?v=4"},"body":"Linus Torvalds writes:\n\n> I pretty much can guarantee you that it improves things only because it \n> makes gcc generate crap code, which then hides some of the P4 issues.\n>\n> I'd also suggest you try gcc-4.4, since that apparently fixes some of the \n> oddest spill issues.\n\n\nThanks for the hint. I tried gcc-4.4 and it produces slower code than\n4.3 on the gnulib SHA1 implementation and my patch makes it even more!\n\nI noticed that on my machine your implementation is ~30-40% faster using\nSHA_ROT for rol/ror instructions than inline assembly, at least with the\ntest-case Pádraig wrote. Am I the only one reporting it?\n\nCheers,\nGiuseppe\n"},{"id":"120799","messageId":"alpine.LFD.2.01.0908161539300.3162@localhost.localdomain","threadId":"20601","inReplyTo":"87ab1ze76y.fsf@master.homenet","subject":"Re: Linus' sha1 is much faster!","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-16T22:47:08Z","receivedAt":"2009-08-16T22:47:08Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 17 Aug 2009, Giuseppe Scrivano wrote:\n> \n> Thanks for the hint. I tried gcc-4.4 and it produces slower code than\n> 4.3 on the gnulib SHA1 implementation and my patch makes it even more!\n\nCheck out the asm, see if you can see why. One of the most common problems \nwith P4's is literally that you end up loading from the same stack slot \nthat you just stored to (gcc can do some really crazy spills), and that \ncauses a store buffer hazard replay.\n\nMy personal opinion is that Netburst is useless for trying to optimize C \ncode for. It's just too random.\n\n> I noticed that on my machine your implementation is ~30-40% faster using\n> SHA_ROT for rol/ror instructions than inline assembly, at least with the\n> test-case Pádraig wrote. Am I the only one reporting it?\n\nI bet it's the same thing. Small perturbations of the source causing small \nchanges to register allocation and thus spilling, and then Netburst goes \ncrazy one way or another. It's interestign trying to fix it, and very \nfrustrating.\n\nMy workstation is a Nehalem (but Core 2 will have pretty much the same \nbehavior), and it doesn't have the crazy netburst behavior. Shorter and \nsimpler code generally performs better (which is _not_ true on Netburst). \n\nOn my machine, for example, forcing gcc to do those rotates on registers \nis the difference between ~381MB/s and 415MB/s. And that's mainly because \nit makes gcc keep A-E in registers, rather than trying to cache the \narray[] references.\n\n\t\t\tLinus\n"},{"id":"120812","messageId":"4A88B80D.40804@draigBrady.com","threadId":"20601","inReplyTo":"87eirbef3c.fsf@master.homenet","subject":"Re: Linus' sha1 is much faster!","fromName":"Pádraig Brady","fromEmail":"p@draigbrady.com","sentAt":"2009-08-17T01:53:17Z","receivedAt":"2009-08-17T01:53:17Z","isPatch":false,"sender":{"key":"p@draigbrady.com","avatar":"https://gravatar.com/avatar/6d16c619bfc08087da3aa2baf6e69e438044a3dd657f0a31637d8de065ef5b27?d=mp&s=160"},"body":"Giuseppe Scrivano wrote:\n> Hi Pádraig,\n> \n> I tried to reproduce your results but I wasn't able to do it. The\n> biggest difference on a 300MB file I noticed was approximately 15% using\n> on both implementations -O2, and 5% using -O3.\n> My GCC version is \"gcc (Debian 4.3.3-14) 4.3.3\" and the CPU is: Intel(R)\n> Pentium(R) D CPU 3.20GHz.\n> \n> I also spent some time trying to improve the gnulib SHA1 implementation\n> and it seems a lookup table can improve things a bit.\n> \n> Can you please try the patch that I have attached and tell me which\n> performance difference (if any) you get?\n\nThanks for looking at this Giuseppe\nand sorry for not mentioning my GCC and CPU.\n\nNote the binaries below is compiled with\n$(rpm -q --qf=\"%{OPTFLAGS}\\n\" coreutils)\nfor consistency, which on my F11 machines is:\n\n -O2 -g -pipe -Wall -Wp,-D_FORTIFY_SOURCE=2 -fexceptions\n -fstack-protector --param=ssp-buffer-size=4 -m32 -march=i586\n -mtune=generic -fasynchronous-unwind-tables -D_GNU_SOURCE=1\n\nTesting on 2 machines I have here:\n\n$ rpm -q gcc\ngcc-4.4.1-2.fc11.i586\n$ grep \"model name\" /proc/cpuinfo | head -n1 | tr -s '[:blank:]' ' '\nmodel name : Intel(R) Pentium(R) M processor 1.70GHz\n$ truncate -s300MB sha1.test\n$ time sha1sum sha1.test\nreal 0m3.540s\n$ time linus-sha1 sha1.test\nreal 0m2.319s (-34%)\n$ time giuseppe-sha1sum sha1.test\nreal 0m3.513s (-.8%)\n\n$ rpm -q gcc\ngcc-4.4.1-2.fc11.i586\n$ grep \"model name\" /proc/cpuinfo | head -n1 | tr -s '[:blank:]' ' '\nmodel name : Intel(R) Core(TM) i7 CPU 920 @ 2.67GHz\n$ truncate -s300MB sha1.test\n$ time sha1sum sha1.test\nreal 0m1.857s\n$ time linus-sha1 sha1.test\nreal 0m1.102s (-40%)\n$ time giuseppe-sha1sum sha1.test\nreal 0m1.932s (+ 4%)\n\ncheers,\nPádraig.\n"},{"id":"120811","messageId":"alpine.LFD.2.00.0908162151180.6044@xanadu.home","threadId":"20601","inReplyTo":"alpine.LFD.2.01.0908151336530.3162@localhost.localdomain","subject":"Re: Linus' sha1 is much faster!","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-08-17T01:55:39Z","receivedAt":"2009-08-17T01:55:39Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 15 Aug 2009, Linus Torvalds wrote:\n\n> (Heh. Looking at that, I probably should move the 'size' field first, \n> since that would have different alignment rules, and the struct would be \n> more tightly packed that way, and initialize better).\n\nI was about to suggest (i.e. post) a patch for that. This is indeed a \ngood idea.\n\n> Afaik, none of the actual code remains (the mozilla SHA1 thing did the \n> wrong thing for performance even for just the final bytes, and did those a \n> byte at a time etc, so I rewrote even the trivial SHA1_Final parts).\n\nMaybe a patch adding a proper header with the actual license would be a \ngood idea too.\n\n\nNicolas\n"},{"id":"120847","messageId":"4A891348.5030203@op5.se","threadId":"20601","inReplyTo":"alpine.LFD.2.01.0908151336530.3162@localhost.localdomain","subject":"Re: Linus' sha1 is much faster!","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2009-08-17T08:22:32Z","receivedAt":"2009-08-17T08:22:32Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Linus Torvalds wrote:\n> \n> On Sat, 15 Aug 2009, Linus Torvalds wrote:\n>> That said, I don't know if the MPL is ok for X11. I've not looked at \n>> compatibility issues with MPL. For git, we could just ignore the MPL, \n>> since the GPLv2 was acceptable regardless of it.\n> \n> If MPL isn't ok for X11, then we'd need to make sure that even the \n> silliest Mozilla crud has been rewritten. There really isn't much, but \n> hey, the _history_ is based on the mozilla code, and who knows - the \n> 'blk_SHA_CTX' struct has things like the fields in the same order as the \n> Mozilla equivalent, for all those historical reasons.\n> \n> (Heh. Looking at that, I probably should move the 'size' field first, \n> since that would have different alignment rules, and the struct would be \n> more tightly packed that way, and initialize better).\n> \n> Afaik, none of the actual code remains (the mozilla SHA1 thing did the \n> wrong thing for performance even for just the final bytes, and did those a \n> byte at a time etc, so I rewrote even the trivial SHA1_Final parts).\n> \n> Of course, maybe the Mozilla people would be interested in taking my \n> faster version, and say that the new-BSD license is ok, and make everybody \n> happy. The only listed author for the Mozilla SHA1 is Paul Kocher. I added \n> him to the Cc.\n> \n> Paul, for your information, we're talking about a faster rewritten \"mostly \n> portable\" SHA1 routines that you can find at\n> \n> \thttp://git.kernel.org/?p=git/git.git;a=tree;f=block-sha1;hb=pu\n> \n> (follow the \"blob\" pointers to see sha1.c and sha1.h). I don't know if \n> you're active with Mozilla/Firefox or whether you even care, but you seem \n> to be the logical choice of person to ask.\n> \n\nI contacted Paul in february this year to get permission to use the mozilla\nsha1 code for libgit2. His reply then was:\n\"I'm not sure which version the diffs are relative to, so I haven't reviewed them.\nIt's fine to distribute under BSD, GPL, or LGPL, however.\"\n\nI also got explicit permission to relicense it under GPLv2 with the gcc exception.\n\nI added the mail-address I used to contact him to CC as well. Sorry if you get\nthis twice, Paul.\n\nNaturally, I'd like to use the faster version for libgit2 as well. The people\nwho Linus listed as contributors earlier (Brandon Casy, Linus, Junio and Nicolas\nPitre) have already consented to relicense their git contributions for libgit2\nuse. If anyone would like to revoke that consent for this code, speak now please,\nor I'll patch it into libgit2 as well.\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":"120863","messageId":"8763cmemsa.fsf@master.homenet","threadId":"20601","inReplyTo":"4A88B80D.40804@draigBrady.com","subject":"Re: Linus' sha1 is much faster!","fromName":"Giuseppe Scrivano","fromEmail":"gscrivano@gnu.org","sentAt":"2009-08-17T10:51:17Z","receivedAt":"2009-08-17T10:51:17Z","isPatch":false,"sender":{"key":"gscrivano@gnu.org","avatar":"https://avatars.githubusercontent.com/u/67430?v=4"},"body":"Pádraig Brady writes:\n\n> -O2 -g -pipe -Wall -Wp,-D_FORTIFY_SOURCE=2 -fexceptions\n> -fstack-protector --param=ssp-buffer-size=4 -m32 -march=i586\n> -mtune=generic -fasynchronous-unwind-tables -D_GNU_SOURCE=1\n\nthanks. I did again all tests on my machine using these same options.\nI repeated each test 6 times and I took the median without consider the\nfirst result. Except the first run that it is not considered, I didn't\nreport a big variance on results of the same test.\n\n\ngcc 4.3.3\n\ngnulib sha1: real\t0m2.543s\ngnulib sha1 lookup: real\t0m1.906s (-25%)\nlinus's sha1: real\t0m2.468s (-3%)\nlinus's sha1 no asm: real\t0m2.289s (-9%)\n\n\ngcc 4.4.1\n\ngnulib sha1: real\t0m3.386s\ngnulib sha1 lookup: real\t0m3.110s (-8%)\nlinus's sha1: real\t0m1.701s (-49%)\nlinus's sha1 no asm: real\t0m1.284s (-62%)\n\n\nI don't see such big differences in asm generated by gcc 4.4.1 and gcc\n4.3.3 to explain this performance difference, what I noticed immediately\nis that in the gcc-4.4 generated asm there are more \"lea\" instructions\n(+30%), but I doubt this is the reason of these poor results. Anyway, I\nhaven't yet looked much in details.\n\nCheers,\nGiuseppe\n"},{"id":"120902","messageId":"f488382f0908170844h649126efxb27f87d7b319961b@mail.gmail.com","threadId":"20601","inReplyTo":"8763cmemsa.fsf@master.homenet","subject":"Re: Linus' sha1 is much faster!","fromName":"Steven Noonan","fromEmail":"steven@uplinklabs.net","sentAt":"2009-08-17T15:44:30Z","receivedAt":"2009-08-17T15:44:30Z","isPatch":false,"sender":{"key":"steven@uplinklabs.net","avatar":"https://gravatar.com/avatar/b0cd397a10638433f76e084531aa0af3bef85f8fdb59b1ebe2ddaf168cd100e9?d=mp&s=160"},"body":"On Mon, Aug 17, 2009 at 3:51 AM, Giuseppe Scrivano wrote:\n> Pádraig Brady writes:\n>\n>>   -O2 -g -pipe -Wall -Wp,-D_FORTIFY_SOURCE=2 -fexceptions\n>>   -fstack-protector --param=ssp-buffer-size=4 -m32 -march=i586\n>>   -mtune=generic -fasynchronous-unwind-tables -D_GNU_SOURCE=1\n>\n> thanks.  I did again all tests on my machine using these same options.\n> I repeated each test 6 times and I took the median without consider the\n> first result.  Except the first run that it is not considered, I didn't\n> report a big variance on results of the same test.\n>\n>\n> gcc 4.3.3\n>\n> gnulib sha1:            real    0m2.543s\n> gnulib sha1 lookup:     real    0m1.906s (-25%)\n> linus's sha1:           real    0m2.468s (-3%)\n> linus's sha1 no asm:    real    0m2.289s (-9%)\n>\n>\n> gcc 4.4.1\n>\n> gnulib sha1:            real    0m3.386s\n> gnulib sha1 lookup:     real    0m3.110s (-8%)\n> linus's sha1:           real    0m1.701s (-49%)\n> linus's sha1 no asm:    real    0m1.284s (-62%)\n>\n>\n> I don't see such big differences in asm generated by gcc 4.4.1 and gcc\n> 4.3.3 to explain this performance difference, what I noticed immediately\n> is that in the gcc-4.4 generated asm there are more \"lea\" instructions\n> (+30%), but I doubt this is the reason of these poor results.  Anyway, I\n> haven't yet looked much in details.\n>\n> Cheers,\n> Giuseppe\n\nInteresting. I compared Linus' implementation to the public domain one\nby Steve Reid[1], which is used in OpenLDAP and a few other projects.\nAnyone with some experience testing these kinds of things in a\nstatistically sound manner want to try it out? In my tests, I got\nthis:\n\n(average of 5 runs)\nLinus' sha1: 283MB/s\nSteve Reid's sha1: 305MB/s\n\n- Steven\n\n[1] http://gpl.nas-central.org/SYNOLOGY/x07-series/514_UNTARED/source/openldap-2.3.11/libraries/liblutil/sha1.c\n"},{"id":"120923","messageId":"alpine.LFD.2.01.0908170852320.3162@localhost.localdomain","threadId":"20601","inReplyTo":"f488382f0908170844h649126efxb27f87d7b319961b@mail.gmail.com","subject":"Re: Linus' sha1 is much faster!","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-17T16:22:56Z","receivedAt":"2009-08-17T16:22:56Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 17 Aug 2009, Steven Noonan wrote:\n> \n> Interesting. I compared Linus' implementation to the public domain one\n> by Steve Reid[1]\n\nYou _really_ need to talk about what kind of environment you have.\n\nThere are three major issues:\n - Netburst vs non-netburst\n - 32-bit vs 64-bit\n - compiler version\n\nSteve Reid's code looks great, but the way it is coded, gcc makes a mess \nof it, which is exactly what my SHA1 tries to avoid.\n\n[ In contrast, gcc does very well on just about _any_ straightforward \n unrolled SHA1 C code if the target architecture is something like PPC or \n ia64 that has enough registers to keep it all in registers.\n\n I haven't really tested other compilers - a less aggressive compiler \n would actually do _better_ on SHA1, because the problem with gcc is that \n it turns the whole temporary 16-entry word array into register accesses, \n and tries to do register allocation on that _array_.\n\n That is wonderful for the above-mentioned PPC and IA64, but it makes gcc \n create totally crazy code when there aren't enough registers, and then \n gcc starts spilling randomly (ie it starts spilling a-e etc). This is \n why the compiler and version matters so much. ]\n\n> (average of 5 runs)\n> Linus' sha1: 283MB/s\n> Steve Reid's sha1: 305MB/s\n\nSo I get very different results:\n\n\t# TIME[s] SPEED[MB/s]\n\tReid 2.742 222.6\n\tlinus 1.464 417\n\nthis is Intel Nehalem, but compiled for 32-bit mode (which is the more \nchallenging one because x86-32 only has 7 general-purpose registers), and \nwith gcc-4.4.0.\n\n\t\t\tLinus\n"},{"id":"120949","messageId":"871vnae47k.fsf@master.homenet","threadId":"20601","inReplyTo":"f488382f0908170844h649126efxb27f87d7b319961b@mail.gmail.com","subject":"Re: Linus' sha1 is much faster!","fromName":"Giuseppe Scrivano","fromEmail":"gscrivano@gnu.org","sentAt":"2009-08-17T17:32:31Z","receivedAt":"2009-08-17T17:32:31Z","isPatch":false,"sender":{"key":"gscrivano@gnu.org","avatar":"https://avatars.githubusercontent.com/u/67430?v=4"},"body":"Hi,\n\nThese are the results I reported (median of 5 plus an additional not\nconsidered first run) on the Steve Reid's SHA1 implementation using the\nsame flags to the compiler that I used for previous tests.\n\nGCC 4.3.3: real\t0m2.627s\nGCC 4.4.1: real\t0m3.742s\n\nIn both cases it showed to be slower than other implementations I have\nalready tried.\n\nAdditional note: as for gnulib SHA1, GCC 4.4.1 produced slower code than\nGCC 4.3.3.\n\nCheers,\nGiuseppe\n\n\n\nSteven Noonan writes:\n\n>\n> Interesting. I compared Linus' implementation to the public domain one\n> by Steve Reid[1], which is used in OpenLDAP and a few other projects.\n> Anyone with some experience testing these kinds of things in a\n> statistically sound manner want to try it out? In my tests, I got\n> this:\n>\n> (average of 5 runs)\n> Linus' sha1: 283MB/s\n> Steve Reid's sha1: 305MB/s\n>\n> - Steven\n>\n> [1] http://gpl.nas-central.org/SYNOLOGY/x07-series/514_UNTARED/source/openldap-2.3.11/libraries/liblutil/sha1.c\n"},{"id":"121001","messageId":"f488382f0908171443n7fa92342v1ac12f52a17fd048@mail.gmail.com","threadId":"20601","inReplyTo":"alpine.LFD.2.01.0908170852320.3162@localhost.localdomain","subject":"Re: Linus' sha1 is much faster!","fromName":"Steven Noonan","fromEmail":"steven@uplinklabs.net","sentAt":"2009-08-17T21:43:55Z","receivedAt":"2009-08-17T21:43:55Z","isPatch":false,"sender":{"key":"steven@uplinklabs.net","avatar":"https://gravatar.com/avatar/b0cd397a10638433f76e084531aa0af3bef85f8fdb59b1ebe2ddaf168cd100e9?d=mp&s=160"},"body":"On Mon, Aug 17, 2009 at 9:22 AM, Linus\nTorvalds wrote:\n>\n>\n> On Mon, 17 Aug 2009, Steven Noonan wrote:\n>>\n>> Interesting. I compared Linus' implementation to the public domain one\n>> by Steve Reid[1]\n>\n> You _really_ need to talk about what kind of environment you have.\n>\n> There are three major issues:\n>  - Netburst vs non-netburst\n>  - 32-bit vs 64-bit\n>  - compiler version\n\nRight. I'm running a Core 2 \"Merom\" 2.33GHz. The code was compiled for\nx86_64 with GCC 4.2.1. I didn't _expect_ it to compile for x86_64, but\napparently the version of GCC that ships with Xcode 3.2 defaults to\ncompiling 64-bit code on machines that are capable of running it.\n\n>\n> Steve Reid's code looks great, but the way it is coded, gcc makes a mess\n> of it, which is exactly what my SHA1 tries to avoid.\n>\n> [ In contrast, gcc does very well on just about _any_ straightforward\n>  unrolled SHA1 C code if the target architecture is something like PPC or\n>  ia64 that has enough registers to keep it all in registers.\n>\n>  I haven't really tested other compilers - a less aggressive compiler\n>  would actually do _better_ on SHA1, because the problem with gcc is that\n>  it turns the whole temporary 16-entry word array into register accesses,\n>  and tries to do register allocation on that _array_.\n>\n>  That is wonderful for the above-mentioned PPC and IA64, but it makes gcc\n>  create totally crazy code when there aren't enough registers, and then\n>  gcc starts spilling randomly (ie it starts spilling a-e etc). This is\n>  why the compiler and version matters so much. ]\n>\n>> (average of 5 runs)\n>> Linus' sha1: 283MB/s\n>> Steve Reid's sha1: 305MB/s\n>\n> So I get very different results:\n>\n>        #             TIME[s] SPEED[MB/s]\n>        Reid            2.742       222.6\n>        linus           1.464         417\n\nAdded -m32:\n\nSteve Reid: 156MB/s\nLinus: 209MB/s\n\nSo on x86, your code really kicks butt.\n\n> this is Intel Nehalem, but compiled for 32-bit mode (which is the more\n> challenging one because x86-32 only has 7 general-purpose registers), and\n> with gcc-4.4.0.\n>\n>                        Linus\n>\n"},{"id":"121792","messageId":"4A951EFB.1010400@draigBrady.com","threadId":"20601","inReplyTo":"alpine.LFD.2.00.0908162151180.6044@xanadu.home","subject":"Re: Linus' sha1 is much faster!","fromName":"Pádraig Brady","fromEmail":"p@draigbrady.com","sentAt":"2009-08-26T11:39:39Z","receivedAt":"2009-08-26T11:39:39Z","isPatch":false,"sender":{"key":"p@draigbrady.com","avatar":"https://gravatar.com/avatar/6d16c619bfc08087da3aa2baf6e69e438044a3dd657f0a31637d8de065ef5b27?d=mp&s=160"},"body":"Nicolas Pitre wrote:\n> On Sat, 15 Aug 2009, Linus Torvalds wrote:\n> \n>> (Heh. Looking at that, I probably should move the 'size' field first, \n>> since that would have different alignment rules, and the struct would be \n>> more tightly packed that way, and initialize better).\n> \n> I was about to suggest (i.e. post) a patch for that. This is indeed a \n> good idea.\n> \n>> Afaik, none of the actual code remains (the mozilla SHA1 thing did the \n>> wrong thing for performance even for just the final bytes, and did those a \n>> byte at a time etc, so I rewrote even the trivial SHA1_Final parts).\n> \n> Maybe a patch adding a proper header with the actual license would be a \n> good idea too.\n\nSo have you decided on a final licence,\nand if so update the headers accordingly?\n\ncheers!\nPádraig.\n"},{"id":"317423","messageId":"1492724128603-7657473.post@n2.nabble.com","threadId":"20601","inReplyTo":"4A951EFB.1010400@draigBrady.com","subject":"Re: Linus' sha1 is much faster!","fromName":"galt","fromEmail":"galt@folkplanet.com","sentAt":"2017-04-20T21:35:28Z","receivedAt":"2017-04-20T21:35:46Z","isPatch":false,"sender":{"key":"galt@folkplanet.com","avatar":null},"body":"I also wanted to include Linus' sha1 in our software at work.\nBut the GPLv2 license was incompatible.\nToo bad it is just just in the public domain.\nI grabbed Steve Reid's public domain code from 1999\nand ran it. It produced the same output.\nI ran it on a 3GB input file, and Linus' code from 2009 takes 37 to 40\nseconds.\n(Just reading the file in the same 4k buffers only takes 3 seconds \nso disk reading does not dominate the time.)\nWhen I ran Steve's old version on the same input it was taking just 36 or 37\nseconds.\nSo it is slightly faster.\nHave compilers improved?\nI am using gcc 4.4.7-17.\n\n\n\n\n\n--\nView this message in context: http://git.661346.n2.nabble.com/Linus-sha1-is-much-faster-tp3448007p7657473.html\nSent from the git mailing list archive at Nabble.com.\n"},{"id":"317424","messageId":"1492724327147-7657474.post@n2.nabble.com","threadId":"20601","inReplyTo":"4A951EFB.1010400@draigBrady.com","subject":"Re: Linus' sha1 is much faster!","fromName":"galt","fromEmail":"galt@folkplanet.com","sentAt":"2017-04-20T21:38:47Z","receivedAt":"2017-04-20T21:38:53Z","isPatch":false,"sender":{"key":"galt@folkplanet.com","avatar":null},"body":"A Phádraig, cá bhfuil tú i do chónaí?\nTá mé i gCalafoirne.\n\n\n\n--\nView this message in context: http://git.661346.n2.nabble.com/Linus-sha1-is-much-faster-tp3448007p7657474.html\nSent from the git mailing list archive at Nabble.com.\n"}]}