시몽

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

Reverse-engineering the Mali G78

After a month of reverse-engineering, we’re excited to release documentation on the Valhall instruction set, available as a PDF. The findings are summarized in an XML architecture description for machine consumption. In tandem with the documentation, we’v…

via On Life and Lisp

Status update, July 2021

Hallo uit Nederland! I’m writing to you from a temporary workstation in Amsterdam, pending the installation of a better one that I’ll put together after I visit a furniture store today. I’ve had to slow a few things down somewhat while I prepare for this mov…

via Drew DeVault's blog

Updating the Go Memory Model

What changes should we make to Go&#39;s memory model? (Memory Models, Part 3)

via research!rsc

Generated by openring