code review 7234055: crypto/rc4: add simple amd64 asm implementation.

crypto/rc4: add simple amd64 asm implementation.

(Although it's still half the speed of OpenSSL.)

benchmark           old ns/op    new ns/op    delta
BenchmarkRC4_128         1409          398  -71.75%
BenchmarkRC4_1K         10920         2898  -73.46%
BenchmarkRC4_8K        131323        23083  -82.42%

benchmark            old MB/s     new MB/s  speedup
BenchmarkRC4_128        90.83       321.43    3.54x
BenchmarkRC4_1K         93.77       353.28    3.77x
BenchmarkRC4_8K         61.65       350.73    5.69x

[agl1, 2013-01-29 21:52:45]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com,
jgrahamc@gmail.com),

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

[rsc, 2013-01-29 22:05:31]

LGTM

https://codereview.appspot.com/7234055/diff/5006/src/pkg/crypto/rc4/rc4_amd64.go
File src/pkg/crypto/rc4/rc4_amd64.go (right):

https://codereview.appspot.com/7234055/diff/5006/src/pkg/crypto/rc4/rc4_amd64...
src/pkg/crypto/rc4/rc4_amd64.go:1: // Copyright 2013 The Go Authors. All rights
reserved.
maybe call this file rc4_asm.go and add a // +build amd64, so that if we write
386 asm we don't need a second file here?

https://codereview.appspot.com/7234055/diff/5006/src/pkg/crypto/rc4/rc4_amd64.s
File src/pkg/crypto/rc4/rc4_amd64.s (right):

https://codereview.appspot.com/7234055/diff/5006/src/pkg/crypto/rc4/rc4_amd64...
src/pkg/crypto/rc4/rc4_amd64.s:18: CMPQ CX, $0
You can move this before the loop: tag, since the DECQ CX before the JMP will
set the ZF flag already. Whether it matters is another thing.

https://codereview.appspot.com/7234055/diff/5006/src/pkg/crypto/rc4/rc4_amd64...
src/pkg/crypto/rc4/rc4_amd64.s:34: MOVQ R10, R11
delete and s/R11/R10/ everywhere below?

[remyoudompheng, 2013-01-29 22:19:01]

Can you benchmark against the following simple improvement?
It gives a large boost here, and we have a performance regression from Go 1 in
the compiler due to the disappearance of "sudoaddable".

func (c *Cipher) XORKeyStream(dst, src []byte) {
      i, j := c.i, c.j
      for k, v := range src {
            i += 1
            j += c.s[i]
            c.s[i], c.s[j] = c.s[j], c.s[i]
            dst[k] = v ^ c.s[c.s[i]+c.s[j]]
      }
      c.i, c.j = i, j
}

[agl1, 2013-01-29 22:22:32]

On Tue, Jan 29, 2013 at 5:19 PM,  <remyoudompheng@gmail.com> wrote:
> Can you benchmark against the following simple improvement?
> It gives a large boost here, and we have a performance regression from
> Go 1 in the compiler due to the disappearance of "sudoaddable".
>
> func (c *Cipher) XORKeyStream(dst, src []byte) {
>       i, j := c.i, c.j
>       for k, v := range src {
>             i += 1
>             j += c.s[i]
>             c.s[i], c.s[j] = c.s[j], c.s[i]
>             dst[k] = v ^ c.s[c.s[i]+c.s[j]]
>       }
>       c.i, c.j = i, j
> }

Thanks! I'd like to include that in this change too, but the asm
version is still worthwhile it appears.

Here's the Go code benchmarked on the same machine as I've run everything else:

BenchmarkRC4_128         2000000              1012 ns/op         126.43 MB/s
BenchmarkRC4_1K   500000              8007 ns/op         127.88 MB/s
BenchmarkRC4_8K    50000             67860 ns/op         119.30 MB/s


Cheers

AGL

[agl1, 2013-01-29 22:23:31]

https://codereview.appspot.com/7234055/diff/5006/src/pkg/crypto/rc4/rc4_amd64.go
File src/pkg/crypto/rc4/rc4_amd64.go (right):

https://codereview.appspot.com/7234055/diff/5006/src/pkg/crypto/rc4/rc4_amd64...
src/pkg/crypto/rc4/rc4_amd64.go:1: // Copyright 2013 The Go Authors. All rights
reserved.
On 2013/01/29 22:05:31, rsc wrote:
> maybe call this file rc4_asm.go and add a // +build amd64, so that if we write
> 386 asm we don't need a second file here?

Done.

https://codereview.appspot.com/7234055/diff/5006/src/pkg/crypto/rc4/rc4_amd64.s
File src/pkg/crypto/rc4/rc4_amd64.s (right):

https://codereview.appspot.com/7234055/diff/5006/src/pkg/crypto/rc4/rc4_amd64...
src/pkg/crypto/rc4/rc4_amd64.s:18: CMPQ CX, $0
On 2013/01/29 22:05:31, rsc wrote:
> You can move this before the loop: tag, since the DECQ CX before the JMP will
> set the ZF flag already. Whether it matters is another thing.

I don't know why, but this slows it down.

https://codereview.appspot.com/7234055/diff/5006/src/pkg/crypto/rc4/rc4_amd64...
src/pkg/crypto/rc4/rc4_amd64.s:34: MOVQ R10, R11
On 2013/01/29 22:05:31, rsc wrote:
> delete and s/R11/R10/ everywhere below?

This also slows it down so I've left it for now.

[agl1, 2013-01-30 16:01:28]

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

crypto/rc4: add simple amd64 asm implementation.

(Although it's still half the speed of OpenSSL.)

benchmark           old ns/op    new ns/op    delta
BenchmarkRC4_128         1409          398  -71.75%
BenchmarkRC4_1K         10920         2898  -73.46%
BenchmarkRC4_8K        131323        23083  -82.42%

benchmark            old MB/s     new MB/s  speedup
BenchmarkRC4_128        90.83       321.43    3.54x
BenchmarkRC4_1K         93.77       353.28    3.77x
BenchmarkRC4_8K         61.65       350.73    5.69x

R=rsc, remyoudompheng
CC=golang-dev, jgrahamc
https://codereview.appspot.com/7234055