1 // Copyright 2013 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 package runtime_test 5 6 import ( 7 "fmt" 8 "strings" 9 "testing" 10 ) 11 12 const size = 10 13 14 func BenchmarkHashStringSpeed(b *testing.B) { 15 strings := make([]string, size) 16 for i := 0; i < size; i++ { 17 strings[i] = fmt.Sprintf("string#%d", i) 18 } 19 sum := 0 20 m := make(map[string]int, size) 21 for i := 0; i < size; i++ { 22 m[strings[i]] = 0 23 } 24 idx := 0 25 b.ResetTimer() 26 for i := 0; i < b.N; i++ { 27 sum += m[strings[idx]] 28 idx++ 29 if idx == size { 30 idx = 0 31 } 32 } 33 } 34 35 type chunk [17]byte 36 37 func BenchmarkHashBytesSpeed(b *testing.B) { 38 // a bunch of chunks, each with a different alignment mod 16 39 var chunks [size]chunk 40 // initialize each to a different value 41 for i := 0; i < size; i++ { 42 chunks[i][0] = byte(i) 43 } 44 // put into a map 45 m := make(map[chunk]int, size) 46 for i, c := range chunks { 47 m[c] = i 48 } 49 idx := 0 50 b.ResetTimer() 51 for i := 0; i < b.N; i++ { 52 if m[chunks[idx]] != idx { 53 b.Error("bad map entry for chunk") 54 } 55 idx++ 56 if idx == size { 57 idx = 0 58 } 59 } 60 } 61 62 func BenchmarkHashInt32Speed(b *testing.B) { 63 ints := make([]int32, size) 64 for i := 0; i < size; i++ { 65 ints[i] = int32(i) 66 } 67 sum := 0 68 m := make(map[int32]int, size) 69 for i := 0; i < size; i++ { 70 m[ints[i]] = 0 71 } 72 idx := 0 73 b.ResetTimer() 74 for i := 0; i < b.N; i++ { 75 sum += m[ints[idx]] 76 idx++ 77 if idx == size { 78 idx = 0 79 } 80 } 81 } 82 83 func BenchmarkHashInt64Speed(b *testing.B) { 84 ints := make([]int64, size) 85 for i := 0; i < size; i++ { 86 ints[i] = int64(i) 87 } 88 sum := 0 89 m := make(map[int64]int, size) 90 for i := 0; i < size; i++ { 91 m[ints[i]] = 0 92 } 93 idx := 0 94 b.ResetTimer() 95 for i := 0; i < b.N; i++ { 96 sum += m[ints[idx]] 97 idx++ 98 if idx == size { 99 idx = 0 100 } 101 } 102 } 103 func BenchmarkHashStringArraySpeed(b *testing.B) { 104 stringpairs := make([][2]string, size) 105 for i := 0; i < size; i++ { 106 for j := 0; j < 2; j++ { 107 stringpairs[i][j] = fmt.Sprintf("string#%d/%d", i, j) 108 } 109 } 110 sum := 0 111 m := make(map[[2]string]int, size) 112 for i := 0; i < size; i++ { 113 m[stringpairs[i]] = 0 114 } 115 idx := 0 116 b.ResetTimer() 117 for i := 0; i < b.N; i++ { 118 sum += m[stringpairs[idx]] 119 idx++ 120 if idx == size { 121 idx = 0 122 } 123 } 124 } 125 126 func BenchmarkMegMap(b *testing.B) { 127 m := make(map[string]bool) 128 for suffix := 'A'; suffix <= 'G'; suffix++ { 129 m[strings.Repeat("X", 1<<20-1)+fmt.Sprint(suffix)] = true 130 } 131 key := strings.Repeat("X", 1<<20-1) + "k" 132 b.ResetTimer() 133 for i := 0; i < b.N; i++ { 134 _, _ = m[key] 135 } 136 } 137 138 func BenchmarkMegOneMap(b *testing.B) { 139 m := make(map[string]bool) 140 m[strings.Repeat("X", 1<<20)] = true 141 key := strings.Repeat("Y", 1<<20) 142 b.ResetTimer() 143 for i := 0; i < b.N; i++ { 144 _, _ = m[key] 145 } 146 } 147 148 func BenchmarkMegEqMap(b *testing.B) { 149 m := make(map[string]bool) 150 key1 := strings.Repeat("X", 1<<20) 151 key2 := strings.Repeat("X", 1<<20) // equal but different instance 152 m[key1] = true 153 b.ResetTimer() 154 for i := 0; i < b.N; i++ { 155 _, _ = m[key2] 156 } 157 } 158 159 func BenchmarkMegEmptyMap(b *testing.B) { 160 m := make(map[string]bool) 161 key := strings.Repeat("X", 1<<20) 162 b.ResetTimer() 163 for i := 0; i < b.N; i++ { 164 _, _ = m[key] 165 } 166 } 167 168 func BenchmarkSmallStrMap(b *testing.B) { 169 m := make(map[string]bool) 170 for suffix := 'A'; suffix <= 'G'; suffix++ { 171 m[fmt.Sprint(suffix)] = true 172 } 173 key := "k" 174 b.ResetTimer() 175 for i := 0; i < b.N; i++ { 176 _, _ = m[key] 177 } 178 } 179 180 func BenchmarkMapStringKeysEight_16(b *testing.B) { benchmarkMapStringKeysEight(b, 16) } 181 func BenchmarkMapStringKeysEight_32(b *testing.B) { benchmarkMapStringKeysEight(b, 32) } 182 func BenchmarkMapStringKeysEight_64(b *testing.B) { benchmarkMapStringKeysEight(b, 64) } 183 func BenchmarkMapStringKeysEight_1M(b *testing.B) { benchmarkMapStringKeysEight(b, 1<<20) } 184 185 func benchmarkMapStringKeysEight(b *testing.B, keySize int) { 186 m := make(map[string]bool) 187 for i := 0; i < 8; i++ { 188 m[strings.Repeat("K", i+1)] = true 189 } 190 key := strings.Repeat("K", keySize) 191 b.ResetTimer() 192 for i := 0; i < b.N; i++ { 193 _ = m[key] 194 } 195 } 196 197 func BenchmarkIntMap(b *testing.B) { 198 m := make(map[int]bool) 199 for i := 0; i < 8; i++ { 200 m[i] = true 201 } 202 b.ResetTimer() 203 for i := 0; i < b.N; i++ { 204 _, _ = m[7] 205 } 206 } 207 208 // Accessing the same keys in a row. 209 func benchmarkRepeatedLookup(b *testing.B, lookupKeySize int) { 210 m := make(map[string]bool) 211 // At least bigger than a single bucket: 212 for i := 0; i < 64; i++ { 213 m[fmt.Sprintf("some key %d", i)] = true 214 } 215 base := strings.Repeat("x", lookupKeySize-1) 216 key1 := base + "1" 217 key2 := base + "2" 218 b.ResetTimer() 219 for i := 0; i < b.N/4; i++ { 220 _ = m[key1] 221 _ = m[key1] 222 _ = m[key2] 223 _ = m[key2] 224 } 225 } 226 227 func BenchmarkRepeatedLookupStrMapKey32(b *testing.B) { benchmarkRepeatedLookup(b, 32) } 228 func BenchmarkRepeatedLookupStrMapKey1M(b *testing.B) { benchmarkRepeatedLookup(b, 1<<20) } 229 230 func BenchmarkNewEmptyMap(b *testing.B) { 231 b.ReportAllocs() 232 for i := 0; i < b.N; i++ { 233 _ = make(map[int]int) 234 } 235 } 236 237 func BenchmarkNewSmallMap(b *testing.B) { 238 b.ReportAllocs() 239 for i := 0; i < b.N; i++ { 240 m := make(map[int]int) 241 m[0] = 0 242 m[1] = 1 243 } 244 } 245 246 func BenchmarkMapIter(b *testing.B) { 247 m := make(map[int]bool) 248 for i := 0; i < 8; i++ { 249 m[i] = true 250 } 251 b.ResetTimer() 252 for i := 0; i < b.N; i++ { 253 for range m { 254 } 255 } 256 } 257 258 func BenchmarkMapIterEmpty(b *testing.B) { 259 m := make(map[int]bool) 260 b.ResetTimer() 261 for i := 0; i < b.N; i++ { 262 for range m { 263 } 264 } 265 } 266 267 func BenchmarkSameLengthMap(b *testing.B) { 268 // long strings, same length, differ in first few 269 // and last few bytes. 270 m := make(map[string]bool) 271 s1 := "foo" + strings.Repeat("-", 100) + "bar" 272 s2 := "goo" + strings.Repeat("-", 100) + "ber" 273 m[s1] = true 274 m[s2] = true 275 b.ResetTimer() 276 for i := 0; i < b.N; i++ { 277 _ = m[s1] 278 } 279 } 280 281 type BigKey [3]int64 282 283 func BenchmarkBigKeyMap(b *testing.B) { 284 m := make(map[BigKey]bool) 285 k := BigKey{3, 4, 5} 286 m[k] = true 287 for i := 0; i < b.N; i++ { 288 _ = m[k] 289 } 290 } 291 292 type BigVal [3]int64 293 294 func BenchmarkBigValMap(b *testing.B) { 295 m := make(map[BigKey]BigVal) 296 k := BigKey{3, 4, 5} 297 m[k] = BigVal{6, 7, 8} 298 for i := 0; i < b.N; i++ { 299 _ = m[k] 300 } 301 } 302 303 func BenchmarkSmallKeyMap(b *testing.B) { 304 m := make(map[int16]bool) 305 m[5] = true 306 for i := 0; i < b.N; i++ { 307 _ = m[5] 308 } 309 } 310 311 type ComplexAlgKey struct { 312 a, b, c int64 313 _ int 314 d int32 315 _ int 316 e string 317 _ int 318 f, g, h int64 319 } 320 321 func BenchmarkComplexAlgMap(b *testing.B) { 322 m := make(map[ComplexAlgKey]bool) 323 var k ComplexAlgKey 324 m[k] = true 325 for i := 0; i < b.N; i++ { 326 _ = m[k] 327 } 328 } 329
