code review 8853048: runtime/bytes: fast Compare for byte arrays and strings.

runtime/bytes: fast Compare for byte arrays and strings.

Uses SSE instructions to process 16 bytes at a time.

fixes issue 5354

[bradfitz, 2013-04-28 05:40:55]

Using +build tags to keep the strings.goc + bytes Portable implementations for
!amd64 isn't incredibly painful.

[julienschmidt, 2013-04-28 13:09:58]

A few benchmark results:

OLD
BenchmarkCompareBytesEqual               50000000                39.7 ns/op
BenchmarkCompareBytesToNil              500000000                7.04 ns/op
BenchmarkCompareBytesEmpty              200000000                8.22 ns/op
BenchmarkCompareBytesIdentical           50000000                39.8 ns/op
BenchmarkCompareBytesSameLength         100000000                17.8 ns/op
BenchmarkCompareBytesDifferentLength    100000000                17.4 ns/op
BenchmarkCompareBytesBigUnaligned            1000             1245071 ns/op    
842.19 MB/s
BenchmarkCompareBytesBig                     1000             1251071 ns/op    
838.15 MB/s
BenchmarkCompareBytesBigIdentical           2000              1245071 ns/op

TRIVIAL ASM
BenchmarkCompareBytesEqual              100000000                16.6 ns/op
BenchmarkCompareBytesToNil              500000000                4.73 ns/op
BenchmarkCompareBytesEmpty              500000000                4.15 ns/op
BenchmarkCompareBytesIdentical          500000000                4.14 ns/op
BenchmarkCompareBytesSameLength         200000000                9.18 ns/op
BenchmarkCompareBytesDifferentLength    100000000                10.1 ns/op
BenchmarkCompareBytesBigUnaligned            5000              656037 ns/op   
1598.36 MB/s
BenchmarkCompareBytesBig                     5000              664237 ns/op   
1578.63 MB/s
BenchmarkCompareBytesBigIdentical       500000000                3.86 ns/op

SEE ASM
BenchmarkCompareBytesEqual              500000000                7.05 ns/op
BenchmarkCompareBytesToNil              500000000                6.17 ns/op
BenchmarkCompareBytesEmpty              500000000                5.29 ns/op
BenchmarkCompareBytesIdentical          500000000                5.27 ns/op
BenchmarkCompareBytesSameLength         500000000                5.95 ns/op
BenchmarkCompareBytesDifferentLength    500000000                6.46 ns/op
BenchmarkCompareBytesBigUnaligned           20000               79954 ns/op  
13114.77 MB/s
BenchmarkCompareBytesBig                    20000               74904 ns/op  
13999.01 MB/s
BenchmarkCompareBytesBigIdentical       500000000                4.98 ns/op



OLD
len = 1       50000000                40.0 ns/op         349.81 MB/s
len = 2       50000000                39.9 ns/op         351.21 MB/s
len = 4       50000000                39.9 ns/op         351.03 MB/s
len = 8       50000000                39.9 ns/op         351.21 MB/s
len = 16      50000000                56.1 ns/op         498.72 MB/s
len = 32      50000000                75.5 ns/op         555.97 MB/s
len = 64      20000000                 105 ns/op         663.78 MB/s
len = 128     10000000                 187 ns/op         746.62 MB/s
len = 256      5000000                 336 ns/op         791.62 MB/s
len = 512      5000000                 634 ns/op         816.99 MB/s
len = 1024     1000000                1242 ns/op         834.09 MB/s
len = 2048     1000000                2446 ns/op         841.33 MB/s
len = 4096      500000                4842 ns/op         847.12 MB/s
len = 8192      200000                9670 ns/op         848.35 MB/s
len = 16384     100000               19281 ns/op         850.26 MB/s
len = 32768      50000               38502 ns/op         851.22 MB/s
len = 65536      20000               77104 ns/op         850.12 MB/s
len = 131072     10000              153308 ns/op         855.02 MB/s
len = 262144      5000              309817 ns/op         846.14 MB/s
len = 524288      5000              619235 ns/op         846.69 MB/s
len = 1048576     2000             1237570 ns/op         847.29 MB/s

TRIVIAL ASM
len = 1      100000000                16.6 ns/op         843.83 MB/s
len = 2      100000000                16.9 ns/op         827.38 MB/s
len = 4      100000000                16.8 ns/op         832.29 MB/s
len = 8      100000000                16.6 ns/op         841.80 MB/s
len = 16     100000000                28.8 ns/op         972.17 MB/s
len = 32      50000000                47.4 ns/op         885.28 MB/s
len = 64      50000000                67.2 ns/op        1042.23 MB/s
len = 128     20000000                 111 ns/op        1259.49 MB/s
len = 256     10000000                 191 ns/op        1386.78 MB/s
len = 512      5000000                 392 ns/op        1319.33 MB/s
len = 1024     2000000                 749 ns/op        1382.18 MB/s
len = 2048     1000000                1452 ns/op        1417.27 MB/s
len = 4096     1000000                2518 ns/op        1628.98 MB/s
len = 8192      500000                5136 ns/op        1597.26 MB/s
len = 16384     200000               11205 ns/op        1463.01 MB/s
len = 32768     100000               20261 ns/op        1617.58 MB/s
len = 65536      50000               40282 ns/op        1627.22 MB/s
len = 131072     20000               81054 ns/op        1617.21 MB/s
len = 262144     10000              161209 ns/op        1626.15 MB/s
len = 524288      5000              322018 ns/op        1628.17 MB/s
len = 1048576     5000              644436 ns/op        1627.14 MB/s

