code review 99380043: runtime: convert map implementation to Go.

runtime: convert map implementation to Go.

It's a bit slower, but not painfully so.  There is still room for
improvement (saving space so we can use nosplit, and removing the
requirement for hash/eq stubs).

benchmark                              old ns/op     new ns/op     delta
BenchmarkMegMap                        23.5          24.2          +2.98%
BenchmarkMegOneMap                     14.9          15.7          +5.37%
BenchmarkMegEqMap                      71668         72234         +0.79%
BenchmarkMegEmptyMap                   4.05          4.93          +21.73%
BenchmarkSmallStrMap                   21.9          22.5          +2.74%
BenchmarkMapStringKeysEight_16         23.1          26.3          +13.85%
BenchmarkMapStringKeysEight_32         21.9          25.0          +14.16%
BenchmarkMapStringKeysEight_64         21.9          25.1          +14.61%
BenchmarkMapStringKeysEight_1M         21.9          25.0          +14.16%
BenchmarkIntMap                        21.8          12.5          -42.66%
BenchmarkRepeatedLookupStrMapKey32     39.3          30.2          -23.16%
BenchmarkRepeatedLookupStrMapKey1M     322353        322675        +0.10%
BenchmarkNewEmptyMap                   129           136           +5.43%
BenchmarkMapIter                       137           107           -21.90%
BenchmarkMapIterEmpty                  7.14          8.71          +21.99%
BenchmarkSameLengthMap                 5.24          6.82          +30.15%
BenchmarkBigKeyMap                     34.5          35.3          +2.32%
BenchmarkBigValMap                     36.1          36.1          +0.00%
BenchmarkSmallKeyMap                   26.9          26.7          -0.74%

[khr, 2014-06-18 00:09:41]

Hello golang-codereviews@googlegroups.com,

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

[dave_cheney.net, 2014-06-18 05:41:13]

This is great. 

I have some very minor comments, please feel free to ignore them if they are not
relevant. 

I'll test this change on arm now.

https://codereview.appspot.com/99380043/diff/400001/src/pkg/reflect/asm_386.s
File src/pkg/reflect/asm_386.s (right):

https://codereview.appspot.com/99380043/diff/400001/src/pkg/reflect/asm_386.s...
src/pkg/reflect/asm_386.s:28: 
It would be nice to not have to have these same lines in all three intel
assembly files.

Maybe it's not an issue now, just wondering what the runtime looks like when we
have ppc64 and arm64 variations.

https://codereview.appspot.com/99380043/diff/400001/src/pkg/runtime/hashmap.go
File src/pkg/runtime/hashmap.go (right):

