code review 7547050: crypto/rc4: faster amd64, 386 implementations

crypto/rc4: faster amd64, 386 implementations

-- amd64 --

On a MacBookPro10,2 (Core i5):

benchmark           old ns/op    new ns/op    delta
BenchmarkRC4_128          470          421  -10.43%
BenchmarkRC4_1K          3123         3275   +4.87%
BenchmarkRC4_8K         26351        25866   -1.84%

benchmark            old MB/s     new MB/s  speedup
BenchmarkRC4_128       272.22       303.40    1.11x
BenchmarkRC4_1K        327.80       312.58    0.95x
BenchmarkRC4_8K        307.24       313.00    1.02x

For comparison, on the same machine, openssl 0.9.8r reports
its rc4 speed as somewhat under 350 MB/s for both 1K and 8K.
The Core i5 performance can be boosted another 20%, but only
by making the Xeon performance significantly slower.

On an Intel Xeon E5520:

benchmark           old ns/op    new ns/op    delta
BenchmarkRC4_128          774          417  -46.12%
BenchmarkRC4_1K          6121         3200  -47.72%
BenchmarkRC4_8K         48394        25151  -48.03%

benchmark            old MB/s     new MB/s  speedup
BenchmarkRC4_128       165.18       306.84    1.86x
BenchmarkRC4_1K        167.28       319.92    1.91x
BenchmarkRC4_8K        167.29       321.89    1.92x

For comparison, on the same machine, openssl 1.0.1
(which uses a different implementation than 0.9.8r)
reports its rc4 speed as 587 MB/s for 1K and 601 MB/s for 8K.
It is using SIMD instructions to do more in parallel.

So there's still some improvement to be had, but even so,
this is almost 2x faster than what it replaced.

-- 386 --

On a MacBookPro10,2 (Core i5):

benchmark           old ns/op    new ns/op    delta
BenchmarkRC4_128         3491          421  -87.94%
BenchmarkRC4_1K         28063         3205  -88.58%
BenchmarkRC4_8K        220392        25228  -88.55%

benchmark            old MB/s     new MB/s  speedup
BenchmarkRC4_128        36.66       303.81    8.29x
BenchmarkRC4_1K         36.49       319.42    8.75x
BenchmarkRC4_8K         36.73       320.90    8.74x

On an Intel Xeon E5520:

benchmark           old ns/op    new ns/op    delta
BenchmarkRC4_128         2268          524  -76.90%
BenchmarkRC4_1K         18161         4137  -77.22%
BenchmarkRC4_8K        142396        32350  -77.28%

benchmark            old MB/s     new MB/s  speedup
BenchmarkRC4_128        56.42       244.13    4.33x
BenchmarkRC4_1K         56.38       247.46    4.39x
BenchmarkRC4_8K         56.86       250.26    4.40x

[rsc, 2013-03-21 05:30:57]

