patch, 7 partsblock-sha1: improved SHA1 hashing

The bulk of this is the patches I sent out yesterday, but there's a few added tweaks from today there, and it's now one nice series instead of a patch followed by a "Haa, I improved on it" etc, so you can get the whole thing without actually having to hunt for the pieces.

It's a series of 7 patches:

      block-sha1: add new optimized C 'block-sha1' routines
      block-sha1: try to use rol/ror appropriately
      block-sha1: make the 'ntohl()' part of the first SHA1 loop
      block-sha1: re-use the temporary array as we calculate the SHA1
      block-sha1: macroize the rounds a bit further
      block-sha1: Use '(B&C)+(D&(B^C))' instead of '(B&C)|(D&(B|C))' in round 3
      block-sha1: get rid of redundant 'lenW' context

where the thing is loosely based on the Mozilla SHA1 routines but by the end doesn't really resemble them all that much. The Mozilla ones suck donkey d*ck in so many ways - unnecessary copies, idiotic byte-at-a-time build-up of the hash input etc.

The end result is pretty much equivalent in performance to the OpenSSL SHA1 code for me on x86-64. Getting rid of OpenSSL gets rid of another couple of shared library loadings, and as a result my "make -j64 test" is now a couple of seconds faster with this than with OpenSSL in my rather unscientific tests.

The code isn't very big:

 Makefile          |    9 +++
 block-sha1/sha1.c |  158 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 block-sha1/sha1.h |   20 +++++++
 3 files changed, 187 insertions(+), 0 deletions(-)
 create mode 100644 block-sha1/sha1.c
 create mode 100644 block-sha1/sha1.h

and passes all my tests. It's really hard to not do the SHA1 right and still pass any tests at all, so it should all be good.

Enable them with BLK_SHA1=1.

		Linus

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Wed, 5 Aug 2009 14:49:32 -0700
Subject: [PATCH 1/7] block-sha1: add new optimized C 'block-sha1' routines

Based ont he mozilla SHA1 routine, but doing the input data accesses a word at a time and with 'htonl()' instead of loading bytes and shifting.

It requires an architecture that is ok with unaligned 32-bit loads and a fast htonl().

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

Side note: we can get rid of the "arch must support unaligned loads" requirement later on by telling the compiler which ones _can_ be unaligned. So the limitations aren't all that fundamental, really.

 Makefile          |    9 +++
 block-sha1/sha1.c |  145 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 block-sha1/sha1.h |   21 ++++++++
 3 files changed, 175 insertions(+), 0 deletions(-)

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Wed, 5 Aug 2009 19:42:15 -0700
Subject: [PATCH 2/7] block-sha1: try to use rol/ror appropriately

Use the one with the smaller constant. It _can_ generate slightly smaller code (a constant of 1 is special), but perhaps more importantly it's possibly faster on any uarch that does a rotate with a loop.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

Ok, this is the hackiest of the bunch. I considered dropping it. But I do suspect we want something like this, even if we might end up massaging the asm for different compilers etc.

 block-sha1/sha1.c |   32 ++++++++++++++++++++++----------
 1 files changed, 22 insertions(+), 10 deletions(-)

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Wed, 5 Aug 2009 20:28:07 -0700
Subject: [PATCH 3/7] block-sha1: make the 'ntohl()' part of the first SHA1 loop

This helps a teeny bit. But what I -really- want to do is to avoid the whole 80-array loop, and do the xor updates as I go along..

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

This is a pretty trivial one, but it was the first stage to getting rid of the annoying 80-word array that not only wastes precious L1 cache, but that loop to initialize it was a noticeable cost.

 block-sha1/sha1.c |   28 ++++++++++++++++------------
 1 files changed, 16 insertions(+), 12 deletions(-)

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Wed, 5 Aug 2009 20:49:41 -0700
Subject: [PATCH 4/7] block-sha1: re-use the temporary array as we calculate the SHA1

The mozilla-SHA1 code did this 80-word array for the 80 iterations. But the SHA1 state is really just 512 bits, and you can actually keep it in a kind of "circular queue" of just 16 words instead.

This requires us to do the xor updates as we go along (rather than as a pre-phase), but that's really what we want to do anyway.

