slicemap_test.go

package main

import (
	"fmt"
	"math/rand"
	"sort"
	"strings"
	"testing"
	"time"
)

const (
	keyLen = 5
	valLen = 20
)

func gen(length int) string {
	var s string
	for i := 0; i < length; i++ {
		s += string(rand.Int31n(126-48) + int32(48))
	}
	return s
}

type Item struct {
	Key string
	Val string
}

/********************
 * A typical key/value storage, once as map[string]string, once
 * as []*Item{string,string}.
 */

func populateKV(theArr []Item, theMap map[string]string) string {
	var query string
	var k, v string

	rand.Seed(time.Now().UnixNano())

	// pick one of the items at random to be the lookup key
	queryI := rand.Intn(len(theArr))

	for i := 0; i < len(theArr); i++ {
		k = gen(keyLen)
		v = gen(valLen)
		theMap[k] = v
		theArr[i] = Item{Key: k, Val: v}

		if i == queryI {
			query = k
		}
	}
	sort.Slice(theArr, func(i, j int) bool { return strings.Compare(theArr[i].Key, theArr[j].Key) > 0 })

	return query
}

func BenchmarkKVItemSlice(b *testing.B) {
	for _, numItems := range []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 50} {
		numItems := numItems
		b.Run(fmt.Sprintf("%d", numItems), func(b *testing.B) {
			theMap := make(map[string]string)
			theArr := make([]Item, numItems)
			q := populateKV(theArr, theMap)

			b.ResetTimer()
			for n := 0; n < b.N; n++ {
				i, j := 0, len(theArr)

				for i < j {
					h := int(uint(i+j) >> 1) // avoid overflow when computing h
					// i ≤ h < j
					if theArr[h].Key > q {
						i = h + 1 // preserves f(i-1) == false
					} else {
						j = h // preserves f(j) == true
					}
				}
				if theArr[i].Key != q {
					b.Fail()
				}
			}
		})
	}
}

func BenchmarkKVStringMap(b *testing.B) {
	for _, numItems := range []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 50} {
		numItems := numItems
		b.Run(fmt.Sprintf("%d", numItems), func(b *testing.B) {
			var found bool
			theMap := make(map[string]string)
			theArr := make([]Item, numItems)
			q := populateKV(theArr, theMap)

			b.ResetTimer()
			for i := 0; i < b.N; i++ {
				if theMap[q] != "" {
					found = true
				}
			}
			if !found {
				b.Fail()
			}
		})
	}
}

name              time/op
KVItemSlice/1-8   7.42ns ± 1%
KVItemSlice/2-8   13.2ns ±10%
KVItemSlice/3-8   13.3ns ± 4%
KVItemSlice/4-8   16.4ns ±22%
KVItemSlice/5-8   18.7ns ± 3%
KVItemSlice/6-8   18.3ns ±11%
KVItemSlice/7-8   18.6ns ± 7%
KVItemSlice/8-8   20.8ns ±21%
KVItemSlice/9-8   23.9ns ± 4%
KVItemSlice/10-8  21.6ns ±20%
KVItemSlice/20-8  28.5ns ± 3%
KVItemSlice/50-8  33.9ns ± 3%
KVStringMap/1-8   5.78ns ± 0%
KVStringMap/2-8   6.96ns ±41%
KVStringMap/3-8   11.9ns ±52%
KVStringMap/4-8   15.3ns ±38%
KVStringMap/5-8   21.4ns ±73%
KVStringMap/6-8   28.2ns ±66%
KVStringMap/7-8   26.8ns ±78%
KVStringMap/8-8   33.2ns ±58%
KVStringMap/9-8   12.2ns ±16%
KVStringMap/10-8  11.6ns ±13%
KVStringMap/20-8  12.6ns ±14%
KVStringMap/50-8  13.7ns ±38%

Seems like the Slice one scale ... "better" but actually the map is pretty consistent once we are above 10 items and actually faster - it is also somehow faster anywhere else but around 4-8 number of items ...

original script https://gist.github.com/grahamking/dbc90cb3f45c8fea2ba6