map vs ordered slice benchmark

map_v_oslice_test.go

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")
			}
		}
	})


}