시몽

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

Status update, April 2021

Another month goes by! I’m afraid that I have very little to share this month. You can check out the sourcehut “what’s cooking” post for sourcehut news, but outside of that I have focused almost entirely on the programming language project this month, for wh…

via Drew DeVault's blog

A First Foray into Rendering Less

In RADV we just added an option to speed up rendering by rendering less pixels.

via Bas Nieuwenhuizen

Testing 4x4 matrix inversion precision

It is extremely rare that a hobby software project of mine gets completed, but now it has happened. Behold! Fourbyfour!Have you ever had to implement a mathematical algorithm, say, matrix inversion? You want it to be fast and measuring the speed is fairly…

via Pekka Paalanen

Generated by openring