Skip to content

Instantly share code, notes, and snippets.

@ear7h
Created June 21, 2018 00:09
Show Gist options
  • Save ear7h/0bdbe938bfd1337e59d582791bb2c8e8 to your computer and use it in GitHub Desktop.
Save ear7h/0bdbe938bfd1337e59d582791bb2c8e8 to your computer and use it in GitHub Desktop.
map vs ordered slice benchmark
package db_test
import (
"testing"
"math/rand"
"sort"
"time"
"fmt"
"encoding/base64"
)
const MaxKeyLen = 20
const MaxValLen = 16
func init() {
rand.Seed(time.Now().Unix())
}
type item struct {
key, val string
}
type set []item
func (s set) Len() int {
return len(s)
}
func (s set) Swap(i, j int) {
s[j], s[i] = s[i], s[j]
}
func (s set)Less(i, j int) bool {
return s[i].key < s[j].key
}
func shuffle(arr []string) []string {
n := len(arr)
perm := rand.Perm(n)
ret := make([]string, n)
for i := 0; i < n; i ++ {
ret[i] = arr[perm[i]]
}
return ret
}
// max length n
func randString(n int) string {
nn := rand.Int31n(int32(n))
byt := make([]byte, nn)
_, err := rand.Read(byt)
if err != nil {
panic(err)
}
return base64.StdEncoding.EncodeToString(byt)
}
func makeDataSet(n int) (s set, m map[string]string, keys []string) {
s = make(set, n)
m = make(map[string]string, n)
keys = make([]string, n)
for i:= 0; i < n; i++ {
k := randString(MaxKeyLen)
v := randString(MaxValLen)
s[i] = item{k, v}
m[k] = v
keys[i] = k
}
keys = shuffle(keys)
sort.Sort(s)
return s, m, keys
}
func BenchmarkMapAndOslice(b *testing.B) {
setLen := 10000
s, m, keys := makeDataSet(setLen)
searchSlice := func (k string) (string, bool) {
i := sort.Search(setLen, func(i int) bool {
return s[i].key >= k
})
if i == setLen {
return "", false
}
return s[i].val, true
}
searchMap := func (k string) (string, bool) {
v, ok := m[k]
return v, ok
}
b.Run("bench slice", func (b *testing.B) {
for n := 0; n < b.N; n ++ {
k := keys[n % setLen]
_, ok := searchSlice(k)
if !ok {
fmt.Println("keys: ", keys)
fmt.Println("s: ", s)
panic(k+ " not found")
}
}
})
b.Run("bench map", func (b *testing.B) {
for n := 0; n < b.N; n ++ {
k := keys[n % setLen]
_, ok := searchMap(k)
if !ok {
fmt.Println("keys: ", keys)
fmt.Println("m: ", m)
panic(k + " not found")
}
}
})
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment