Benchmark comparing map access vs slice search

slicemap_test.go

package main

import (
	"math/rand"
	"testing"
	"time"
)

const (
	numItems = 100 // change this to see how number of items affects speed
	keyLen   = 10
	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.Int31n(numItems)

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

		if i == int(queryI) {
			query = k
		}
	}
	return query
}

func BenchmarkKVItemSlice(b *testing.B) {
	var found bool
	theMap := make(map[string]string)
	theArr := make([]*Item, numItems)
	q := populateKV(theArr, theMap)

	b.ResetTimer()
	var j int
	for i := 0; i < b.N; i++ {
		for j = 0; j < numItems; j++ {
			if theArr[j].Key == q {
				found = true
				continue
			}
		}
	}
	if !found {
		b.Fail()
	}
}

func BenchmarkKVStringMap(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()
	}
}

/********************
 * A set of integers, once as []int, once as map[int]struct{}
 */

func populateInts(theArr []int, theMap map[int]struct{}) int {
	var query int
	rand.Seed(time.Now().UnixNano())

	// pick one of the items at random to be the lookup key
	queryI := rand.Int31n(numItems)

	for i := 0; i < numItems; i++ {
		num := rand.Int()
		theArr[i] = num
		theMap[num] = struct{}{}

		if i == int(queryI) {
			query = num
		}
	}
	return query
}

func BenchmarkSetIntSlice(b *testing.B) {
	var found bool
	theMap := make(map[int]struct{})
	theArr := make([]int, numItems)
	q := populateInts(theArr, theMap)

	b.ResetTimer()
	var j int
	for i := 0; i < b.N; i++ {
		for j = 0; j < numItems; j++ {
			if theArr[j] == q {
				found = true
				continue
			}
		}
	}
	if !found {
		b.Fail()
	}
}

func BenchmarkSetIntMap(b *testing.B) {
	var found bool
	theMap := make(map[int]struct{})
	theArr := make([]int, numItems)
	q := populateInts(theArr, theMap)

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

A "continue" statement begins the next iteration of the innermost "for" loop at its post statement.

Is there not a flaw in this code, regarding the continue statements? They continue on the innermost, while you mean outer, right?

definately should rewrite this part of code

for j = 0; j < numItems; j++ {
	if theArr[j] == q {
		found = true
		continue
	}
}

like this

for _, value := range theArr {//use range instead increment to avoid unnesessary index bounds check
	if value == q {
		found = true
		break//continue just pass all the items even if we found
	}
}

So on my i7-7700 On 20 items

go test -bench=Set
BenchmarkSetIntSlice-8          300000000                3.64 ns/op
BenchmarkSetIntMap-8            200000000                6.40 ns/op

100 items

BenchmarkSetIntSlice-8          100000000               27.1 ns/op
BenchmarkSetIntMap-8            200000000                6.71 ns/op

I created a fork of your benchmark that fixes some issues I found with it (including the continue and bounds check one mentioned above): https://gist.github.com/JelteF/1251f180966eb974d7732ea6c3d3b7ff

The numbers I now get are that the int set is now slower only at ~100 items and strings are slower at ~20 items.