시몽

Just a tech.

Sets in Go

Go doesn’t have a type for sets. Some propose to use a map[T]bool to build a set of items of type T. For instance:

// Create a set
set := make(map[int]bool)

// Add some values
set[1] = true
set[5] = true

// Check if some values are in the set
if set[1] {
	fmt.Println("1 is in the set")
}
if set[2] {
	fmt.Println("2 is in the set")
}

// Remove a value
delete(set, 1)

// List values
for i := range set {
	fmt.Println(i)
}

This has two drawbacks:

  • Values in the map must always be true, otherwise listing values doesn’t work (or requires an additional if). This is misleading.
  • Values in the map take some space (1 byte per key).

A better alternative is to use map[T]struct{} (a map with empty structs as values). For instance:

// Create a set
set := make(map[int]struct{})

// Add some values
set[1] = struct{}{}
set[5] = struct{}{}

// Check if some values are in the set
if _, ok := set[1]; ok {
	fmt.Println("1 is in the set")
}
if _, ok := set[2]; ok {
	fmt.Println("2 is in the set")
}

// Remove a value
delete(set, 1)

// List values
for i := range set {
	fmt.Println(i)
}

Update: benchmarks

Some of you requested some benchmarks to know how much memory is saved by using struct{} instead of bool values. I ran this little test program:

package main

import (
	"fmt"
	"testing"
)

func benchmarkBool(b *testing.B) {
	s := make(map[int]bool)

	for i := 0; i < 10000*b.N; i++ {
		s[2*i] = true
	}
}

func benchmarkStruct(b *testing.B) {
	s := make(map[int]struct{})

	for i := 0; i < 10000*b.N; i++ {
		s[2*i] = struct{}{}
	}
}

func main() {
	boolRes := testing.Benchmark(benchmarkBool)
	fmt.Println("bool:", boolRes.MemString())

	structRes := testing.Benchmark(benchmarkStruct)
	fmt.Println("struct{}:", structRes.MemString())

	fmt.Println("ratio:", float32(boolRes.AllocedBytesPerOp()) / float32(structRes.AllocedBytesPerOp()))
}

Here are the results:

> go run set.go
bool:   444249 B/op	     307 allocs/op
struct{}:   403625 B/op	     306 allocs/op
ratio: 1.1006479

So you save 10% memory for int maps (on a 64-bit machine).


Questions, comments? Please use my public inbox by sending a plain-text email to ~emersion/public-inbox@lists.sr.ht.