setmemtest.go

package main

import (
	"flag"
	"fmt"
	"math/rand"
	"runtime"
)

type (
	intSet map[int32]struct{}
)

func buildSet(n int) intSet {
	s := intSet{}

	for i := 0; i < n; i++ {
		s[int32(i)] = struct{}{}
	}

	return s
}

func buildRandomSet(n int) intSet {
	s := intSet{}

	for i := 0; i < n; i++ {
		s[rand.Int31()] = struct{}{}
	}

	return s
}

// make sure set can not be garbage collected until we are done
func useSet(s intSet, n int) {
	if len(s) == n*n {
		panic("wtf")
	}
}

func main() {
	maxN := flag.Int("maxN", 100*1000*1000, "maximum number of set elements")
	flag.Parse()

	data := []struct {
		name string
		ctor func(int) intSet
	}{
		{"linear", buildSet},
		{"random", buildRandomSet},
	}

	for _, d := range data {
		for n := 10; n <= *maxN; n *= 10 {
			s := d.ctor(n)

			runtime.GC()
			var m runtime.MemStats
			runtime.ReadMemStats(&m)

			fmt.Printf("%v %v:\t%v bytes\t(%v per element)\n", n, d.name, m.Alloc, float64(m.Alloc)/float64(n))
			useSet(s, n)
		}
	}
}

Go 1.6, OS X 64bit:

10 linear:  42040 bytes (4204 per element)
100 linear: 44776 bytes (447.76 per element)
1000 linear:    56176 bytes (56.176 per element)
10000 linear:   150376 bytes    (15.0376 per element)
100000 linear:  981560 bytes    (9.8156 per element)
1000000 linear: 12873480 bytes  (12.87348 per element)
10000000 linear:    107134312 bytes (10.7134312 per element)
100000000 linear:   947442216 bytes (9.47442216 per element)
10 random:  45640 bytes (4564 per element)
100 random: 46584 bytes (465.84 per element)
1000 random:    58184 bytes (58.184 per element)
10000 random:   152136 bytes    (15.2136 per element)
100000 random:  984856 bytes    (9.84856 per element)
1000000 random: 12880088 bytes  (12.880088 per element)
10000000 random:    107053896 bytes (10.7053896 per element)
100000000 random:   936508568 bytes (9.36508568 per element)