Hello agl@golang.org (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://code.google.com/p/go/

[agl1, 2013-03-21 11:11:59]

This seems to fix an issue with the old amd64 asm on older Intel CPUs, so LGTM.

https://codereview.appspot.com/7547050/diff/16001/src/pkg/crypto/rc4/rc4_386.s
File src/pkg/crypto/rc4/rc4_386.s (right):

https://codereview.appspot.com/7547050/diff/16001/src/pkg/crypto/rc4/rc4_386....
src/pkg/crypto/rc4/rc4_386.s:1: // Copyright 2013 The Go Authors. All rights
reserved.
This looks like a port of the old amd64 code. If mercurial can be convinced that
it's a copy without too much effort, that would be nice, but not important.

[rsc, 2013-03-21 13:51:21]

On Thu, Mar 21, 2013 at 7:11 AM, <agl@golang.org> wrote:

> This seems to fix an issue with the old amd64 asm on older Intel CPUs,
> so LGTM.
>

By an issue do you mean performance? The magic word to unlock the Xeon was
the no-op MOVBLZX (aka EXTEND macro). If I just add those to the original
that you wrote, that's enough to get something like 1.5x. But the new
version also does one-round-early loads, which gives the rest of the almost
2x.

Russ

[agl1, 2013-03-21 14:25:07]

On Thu, Mar 21, 2013 at 9:51 AM, Russ Cox <rsc@golang.org> wrote:
> By an issue do you mean performance? The magic word to unlock the Xeon was
> the no-op MOVBLZX (aka EXTEND macro). If I just add those to the original
> that you wrote, that's enough to get something like 1.5x. But the new
> version also does one-round-early loads, which gives the rest of the almost
> 2x.

Yes. The "MacBookPro10,2" appears to be an Ivy Bridge core and the
difference is small. But it's doing much better on the Nehalem core in
the E5520.


Cheers

AGL

[rsc, 2013-03-21 15:25:15]

*** Submitted as https://code.google.com/p/go/source/detail?r=97e26e028a6e ***

crypto/rc4: faster amd64, 386 implementations

-- amd64 --

On a MacBookPro10,2 (Core i5):

benchmark           old ns/op    new ns/op    delta
BenchmarkRC4_128          470          421  -10.43%
BenchmarkRC4_1K          3123         3275   +4.87%
BenchmarkRC4_8K         26351        25866   -1.84%

benchmark            old MB/s     new MB/s  speedup
BenchmarkRC4_128       272.22       303.40    1.11x
BenchmarkRC4_1K        327.80       312.58    0.95x
BenchmarkRC4_8K        307.24       313.00    1.02x

For comparison, on the same machine, openssl 0.9.8r reports
its rc4 speed as somewhat under 350 MB/s for both 1K and 8K.
The Core i5 performance can be boosted another 20%, but only
by making the Xeon performance significantly slower.

On an Intel Xeon E5520:

benchmark           old ns/op    new ns/op    delta
BenchmarkRC4_128          774          417  -46.12%
BenchmarkRC4_1K          6121         3200  -47.72%
BenchmarkRC4_8K         48394        25151  -48.03%

benchmark            old MB/s     new MB/s  speedup
BenchmarkRC4_128       165.18       306.84    1.86x
BenchmarkRC4_1K        167.28       319.92    1.91x
BenchmarkRC4_8K        167.29       321.89    1.92x

For comparison, on the same machine, openssl 1.0.1
(which uses a different implementation than 0.9.8r)
reports its rc4 speed as 587 MB/s for 1K and 601 MB/s for 8K.
It is using SIMD instructions to do more in parallel.

So there's still some improvement to be had, but even so,
this is almost 2x faster than what it replaced.

-- 386 --

On a MacBookPro10,2 (Core i5):

benchmark           old ns/op    new ns/op    delta
BenchmarkRC4_128         3491          421  -87.94%
BenchmarkRC4_1K         28063         3205  -88.58%
BenchmarkRC4_8K        220392        25228  -88.55%

benchmark            old MB/s     new MB/s  speedup
BenchmarkRC4_128        36.66       303.81    8.29x
BenchmarkRC4_1K         36.49       319.42    8.75x
BenchmarkRC4_8K         36.73       320.90    8.74x

On an Intel Xeon E5520:

benchmark           old ns/op    new ns/op    delta
BenchmarkRC4_128         2268          524  -76.90%
BenchmarkRC4_1K         18161         4137  -77.22%
BenchmarkRC4_8K        142396        32350  -77.28%

benchmark            old MB/s     new MB/s  speedup
BenchmarkRC4_128        56.42       244.13    4.33x
BenchmarkRC4_1K         56.38       247.46    4.39x
BenchmarkRC4_8K         56.86       250.26    4.40x

R=agl
CC=golang-dev
https://codereview.appspot.com/7547050

https://codereview.appspot.com/7547050/diff/16001/src/pkg/crypto/rc4/rc4_386.s
File src/pkg/crypto/rc4/rc4_386.s (right):

https://codereview.appspot.com/7547050/diff/16001/src/pkg/crypto/rc4/rc4_386....
src/pkg/crypto/rc4/rc4_386.s:1: // Copyright 2013 The Go Authors. All rights
reserved.
On 2013/03/21 11:11:59, agl1 wrote:
> This looks like a port of the old amd64 code. If mercurial can be convinced
that
> it's a copy without too much effort, that would be nice, but not important.

Done. (Thought I'd already done it but maybe Mercurial forgot somehow.)