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