I've noticed before that coreutils hashing utils
were a little behind in performance, but was prompted
to look at it again when I noticed the recently
updated sha1 implementation in git:
http://git.kernel.org/?p=git/git.git;a=history;f=block-sha1;h=d3121f7;hb=pu
Testing that with the attached program which I wrote
in a couple of mins to try and match sha1sum's system calls
shows that it's around 33% faster, as shown below:
$ gcc $(rpm -q --qf="%{OPTFLAGS}\n" coreutils) linus-sha1.c sha1.c -o linus-sha1
$ time ./linus-sha1 300MB_file
df1e19e245fee4f53087b50ef953ca2c8d1644d7 300MB_file
real 0m2.742s
user 0m2.516s
sys 0m0.206s
$ time ~/git/coreutils/src/sha1sum 300MB_file
df1e19e245fee4f53087b50ef953ca2c8d1644d7 300MB_file
real 0m4.166s
user 0m3.846s
sys 0m0.298s
So, could we use that code in coreutils?
Think of all the dead fish it would save.
I've also attached a trivial block-sha1 patch which doesn't
affect performance, but does suppress a signed unsigned
comparison warning which occurs with -Wextra for example.
cheers,
Pádraig.
I've noticed before that coreutils hashing utils
were a little behind in performance, but was prompted
to look at it again when I noticed the recently
updated sha1 implementation in git:
http://git.kernel.org/?p=git/git.git;a=history;f=block-sha1;h=d3121f7;hb=pu
Testing that with the attached program which I wrote
in a couple of mins to try and match sha1sum's system calls
shows that it's around 33% faster, as shown below:
$ gcc $(rpm -q --qf="%{OPTFLAGS}\n" coreutils) linus-sha1.c sha1.c -o linus-sha1
$ time ./linus-sha1 300MB_file
df1e19e245fee4f53087b50ef953ca2c8d1644d7 300MB_file
real 0m2.742s
user 0m2.516s
sys 0m0.206s
$ time ~/git/coreutils/src/sha1sum 300MB_file
df1e19e245fee4f53087b50ef953ca2c8d1644d7 300MB_file
real 0m4.166s
user 0m3.846s
sys 0m0.298s
So, could we use that code in coreutils?
Think of all the dead fish it would save.
coreutils is licensed under GPLv3, and git under GPLv2 (only), so
you'd need permission from all contributors to the implementation in
order to relicense under GPLv3. A quick grep of the history suggests
these contributors to be:
Brandon Casey [off-list ref]
Junio C Hamano [off-list ref]
Linus Torvalds [off-list ref]
Nicolas Pitre [off-list ref]
(adding these people to the CC list)
Additionally, it was originally based on the code in
mozilla-sha1/sha1.c, but that contains a license grant allowing it to
be used under GPLv2 /or later/, so if GPLv3 relicensing is enough it
shouldn't be necessary to get in contact with the original author.
However if the FSF requires copyright assignment to accept the new
implementation, it will be necessary to track down contributors to the
original mozilla-sha1/sha1.c as well.
Note that I'm not a lawyer, so there might be other roadblocks etc to
this as well, etc :)
From: John Tapsell <hidden> Date: 2016-06-15 22:47:15
2009/8/15 Bryan Donlan [off-list ref]:
coreutils is licensed under GPLv3, and git under GPLv2 (only), so
you'd need permission from all contributors to the implementation in
order to relicense under GPLv3. A quick grep of the history suggests
these contributors to be:
X11 also requires a fast SHA1 implementation. It uses this to check
if two pixmaps are the same. So it would be really nice to relicense
under a liberal enough license that xorg can use it.
John
coreutils is licensed under GPLv3, and git under GPLv2 (only), so
you'd need permission from all contributors to the implementation in
order to relicense under GPLv3. A quick grep of the history suggests
these contributors to be:
X11 also requires a fast SHA1 implementation. It uses this to check
if two pixmaps are the same. So it would be really nice to relicense
under a liberal enough license that xorg can use it.
I'm personally ok with retaining the mozilla-sha1 license.
There's not really anything _remaining_ of the mozilla code, but hey, I
started from it. In retrospect I probably should have started from the PPC
asm code that already did the blocking sanely - but that's a "20/20
hindsight" kind of thing.
Plus hey, the mozilla code being a horrid pile of crud was why I was so
convinced that I could improve on things. So that's a kind of source for
it, even if it's more about the motivational side than any actual
remaining code ;)
That said, I don't know if the MPL is ok for X11. I've not looked at
compatibility issues with MPL. For git, we could just ignore the MPL,
since the GPLv2 was acceptable regardless of it.
Linus
That said, I don't know if the MPL is ok for X11. I've not looked at
compatibility issues with MPL. For git, we could just ignore the MPL,
since the GPLv2 was acceptable regardless of it.
If MPL isn't ok for X11, then we'd need to make sure that even the
silliest Mozilla crud has been rewritten. There really isn't much, but
hey, the _history_ is based on the mozilla code, and who knows - the
'blk_SHA_CTX' struct has things like the fields in the same order as the
Mozilla equivalent, for all those historical reasons.
(Heh. Looking at that, I probably should move the 'size' field first,
since that would have different alignment rules, and the struct would be
more tightly packed that way, and initialize better).
Afaik, none of the actual code remains (the mozilla SHA1 thing did the
wrong thing for performance even for just the final bytes, and did those a
byte at a time etc, so I rewrote even the trivial SHA1_Final parts).
Of course, maybe the Mozilla people would be interested in taking my
faster version, and say that the new-BSD license is ok, and make everybody
happy. The only listed author for the Mozilla SHA1 is Paul Kocher. I added
him to the Cc.
Paul, for your information, we're talking about a faster rewritten "mostly
portable" SHA1 routines that you can find at
http://git.kernel.org/?p=git/git.git;a=tree;f=block-sha1;hb=pu
(follow the "blob" pointers to see sha1.c and sha1.h). I don't know if
you're active with Mozilla/Firefox or whether you even care, but you seem
to be the logical choice of person to ask.
Linus
On Sat, Aug 15, 2009 at 09:12:58PM +0100, John Tapsell wrote:
2009/8/15 Bryan Donlan [off-list ref]:
quoted
coreutils is licensed under GPLv3, and git under GPLv2 (only), so
you'd need permission from all contributors to the implementation in
order to relicense under GPLv3. A quick grep of the history suggests
these contributors to be:
X11 also requires a fast SHA1 implementation. It uses this to check
if two pixmaps are the same. So it would be really nice to relicense
under a liberal enough license that xorg can use it.
If the checksum isn't being exposed in the protocol (i.e., it's just
internal to the X server), one possibility for X11 is to consider to
use the SHA-3 candidate Skein instead. After receiving a large amount
of evaluation by cryptographic experts, it was one of the 18
algorithms (our of an original 64 entries) that have made it the 2nd
round of the NIST competition. It's also *substantially* faster than
SHA:
One exception to this is Skein, created by several well-known
cryptographers and noted pundit Bruce Schneier. It was designed
specifically to exploit all three of the Core 2 execution units
and to run at a full 64-bits. This gives it roughly four to 10
times the logic density of competing submissions.
This is what I meant by the Matrix quote above. They didn't bend
the spoon; they bent the crypto algorithm. They moved the logic
operations around in a way that wouldn't weaken the crypto, but
would strengthen its speed on the Intel Core 2.
In their paper (PDF), the authors of Skein express surprise that a
custom silicon ASIC implementation is not any faster than the
software implementation. They shouldn't be surprised. Every time
you can redefine a problem to run optimally in software, you will
reach the same speeds you get with optimized ASIC hardware. The
reason software has a reputation of being slow is because people
don't redefine the original problem.
http://www.darkreading.com/blog/archives/2008/11/bending_skein_c.html
For more information and some optimized implementation, see:
http://www.skein-hash.info/
- Ted
From: Nicolas Pitre <hidden> Date: 2016-06-15 22:47:15
On Sat, 15 Aug 2009, Linus Torvalds wrote:
(Heh. Looking at that, I probably should move the 'size' field first,
since that would have different alignment rules, and the struct would be
more tightly packed that way, and initialize better).
I was about to suggest (i.e. post) a patch for that. This is indeed a
good idea.
Afaik, none of the actual code remains (the mozilla SHA1 thing did the
wrong thing for performance even for just the final bytes, and did those a
byte at a time etc, so I rewrote even the trivial SHA1_Final parts).
Maybe a patch adding a proper header with the actual license would be a
good idea too.
Nicolas
From: Andreas Ericsson <hidden> Date: 2016-06-15 22:47:15
Linus Torvalds wrote:
On Sat, 15 Aug 2009, Linus Torvalds wrote:
quoted
That said, I don't know if the MPL is ok for X11. I've not looked at
compatibility issues with MPL. For git, we could just ignore the MPL,
since the GPLv2 was acceptable regardless of it.
If MPL isn't ok for X11, then we'd need to make sure that even the
silliest Mozilla crud has been rewritten. There really isn't much, but
hey, the _history_ is based on the mozilla code, and who knows - the
'blk_SHA_CTX' struct has things like the fields in the same order as the
Mozilla equivalent, for all those historical reasons.
(Heh. Looking at that, I probably should move the 'size' field first,
since that would have different alignment rules, and the struct would be
more tightly packed that way, and initialize better).
Afaik, none of the actual code remains (the mozilla SHA1 thing did the
wrong thing for performance even for just the final bytes, and did those a
byte at a time etc, so I rewrote even the trivial SHA1_Final parts).
Of course, maybe the Mozilla people would be interested in taking my
faster version, and say that the new-BSD license is ok, and make everybody
happy. The only listed author for the Mozilla SHA1 is Paul Kocher. I added
him to the Cc.
Paul, for your information, we're talking about a faster rewritten "mostly
portable" SHA1 routines that you can find at
http://git.kernel.org/?p=git/git.git;a=tree;f=block-sha1;hb=pu
(follow the "blob" pointers to see sha1.c and sha1.h). I don't know if
you're active with Mozilla/Firefox or whether you even care, but you seem
to be the logical choice of person to ask.
I contacted Paul in february this year to get permission to use the mozilla
sha1 code for libgit2. His reply then was:
"I'm not sure which version the diffs are relative to, so I haven't reviewed them.
It's fine to distribute under BSD, GPL, or LGPL, however."
I also got explicit permission to relicense it under GPLv2 with the gcc exception.
I added the mail-address I used to contact him to CC as well. Sorry if you get
this twice, Paul.
Naturally, I'd like to use the faster version for libgit2 as well. The people
who Linus listed as contributors earlier (Brandon Casy, Linus, Junio and Nicolas
Pitre) have already consented to relicense their git contributions for libgit2
use. If anyone would like to revoke that consent for this code, speak now please,
or I'll patch it into libgit2 as well.
--
Andreas Ericsson andreas.ericsson@op5.se
OP5 AB www.op5.se
Tel: +46 8-230225 Fax: +46 8-230231
Considering the successes of the wars on alcohol, poverty, drugs and
terror, I think we should give some serious thought to declaring war
on peace.
(Heh. Looking at that, I probably should move the 'size' field first,
since that would have different alignment rules, and the struct would be
more tightly packed that way, and initialize better).
I was about to suggest (i.e. post) a patch for that. This is indeed a
good idea.
quoted
Afaik, none of the actual code remains (the mozilla SHA1 thing did the
wrong thing for performance even for just the final bytes, and did those a
byte at a time etc, so I rewrote even the trivial SHA1_Final parts).
Maybe a patch adding a proper header with the actual license would be a
good idea too.
So have you decided on a final licence,
and if so update the headers accordingly?
cheers!
Pádraig.
I also wanted to include Linus' sha1 in our software at work.
But the GPLv2 license was incompatible.
Too bad it is just just in the public domain.
I grabbed Steve Reid's public domain code from 1999
and ran it. It produced the same output.
I ran it on a 3GB input file, and Linus' code from 2009 takes 37 to 40
seconds.
(Just reading the file in the same 4k buffers only takes 3 seconds
so disk reading does not dominate the time.)
When I ran Steve's old version on the same input it was taking just 36 or 37
seconds.
So it is slightly faster.
Have compilers improved?
I am using gcc 4.4.7-17.
--
View this message in context: http://git.661346.n2.nabble.com/Linus-sha1-is-much-faster-tp3448007p7657473.html
Sent from the git mailing list archive at Nabble.com.