libgo/go/runtime/mapspeed_test.go

   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 BenchmarkMapIter(b *testing.B) {
 238         m := make(map[int]bool)
 239         for i := 0; i < 8; i++ {
 240                 m[i] = true
 241         }
 242         b.ResetTimer()
 243         for i := 0; i < b.N; i++ {
 244                 for _, _ = range m {
 245                 }
 246         }
 247 }
 248
 249 func BenchmarkMapIterEmpty(b *testing.B) {
 250         m := make(map[int]bool)
 251         b.ResetTimer()
 252         for i := 0; i < b.N; i++ {
 253                 for _, _ = range m {
 254                 }
 255         }
 256 }
 257
 258 func BenchmarkSameLengthMap(b *testing.B) {
 259         // long strings, same length, differ in first few
 260         // and last few bytes.
 261         m := make(map[string]bool)
 262         s1 := "foo" + strings.Repeat("-", 100) + "bar"
 263         s2 := "goo" + strings.Repeat("-", 100) + "ber"
 264         m[s1] = true
 265         m[s2] = true
 266         b.ResetTimer()
 267         for i := 0; i < b.N; i++ {
 268                 _ = m[s1]
 269         }
 270 }