https://codereview.appspot.com/99380043/diff/400001/src/pkg/runtime/hashmap.g...
src/pkg/runtime/hashmap.go:157: if unsafe.Sizeof(hmap{}) > 48 {
nice.

https://codereview.appspot.com/99380043/diff/400001/src/pkg/runtime/hashmap.g...
src/pkg/runtime/hashmap.go:170: flags := uint32(0)
nit: var flags uint32

https://codereview.appspot.com/99380043/diff/400001/src/pkg/runtime/hashmap.g...
src/pkg/runtime/hashmap.go:213: B := uint8(0)
nit: var B uint8

https://codereview.appspot.com/99380043/diff/400001/src/pkg/runtime/hashmap.g...
src/pkg/runtime/hashmap.go:300: func mapaccess2(t *maptype, h *hmap, key
unsafe.Pointer) (unsafe.Pointer, bool) {
for a followup: now this file is in Go, could some of the code between
mapaccess1 and 2 be moved to shared functions with a view of it being inlined?

https://codereview.appspot.com/99380043/diff/400001/src/pkg/runtime/hashmap.g...
src/pkg/runtime/hashmap.go:302: callerpc := gogetcallerpc(unsafe.Pointer(&t))
For example, this raceenabled code is similar acorss mapaccess1,2, and K

https://codereview.appspot.com/99380043/diff/400001/src/pkg/runtime/hashmap.g...
src/pkg/runtime/hashmap.go:320: top := uint8(hash >> (ptrSize*8 - 8))
this top ajustment could be moved into a small helper.

https://codereview.appspot.com/99380043/diff/400001/src/pkg/runtime/hashmap.g...
src/pkg/runtime/hashmap.go:551: it.key = nil
could this be done simpler (possibly faster) with something like

*it = hiter{}

https://codereview.appspot.com/99380043/diff/400001/src/pkg/runtime/hashmap.g...
src/pkg/runtime/hashmap.go:566: it.key = nil
these two were just nil'ed before

https://codereview.appspot.com/99380043/diff/400001/src/pkg/runtime/hashmap.g...
src/pkg/runtime/hashmap.go:602: func mapiternext(it *hiter) {
nit: could this be converted into a method ?

[dvyukov, 2014-06-18 16:22:56]

https://codereview.appspot.com/99380043/diff/400001/src/pkg/runtime/hashmap.go
File src/pkg/runtime/hashmap.go (right):

https://codereview.appspot.com/99380043/diff/400001/src/pkg/runtime/hashmap.g...
src/pkg/runtime/hashmap.go:156: 
remove empty line

[dave_cheney.net, 2014-06-19 01:51:48]

On 2014/06/18 16:22:56, dvyukov wrote:
> https://codereview.appspot.com/99380043/diff/400001/src/pkg/runtime/hashmap.go
> File src/pkg/runtime/hashmap.go (right):
> 
>
https://codereview.appspot.com/99380043/diff/400001/src/pkg/runtime/hashmap.g...
> src/pkg/runtime/hashmap.go:156: 
> remove empty line

Can you please remail this CL, it doesn't apply cleanly against the changes to
asm_386.s

[dave_cheney.net, 2014-06-27 03:07:51]

ping. Could you please hg mail this again so it applys cleanly.

[rsc, 2014-06-27 16:50:43]

Looks good. I didn't read hashmap.go closely - waiting for the diff view.

https://codereview.appspot.com/99380043/diff/400001/src/pkg/reflect/asm_386.s
File src/pkg/reflect/asm_386.s (right):

https://codereview.appspot.com/99380043/diff/400001/src/pkg/reflect/asm_386.s...
src/pkg/reflect/asm_386.s:28: 
On 2014/06/18 05:41:12, dfc wrote:
> It would be nice to not have to have these same lines in all three intel
> assembly files.
> 
> Maybe it's not an issue now, just wondering what the runtime looks like when
we
> have ppc64 and arm64 variations.

If you want to factor these out, it's fine to do what os/signal/sig.s does.

https://codereview.appspot.com/99380043/diff/400001/src/pkg/runtime/hashmap.go
File src/pkg/runtime/hashmap.go (right):

https://codereview.appspot.com/99380043/diff/400001/src/pkg/runtime/hashmap.g...
src/pkg/runtime/hashmap.go:1: // Copyright 2014 The Go Authors. All rights
reserved.
Can you run

hg mv -A hashmap.goc hashmap.go

and then re-mail? That should make this file show diffs and will thread the
history through for people digging backward.

https://codereview.appspot.com/99380043/diff/400001/src/pkg/runtime/hashmap_f...
File src/pkg/runtime/hashmap_fast.go (right):

https://codereview.appspot.com/99380043/diff/400001/src/pkg/runtime/hashmap_f...
src/pkg/runtime/hashmap_fast.go:1: package runtime
Same hg mv -A here.
Also add copyright.

[khr, 2014-06-29 02:01:59]

Hello golang-codereviews@googlegroups.com, dave@cheney.net, dvyukov@google.com,
rsc@golang.org (cc: golang-codereviews@googlegroups.com),

Please take another look.

[dave_cheney.net, 2014-06-30 09:28:10]

Tests pass on linux/arm

Results are not great on 5g

BenchmarkMegMap                           269           349           +29.74%   
 
BenchmarkMegOneMap                        205           257           +25.37%   
 
BenchmarkMegEqMap                         11012573      11082458      +0.63%    
 
BenchmarkMegEmptyMap                      87.5          84.8          -3.09%    
 
BenchmarkSmallStrMap                      278           324           +16.55%   
 
BenchmarkMapStringKeysEight_16            216           343           +58.80%   
 
BenchmarkMapStringKeysEight_32            198           346           +74.75%   
 
BenchmarkMapStringKeysEight_64            198           348           +75.76%   
 
BenchmarkMapStringKeysEight_1M            198           348           +75.76%   
 
BenchmarkIntMap                           168           214           +27.38%   
 
BenchmarkRepeatedLookupStrMapKey32        3554          3609          +1.55%    
 
BenchmarkRepeatedLookupStrMapKey1M        101949462     101383667     -0.55%    
 
BenchmarkNewEmptyMap                      2003          1911          -4.59%    
 
BenchmarkMapIter                          1342          2039          +51.94%   
 
BenchmarkMapIterEmpty                     68.9          83.6          +21.34%   
 
BenchmarkSameLengthMap                    89.1          136           +52.64%   
 
BenchmarkBigKeyMap                        2969          3047          +2.63%    
 
BenchmarkBigValMap                        3069          3021          -1.56%    
 
BenchmarkSmallKeyMap                      663           674           +1.66%    
 
BenchmarkNewEmptyMap     1              1              +0.00%     
BenchmarkNewEmptyMap     33            33            +0.00%    

go 1 results appear unaffected, and sometimes oddly improved.

benchmark                          old ns/op       new ns/op       delta      
BenchmarkBinaryTree17              61046234131     60017852784     -1.68%     
BenchmarkFannkuch11                52737213135     52946105957     +0.40%     
BenchmarkFmtFprintfEmpty           1501            1444            -3.80%     
BenchmarkFmtFprintfString          4858            4466            -8.07%     
BenchmarkFmtFprintfInt             3378            3220            -4.68%     
BenchmarkFmtFprintfIntInt          5198            4997            -3.87%     
BenchmarkFmtFprintfPrefixedInt     4893            4712            -3.70%     
BenchmarkFmtFprintfFloat           11358           11149           -1.84%     
BenchmarkFmtManyArgs               22116           21827           -1.31%     
BenchmarkGobDecode                 156240844       150808715       -3.48%     
BenchmarkGobEncode                 82759094        82667541        -0.11%     
BenchmarkGzip                      6224700928      6215728760      -0.14%     
BenchmarkGunzip                    934020996       933517456       -0.05%     
BenchmarkHTTPClientServer          625350          628295          +0.47%     
BenchmarkJSONEncode                503936768       503402710       -0.11%     
BenchmarkJSONDecode                1796783447      1816986084      +1.12%     
BenchmarkMandelbrot200             98439025        98437500        -0.00%     
BenchmarkGoParse                   75508117        75775146        +0.35%     
BenchmarkRegexpMatchEasy0_32       1903            1852            -2.68%     
BenchmarkRegexpMatchEasy0_1K       7163            7008            -2.16%     
BenchmarkRegexpMatchEasy1_32       1951            1935            -0.82%     
BenchmarkRegexpMatchEasy1_1K       16939           16875           -0.38%     
BenchmarkRegexpMatchMedium_32      3201            3160            -1.28%     
BenchmarkRegexpMatchMedium_1K      1040328         1046218         +0.57%     
BenchmarkRegexpMatchHard_32        58598           59057           +0.78%     
BenchmarkRegexpMatchHard_1K        1792572         1810638         +1.01%     
BenchmarkRevcomp                   141564941       141647338       +0.06%     
BenchmarkTemplate                  2348022461      2314208985      -1.44%     
BenchmarkTimeParse                 9641            9852            +2.19%     
BenchmarkTimeFormat                16026           16813           +4.91%     

benchmark                         old MB/s     new MB/s     speedup     
BenchmarkGobDecode                4.91         5.09         1.04x       
BenchmarkGobEncode                9.27         9.28         1.00x       
BenchmarkGzip                     3.12         3.12         1.00x       
BenchmarkGunzip                   20.78        20.79        1.00x       
BenchmarkJSONEncode               3.85         3.85         1.00x       
BenchmarkJSONDecode               1.08         1.07         0.99x       
BenchmarkGoParse                  0.77         0.76         0.99x       
BenchmarkRegexpMatchEasy0_32      16.81        17.27        1.03x       
BenchmarkRegexpMatchEasy0_1K      142.95       146.12       1.02x       
BenchmarkRegexpMatchEasy1_32      16.40        16.53        1.01x       
BenchmarkRegexpMatchEasy1_1K      60.45        60.68        1.00x       
BenchmarkRegexpMatchMedium_32     0.31         0.32         1.03x       
BenchmarkRegexpMatchMedium_1K     0.98         0.98         1.00x       
BenchmarkRegexpMatchHard_32       0.55         0.54         0.98x       
BenchmarkRegexpMatchHard_1K       0.57         0.57         1.00x       
BenchmarkRevcomp                  17.95        17.94        1.00x       
BenchmarkTemplate                 0.83         0.84         1.01x

[rsc, 2014-06-30 15:37:20]

LGTM

https://codereview.appspot.com/99380043/diff/460001/src/pkg/runtime/hashmap.go
File src/pkg/runtime/hashmap.go (right):

https://codereview.appspot.com/99380043/diff/460001/src/pkg/runtime/hashmap.g...
src/pkg/runtime/hashmap.go:185: panic("bucketsize wrong")
I can't decide if I should worry that these are now recoverable panics instead
of throws. Maybe it doesn't matter.

https://codereview.appspot.com/99380043/diff/460001/src/pkg/runtime/hashmap.g...
src/pkg/runtime/hashmap.go:222: if checkgc {
What is this?

[dave_cheney.net, 2014-06-30 22:33:49]

>
https://codereview.appspot.com/99380043/diff/460001/src/pkg/runtime/hashmap.g...
> src/pkg/runtime/hashmap.go:185: panic("bucketsize wrong")
> I can't decide if I should worry that these are now recoverable panics
> instead of throws. Maybe it doesn't matter.

Good point. Is there an argument for making runtime.throw visible to
go code in this package and then using it. Code like net/http with
it's blanket recover() around each serving goroutine would suffer
badly if the program tried to continue after recovering this.

[gobot, 2014-07-01 05:32:25]

R=rsc@golang.org (assigned by dave@cheney.net)

[dvyukov, 2014-07-01 05:57:05]

https://codereview.appspot.com/99380043/diff/460001/src/pkg/runtime/hashmap.go
File src/pkg/runtime/hashmap.go (right):

https://codereview.appspot.com/99380043/diff/460001/src/pkg/runtime/hashmap.g...
src/pkg/runtime/hashmap.go:185: panic("bucketsize wrong")
On 2014/06/30 15:37:20, rsc wrote:
> I can't decide if I should worry that these are now recoverable panics instead
> of throws. Maybe it doesn't matter.

This one is probably fine. But there are more "dynamic" checks, e.g. check that
chan is closed in chan.goc. We don't want it to be suppressed by recover in http
handler, so we will need to expose throw for them. Once we do it, we can revert
this back to throw as well.

[dave_cheney.net, 2014-07-01 06:02:44]

On Tue, Jul 1, 2014 at 3:57 PM,  <dvyukov@google.com> wrote:
>
>
https://codereview.appspot.com/99380043/diff/460001/src/pkg/runtime/hashmap.go
> File src/pkg/runtime/hashmap.go (right):
>
>
https://codereview.appspot.com/99380043/diff/460001/src/pkg/runtime/hashmap.g...
> src/pkg/runtime/hashmap.go:185: panic("bucketsize wrong")
> On 2014/06/30 15:37:20, rsc wrote:
>>
>> I can't decide if I should worry that these are now recoverable panics
>
> instead
>>
>> of throws. Maybe it doesn't matter.
>
>
> This one is probably fine. But there are more "dynamic" checks, e.g.
> check that chan is closed in chan.goc. We don't want it to be suppressed
> by recover in http handler, so we will need to expose throw for them.
> Once we do it, we can revert this back to throw as well.
>
> https://codereview.appspot.com/99380043/

Fair enough, Keith, can you please add a todo and/or open an issue to
expose runtime.throw go side.

[khr1, 2014-07-02 15:13:43]

On Mon, Jun 30, 2014 at 8:37 AM, <rsc@golang.org> wrote:

> LGTM
>
>
>
> https://codereview.appspot.com/99380043/diff/460001/src/
> pkg/runtime/hashmap.go
> File src/pkg/runtime/hashmap.go (right):
>
> https://codereview.appspot.com/99380043/diff/460001/src/
> pkg/runtime/hashmap.go#newcode185
> src/pkg/runtime/hashmap.go:185: panic("bucketsize wrong")
> I can't decide if I should worry that these are now recoverable panics
> instead of throws. Maybe it doesn't matter.
>
> https://codereview.appspot.com/99380043/diff/460001/src/
> pkg/runtime/hashmap.go#newcode222
> src/pkg/runtime/hashmap.go:222: if checkgc {
> What is this?
>
>
This is code that triggers a GC during every allocation call from the
hashmap code.  It was useful once upon a time to find bugs in the custom GC
walking code and the compiler-generated types.  It's probably not all that
useful any more.


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

[khr, 2014-07-16 21:16:32]

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

runtime: convert map implementation to Go.

It's a bit slower, but not painfully so.  There is still room for
improvement (saving space so we can use nosplit, and removing the
requirement for hash/eq stubs).

benchmark                              old ns/op     new ns/op     delta
BenchmarkMegMap                        23.5          24.2          +2.98%
BenchmarkMegOneMap                     14.9          15.7          +5.37%
BenchmarkMegEqMap                      71668         72234         +0.79%
BenchmarkMegEmptyMap                   4.05          4.93          +21.73%
BenchmarkSmallStrMap                   21.9          22.5          +2.74%
BenchmarkMapStringKeysEight_16         23.1          26.3          +13.85%
BenchmarkMapStringKeysEight_32         21.9          25.0          +14.16%
BenchmarkMapStringKeysEight_64         21.9          25.1          +14.61%
BenchmarkMapStringKeysEight_1M         21.9          25.0          +14.16%
BenchmarkIntMap                        21.8          12.5          -42.66%
BenchmarkRepeatedLookupStrMapKey32     39.3          30.2          -23.16%
BenchmarkRepeatedLookupStrMapKey1M     322353        322675        +0.10%
BenchmarkNewEmptyMap                   129           136           +5.43%
BenchmarkMapIter                       137           107           -21.90%
BenchmarkMapIterEmpty                  7.14          8.71          +21.99%
BenchmarkSameLengthMap                 5.24          6.82          +30.15%
BenchmarkBigKeyMap                     34.5          35.3          +2.32%
BenchmarkBigValMap                     36.1          36.1          +0.00%
BenchmarkSmallKeyMap                   26.9          26.7          -0.74%

LGTM=rsc
R=golang-codereviews, dave, dvyukov, rsc, gobot, khr
CC=golang-codereviews
https://codereview.appspot.com/99380043

[gobot, 2014-07-16 21:39:45]

This CL appears to have broken the nacl-amd64p32 builder.
See http://build.golang.org/log/49c10120b5000e37ba395be5d5ad7a651506c449

[dave_cheney.net, 2014-07-16 21:45:35]

This is a real failure. I've raised
https://code.google.com/p/go/issues/detail?id=8378


On Thu, Jul 17, 2014 at 7:39 AM, <gobot@golang.org> wrote:

> This CL appears to have broken the nacl-amd64p32 builder.
> See http://build.golang.org/log/49c10120b5000e37ba395be5d5ad7a651506c449
>
> https://codereview.appspot.com/99380043/
>