Set in Go

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 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)
}

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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("AllocedBytesPerOp ratio:", float32(boolRes.AllocedBytesPerOp()) / float32(structRes.AllocedBytesPerOp()))
	fmt.Println("AllocsPerOp ratio:", float32(boolRes.AllocsPerOp()) / float32(structRes.AllocsPerOp()))
} 

/* 
result:

> go run set.go
bool:       615078 B/op	     429 allocs/op
struct{}:   393032 B/op	     299 allocs/op
AllocedBytesPerOp ratio: 1.5649565
AllocsPerOp ratio:       1.4347826

*/
  • allocs/op 表示每个 op 发生多少个不同的内存分配（单次迭代）。越小越好
  • B/op 是每个操作分配了多少字节。 越小越好

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