Re: x86 SHA1: Faster than OpenSSL

From: Artur Skawina <art.08.09@gmail.com>
Date: Aug 6, 2009, 04:08 UTC
Message-ID: <4A7A5723.6070704@gmail.com>
In-Reply-To: <alpine.LFD.2.01.0908052024081.3390@localhost.localdomain>

Linus Torvalds wrote:

Show 21 quoted lines

> 
> On Thu, 6 Aug 2009, Artur Skawina wrote:
>>>  #define T_0_19(t) \
>>> -	TEMP = SHA_ROT(A,5) + (((C^D)&B)^D)     + E + W[t] + 0x5a827999; \
>>> -	E = D; D = C; C = SHA_ROT(B, 30); B = A; A = TEMP;
>>> +	TEMP = SHA_ROL(A,5) + (((C^D)&B)^D)     + E + W[t] + 0x5a827999; \
>>> +	E = D; D = C; C = SHA_ROR(B, 2); B = A; A = TEMP;
>>>  
>>>  	T_0_19( 0); T_0_19( 1); T_0_19( 2); T_0_19( 3); T_0_19( 4);
>>>  	T_0_19( 5); T_0_19( 6); T_0_19( 7); T_0_19( 8); T_0_19( 9);
>> unrolling these otoh is a clear loss (iirc ~10%). 
> 
> I can well imagine. The P4 decode bandwidth is abysmal unless you get 
> things into the trace cache, and the trace cache is of a very limited 
> size.
> 
> However, on at least Nehalem, unrolling it all is quite a noticeable win.
> 
> The way it's written, I can easily make it do one or the other by just 
> turning the macro inside a loop (and we can have a preprocessor flag to 
> choose one or the other), but let me work on it a bit more first.

that's of course how i measured it.. :)

> I'm trying to move the htonl() inside the loops (the same way I suggested 
> George do with his assembly), and it seems to help a tiny bit. But I may 
> be measuring noise.

i haven't tried your version at all yet (just applied the rol/ror and unrolling changes, but neither was a win on p4)

Show 7 quoted lines

> However, right now my biggest profile hit is on this irritating loop:
> 
> 	/* Unroll it? */
> 	for (t = 16; t <= 79; t++)
> 		W[t] = SHA_ROL(W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16], 1);
> 
> and I haven't been able to move _that_ into the other iterations yet.

i've done that before -- was a small loss -- maybe because of the small trace cache. deleted that attempt while cleaning up the #if mess, so don't have the patch, but it was basically

#define newW(t) (W[t] = SHA_ROL(W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16], 1))

and than s/W[t]/newW(t)/ in rounds 16..79.

I've only tested on p4 and there the winner so far is still:

-  for (t = 16; t <= 79; t++)
+  for (t = 16; t <= 79; t+=2) {
     ctx->W[t] =
-      SHA_ROT(ctx->W[t-3] ^ ctx->W[t-8] ^ ctx->W[t-14] ^ ctx->W[t-16], 1);
+      SHA_ROT(ctx->W[t-16] ^ ctx->W[t-14] ^ ctx->W[t-8] ^ ctx->W[t-3], 1);
+    ctx->W[t+1] =
+      SHA_ROT(ctx->W[t-15] ^ ctx->W[t-13] ^ ctx->W[t-7] ^ ctx->W[t-2], 1);
+  }

> Here's my micro-optimization update. It does the first 16 rounds (of the 
> first 20-round thing) specially, and takes the data directly from the 
> input array. I'm _this_ close to breaking the 28s second barrier on 
> git-fsck, but not quite yet.

tried this before too -- doesn't help. Not much a of a surprise -- if unrolling didn't help adding another loop (for rounds 17..20) won't.

artur