SEE ASM
len = 1      500000000                7.34 ns/op        1906.73 MB/s
len = 2      500000000                7.28 ns/op        1923.50 MB/s
len = 4      500000000                7.27 ns/op        1926.14 MB/s
len = 8      500000000                7.29 ns/op        1919.80 MB/s
len = 16     200000000                8.40 ns/op        3335.13 MB/s
len = 32     200000000                9.51 ns/op        4416.15 MB/s
len = 64     100000000                11.5 ns/op        6065.51 MB/s
len = 128    100000000                16.7 ns/op        8407.93 MB/s
len = 256    100000000                25.9 ns/op       10273.65 MB/s
len = 512     50000000                45.5 ns/op       11373.97 MB/s
len = 1024    20000000                80.9 ns/op       12805.20 MB/s
len = 2048    20000000                 137 ns/op       14999.14 MB/s
len = 4096    10000000                 249 ns/op       16446.53 MB/s
len = 8192     5000000                 478 ns/os       17147.85 MB/s
len = 16384    2000000                 927 ns/op       17683.99 MB/s
len = 32768    1000000                1925 ns/op       17024.48 MB/s
len = 65536     500000                3824 ns/op       17140.23 MB/s
len = 131072    200000                8035 ns/op       16312.94 MB/s
len = 262144    100000               18701 ns/op       14017.91 MB/s
len = 524288     50000               37442 ns/op       14002.94 MB/s
len = 1048576    20000               74804 ns/op       14017.73 MB/s


I'm really impressed... I'm studying your code now ;-)

[julienschmidt, 2013-04-28 13:12:35]

SEE ASM = SSE ASM (by khr)

[julienschmidt, 2013-04-28 14:00:56]

The amd64 assembly looks fine to me so far

https://codereview.appspot.com/8853048/diff/2001/src/pkg/bytes/bytes_decl.go
File src/pkg/bytes/bytes_decl.go (right):

https://codereview.appspot.com/8853048/diff/2001/src/pkg/bytes/bytes_decl.go#...
src/pkg/bytes/bytes_decl.go:17: 
What about the //go:noescape directive?

[khr, 2013-05-14 18:38:39]

Cleaned up and ready to check in.  Care for a final look?

On 2013/04/28 14:00:56, julienschmidt wrote:
> The amd64 assembly looks fine to me so far
> 
> https://codereview.appspot.com/8853048/diff/2001/src/pkg/bytes/bytes_decl.go
> File src/pkg/bytes/bytes_decl.go (right):
> 
>
https://codereview.appspot.com/8853048/diff/2001/src/pkg/bytes/bytes_decl.go#...
> src/pkg/bytes/bytes_decl.go:17: 
> What about the //go:noescape directive?

[julienschmidt, 2013-05-14 18:57:02]

On 2013/05/14 18:38:39, khr wrote:
> Care for a final look?
Yes.

LGTM

[bradfitz, 2013-05-14 19:06:26]

LGTM



On Tue, May 14, 2013 at 11:38 AM, <khr@golang.org> wrote:

> Reviewers: bradfitz, julienschmidt,
>
> Message:
> Cleaned up and ready to check in.  Care for a final look?
>
> On 2013/04/28 14:00:56, julienschmidt wrote:
>
>> The amd64 assembly looks fine to me so far
>>
>
>
> https://codereview.appspot.**com/8853048/diff/2001/src/pkg/**
>
bytes/bytes_decl.go<https://codereview.appspot.com/8853048/diff/2001/src/pkg/bytes/bytes_decl.go>
>
>> File src/pkg/bytes/bytes_decl.go (right):
>>
>
>
> https://codereview.appspot.**com/8853048/diff/2001/src/pkg/**
>
bytes/bytes_decl.go#newcode17<https://codereview.appspot.com/8853048/diff/2001/src/pkg/bytes/bytes_decl.go#newcode17>
>
>> src/pkg/bytes/bytes_decl.go:**17:
>> What about the //go:noescape directive?
>>
>
>
>
> Description:
> runtime/bytes: fast Compare for byte arrays and strings.
>
> Uses SSE instructions to process 16 bytes at a time.
>
> fixes issue 5354
>
> Please review this at
https://codereview.appspot.**com/8853048/<https://codereview.appspot.com/8853...
>
> Affected files:
>   M src/pkg/bytes/bytes.go
>   M src/pkg/bytes/bytes_decl.go
>   M src/pkg/bytes/bytes_test.go
>   A src/pkg/bytes/compare_test.go
>   M src/pkg/runtime/asm_386.s
>   M src/pkg/runtime/asm_amd64.s
>   A src/pkg/runtime/noasm_arm.goc
>   M src/pkg/runtime/string.goc
>
>
>

[khr, 2013-05-14 23:05:49]

Hello bradfitz@golang.org, google@julienschmidt.com (cc:
golang-dev@googlegroups.com),

I'd like you to review this change to
https://khr%40golang.org@code.google.com/p/go/

[khr, 2013-05-14 23:05:54]

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

runtime/bytes: fast Compare for byte arrays and strings.

Uses SSE instructions to process 16 bytes at a time.

fixes issue 5354

R=bradfitz, google
CC=golang-dev
https://codereview.appspot.com/8853048