This gets me really close to the OpenSSL performance on my Nehalem. Look ma, all C code (ok, there's the rol/ror hack, but that one doesn't strictly even matter on my Nehalem, it's just a local optimization).

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

This gets rid of the annoying pre-initialization and its need for that extra space. We can dynamically iterate over a 512-bit circular buffer instead.

 block-sha1/sha1.c |   28 ++++++++++++++++------------
 1 files changed, 16 insertions(+), 12 deletions(-)

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Thu, 6 Aug 2009 07:20:54 -0700
Subject: [PATCH 5/7] block-sha1: macroize the rounds a bit further

Avoid repeating the shared parts of the different rounds by adding a macro layer or two. It was already more cpp than C.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

This makes things denser, and puts all the core rules in one place. That first hunk really contains just about all of the important parts of SHA1. The rest is just fluff and the necessary expansions etc.

 block-sha1/sha1.c |   56 ++++++++++++++++++++++++----------------------------
 1 files changed, 26 insertions(+), 30 deletions(-)

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Thu, 6 Aug 2009 07:27:57 -0700
Subject: [PATCH 6/7] block-sha1: Use '(B&C)+(D&(B^C))' instead of '(B&C)|(D&(B|C))' in round 3

It's an equivalent expression, but the '+' gives us some freedom in instruction selection (for example, we can use 'lea' rather than 'add'), and associates with the other additions around it to give some minor scheduling freedom.

Suggested-by: linux@horizon.com
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

A small micro-optimization. It may not matter hugely, but it's definitely the right thing to do. And with the new macroized thing, you can see clearly what part of the SHA1 rounds it affects, and how.

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

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Thu, 6 Aug 2009 07:45:46 -0700
Subject: [PATCH 7/7] block-sha1: get rid of redundant 'lenW' context

.. and simplify the ctx->size logic.

We now count the size in bytes, which means that 'lenW' was always just the low 6 bits of the total size, so we don't carry it around separately any more. And we do the 'size in bits' shift at the end.

Suggested by Nicolas Pitre and linux@horizon.com.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

Some final cleanup. Based on two separate discussions yesterday. Trivial and doesn't make any difference that I can tell, but definitely the right thing to do.

 block-sha1/sha1.c |   17 +++++++----------
 block-sha1/sha1.h |    1 -
 2 files changed, 7 insertions(+), 11 deletions(-)

Hi,

On Thu, Aug 6, 2009 at 17:16, Linus Torvalds<torvalds@linux-foundation.org> wrote:

I suspect, this should be: #define SHA_ROT(X,l.r) (((X) << (l)) | ((X) >> (r)))

Bert

Linus Torvalds wrote:

For those curious just how close the C version is to the various asm and C implementations, the q&d microbenchmark is at http://www.src.multimo.pl/YDpqIo7Li27O0L0h/sha1bench.tar.gz

In short: 88% of openssl speed on P3, 42% on P4, 66% on Atom.

artur

On Thu, 6 Aug 2009, Artur Skawina wrote:

Hmm. That thing doesn't work at all on x86-64. Even apart from the asm sources, your timing thing does soem really odd things (why do you do that odd "iret" in GETCYCLES and GETTIME?). You're better off using lfence/mfence/cpuid, and I think you could make it work on 64-bit that way too.

I just hacked it away for testing.

I'll use this to see if I can improve the 32-bit case.

On Nehalem, with your benchmark, I get:

	#             TIME[s] SPEED[MB/s]
	rfc3174         5.122       119.2
	# New hash result: d829b9e028e64840094ab6702f9acdf11bec3937
	rfc3174         5.153       118.5
	linus           2.092       291.8
	linusas         2.056       296.8
	linusas2        1.909       319.8
	mozilla         5.139       118.8
	mozillaas       5.775       105.7
	openssl         1.627       375.1
	spelvin         1.678       363.7
	spelvina        1.603       380.8
	nettle          1.592       383.4

And with the hacked version to get some 64-bit numbers:

	#             TIME[s] SPEED[MB/s]
	rfc3174         3.992       152.9
	# New hash result: b78fd74c0033a4dfe0ededccb85ab00cb56880ab
	rfc3174         3.991       152.9
	linus            1.54       396.3
	linusas         1.533       398.1
	linusas2        1.603       380.9
	mozilla         4.352       140.3
	mozillaas       4.227       144.4

so as you can see, your improvements in 32-bit mode are actually de-provements in 64-bit mode (ok, your first one seems to be a tiny improvement, but I think it's in the noise).

But you're right, I need to try to improve the 32-bit case.

			Linus

Linus Torvalds wrote:

yes, it's 32-bit only, i should have mentioned that. The timing code was written more than a decade ago, it really works on p2, haven't updated it, it's all just c&p'ed ever since. All of it can be safely disabled; on p2 you could account for every cycle, nowadays gettimeofday is more than enough.

Actually i didn't keep anything that wasn't a win, one reason why linusas2 stayed was that it really surprised me, i'd have expected for gcc to do a lot worse w/ the many temporaries and the compiler came up w/ a 70% gain; gcc really must have improved when i wasn't looking.

I never said anything like that. :) there probably isn't all that much that can be done. I tried a few things, but never saw any improvement above measurement noise (a few percent). Would have though that overlapping the iterations a bit would be a gain, but that didn't do much (-20%..0), maybe on 64 bit, with more registers...

Oh, i noticed that '-mtune' makes quite a difference, it can change the relative performance of the functions significantly, in unobvious ways; depending on which cpu gcc tunes for (build config or -mtune); some implementations slow down, others become a bit faster.

artur

On Thu, 6 Aug 2009, Artur Skawina wrote:

That probably is mainly true for P4, although it's quite possible that it has an effect for just what the register allocator does, and then for spilling.

And it looks like _all_ the tweakability is in the spilling. Nothing else matters.

How does this patch work for you? It avoids doing that C-level register rotation, and instead rotates the register names with the preprocessor.

I realize it's ugly as hell, but it does make it easier for gcc to see what's going on.

The patch is against my git patches, but I think it should apply pretty much as-is to your sha1bench sources too. Does it make any difference for you?

		Linus

---
 block-sha1/sha1.c |  117 ++++++++++++++++++++++++++++++++++++++++------------
 1 files changed, 90 insertions(+), 27 deletions(-)

Linus Torvalds wrote:

it's a bit slower (P4):

before: linus 0.6288 97.06 after: linus 0.6604 92.42

i was trying similar things, like the example below, too, but it wasn't a win on 32 bit...

artur

[the iteration below is functionally correct, but scheduling is most likely
 fubared as it wasn't a win and i was checking how much a difference it made
 on P4 -- ~-20..~0%, but never faster (relative to linusas2; it _is_ faster
 than 'linus'. Dropped this version when merging your new preprocessor macros.]

On Thu, 6 Aug 2009, Artur Skawina wrote:

Hmm. Ok, I just tested with your harness, and I get

	#             TIME[s] SPEED[MB/s]
	rfc3174           5.1       119.7
	rfc3174         5.097       119.7
	linus           1.836       332.5
	linusas         2.006       304.3
	linusas2        1.879       324.9
	mozilla         5.562       109.7
	mozillaas       5.913       103.2
	openssl         1.613       378.5
	spelvin         1.698       359.5
	spelvina        1.602         381
	nettle          1.594       382.9

with it, so it is faster for me. So your slowdown seems to be yet another P4 thing. Dang crazy micro-architecture.

Of course, it might be a compiler version difference too. I'm using gcc-4.4.0.

With the cpp variable renaming, the compiler really has less to be smart about, but spill decisions will still matter a lot.

(My old 32-bit numbers were 

        linus           2.092       291.8

so it's a clear improvement on my machine and with my compiler).

It also seems to improve the 64-bit numbers a small bit, I'm getting

	#             TIME[s] SPEED[MB/s]
	rfc3174          3.98       153.3
	rfc3174         3.972       153.7
	linus           1.514       403.1
	linusas         1.555       392.6
	linusas2        1.599       381.7
	mozilla          4.34       140.6
	mozillaas       4.223       144.5

with my 64-bit compile, so on a Nehalem it's the best one of the C ones by a noticeable margin. (My original 64-bit numbers were

        linus            1.54       396.3

and while the numbers seem to fluctuate a bit, the fluctuation is roughly in the 1% range, so that improvement seems to be statistically significant.

Oh, I did make a small change, but I doubt it matters. Instead of doing

	TEMP += E + SHA_ROL(A,5) + (fn) + (constant); \
	B = SHA_ROR(B, 2); E = TEMP; } while (0)

I now do

	E += TEMP + SHA_ROL(A,5) + (fn) + (constant); \
	B = SHA_ROR(B, 2); } while (0)

which is a bit more logical (the old TEMP usage was just due to a fairly mindless conversion). That _might_ have lower register pressure if the compiler is silly enough to not notice that it can do it. Maybe that matters.

			Linus

On Thu, 6 Aug 2009, Linus Torvalds wrote:

On atom, I get things like:

	#             TIME[s] SPEED[MB/s]
	rfc3174         2.186       27.92
	rfc3174         2.186       27.92
	linus          0.9492        64.3
	linusas        0.9656       63.21
	linusas2        1.012       60.29
	mozilla         2.492       24.49
	mozillaas         2.5       24.41
	openssl        0.6411        95.2
	spelvin        0.6052       100.8
	spelvina       0.6655       91.71
	nettle         0.7149       85.37

but quite frankly, those timings aren't stable enough to say anything. Another few runs got me:

	#             TIME[s] SPEED[MB/s]
	rfc3174         2.207       27.65
	rfc3174          2.21       27.62
	linus           1.022       59.74
	linusas         1.058        57.7
	linusas2        1.008       60.58
	mozilla         2.485       24.56
	mozillaas       2.522        24.2
	openssl        0.6421       95.06
	spelvin        0.5989       101.9
	spelvina       0.6638       91.94
	nettle         0.7132       85.58

	#             TIME[s] SPEED[MB/s]
	rfc3174         2.224       27.44
	rfc3174         2.205       27.68
	linus          0.9727       62.75
	linusas        0.9766        62.5
	linusas2        1.026        59.5
	mozilla          2.52       24.22
	mozillaas       2.547       23.96
	openssl        0.6459        94.5
	spelvin        0.6074       100.5
	spelvina       0.6751       90.41
	nettle         0.7254       84.14

so whatever differences there are between linus*, they seem to be in the noise, and the hand-scheduled asm beats all the C versions senseless.

I'd like to get closer to the hand-tuned ones, but I don't see anything to do any more. It's all about gcc register choice and avoiding spilling. So compiler flags changing small details can have _huge_ differences in performance. Here's the Atom numbers with gcc given the "-Os" flag (just because I wanted to try):

	linus           1.072       56.94
	linusas        0.9573       63.76
	linusas2       0.9906       61.61

Why did 'linus' numbers go down? No idea. With -O3, it's the other way around:

	linus          0.9537          64
	linusas        0.9566        63.8
	linusas2        1.013       60.26

but again, there's variation enough that I'd probabyl need to run ten runs just to see how much is noise. But the "linusas2 sucks with -O3" is clear, as is the "linus sucks with -Os" thing. Very odd, and very random.

		Linus

Linus Torvalds wrote:

gcc version 4.4.1 20090603 (prerelease)

before: linus 0.6622 92.17 after: linus 0.6631 92.05 after: linus 0.6601 92.46 after: linus 0.6624 92.14

IOW, no difference, just noise.

Artur Skawina wrote:

Just to check, i did this: 

diff -urNp sha1bench-linus.org/block-sha1/sha1.c sha1bench-linus/block-sha1/sha1.c --- sha1bench-linus.org/block-sha1/sha1.c 2009-08-06 23:26:15.607321815 +0200 +++ sha1bench-linus/block-sha1/sha1.c 2009-08-06 23:41:36.858325807 +0200

On Thu, 6 Aug 2009, Artur Skawina wrote:

Nope. If anything, it's bit slower, but it might be in the noise. I generally got 330MB/s with my "cpp renaming" on Nehalem (32-bit - the 64-bit numbers are ~400MB/s), but with this I got 325MB/s twice in a row, which matches the linusas2 numbers pretty exactly.

But it seems to make a big difference for you.

Btw, _what_ P4 do you have (Northwood or Prescott)?

The Intel optimization manuals very much talk about avoiding rotates. And they mention "with a CPUID signature corresponding to family 15 and model encoding of 0, 1, or 2" specifically as being longer latency. That's basically pre-prescott P4, I think.

Anyway, on P4 I think you have two double-speed integer issue ports (ie max four ops per cycle), but only one of them takes a rotate, and only in the first half of the cycle (ie just one shift per cycle).

And afaik, that is actually the _improved_ state in Prescott. The older P4's didn't have a full shifter unit at all, iirc: shifts were "complex instructions" in Northwood and weren't even single-clock.

In Core 2, I think there's still just one shifter unit, but at least it's as fast as all the other units. So P4 really does stand out as sucking as far as shifts are concerned, and if you have an older P4, it will be even worse.

		Linus

On Thu, 6 Aug 2009, Linus Torvalds wrote:

Yeah, verified. Google for

	northwood "barrel shifter"

and you'll find a lot of it.

Basically, older P4's will I think shift one bit at a time. So while even Prescott is relatively weak in the shifter department, pre-prescott (Willamette and Northwood) are _really_ weak. If your P4 is one of those, you really shouldn't use it to decide on optimizations.

		Linus

Linus Torvalds wrote:

Actually that's even more of a reason to make sure the code doesn't suck :) The difference on less perverse cpus will usually be small, but on P4 it can be huge.

