# Slice vs map for set in golang

Date: 15 Aug 2015
Author: Erik Dubbelboer

Ever wonder if it’s faster to use a slice or map to represent a set in go? I wrote the following program to find out:

``````package main

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

const maxSize = 26
const tests = 20000000
const findMult = 9999999999 // 100 = 1% hit rate, 1 = 100% hit rate.

type lst []int

func (l lst) has(xxxx int) bool {
for _, i := range l {
if i == xxxx {
return true
}
}
return false
}

type mp map[int]struct{}

func (m mp) has(xxxx int) bool {
_, ok := m[xxxx]
return ok
}

func main() {
rand.Seed(time.Now().UnixNano())

for size := 1; size < maxSize; size++ {
l := make(lst, 0, size)
m := make(mp, size)
for i := 0; i < size; i++ {
e := rand.Int()
l = append(l, e)
m[e] = struct{}{}
}

found := 0
start := time.Now()
for x := 0; x < tests; x++ {
xxxx := rand.Intn(size * findMult)
if l.has(xxxx) {
found++
}
}
sliceDuration := time.Now().Sub(start)

start = time.Now()
for x := 0; x < tests; x++ {
xxxx := rand.Intn(size * findMult)
if m.has(xxxx) {
found++
}
}
mapDuration := time.Now().Sub(start)

// Do something with found so it doesn't get optimized away.
if found > 0 {
rand.Int()
}

fmt.Printf("%d\t%v\n", size, sliceDuration-mapDuration)
}
}``````

And here is the output:

```\$ ./bench.sh
1       -261.887532ms
2       -283.816189ms
3       -180.629338ms
4       -273.558558ms
5       -170.395637ms
6       -110.11527ms
7       -238.179383ms
8       -86.595302ms
9       -386.665905ms
10      -230.164293ms
11      -240.030718ms
12      -310.295027ms
13      -183.209792ms
14      -172.458055ms
15      -210.97313ms
16      -130.370425ms
17      -134.322002ms
18      37.839305ms
19      49.001029ms
20      35.248726ms
21      158.058773ms
22      231.8019ms
23      1.846585ms
24      39.449983ms
25      33.189299ms
```

## Conclusion

As you can see, for less than 18 elements a slice seems to be faster than a map.

Here is the resulting set that I wrote: github.com/ErikDubbelboer/set

The out of place timings you see around 7, 15 and 23 probably have to do with the number of elements go stores per bucket. But I haven’t had the time to look into this.

comments powered by Disqus