Re: [PATCH 0/7] block-sha1: improved SHA1 hashing

On Sat, 8 Aug 2009, Artur Skawina wrote:

i was seeing such large variations depending on the -mtune flags that
i gave up and now do just -march=i686; that's what i would expect
for generic x86 binaries.

I think I have found a way to avoid the gcc crazyness.

Lookie here:

	#             TIME[s] SPEED[MB/s]
	rfc3174         5.094       119.8
	rfc3174         5.098       119.7
	linus           1.462       417.5
	linusas         2.008         304
	linusas2        1.878         325
	mozilla         5.566       109.6
	mozillaas       5.866       104.1
	openssl         1.609       379.3
	spelvin         1.675       364.5
	spelvina        1.601       381.3
	nettle          1.591       383.6

notice? I outperform all the hand-tuned asm on 32-bit too. By quite a 
margin, in fact.

Now, I didn't try a P4, and it's possible that it won't do that there, but 
the 32-bit code generation sure looks impressive on my Nehalem box. The 
magic? I force the stores to the 512-bit hash bucket to be done in order. 
That seems to help a lot.

The diff is trivial (on top of the "rename registers with cpp" patch), as 
appended. And it does seem to fix the P4 issues too, although I can 
obviously (once again) only test Prescott, and only in 64-bit mode:

	#             TIME[s] SPEED[MB/s]
	rfc3174         1.662       36.73
	rfc3174          1.64       37.22
	linus          0.2523       241.9
	linusas        0.4367       139.8
	linusas2       0.4487         136
	mozilla        0.9704        62.9
	mozillaas      0.9399       64.94

that's some really impressive improvement. All from just saying "do the 
stores in the order I told you to, dammit!" to the compiler.

		Linus

---
 block-sha1/sha1.c |    3 ++-
 1 files changed, 2 insertions(+), 1 deletions(-)

diff --git a/block-sha1/sha1.c b/block-sha1/sha1.c
index 19dc41d..f70e1ba 100644
--- a/block-sha1/sha1.c
+++ b/block-sha1/sha1.c

@@ -93,6 +93,7 @@ void blk_SHA1_Final(unsigned char hashout[20], blk_SHA_CTX *ctx)
 
 /* This "rolls" over the 512-bit array */
 #define W(x) (array[(x)&15])
+#define setW(x, val) (*(volatile unsigned int *)&W(x) = (val))
 
 /*
  * Where do we get the source from? The first 16 iterations get it from

@@ -102,7 +103,7 @@ void blk_SHA1_Final(unsigned char hashout[20], blk_SHA_CTX *ctx)
 #define SHA_MIX(t) SHA_ROL(W(t+13) ^ W(t+8) ^ W(t+2) ^ W(t), 1)
 
 #define SHA_ROUND(t, input, fn, constant, A, B, C, D, E) do { \
-	unsigned int TEMP = input(t); W(t) = TEMP; \
+	unsigned int TEMP = input(t); setW(t, TEMP); \
 	E += TEMP + SHA_ROL(A,5) + (fn) + (constant); \
 	B = SHA_ROR(B, 2); } while (0)
 

Linus Torvalds wrote:

I think I have found a way to avoid the gcc crazyness.

Lookie here:

	#             TIME[s] SPEED[MB/s]
	rfc3174         5.094       119.8
	rfc3174         5.098       119.7
	linus           1.462       417.5
	linusas         2.008         304
	linusas2        1.878         325
	mozilla         5.566       109.6
	mozillaas       5.866       104.1
	openssl         1.609       379.3
	spelvin         1.675       364.5
	spelvina        1.601       381.3
	nettle          1.591       383.6

notice? I outperform all the hand-tuned asm on 32-bit too. By quite a 
margin, in fact.

Now, I didn't try a P4, and it's possible that it won't do that there, but 
the 32-bit code generation sure looks impressive on my Nehalem box. The 
magic? I force the stores to the 512-bit hash bucket to be done in order. 
That seems to help a lot.

I named it 'linusv':

P4/i686:
#             TIME[s] SPEED[MB/s]
rfc3174         1.456       41.92
rfc3174         1.445       42.22
linus          0.5865       104.1
linusph        0.5643       108.2
linusv         0.3697       165.1
linusvph       0.3618       168.7
linusp4        0.4312       141.5
linusas        0.4091       149.2
linusas2       0.4364       139.9
mozilla         1.102       55.37
mozillaas       1.297       47.07
openssl         0.261       233.9
opensslb       0.2395       254.9
spelvin        0.2653         230
nettle          0.438       139.4

and when tuning for prescott:

linus          0.6544       93.27
linusph        0.6523       93.57
linusv         0.3439       177.5
linusvph       0.3547       172.1
linusp4        0.3585       170.3

so it isn't as fast as the openssl asm ones, but it does win
in the C category.

I outperform all the hand-tuned asm on 32-bit too. By quite a 
margin, in fact.

I've inlined the byteswapping in 'opensslb', maybe that one will
do a bit better.

http://www.src.multimo.pl/YDpqIo7Li27O0L0h/sha1bench.tar.gz

artur

On Sat, 8 Aug 2009, Artur Skawina wrote:

I've inlined the byteswapping in 'opensslb', maybe that one will
do a bit better.

http://www.src.multimo.pl/YDpqIo7Li27O0L0h/sha1bench.tar.gz

Hmm. Testing on my atom, the inlined bswap is worse, but the asm versions 
are generally superior to any C one:

	#             TIME[s] SPEED[MB/s]
	rfc3174         2.194       27.82
	rfc3174          2.19       27.87
	linus           0.947       64.45
	linusph        0.9381       65.06
	linusv         0.8943       68.25
	linusvph       0.8803       69.34
	linusasm       0.9349       65.29
	linusp4         1.006       60.66
	linusas         1.062       57.48
	linusas2        1.009        60.5
	mozilla         2.264       26.96
	mozillaas       2.197       27.78
	openssl         0.648       94.19
	opensslb       0.7419       82.27
	spelvin         0.636       95.96
	spelvina       0.6671       91.49
	nettle          0.717       85.12
	nettle-ror     0.7137       85.52
	nettle-p4sch   0.7158       85.27

Interestingly, -mtune=prescott does well for that 'linusv' version on atom 
too, and gets it up to

	linusv         0.8365       72.96

and it's the only one that improves. Odd interactions.

			Linus

Linus Torvalds wrote:

On Sat, 8 Aug 2009, Artur Skawina wrote:

quoted

I've inlined the byteswapping in 'opensslb', maybe that one will
do a bit better.

Hmm. Testing on my atom, the inlined bswap is worse, but the asm versions 
are generally superior to any C one:

It loses on atom, but is the best one on both P3 and P4 here.
Based on your other numbers I was expecting it to win on 32-bit
nehalem too. gcc doing a better job of scheduling w/ 'linusv'
wouldn't surprise though (since there are no spills, the data reads
are about the only other thing that could make a difference. And, yes,
they show up in the profiles; if x86 only had one more register...)

artur

Artur Skawina wrote:

Linus Torvalds wrote:

quoted

magic? I force the stores to the 512-bit hash bucket to be done in order. 
That seems to help a lot.

I named it 'linusv':

linusv         0.3697       165.1

I was not going to spend even more time on the C version, but after looking
at what gcc does to it, tried this: 

diff --git a/block-sha1/sha1vol.c b/block-sha1/sha1vol.c
--- a/block-sha1/sha1vol.c
+++ b/block-sha1/sha1vol.c

@@ -93,7 +93,7 @@ void blk_SHA1_Finalv(unsigned char hashout[20], blk_SHA_CTX *ctx)
 
 /* This "rolls" over the 512-bit array */
 #define W(x) (array[(x)&15])