A few years back I found my old ip checksum microbenchmark, and when I ran it on a P4 (prescott iirc) i didn't believe my eyes. The straightforward 32-bit C implementation was running circles around the in-kernel one... And a few tweaks to the assembler version got me another ~100% speedup.[1]

After that the P4 became the very first cpu to test any code on... :)

artur

[1] just reran the benchmark on this p4; true on northwood too:

IACCK 0.9.30  Artur Skawina <...>
[ exec time; lower is better  ] [speed ] [ time ]  [ok?]
TIME-N+S TIME32 TIME33 TIME1480 MBYTES/S TIMEXXXX  CSUM FUNCTION ( rdtsc_overhead=0  null=0 )
   17901    510    557     3010   393.36    59772  56dd csum_partial_cdumb16
    3019    154    156      431  2747.10    43106  56dd csum_partial_c32
    2413    170    177      328  3609.76    37501  56dd csum_partial_c32l
    2437    170    170      328  3609.76    37488  56dd csum_partial_c32i
    5078    205    254      767  1543.68    48117  56dd csum_partial_std
    5612    299    291      851  1391.30    53673  56dd csum_partial_686
    1584     99    127      227  5215.86    14495  56dd csum_partial_586f
    1738    107    121      229  5170.31    14785  56dd csum_partial_586fs
    4893    175    171      759  1559.95    52347  56dd csum_partial_copy_generic_std
    4949    151    189      756  1566.14    67847  56dd csum_partial_copy_generic_686
    2072    110    134      302  3920.53    39061  56dd csum_partial_copy_generic_p4as1

