code review 83740044: cmd/gc, runtime: optimize map[string] lookup from []byte key

cmd/gc, runtime: optimize map[string] lookup from []byte key

Brad has been asking for this for a while.
I have resisted because I wanted to find a more general way to
do this, one that would keep the performance of code introducing
variables the same as the performance of code that did not.
(See golang.org/issue/3512#c20).

I have not found the more general way, and recent changes to
remove ambiguously live temporaries have blown away the
property I was trying to preserve, so that's no longer a reason
not to make the change.

Fixes issue 3512.

[rsc, 2014-04-03 03:26:18]

Hello iant (cc: bradfitz, golang-codereviews@googlegroups.com, khr, r),

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

[bradfitz, 2014-04-03 17:39:33]

I got unexpected results trying to use this in an experiment just now, in
net/textproto's canonicalMIMEHeaderKey.

Before & after:

bradfitz@bradfitz:~/go/src$ go test -v -run=XX
-bench=BenchmarkReadMIMEHeader -benchtime=2s net/textproto
PASS
BenchmarkReadMIMEHeader  500000      6017 ns/op    1317 B/op      12
allocs/op

PASS
BenchmarkReadMIMEHeader 1000000      5418 ns/op    1421 B/op      18
allocs/op


Why did allocs increase?

diff -r ddfee9dfca20 src/pkg/net/textproto/reader.go
--- a/src/pkg/net/textproto/reader.go Wed Apr 02 21:05:41 2014 -0700
+++ b/src/pkg/net/textproto/reader.go Thu Apr 03 10:36:41 2014 -0700
@@ -567,14 +567,11 @@
  // of textproto. If we don't find it, a has been canonicalized
  // so just return string(a).
  upper := true
- lo := 0
- hi := len(commonHeaders)
- for i := 0; i < len(a); i++ {
+ for i, c := range a {
  // Canonicalize: first letter upper case
  // and upper case after each dash.
  // (Host, User-Agent, If-Modified-Since).
  // MIME headers are ASCII only, so no Unicode issues.
- c := a[i]
  if c == ' ' {
  c = '-'
  } else if upper && 'a' <= c && c <= 'z' {
@@ -584,18 +581,9 @@
  }
  a[i] = c
  upper = c == '-' // for next time
-
- if lo < hi {
- for lo < hi && (len(commonHeaders[lo]) <= i || commonHeaders[lo][i] < c) {
- lo++
- }
- for hi > lo && commonHeaders[hi-1][i] > c {
- hi--
- }
- }
  }
- if lo < hi && len(commonHeaders[lo]) == len(a) {
- return commonHeaders[lo]
+ if v, ok := commonHeaderInterned[string(a)]; ok {
+ return v
  }
  return string(a)
 }
@@ -641,3 +629,11 @@
  "X-Imforwards",
  "X-Powered-By",
 }
+
+var commonHeaderInterned = make(map[string]string)
+
+func init() {
+ for _, v := range commonHeaders {
+ commonHeaderInterned[v] = v
+ }
+}





On Wed, Apr 2, 2014 at 8:26 PM, <rsc@golang.org> wrote:

> Reviewers: iant,
>
> Message:
> Hello iant (cc: bradfitz, golang-codereviews@googlegroups.com, khr, r),
>
> I'd like you to review this change to
> https://code.google.com/p/go/
>
>
> Description:
> cmd/gc, runtime: optimize map[string] lookup from []byte key
>
> Brad has been asking for this for a while.
> I have resisted because I wanted to find a more general way to
> do this, one that would keep the performance of code introducing
> variables the same as the performance of code that did not.
> (See golang.org/issue/3512#c20).
>
> I have not found the more general way, and recent changes to
> remove ambiguously live temporaries have blown away the
> property I was trying to preserve, so that's no longer a reason
> not to make the change.
>
> Fixes issue 3512.
>
> Please review this at https://codereview.appspot.com/83740044/
>
> Affected files (+67, -0 lines):
>   M src/cmd/gc/builtin.c
>   M src/cmd/gc/go.h
>   M src/cmd/gc/order.c
>   M src/cmd/gc/runtime.go
>   M src/cmd/gc/walk.c
>   M src/pkg/runtime/map_test.go
>   M src/pkg/runtime/string.goc
>
>
> Index: src/cmd/gc/builtin.c
> ===================================================================
> --- a/src/cmd/gc/builtin.c
> +++ b/src/cmd/gc/builtin.c
> @@ -33,6 +33,7 @@
>         "func @\"\".eqstring (? string, ? string) (? bool)\n"
>         "func @\"\".intstring (? int64) (? string)\n"
>         "func @\"\".slicebytetostring (? []byte) (? string)\n"
> +       "func @\"\".slicebytetostringtmp (? []byte) (? string)\n"
>         "func @\"\".slicerunetostring (? []rune) (? string)\n"
>         "func @\"\".stringtoslicebyte (? string) (? []byte)\n"
>         "func @\"\".stringtoslicerune (? string) (? []rune)\n"
> Index: src/cmd/gc/go.h
> ===================================================================
> --- a/src/cmd/gc/go.h
> +++ b/src/cmd/gc/go.h
> @@ -450,6 +450,7 @@
>         OANDAND,        // b0 && b1
>         OAPPEND,        // append
>         OARRAYBYTESTR,  // string(bytes)
> +       OARRAYBYTESTRTMP, // string(bytes) ephemeral
>         OARRAYRUNESTR,  // string(runes)
>         OSTRARRAYBYTE,  // []byte(s)
>         OSTRARRAYRUNE,  // []rune(s)
> Index: src/cmd/gc/order.c
> ===================================================================
> --- a/src/cmd/gc/order.c
> +++ b/src/cmd/gc/order.c
> @@ -935,6 +935,20 @@
>                 // key must be addressable
>                 orderexpr(&n->left, order);
>                 orderexpr(&n->right, order);
> +
> +               // For x = m[string(k)] where k is []byte, the allocation
> of
> +               // backing bytes for the string can be avoided by reusing
> +               // the []byte backing array. This is a special case that it
> +               // would be nice to handle more generally, but because
> +               // there are no []byte-keyed maps, this specific case comes
> +               // up in important cases in practice. See issue 3512.
> +               // Nothing can change the []byte we are not copying before
> +               // the map index, because the map access is going to
> +               // be forced to happen immediately following this
> +               // conversion (by the ordercopyexpr a few lines below).
> +               if(n->etype == 0 && n->right->op == OARRAYBYTESTR)
> +                       n->right->op = OARRAYBYTESTRTMP;
> +
>                 orderaddrtemp(&n->right, order);
>                 if(n->etype == 0) {
>                         // use of value (not being assigned);
> Index: src/cmd/gc/runtime.go
> ===================================================================
> --- a/src/cmd/gc/runtime.go
> +++ b/src/cmd/gc/runtime.go
> @@ -47,6 +47,7 @@
>  func eqstring(string, string) bool
>  func intstring(int64) string
>  func slicebytetostring([]byte) string
> +func slicebytetostringtmp([]byte) string
>  func slicerunetostring([]rune) string
>  func stringtoslicebyte(string) []byte
>  func stringtoslicerune(string) []rune
> Index: src/cmd/gc/walk.c
> ===================================================================
> --- a/src/cmd/gc/walk.c
> +++ b/src/cmd/gc/walk.c
> @@ -1316,6 +1316,11 @@
>                 n = mkcall("slicebytetostring", n->type, init, n->left);
>                 goto ret;
>
> +       case OARRAYBYTESTRTMP:
> +               // slicebytetostringtmp([]byte) string;
> +               n = mkcall("slicebytetostringtmp", n->type, init, n->left);
> +               goto ret;
> +
>         case OARRAYRUNESTR:
>                 // slicerunetostring([]rune) string;
>                 n = mkcall("slicerunetostring", n->type, init, n->left);
> Index: src/pkg/runtime/map_test.go
> ===================================================================
> --- a/src/pkg/runtime/map_test.go
> +++ b/src/pkg/runtime/map_test.go
> @@ -438,3 +438,29 @@
>                 }
>         }
>  }
> +
> +func TestMapStringBytesLookup(t *testing.T) {
> +       // Use large string keys to avoid small-allocation coalescing,
> +       // which can cause AllocsPerRun to report lower counts than it
> should.
> +       m := map[string]int{
> +               "1000000000000000000000000000000000000000000000000": 1,
> +               "2000000000000000000000000000000000000000000000000": 2,
> +       }
> +       buf := []byte("1000000000000000000000000000000000000000000000000")
> +       if x := m[string(buf)]; x != 1 {
> +               t.Errorf(`m[string([]byte("1"))] = %d, want 1`, x)
> +       }
> +       buf[0] = '2'
> +       if x := m[string(buf)]; x != 2 {
> +               t.Errorf(`m[string([]byte("2"))] = %d, want 2`, x)
> +       }
> +
> +       var x int
> +       n := testing.AllocsPerRun(100, func() {
> +               x += m[string(buf)]
> +       })
> +
> +       if n != 0 {
> +               t.Errorf("AllocsPerRun for m[string(buf)] = %v, want 0", n)
> +       }
> +}
> Index: src/pkg/runtime/string.goc
> ===================================================================
> --- a/src/pkg/runtime/string.goc
> +++ b/src/pkg/runtime/string.goc
> @@ -294,6 +294,25 @@
>         runtime·memmove(s.str, b.array, s.len);
>  }
>
> +func slicebytetostringtmp(b Slice) (s String) {
> +       void *pc;
> +
> +       if(raceenabled) {
> +               pc = runtime·getcallerpc(&b);
> +               runtime·racereadrangepc(b.array, b.len, pc,
> runtime·slicebytetostringtmp);
> +       }
> +
> +       // Return a "string" referring to the actual []byte bytes.
> +       // This is only for use by internal compiler optimizations
> +       // that know that the string form will be discarded before
> +       // the calling goroutine could possibly modify the original
> +       // slice or synchronize with another goroutine.
> +       // Today, the only such case is a m[string(k)] lookup where
> +       // m is a string-keyed map and k is a []byte.
> +       s.str = b.array;
> +       s.len = b.len;
> +}
> +
>  func stringtoslicebyte(s String) (b Slice) {
>         uintptr cap;
>
>
>
>

[rsc, 2014-04-03 18:02:14]

Run the malloc profiler to find where the allocations are?

[iant, 2014-04-03 20:53:57]

LGTM

[bradfitz, 2014-04-03 21:19:02]

From chat with Russ, we determined that the optimization works for
mapaccess1 but not mapaccess2:

if v := m[string(b)]; v != "" {
BenchmarkReadMIMEHeader  500000      5114 ns/op    1317 B/op      12
allocs/op

if v, ok := m[string(b); ok {
BenchmarkReadMIMEHeader  500000      5518 ns/op    1421 B/op      18
allocs/op




On Thu, Apr 3, 2014 at 1:53 PM, <iant@golang.org> wrote:

> LGTM
>
> https://codereview.appspot.com/83740044/
>

[rsc, 2014-04-03 23:05:23]

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

cmd/gc, runtime: optimize map[string] lookup from []byte key

Brad has been asking for this for a while.
I have resisted because I wanted to find a more general way to
do this, one that would keep the performance of code introducing
variables the same as the performance of code that did not.
(See golang.org/issue/3512#c20).

I have not found the more general way, and recent changes to
remove ambiguously live temporaries have blown away the
property I was trying to preserve, so that's no longer a reason
not to make the change.

Fixes issue 3512.

LGTM=iant
R=iant
CC=bradfitz, golang-codereviews, khr, r
https://codereview.appspot.com/83740044

[oleku, 2014-04-08 00:57:58]

Would this be extended to mapaccess2 ? 


On 2014/04/03 23:05:23, rsc wrote:
> *** Submitted as https://code.google.com/p/go/source/detail?r=881e5ceda5bf ***
> 
> cmd/gc, runtime: optimize map[string] lookup from []byte key
> 
> Brad has been asking for this for a while.
> I have resisted because I wanted to find a more general way to
> do this, one that would keep the performance of code introducing
> variables the same as the performance of code that did not.
> (See golang.org/issue/3512#c20).
> 
> I have not found the more general way, and recent changes to
> remove ambiguously live temporaries have blown away the
> property I was trying to preserve, so that's no longer a reason
> not to make the change.
> 
> Fixes issue 3512.
> 
> LGTM=iant
> R=iant
> CC=bradfitz, golang-codereviews, khr, r
> https://codereview.appspot.com/83740044

[bradfitz, 2014-04-08 01:01:48]

It was.
 On Apr 7, 2014 5:57 PM, <oleku.konko@gmail.com> wrote:

> Would this be extended to mapaccess2 ?
>
>
> On 2014/04/03 23:05:23, rsc wrote:
>
>> *** Submitted as
>>
> https://code.google.com/p/go/source/detail?r=881e5ceda5bf ***
>
>  cmd/gc, runtime: optimize map[string] lookup from []byte key
>>
>
>  Brad has been asking for this for a while.
>> I have resisted because I wanted to find a more general way to
>> do this, one that would keep the performance of code introducing
>> variables the same as the performance of code that did not.
>> (See golang.org/issue/3512#c20).
>>
>
>  I have not found the more general way, and recent changes to
>> remove ambiguously live temporaries have blown away the
>> property I was trying to preserve, so that's no longer a reason
>> not to make the change.
>>
>
>  Fixes issue 3512.
>>
>
>  LGTM=iant
>> R=iant
>> CC=bradfitz, golang-codereviews, khr, r
>> https://codereview.appspot.com/83740044
>>
>
>
> https://codereview.appspot.com/83740044/
>

[oleku, 2014-04-08 01:40:37]

Thanks for the clarification. Well done.

On 2014/04/08 01:01:48, bradfitz wrote:
> It was.
>  On Apr 7, 2014 5:57 PM, <mailto:oleku.konko@gmail.com> wrote:
> 
> > Would this be extended to mapaccess2 ?
> >
> >
> > On 2014/04/03 23:05:23, rsc wrote:
> >
> >> *** Submitted as
> >>
> > https://code.google.com/p/go/source/detail?r=881e5ceda5bf ***
> >
> >  cmd/gc, runtime: optimize map[string] lookup from []byte key
> >>
> >
> >  Brad has been asking for this for a while.
> >> I have resisted because I wanted to find a more general way to
> >> do this, one that would keep the performance of code introducing
> >> variables the same as the performance of code that did not.
> >> (See golang.org/issue/3512#c20).
> >>
> >
> >  I have not found the more general way, and recent changes to
> >> remove ambiguously live temporaries have blown away the
> >> property I was trying to preserve, so that's no longer a reason
> >> not to make the change.
> >>
> >
> >  Fixes issue 3512.
> >>
> >
> >  LGTM=iant
> >> R=iant
> >> CC=bradfitz, golang-codereviews, khr, r
> >> https://codereview.appspot.com/83740044
> >>
> >
> >
> > https://codereview.appspot.com/83740044/
> >