Benchmark Maps Against Slices for Small Collections in Go

Go programmers reach for a map the moment they need a lookup, and often the collection has six entries: a list of allowed roles, the flags of a command, the headers a handler cares about. For six items a map is not clearly better than a loop over a slice, and it costs more to build and to keep. This article measures where the crossover is on Go 1.25, for int keys and for string keys, for a plain slice scan and for a sorted slice with binary search, and then measures the other half of the bill, which is the cost of building the collection.

It uses the method from benchmarking a Go function properly and avoids the traps in microbenchmark pitfalls. Memory behaviour of large maps is in maps that never shrink. The cornerstone is the Go performance guide.

The benchmark

For each size the program builds the same keys four ways: a []int, a sorted copy, a map[int]struct{}, and the string versions ("user:7932", 9 to 13 bytes) in a []string and a map[string]struct{}. Each benchmark looks up a key that is present, rotating through all the keys so that the branch predictor and the cache cannot specialise on one. The second table times building each collection from empty without a size hint, as code usually does.

package main

import (
	"flag"
	"fmt"
	"slices"
	"sort"
	"strconv"
	"testing"
)

var sinkB bool
var sinkI int

func init() {
	testing.Init()
	flag.Set("test.benchtime", "150ms")
}

func median(f func(b *testing.B)) float64 {
	const runs = 5
	ns := make([]float64, 0, runs)
	for i := 0; i < runs; i++ {
		r := testing.Benchmark(f)
		ns = append(ns, float64(r.T.Nanoseconds())/float64(r.N))
	}
	sort.Float64s(ns)
	return ns[runs/2]
}

func linearInt(keys []int, k int) bool {
	for _, v := range keys {
		if v == k {
			return true
		}
	}
	return false
}

func linearStr(keys []string, k string) bool {
	for _, v := range keys {
		if v == k {
			return true
		}
	}
	return false
}

func main() {
	sizes := []int{1, 4, 8, 16, 64, 1024}
	fmt.Println("lookup of a key that is present, rotating through all keys; ns per lookup")
	fmt.Printf("%6s | %8s %8s %8s %8s | %8s %8s %8s\n", "n", "int:slice", "sorted", "map", "map/slice", "str:slice", "map", "map/slice")
	for _, n := range sizes {
		ik := make([]int, n)
		im := make(map[int]struct{}, n)
		sk := make([]string, n)
		sm := make(map[string]struct{}, n)
		for i := 0; i < n; i++ {
			ik[i] = i*7919 + 13
			im[ik[i]] = struct{}{}
			sk[i] = "user:" + strconv.Itoa(i*7919+13)
			sm[sk[i]] = struct{}{}
		}
		sorted := slices.Clone(ik)
		slices.Sort(sorted)
		a := median(func(b *testing.B) {
			i := 0
			for b.Loop() {
				sinkB = linearInt(ik, ik[i%n])
				i++
			}
		})
		bs := median(func(b *testing.B) {
			i := 0
			for b.Loop() {
				_, sinkB = slices.BinarySearch(sorted, sorted[i%n])
				i++
			}
		})
		c := median(func(b *testing.B) {
			i := 0
			for b.Loop() {
				_, sinkB = im[ik[i%n]]
				i++
			}
		})
		d := median(func(b *testing.B) {
			i := 0
			for b.Loop() {
				sinkB = linearStr(sk, sk[i%n])
				i++
			}
		})
		e := median(func(b *testing.B) {
			i := 0
			for b.Loop() {
				_, sinkB = sm[sk[i%n]]
				i++
			}
		})
		fmt.Printf("%6d | %8.2f %8.2f %8.2f %8.2f | %8.2f %8.2f %8.2f\n", n, a, bs, c, c/a, d, e, e/d)
	}
	fmt.Println()
	fmt.Println("building: n inserts into an empty collection, ns per build (no size hint)")
	fmt.Printf("%6s | %10s %10s\n", "n", "slice", "map")
	for _, n := range []int{4, 64, 256} {
		a := median(func(b *testing.B) {
			for b.Loop() {
				var s []int
				for i := 0; i < n; i++ {
					s = append(s, i)
				}
				sinkI = len(s)
			}
		})
		c := median(func(b *testing.B) {
			for b.Loop() {
				m := map[int]struct{}{}
				for i := 0; i < n; i++ {
					m[i] = struct{}{}
				}
				sinkI = len(m)
			}
		})
		fmt.Printf("%6d | %10.0f %10.0f\n", n, a, c)
	}
}