On Fri, 7 Aug 2009, Artur Skawina wrote:

No. First off, the things you have to do on P4 are just insane. See the email I just sent out asking you to test whether two 1-bit rotates might be faster than 1 2-bit rotate.

So optimizing for P4 is often the wrong thing.

Secondly, P4's are going away. You may have one, but they are getting rare. So optimizing for them is a losing proposition in the long run.

Yeah, not very surprising. The P4 is very good at the simplest possible kind of code that does _nothing_ fancy.

But then it completely chokes on some code. I mean _totally_. It slows down by a huge amount if there is anything but the most trivial kinds of instructions. And by "trivial", I mean _really_ trivial. Shifts (as in SHA1), but iirc also things like "adc" (add with carry) etc.

So it's not hard to write code that works well on other uarchs, and then totally blow up on P4. I think it doesn't rename the flags at all, so any flag dependency (carry being the most common one) will stall things horrible.

There's also a very subtle store forwarding failure thing (and a lot of other events) that causes a nasty micro-architectural replay trap, and again you go from "running like a bat out of hell" to "slower than a i486 at a tenth the frequency".

Really. It's disgusting. Perfectly fine code can run really slowly on the P4 just because it hits some random internal micro-architectural flaw. And there's a _lot_ of those "glass jaw" issues.

