code review 105280044: runtime: implement eqstring in assembly.

runtime: implement eqstring in assembly.

BenchmarkCompareStringEqual               10.4          7.33          -29.52%
BenchmarkCompareStringIdentical           3.99          3.67          -8.02%
BenchmarkCompareStringSameLength          9.80          6.84          -30.20%
BenchmarkCompareStringDifferentLength     1.09          0.95          -12.84%
BenchmarkCompareStringBigUnaligned        75220         76071         +1.13%
BenchmarkCompareStringBig                 69843         74746         +7.02%

[khr, 2014-06-17 00:12:26]

Hello golang-codereviews@googlegroups.com,

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

[bradfitz, 2014-06-17 00:16:36]

LGTM



On Mon, Jun 16, 2014 at 5:12 PM, <khr@golang.org> wrote:

> Reviewers: golang-codereviews,
>
> Message:
> Hello golang-codereviews@googlegroups.com,
>
> I'd like you to review this change to
> https://khr%40golang.org@code.google.com/p/go/
>
>
> Description:
> runtime: implement eqstring in assembly.
>
> BenchmarkCompareStringEqual               10.4          7.33
> -29.52%
> BenchmarkCompareStringIdentical           3.99          3.67
> -8.02%
> BenchmarkCompareStringSameLength          9.80          6.84
> -30.20%
> BenchmarkCompareStringDifferentLength     1.09          0.95
> -12.84%
> BenchmarkCompareStringBigUnaligned        75220         76071
> +1.13%
> BenchmarkCompareStringBig                 69843         74746
> +7.02%
>
> Please review this at https://codereview.appspot.com/105280044/
>
> Affected files (+62, -12 lines):
>   M src/pkg/runtime/asm_386.s
>   M src/pkg/runtime/asm_amd64.s
>   M src/pkg/runtime/asm_arm.s
>   M src/pkg/runtime/string.goc
>
>
> Index: src/pkg/runtime/asm_386.s
> ===================================================================
> --- a/src/pkg/runtime/asm_386.s
> +++ b/src/pkg/runtime/asm_386.s
> @@ -1096,6 +1096,25 @@
>         MOVL    count+8(FP), BX
>         JMP     runtime·memeqbody(SB)
>
> +TEXT runtime·eqstring(SB),NOSPLIT,$0-17
> +       MOVL    s1len+4(FP), AX
> +       MOVL    s2len+12(FP), BX
> +       CMPL    AX, BX
> +       JNE     different
> +       MOVL    s1str+0(FP), SI
> +       MOVL    s2str+8(FP), DI
> +       CMPL    SI, DI
> +       JEQ     same
> +       CALL    runtime·memeqbody(SB)
> +       MOVB    AX, v+16(FP)
> +       RET
> +same:
> +       MOVB    $1, v+16(FP)
> +       RET
> +different:
> +       MOVB    $0, v+16(FP)
> +       RET
> +
>  TEXT bytes·Equal(SB),NOSPLIT,$0-25
>         MOVL    a_len+4(FP), BX
>         MOVL    b_len+16(FP), CX
> Index: src/pkg/runtime/asm_amd64.s
> ===================================================================
> --- a/src/pkg/runtime/asm_amd64.s
> +++ b/src/pkg/runtime/asm_amd64.s
> @@ -1058,6 +1058,25 @@
>         MOVQ    count+16(FP), BX
>         JMP     runtime·memeqbody(SB)
>
> +TEXT runtime·eqstring(SB),NOSPLIT,$0-33
> +       MOVQ    s1len+8(FP), AX
> +       MOVQ    s2len+24(FP), BX
> +       CMPQ    AX, BX
> +       JNE     different
> +       MOVQ    s1str+0(FP), SI
> +       MOVQ    s2str+16(FP), DI
> +       CMPQ    SI, DI
> +       JEQ     same
> +       CALL    runtime·memeqbody(SB)
> +       MOVB    AX, v+32(FP)
> +       RET
> +same:
> +       MOVB    $1, v+32(FP)
> +       RET
> +different:
> +       MOVB    $0, v+32(FP)
> +       RET
> +
>  // a in SI
>  // b in DI
>  // count in BX
> Index: src/pkg/runtime/asm_arm.s
> ===================================================================
> --- a/src/pkg/runtime/asm_arm.s
> +++ b/src/pkg/runtime/asm_arm.s
> @@ -646,6 +646,30 @@
>         MOVW    $0, R0
>         RET
>
> +TEXT runtime·eqstring(SB),NOSPLIT,$-4-17
> +       MOVW    s1len+4(FP), R0
> +       MOVW    s2len+12(FP), R1
> +       MOVW    $0, R7
> +       CMP     R0, R1
> +       MOVB.NE R7, v+16(FP)
> +       RET.NE
> +       MOVW    s1str+0(FP), R2
> +       MOVW    s2str+8(FP), R3
> +       MOVW    $1, R8
> +       MOVB    R8, v+16(FP)
> +       CMP     R2, R3
> +       RET.EQ
> +       ADD     R2, R0, R6
> +_eqnext:
> +       CMP     R2, R6
> +       RET.EQ
> +       MOVBU.P 1(R2), R4
> +       MOVBU.P 1(R3), R5
> +       CMP     R4, R5
> +       BEQ     _eqnext
> +       MOVB    R7, v+16(FP)
> +       RET
> +
>  // We have to resort to TLS variable to save g(R10) and
>  // m(R9). One reason is that external code might trigger
>  // SIGSEGV, and our runtime.sigtramp don't even know we
> Index: src/pkg/runtime/string.goc
> ===================================================================
> --- a/src/pkg/runtime/string.goc
> +++ b/src/pkg/runtime/string.goc
> @@ -206,18 +206,6 @@
>         res = concatstring(s.len, (String*)s.array);
>  }
>
> -func eqstring(s1 String, s2 String) (v bool) {
> -       if(s1.len != s2.len) {
> -               v = false;
> -               return;
> -       }
> -       if(s1.str == s2.str) {
> -               v = true;
> -               return;
> -       }
> -       v = runtime·memeq(s1.str, s2.str, s1.len);
> -}
> -
>  int32
>  runtime·strcmp(byte *s1, byte *s2)
>  {
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "golang-codereviews" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-codereviews+unsubscribe@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>

[josharian, 2014-06-17 00:43:43]

The code looks good.

Can we keep the original or a pseudo-code equivalent around as a comment
somewhere? It's useful to have readable reference implementations.

Is it worth a Duff's device for ARM's inlined comparison?

[bradfitz, 2014-06-17 00:51:35]

If we do keep the original, it'd be nice to keep it building as well.
 Ideally tested, but that's a stretch here.  We jump through those hoops
with the portable implementations in crypto/* which no longer are used in
the general case.

In lieu of that, some short summary comments on the assembly would probably
suffice.



On Mon, Jun 16, 2014 at 5:43 PM, <josharian@gmail.com> wrote:

> The code looks good.
>
> Can we keep the original or a pseudo-code equivalent around as a comment
> somewhere? It's useful to have readable reference implementations.
>
> Is it worth a Duff's device for ARM's inlined comparison?
>
>
> https://codereview.appspot.com/105280044/
>

[dave_cheney.net, 2014-06-17 01:39:26]

Testing on linux/arm now.

I think you need to also make the change to asm_arm64p32.s

[dave_cheney.net, 2014-06-17 01:46:25]

LG on linux/arm

[root@alarmcbi runtime]# benchcmp {old,new}.txt
benchmark                                 old ns/op     new ns/op     delta     
 
BenchmarkCompareStringEqual               220           128           -41.82%   
 
BenchmarkCompareStringIdentical           42.8          27.6          -35.51%   
 
BenchmarkCompareStringSameLength          99.3          96.5          -2.82%    
 
BenchmarkCompareStringDifferentLength     8.20          9.05          +10.37%   
 
BenchmarkCompareStringBigUnaligned        6047583       5784357       -4.35%    
 
BenchmarkCompareStringBig                 5282953       5271501       -0.22%    
 

benchmark                              old MB/s     new MB/s     speedup     
BenchmarkCompareStringBigUnaligned     173.39       181.28       1.05x       
BenchmarkCompareStringBig              198.48       198.92       1.00x   

ARM aficioandos can probably recover the 0.85 of a ns lost in
BenchmarkCompareStringDifferentLength, I don't think it should block this
review.

[khr1, 2014-06-17 02:18:19]

On Mon, Jun 16, 2014 at 6:39 PM, <dave@cheney.net> wrote:

> Testing on linux/arm now.
>
> I think you need to also make the change to asm_arm64p32.s
>

Yes, I'll fix that.


>
> https://codereview.appspot.com/105280044/
>

[josharian, 2014-06-17 02:21:34]

> In lieu of that, some short summary comments on the assembly would probably
> suffice.

Yeah, that'd probably do.

[khr1, 2014-06-17 02:24:37]

On Mon, Jun 16, 2014 at 5:43 PM, <josharian@gmail.com> wrote:

> The code looks good.
>
> Can we keep the original or a pseudo-code equivalent around as a comment
> somewhere? It's useful to have readable reference implementations.
>

Yes, I'll put it somewhere.  Perhaps a Go version in a test file that
compares
against the assembly version.


>
> Is it worth a Duff's device for ARM's inlined comparison?
>

Might be useful.


>
>
> https://codereview.appspot.com/105280044/
>

[khr1, 2014-06-17 02:46:08]

All fixed up.  PTAL.



On Mon, Jun 16, 2014 at 7:24 PM, Keith Randall <khr@google.com> wrote:

>
>
>
> On Mon, Jun 16, 2014 at 5:43 PM, <josharian@gmail.com> wrote:
>
>> The code looks good.
>>
>> Can we keep the original or a pseudo-code equivalent around as a comment
>> somewhere? It's useful to have readable reference implementations.
>>
>
> Yes, I'll put it somewhere.  Perhaps a Go version in a test file that
> compares
> against the assembly version.
>
>
>>
>> Is it worth a Duff's device for ARM's inlined comparison?
>>
>
> Might be useful.
>
>
>>
>>
>> https://codereview.appspot.com/105280044/
>>
>
>

[bradfitz, 2014-06-17 02:53:37]

LGTM

https://codereview.appspot.com/105280044/diff/80001/src/pkg/runtime/asm_amd64...
File src/pkg/runtime/asm_amd64p32.s (right):

https://codereview.appspot.com/105280044/diff/80001/src/pkg/runtime/asm_amd64...
src/pkg/runtime/asm_amd64p32.s:720: // equivlaent Go code.
typo: equivalent. here and other files too.

https://codereview.appspot.com/105280044/diff/80001/src/pkg/runtime/runtime_t...
File src/pkg/runtime/runtime_test.go (right):

https://codereview.appspot.com/105280044/diff/80001/src/pkg/runtime/runtime_t...
src/pkg/runtime/runtime_test.go:210: for i := 0; i < len(s1); i++ {
doesn't do equivalent of
 
   if &s1[0] == &s2[0] {
        return true
   }

... before the byte loop.  (if the purpose of this function is documentation)

Which I guess you'd need to do with a local version of reflect.SliceHeader.

https://codereview.appspot.com/105280044/diff/80001/src/pkg/runtime/runtime_t...
src/pkg/runtime/runtime_test.go:227: "ccc",
make one of the strings equal but different?

"ccc",
"cccc"[:3],

To test the above pointer+len equal case?

[khr1, 2014-06-17 03:09:49]

On Mon, Jun 16, 2014 at 7:53 PM, <bradfitz@golang.org> wrote:

> LGTM
>
>
>
> https://codereview.appspot.com/105280044/diff/80001/src/
> pkg/runtime/asm_amd64p32.s
> File src/pkg/runtime/asm_amd64p32.s (right):
>
> https://codereview.appspot.com/105280044/diff/80001/src/
> pkg/runtime/asm_amd64p32.s#newcode720
> src/pkg/runtime/asm_amd64p32.s:720: // equivlaent Go code.
> typo: equivalent. here and other files too.
>
> https://codereview.appspot.com/105280044/diff/80001/src/
> pkg/runtime/runtime_test.go
> File src/pkg/runtime/runtime_test.go (right):
>
> https://codereview.appspot.com/105280044/diff/80001/src/
> pkg/runtime/runtime_test.go#newcode210
> src/pkg/runtime/runtime_test.go:210: for i := 0; i < len(s1); i++ {
> doesn't do equivalent of
>
>    if &s1[0] == &s2[0] {
>         return true
>    }
>
> ... before the byte loop.  (if the purpose of this function is
> documentation)
>
> Which I guess you'd need to do with a local version of
> reflect.SliceHeader.
>
>
I don't think I want to go there.  It's just an optimization the assembly
(and the old C code) happens to do, it's not part of the spec.


> https://codereview.appspot.com/105280044/diff/80001/src/
> pkg/runtime/runtime_test.go#newcode227
> src/pkg/runtime/runtime_test.go:227: "ccc",
> make one of the strings equal but different?
>
> "ccc",
> "cccc"[:3],
>
> To test the above pointer+len equal case?
>

Sure.  I worry about "cccc"[:3] being evaluated at compile time though.
 Perhaps something more devious?


>
> https://codereview.appspot.com/105280044/
>

[josharian, 2014-06-17 03:20:32]

LGTM 

> > make one of the strings equal but different?
> >
> > "ccc",
> > "cccc"[:3],
> >
> > To test the above pointer+len equal case?
> 
> Sure.  I worry about "cccc"[:3] being evaluated at compile time though.
>  Perhaps something more devious?

You could pass it through a non-inlinable function:

func prefix(s string) string {
  defer func() {}() // prevent inlining
  return s[:3]
}

prefix("cccc")

[bradfitz, 2014-06-17 03:22:16]

At least add a comment in the code like my pseudo code? The assembly refers
to this code as "equivalent". I know the spec doesn't define how equality
is implemented but I thought we were showing one implementation to explain
another implementation.
 On Jun 16, 2014 8:09 PM, "Keith Randall" <khr@google.com> wrote:

>
>
>
> On Mon, Jun 16, 2014 at 7:53 PM, <bradfitz@golang.org> wrote:
>
>> LGTM
>>
>>
>>
>> https://codereview.appspot.com/105280044/diff/80001/src/
>> pkg/runtime/asm_amd64p32.s
>> File src/pkg/runtime/asm_amd64p32.s (right):
>>
>> https://codereview.appspot.com/105280044/diff/80001/src/
>> pkg/runtime/asm_amd64p32.s#newcode720
>> src/pkg/runtime/asm_amd64p32.s:720: // equivlaent Go code.
>> typo: equivalent. here and other files too.
>>
>> https://codereview.appspot.com/105280044/diff/80001/src/
>> pkg/runtime/runtime_test.go
>> File src/pkg/runtime/runtime_test.go (right):
>>
>> https://codereview.appspot.com/105280044/diff/80001/src/
>> pkg/runtime/runtime_test.go#newcode210
>> src/pkg/runtime/runtime_test.go:210: for i := 0; i < len(s1); i++ {
>> doesn't do equivalent of
>>
>>    if &s1[0] == &s2[0] {
>>         return true
>>    }
>>
>> ... before the byte loop.  (if the purpose of this function is
>> documentation)
>>
>> Which I guess you'd need to do with a local version of
>> reflect.SliceHeader.
>>
>>
> I don't think I want to go there.  It's just an optimization the assembly
> (and the old C code) happens to do, it's not part of the spec.
>
>
>> https://codereview.appspot.com/105280044/diff/80001/src/
>> pkg/runtime/runtime_test.go#newcode227
>> src/pkg/runtime/runtime_test.go:227: "ccc",
>> make one of the strings equal but different?
>>
>> "ccc",
>> "cccc"[:3],
>>
>> To test the above pointer+len equal case?
>>
>
> Sure.  I worry about "cccc"[:3] being evaluated at compile time though.
>  Perhaps something more devious?
>
>
>>
>> https://codereview.appspot.com/105280044/
>>
>
>

[khr, 2014-06-17 04:00:54]

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

runtime: implement eqstring in assembly.

BenchmarkCompareStringEqual               10.4          7.33          -29.52%
BenchmarkCompareStringIdentical           3.99          3.67          -8.02%
BenchmarkCompareStringSameLength          9.80          6.84          -30.20%
BenchmarkCompareStringDifferentLength     1.09          0.95          -12.84%
BenchmarkCompareStringBigUnaligned        75220         76071         +1.13%
BenchmarkCompareStringBig                 69843         74746         +7.02%

LGTM=bradfitz, josharian
R=golang-codereviews, bradfitz, josharian, dave, khr
CC=golang-codereviews
https://codereview.appspot.com/105280044

[cahooon, 2014-06-17 14:54:24]

On 2014/06/17 04:00:54, khr wrote:
> *** Submitted as https://code.google.com/p/go/source/detail?r=62285adb2b50 ***
> 
> runtime: implement eqstring in assembly.
> 
> BenchmarkCompareStringEqual               10.4          7.33          -29.52%
> BenchmarkCompareStringIdentical           3.99          3.67          -8.02%
> BenchmarkCompareStringSameLength          9.80          6.84          -30.20%
> BenchmarkCompareStringDifferentLength     1.09          0.95          -12.84%
> BenchmarkCompareStringBigUnaligned        75220         76071         +1.13%
> BenchmarkCompareStringBig                 69843         74746         +7.02%
> 
> LGTM=bradfitz, josharian
> R=golang-codereviews, bradfitz, josharian, dave, khr
> CC=golang-codereviews
> https://codereview.appspot.com/105280044

s/equivlaent/equivalent in the asm files