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://golang.org/cl/
99380043