The best way to avoid them is to use _only_ simple ALU instructions (add, sub, and/or/not), and to be _very_ careful with loads and stores.

		Linus

Linus Torvalds wrote:

It seems to do well on P2 and P4 here, if it works for core2 this could be a good generic candidate. It only does 62% on an Atom, but the best C version so far exceeds it only by ~2%.

northwood

cpu family : 15 model : 2 model name : Intel(R) Pentium(R) 4 CPU 2.80GHz stepping : 5

hmm, I might be able to try it on some old willamette, but my prescott's mobo died, so i can't verify that right now.

I'll upload an updated sha1bench, maybe somebody else feels like checking...

artur 

On Fri, 7 Aug 2009, Artur Skawina wrote:

I think willamette and northwood are basically the same wrt shifters (and pretty much everything else too, for that matter). I think northwood is a shrink, and had an increased cache size (and higher frequencies). But I think core-wise, they're very similar.

It was prescott that changed a lot (mostly for the worse - the shifter was one of the few upsides of prescott, although increased frequency often made up for the downsides).

		Linus

On Thu, 6 Aug 2009, Linus Torvalds wrote:

Anyway, since you have a Northwood, I bet that the #1 issue for you is to spread out the shift instructions in a way that simply doesn't matter anywhere else.

In netburst, if I remember the details correcty, a "complex instruction" will basically get the trace cache from the microcode roms. I'm not sure how it interacts with the TC entries around it, but it's entirely possible that it basically disables any instruction scheduling (the microcode traces are presumably "pre-scheduled"), so you'd basically see stalls where there's little out-of-order execution.