-#define setW(x, val) (*(volatile unsigned int *)&W(x) = (val))
+#define setW(x, val) W(x) = (val); __asm__ volatile ("": "+m" (W(x)))
 
 /*
  * Where do we get the source from? The first 16 iterations get it from

and got a nice improvement:

rfc3174         1.436       42.49
linus          0.5843       104.5
linusph        0.5639       108.2
linusv         0.3098         197
linusvph       0.3082       198.1
linusasm       0.5849       104.3
linusp4         0.433         141
linusas        0.4077       149.7
linusas2        0.436         140
mozilla         1.099       55.54
mozillaas       1.295       47.11
openssl        0.2632       231.9
opensslb       0.2395       254.8
spelvin        0.2687       227.2
spelvina       0.2526       241.7
nettle         0.4378       139.4
nettle-ror     0.4379       139.4
nettle-p4sch   0.4231       144.2

The atom numbers didn't change much.

artur

Artur Skawina wrote:

Artur Skawina wrote:

-#define setW(x, val) (*(volatile unsigned int *)&W(x) = (val))
+#define setW(x, val) W(x) = (val); __asm__ volatile ("": "+m" (W(x)))

and w/ this on top:

diff --git a/block-sha1/sha1vol.c b/block-sha1/sha1vol.c
--- a/block-sha1/sha1vol.c
+++ b/block-sha1/sha1vol.c

@@ -103,9 +103,9 @@ void blk_SHA1_Finalv(unsigned char hashout[20], blk_SHA_CTX *ctx)
 #define SHA_MIX(t) SHA_ROL(W(t+13) ^ W(t+8) ^ W(t+2) ^ W(t), 1)
 
 #define SHA_ROUND(t, input, fn, constant, A, B, C, D, E) do { \
-	unsigned int TEMP = input(t); setW(t, TEMP); \
-	E += TEMP + SHA_ROL(A,5) + (fn) + (constant); \
-	B = SHA_ROR(B, 2); } while (0)
+	unsigned int TEMP = SHA_ROL(A,5); E+= (fn); \
+	E += (constant) + TEMP; TEMP = input(t); setW(t, TEMP); \
+	B = SHA_ROR(B, 2); E += TEMP; } while (0)
 
 #define T_0_15(t, A, B, C, D, E)  SHA_ROUND(t, SHA_SRC, (((C^D)&B)^D) , 0x5a827999, A, B, C, D, E )
 #define T_16_19(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, (((C^D)&B)^D) , 0x5a827999, A, B, C, D, E )

I see an improvement on atom and reach ~200M/s on P4 (i686).
.
When compiled w/ '-mtune=prescott':

rfc3174         1.459       41.84
linus          0.6574       92.85
linusph        0.6613       92.29
linusv         0.2682       227.6
linusvph       0.2681       227.7
linusasm       0.5868         104
linusp4        0.3586       170.2
linusas        0.3795       160.8
linusas2       0.3583       170.3
mozilla         1.171       52.11
mozillaas       1.381        44.2
openssl        0.2623       232.7
opensslb       0.2404       253.9
spelvin        0.2659       229.6
spelvina       0.2492       244.9
nettle         0.4362       139.9
nettle-ror      0.436         140
nettle-p4sch   0.4204       145.2

it's now just 2% slower than the openssl assembler version.

artur