시몽

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.

Articles from blogs I follow

Right Out The Gate

Droppin’ Em

via Mike Blumenkrantz

Apple GPU drivers now in Asahi Linux

We’re excited to announce our first Apple GPU driver release! We’ve been working hard over the past two years to bring this new driver to everyone, and we’re really proud to finally be here. This is still an alpha driver, but it’s already good enough to ru…

via On Life and Lisp

I shall toil at a reduced volume

Over the last nine years I have written 300,000 words for this blog on the topics which are important to me. I am not certain that I have much left to say. I can keep revisiting these topics for years, each time adding a couple more years of wisdom and impro…

via Drew DeVault's blog

Generated by openring