All Benchmarks

Go Benchmark

Map Lookup vs Slice Search

When does a map actually beat a linear slice search for membership tests?

mapslicelookupmembershipcontainsdata-structures

Checking whether a value is part of a known set is one of the most common operations in Go programs. The reflexive answer is "use a map[string]struct{}, maps are O(1)" — but hashing a key has a fixed cost, while scanning a small slice with slices.Contains is a tight, cache-friendly loop. This benchmark measures both approaches at 5, 10, 50, and 1000 elements to find the crossover point where the map's constant-time lookup overtakes the linear search. The result surprises most people: for small collections, the "slower" linear search wins.

linux/amd64AMD Ryzen 9 9950X3D 16-Core Processorbenchmarks/map-membership-vs-slice-search
Compare atCPUs

1 CPU

Size5

Fastest

Map Lookup

4.22 ns/op

Slowest

Slice Contains

4.61 ns/op

Size10

Fastest

Map Lookup

5.27 ns/op

Slowest

Slice Contains

8.83 ns/op · 1.7x slower

Size50

Fastest

Map Lookup

5.82 ns/op

Slowest

Slice Contains

34.38 ns/op · 5.9x slower

Size1000

Fastest

Map Lookup

6.4 ns/op

Slowest

Slice Contains

658.45 ns/op · 103x slower

32 CPUs

Size5

Fastest

Map Lookup

4.28 ns/op

Slowest

Slice Contains

4.63 ns/op

Size10

Fastest

Map Lookup

5.38 ns/op

Slowest

Slice Contains

8.86 ns/op · 1.6x slower

Size50

Fastest

Map Lookup

6.01 ns/op

Slowest

Slice Contains

34.55 ns/op · 5.7x slower

Size1000

Fastest

Map Lookup

6.52 ns/op

Slowest

Slice Contains

662.38 ns/op · 102x slower

Performance Comparison (lower is better)
CPU:

Map Lookup #

Fastest (Size5)Fastest (Size10)Fastest (Size50)Fastest (Size1000)

Uses a map[string]struct{} as a set and checks membership with _, ok := set[key]. Every lookup pays the fixed cost of hashing the key, but the cost stays flat no matter how many elements the set holds — the classic O(1) behavior maps are known for.

Performance (lower is better)
CPU:
// Collection sizes covered by the size* behaviors.
const (
	sizeTiny   = 5
	sizeSmall  = 10
	sizeMedium = 50
	sizeLarge  = 1000
)

func benchmarkMapLookup(b *testing.B, size int) {
	keys := makeKeys(size)
	set := make(map[string]struct{}, size)
	for _, key := range keys {
		set[key] = struct{}{}
	}

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		_, sink = set[keys[i%size]]
	}
}

func BenchmarkMapLookup_size5(b *testing.B)    { benchmarkMapLookup(b, sizeTiny) }
func BenchmarkMapLookup_size10(b *testing.B)   { benchmarkMapLookup(b, sizeSmall) }
func BenchmarkMapLookup_size50(b *testing.B)   { benchmarkMapLookup(b, sizeMedium) }
func BenchmarkMapLookup_size1000(b *testing.B) { benchmarkMapLookup(b, sizeLarge) }
1 CPU

Size5

1.1xfaster(9%)thanSlice Contains

Size10

1.7xfaster(67%)thanSlice Contains

Size50

5.9xfaster(490%)thanSlice Contains

Size1000

102.8xfaster(10181%)thanSlice Contains
32 CPUs

Size5

1.1xfaster(8%)thanSlice Contains

Size10

1.6xfaster(65%)thanSlice Contains

Size50

5.7xfaster(475%)thanSlice Contains

Size1000

101.6xfaster(10057%)thanSlice Contains

Slice Contains #

Slowest (Size5)Slowest (Size10)Slowest (Size50)Slowest (Size1000)

Uses slices.Contains(keys, key) from the standard library, which walks the slice front to back and compares each element. The work grows linearly with the slice length, but for small slices the sequential, cache-friendly memory access and lack of hashing make it faster than a map lookup.

Performance (lower is better)
CPU:
// Collection sizes covered by the size* behaviors.
const (
	sizeTiny   = 5
	sizeSmall  = 10
	sizeMedium = 50
	sizeLarge  = 1000
)

func benchmarkSliceContains(b *testing.B, size int) {
	keys := makeKeys(size)

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		sink = slices.Contains(keys, keys[i%size])
	}
}

func BenchmarkSliceContains_size5(b *testing.B)    { benchmarkSliceContains(b, sizeTiny) }
func BenchmarkSliceContains_size10(b *testing.B)   { benchmarkSliceContains(b, sizeSmall) }
func BenchmarkSliceContains_size50(b *testing.B)   { benchmarkSliceContains(b, sizeMedium) }
func BenchmarkSliceContains_size1000(b *testing.B) { benchmarkSliceContains(b, sizeLarge) }
1 CPU

Size5

1.1xslower(9%)thanMap Lookup

Size10

1.7xslower(67%)thanMap Lookup

Size50

5.9xslower(490%)thanMap Lookup

Size1000

102.8xslower(10181%)thanMap Lookup
32 CPUs

Size5

1.1xslower(8%)thanMap Lookup

Size10

1.6xslower(65%)thanMap Lookup

Size50

5.7xslower(475%)thanMap Lookup

Size1000

101.6xslower(10057%)thanMap Lookup

Contributors

MarvinJWendt
MarvinJWendt