That then explains why you see huge differences from what is basically trivial scheduling decisions, and why some random placement of a shift makes a big difference.

Just out of curiosity, does anything change if you change the

	B = SHA_ROR(B,2)

into a

	B = SHA_ROR(SHA_ROR(B,1),1)

instead? It's very possible that it becomes _much_ worse, but I guess it's also possible in theory that a single-bit rotate ends up being a simple instruction and that doing two single-bit ROR's is actually faster than one 2-bit ROR (assuming the second one is microcoded and the first one).

In particular, I'm thinking about the warnign in the intel optimization manual:

	The rotate by immediate and rotate by register instructions are 
	more expensive than a shift. The rotate by 1 instruction has the 
	same latency as a shift.

so it's very possible that "rotate by 1" is much better than other rotates.

			Linus

On Thu, 6 Aug 2009, Linus Torvalds wrote:

Hmm. Probably not. Googling more seems to indicate that rotates and shifts have a fixed 4-cycle latency on Northwood. I'm not seeing anything that indicates that a single-bit rotate/shift would be any faster.

(And remember, if 4 cycles doesn't sound so bad: that's enough of a latency to do _16_ "simple" ALU's, since they can be double-pumped in the two regular ALU's).

I think long-running ALU ops that feed into a store (spill) also happen to be the thing that makes the dreaded store-buffer replay trap nasties happen more (load vs store scheduled badly, and then you end up spending tens of cycles just replaying).

			Linus

Linus Torvalds wrote:

looking at the generated code, there is a lot of ro[rl] movement, so it's likely that contributes to the problem.

I also see 44 extra lea instructions, 44 less adds and changes like:
        [...]
        mov    XX(%eRX),%eRX
        xor    XX(%eRX),%eRX
-       and    %eRX,%eRX
+       and    XX(%eRX),%eRX
        xor    XX(%eRX),%eRX
-       add    %eRX,%eRX
-       ror    $0x2,%eRX
-       mov    %eRX,XX(%eRX)
+       lea    (%eRX,%eRX,1),%eRX
        mov    XX(%eRX),%eRX
        bswap  %eRX
        mov    %eRX,XX(%eRX)
        mov    %eRX,%eRX
+       ror    $0x2,%eRX
+       mov    %eRX,XX(%eRX)
+       mov    %eRX,%eRX
        rol    $0x5,%eRX
        mov    XX(%eRX),%eRX
-       mov    XX(%eRX),%eRX
        [...]
which could mean that gcc did a better job of register allocation
(where "better job" might be just luck).

artur

On Fri, 7 Aug 2009, Artur Skawina wrote:

add and lea (as long as the lea shift is 1) should be the same on a P4 (they are not the same on some other microarchitectures and lea can have address generation stalls etc).

Lea, of course, gives the potential for register movement at the same time (three-address op), and that's likely the reason for lea-vs-adds.

Yeah, different spill patterns. That's the biggest issue, I think.

In particular, on P4, with unlucky spills, you may end up with things like

	ror $2,reg
	mov reg,x(%esp)
	.. a few instructions ..
	xor x(%esp), reg

and the above is exactly when one of the worst P4 problems hit: a store, followed a few cycles later by a load from the same address (and "a few cycles later" can be quite a few instructions if they are the nice ones).