lookup of a key that is present, rotating through all keys; ns per lookup
     n | int:slice   sorted      map map/slice | str:slice      map map/slice
     1 |     2.15     3.48     2.56     1.19 |     3.16     6.45     2.04
     4 |     3.47     5.64     3.64     1.05 |     4.75     7.85     1.66
     8 |     4.09     6.24     4.45     1.09 |     8.75     8.29     0.95
    16 |     5.40     6.92     5.45     1.01 |    13.10     8.94     0.68
    64 |    15.09     8.02     5.46     0.36 |    55.71     9.62     0.17
  1024 |   175.91    33.51     6.91     0.04 |   847.41    10.53     0.01

building: n inserts into an empty collection, ns per build (no size hint)
     n |      slice        map
     4 |         52         27
    64 |        208       2267
   256 |        571       8588

Lookup results

Int keys: a tie up to 16, then the map

At 1 to 16 entries the scan and the map are within a few percent of each other: 5.40 ns against 5.45 ns at 16. The scan is a tight loop over contiguous memory that the processor can run ahead on, and the map does a hash and a probe. Past 16 the scan grows linearly (15.09 ns at 64, 175.91 ns at 1,024) while the map stays near 5 to 7 ns. At 1,024 the map was 25 times faster.

Binary search is rarely the answer

A sorted slice with slices.BinarySearch was slower than the plain scan up to 16 entries (6.92 ns against 5.40 ns), because each step is a data dependent branch the processor cannot predict, and the scan's branches are predictable. It overtook the scan at 64 (8.02 ns against 15.09 ns) and never beat the map. It is useful when the data is already sorted, must be ordered for another reason, or when memory matters more than speed, since a sorted slice of ints costs 8 bytes per entry.

String keys: the map wins sooner

Comparing two strings costs a length check and a memory comparison, so a scan over strings is more expensive per step than over ints. The scan took 8.75 ns at 8 entries against 8.29 ns for the map, and from there the gap widened: 55.71 ns against 9.62 ns at 64, and 847.41 ns against 10.53 ns at 1,024. At 1 to 4 entries the scan won by about 2 ns. The practical rule for strings is a map from about 8 entries, and the rule for ints is a map from about 16 to 32.

(The keys share the prefix user:, so each comparison reads several bytes before it finds a difference, which favours the map. Short, distinct keys make the scan cheaper.)

Building results

At 4 entries the map was cheaper to build (27 ns against 52 ns) because Go 1.24's map starts as a single group of 8 slots that is allocated with the map, while the slice grows by reallocation at 1, 2 and 4 entries. At 64 entries the picture reversed: building the map cost 2,267 ns against 208 ns, 11 times more. Each insert hashes the key and finds a slot, and the table grows and rehashes several times without a hint. At 256 entries it was 15 times more.

The map is the right structure when lookups outnumber insertions enough to repay that. If you build a 64 entry map and look up once, a scan of the slice would have been 15 ns against 2,267 + 5 ns. Amortised over a few hundred lookups, the map wins. Two things shift the balance: make(map[int]struct{}, n) with a size hint removes the regrowth, and a collection that is built once and read for the life of the process (a configuration table, a routing set) makes the build cost irrelevant.

Memory

A []int of 1,024 entries is 8 KB. The map of the same keys with struct{} values is several times that, since each slot carries a control byte and the table keeps spare capacity to stay fast. For a collection per request or per user, the memory difference matters more than the nanoseconds: ten thousand small maps are ten thousand allocations the collector must track. A slice is one allocation with no pointers inside.

Choosing

1. Up to about 8 entries, use a slice and a loop (or slices.Contains). It is as fast for ints, nearly as fast for strings, cheaper to build and smaller.
2. From 16 to 32 entries, measure with your real keys. Short ints favour the slice up to 16, and strings favour the map from 8.
3. At 64 entries and above, use a map unless the collection is built far more often than read.
4. Use a sorted slice when you need order, range queries or a compact read only structure.
5. Presize (make(map[K]V, n)) whenever you know the count.
6. Prefer correctness of intent. A set that people will add to should be a map, because the code says what it means and the performance cliff of a growing slice scan is quiet and painful. A short constant list can stay a slice.

What this does not tell you

The benchmark looked up keys that are present. A miss on a slice scans everything, and a miss in a map costs about the same as a hit, so absent keys favour the map further. The keys were rotated, so the cache stayed warm; a cold map in a large working set takes cache misses that a contiguous slice avoids. Values were empty structs; a map of large values or a slice of large structs changes the memory picture. Measure with your own types before moving a hot path.

Checklist

• For ints the slice and the map tie to about 16 entries; beyond that the map wins.
• For strings the map wins from about 8 entries.
• Binary search beats the scan only from about 64 entries and never beats the map.
• Building a large map costs about 10 times a slice, so presize it or build it once.
• A slice is one allocation and has no pointers; a map is neither.
• Measure with your keys, sizes and hit rate.

The map implementation is described in the Go 1.24 release notes and the helpers in the slices package documentation.