code review 19910043: crypto/sha1: Optimise FUNC1 with alternate formulation

crypto/sha1: Optimise FUNC1 with alternate formulation

According to Wikipedia: http://en.wikipedia.org/wiki/SHA-1
there is an alternate formulation for the FUNC1 transform,
namely

f1 = d xor (b and (c xor d))

instead of

f1 = (b and c) or ((not b) and d)

This reduces the instruction count of FUNC1 from 6 to 4 and
makes about 5% speed improvement on amd64 and suprisingly 17%
on 386.

amd64 Intel(R) Core(TM) i7 CPU Q 820 @ 1.73GHz:

benchmark              old ns/op    new ns/op    delta
BenchmarkHash8Bytes          506          499   -1.38%
BenchmarkHash1K             3099         2961   -4.45%
BenchmarkHash8K            22292        21243   -4.71%

benchmark               old MB/s     new MB/s  speedup
BenchmarkHash8Bytes        15.80        16.00    1.01x
BenchmarkHash1K           330.40       345.82    1.05x
BenchmarkHash8K           367.48       385.63    1.05x

i386 Intel(R) Core(TM) i7 CPU Q 820 @ 1.73GHz:

benchmark              old ns/op    new ns/op    delta
BenchmarkHash8Bytes          647          615   -4.95%
BenchmarkHash1K             3673         3161  -13.94%
BenchmarkHash8K            26141        22374  -14.41%

benchmark               old MB/s     new MB/s  speedup
BenchmarkHash8Bytes        12.35        13.01    1.05x
BenchmarkHash1K           278.74       323.94    1.16x
BenchmarkHash8K           313.37       366.13    1.17x

The improvements on an Intel(R) Core(TM) i7-4770K CPU @
3.50GHz were almost identical.

[Nick Craig-Wood, 2013-10-30 19:42:26]

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

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

[r, 2013-10-30 19:47:26]

Thanks but we're in a freeze for the Go 1.2 release. Please refresh this
when 1.2 is out in early December.



On Wed, Oct 30, 2013 at 12:42 PM, <nickcw@gmail.com> wrote:

> Reviewers: golang-dev1,
>
> Message:
> Hello golang-dev@googlegroups.com (cc: rsc@golang.org),
>
> I'd like you to review this change to
> https://code.google.com/p/go
>
>
> Description:
> crypto/sha1: Optimise FUNC1 with alternate formulation
>
> According to Wikipedia:
http://en.wikipedia.org/wiki/**SHA-1<http://en.wikipedia.org/wiki/SHA-1>
> there is an alternate formulation for the FUNC1 transform,
> namely
>
> f1 = d xor (b and (c xor d))
>
> instead of
>
> f1 = (b and c) or ((not b) and d)
>
> This reduces the instruction count of FUNC1 from 6 to 4 and
> makes about 5% speed improvement on amd64 and suprisingly 17%
> on 386.
>
> amd64 Intel(R) Core(TM) i7 CPU Q 820 @ 1.73GHz:
>
> benchmark              old ns/op    new ns/op    delta
> BenchmarkHash8Bytes          506          499   -1.38%
> BenchmarkHash1K             3099         2961   -4.45%
> BenchmarkHash8K            22292        21243   -4.71%
>
> benchmark               old MB/s     new MB/s  speedup
> BenchmarkHash8Bytes        15.80        16.00    1.01x
> BenchmarkHash1K           330.40       345.82    1.05x
> BenchmarkHash8K           367.48       385.63    1.05x
>
> i386 Intel(R) Core(TM) i7 CPU Q 820 @ 1.73GHz:
>
> benchmark              old ns/op    new ns/op    delta
> BenchmarkHash8Bytes          647          615   -4.95%
> BenchmarkHash1K             3673         3161  -13.94%
> BenchmarkHash8K            26141        22374  -14.41%
>
> benchmark               old MB/s     new MB/s  speedup
> BenchmarkHash8Bytes        12.35        13.01    1.05x
> BenchmarkHash1K           278.74       323.94    1.16x
> BenchmarkHash8K           313.37       366.13    1.17x
>
> The improvements on an Intel(R) Core(TM) i7-4770K CPU @
> 3.50GHz were almost identical.
>
> Please review this at
https://codereview.appspot.**com/19910043/<https://codereview.appspot.com/199...
>
> Affected files (+8, -12 lines):
>   M src/pkg/crypto/sha1/sha1block_**386.s
>   M src/pkg/crypto/sha1/sha1block_**amd64.s
>
>
> Index: src/pkg/crypto/sha1/sha1block_**386.s
> ==============================**==============================**=======
> --- a/src/pkg/crypto/sha1/**sha1block_386.s
> +++ b/src/pkg/crypto/sha1/**sha1block_386.s
> @@ -46,12 +46,10 @@
>         ADDL    DI, e
>
>  #define FUNC1(a, b, c, d, e) \
> -       MOVL    b, SI; \
> -       ANDL    c, SI; \
> -       MOVL    b, DI; \
> -       NOTL    DI; \
> -       ANDL    d, DI; \
> -       ORL     SI, DI
> +       MOVL    d, DI; \
> +       XORL    c, DI; \
> +       ANDL    b, DI; \
> +       XORL    d, DI
>
>  #define FUNC2(a, b, c, d, e) \
>         MOVL    b, DI; \
> Index: src/pkg/crypto/sha1/sha1block_**amd64.s
> ==============================**==============================**=======
> --- a/src/pkg/crypto/sha1/**sha1block_amd64.s
> +++ b/src/pkg/crypto/sha1/**sha1block_amd64.s
> @@ -34,12 +34,10 @@
>         MOVL    R10, (((index)&0xf)*4)(SP)
>
>  #define FUNC1(a, b, c, d, e) \
> -       MOVL    b, R8; \
> -       ANDL    c, R8; \
> -       MOVL    b, R9; \
> -       NOTL    R9; \
> -       ANDL    d, R9; \
> -       ORL     R8, R9
> +       MOVL    d, R9; \
> +       XORL    c, R9; \
> +       ANDL    b, R9; \
> +       XORL    d, R9
>
>  #define FUNC2(a, b, c, d, e) \
>         MOVL    b, R9; \
>
>
> --
>
> ---You received this message because you are subscribed to the Google
> Groups "golang-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to
golang-dev+unsubscribe@**googlegroups.com<golang-dev%2Bunsubscribe@googlegrou...
> .
> For more options, visit
https://groups.google.com/**groups/opt_out<https://groups.google.com/groups/o...
> .
>

[hanwen-google, 2013-11-11 15:46:58]

On Wed, Oct 30, 2013 at 8:42 PM,  <nickcw@gmail.com> wrote:
>
> benchmark              old ns/op    new ns/op    delta
> BenchmarkHash8Bytes          506          499   -1.38%
> BenchmarkHash1K             3099         2961   -4.45%
> BenchmarkHash8K            22292        21243   -4.71%
>
> benchmark               old MB/s     new MB/s  speedup
> BenchmarkHash8Bytes        15.80        16.00    1.01x
> BenchmarkHash1K           330.40       345.82    1.05x
> BenchmarkHash8K           367.48       385.63    1.05x
>
> i386 Intel(R) Core(TM) i7 CPU Q 820 @ 1.73GHz:

What is the tool that people use to create these nicely formatted statistics?

-- 
Han-Wen Nienhuys
Google Munich
hanwen@google.com

[rsc, 2013-11-11 15:47:33]

cat oldbenchmarks newbenchmarks | $GOROOT/misc/benchcmp

[Nick Craig-Wood, 2013-12-04 16:25:36]

Hello golang-dev@googlegroups.com, r@golang.org, hanwen@google.com (cc:
golang-dev@googlegroups.com, rsc@golang.org),

Please take another look.

[r, 2013-12-12 19:26:29]

LGTM

[r, 2013-12-12 19:26:45]

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

crypto/sha1: Optimise FUNC1 with alternate formulation

According to Wikipedia: http://en.wikipedia.org/wiki/SHA-1
there is an alternate formulation for the FUNC1 transform,
namely

f1 = d xor (b and (c xor d))

instead of

f1 = (b and c) or ((not b) and d)

This reduces the instruction count of FUNC1 from 6 to 4 and
makes about 5% speed improvement on amd64 and suprisingly 17%
on 386.

amd64 Intel(R) Core(TM) i7 CPU Q 820 @ 1.73GHz:

benchmark              old ns/op    new ns/op    delta
BenchmarkHash8Bytes          506          499   -1.38%
BenchmarkHash1K             3099         2961   -4.45%
BenchmarkHash8K            22292        21243   -4.71%

benchmark               old MB/s     new MB/s  speedup
BenchmarkHash8Bytes        15.80        16.00    1.01x
BenchmarkHash1K           330.40       345.82    1.05x
BenchmarkHash8K           367.48       385.63    1.05x

i386 Intel(R) Core(TM) i7 CPU Q 820 @ 1.73GHz:

benchmark              old ns/op    new ns/op    delta
BenchmarkHash8Bytes          647          615   -4.95%
BenchmarkHash1K             3673         3161  -13.94%
BenchmarkHash8K            26141        22374  -14.41%

benchmark               old MB/s     new MB/s  speedup
BenchmarkHash8Bytes        12.35        13.01    1.05x
BenchmarkHash1K           278.74       323.94    1.16x
BenchmarkHash8K           313.37       366.13    1.17x

The improvements on an Intel(R) Core(TM) i7-4770K CPU @
3.50GHz were almost identical.

R=golang-dev, r, hanwen
CC=golang-dev, rsc
https://codereview.appspot.com/19910043

Committer: Rob Pike <r@golang.org>