What can happen is that if the store data isn't ready yet (because it comes from a long-latency op like a shift or a multiply), then you hit a store buffer replay thing. The P4 (with its long pipeline) basically starts the load speculatively, and if anything bad happens for the load (L1 cache miss, TLB miss, store buffer fault, you name it), it will cause a replay of the whole pipeline.

Which can take tens of cycles. 

[ That said, it's been a long time since I did a lot of P4 worrying. So I 
  may mis-remember the details. But that whole store buffer forwarding had 
  some really nasty replay issues ]

I suspect that's the biggest issue. Just _happening_ to get the spills so that they don't hurt. And with unlucky scheduling, you might hit some of the P4 replay issues every single time.

There are some P4 optimizations that are simple:
 - avoid complex instructions
 - don't blow the trace cache
 - predictable branches
but the replay faults can really get you.

			Linus

Linus Torvalds wrote:

Did try that yesterday, didn't help. Will recheck now.. yep:

before: linus 0.3554 171.7 after: linus 0.407 150

still true for the current version.

Sure, no argument; it's just that avoiding the P4 pitfalls is usually not that hard and the impact on other, non-netburst, archs is low. There are a lot of P4s out there and they're not going away soon. (i'm still keeping most of my git trees on a P3...)

For generic C code such as this the difference for your i7 was -2% and +70% for my P4; all the other (but one, i think) optimizations which worked on P4 also applied to 32-bit i7. As i happen to have a p4 i can just as well test the code on it, many improvements will likely apply to other cpus too. That's all, i doubt anybody seriously considered "optimizing for P4"; there is a reason intel discontinued them :)

The atom is a more important target, but only the asm versions did well there so far.

artur

On Thu, 6 Aug 2009, Linus Torvalds wrote:

I actually found a P4 I have access to, except that one is a Prescott.

And I can't run it in 32-bit mode, because I only have a regular user login, and it only has the 64-bit development environment.

But I can do the hacked-for-64bit sha1bench runs, and I tested your patch.

It's horrible.

Here's the plain "linus" baseline (ie the "Do register rotation in cpp") thing, with the fixed "E += TEMP .." thing):

	#             TIME[s] SPEED[MB/s]
	rfc3174         1.648       37.03
	rfc3174         1.677        36.4
	linus          0.4018       151.9
	linusas        0.4439       137.5
	linusas2       0.4381       139.3
	mozilla        0.9587       63.66
	mozillaas      0.9434        64.7

and here it is with your patch:

	#             TIME[s] SPEED[MB/s]
	rfc3174         1.667       36.61
	rfc3174         1.644       37.12
	linus          0.4653       131.2
	linusas        0.4412       138.3
	linusas2       0.4388       139.1
	mozilla        0.9466       64.48
	mozillaas      0.9449       64.59

(ok, so the numbers aren't horribly stable, but the "plain linus" thing consistently outperforms here - and underperforms with your patch).

However, note that since this is the 64-bit thing, there likely aren't any spill issues, but it's simply an issue of "just how did the array[] accesses get scheduled" etc. And since this is a Prescott (or rather "Xeon") P4, the shifter isn't quite as horrible as yours is. _And_ this is a different gcc version (4.0.3).

So the numbers aren't really all that comparable. It's more an example of "optimizing for P4 is futile, because you're just playing with total randomness". That's like a 20MB/s difference, just from moving a few ALU ops around a bit.

And it's entirely possible that if I had gcc-4.4 on that machine, your patch would magically do the right thing ;)

Sadly, that machine is just a ssh gateway, so there's no real development tools on it at all - no way to get good profiles etc. So I can't really say exactly what the problem pattern is :(

		Linus

Linus Torvalds wrote:

Well, I'd be surprised if one C version would always be the winner on every single cpu; that 13% loss[1] I think would be an acceptable compromise, if the goal is to have one implementation that does reasonably well on all cpus.

That's why i asked how the change did on nehalem; if it's a measurable loss on anything modern (core2+), then of course the P4s must suffer; and one could always blame the compiler ;) It's not like the difference in sha1 overhead will be noticeable in normal git use.

artur

[1] I suspect the old gcc is a factor (4.0.4 does <100M/s here).

On Sat, 8 Aug 2009, Artur Skawina 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.

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(-)

Linus Torvalds wrote:

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'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:

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:

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:

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

Artur Skawina wrote:

and w/ this on top: