Skip to content

Instantly share code, notes, and snippets.

@lemire
Created November 15, 2019 02:12
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save lemire/97e7b57a99ed0fb5925b9ec83b8a5dc1 to your computer and use it in GitHub Desktop.
Memory usage in Go
package Main
import (
"math"
"reflect"
"testing"
"github.com/RoaringBitmap/roaring"
"github.com/willf/bitset"
)
// go test -bench=Benchmark
const maxvalue = 1000000
const step = 100
func DeepSize(v interface{}) int64 {
return int64(valueSize(reflect.ValueOf(v), make(map[uintptr]bool)))
}
func valueSize(v reflect.Value, seen map[uintptr]bool) uintptr {
base := v.Type().Size()
switch v.Kind() {
case reflect.Ptr:
p := v.Pointer()
if !seen[p] && !v.IsNil() {
seen[p] = true
return base + valueSize(v.Elem(), seen)
}
case reflect.Slice:
n := v.Len()
for i := 0; i < n; i++ {
base += valueSize(v.Index(i), seen)
}
// Account for the parts of the array not covered by this slice. Since
// we can't get the values directly, assume they're zeroes. That may be
// incorrect, in which case we may underestimate.
if cap := v.Cap(); cap > n {
base += v.Type().Size() * uintptr(cap-n)
}
case reflect.Map:
// A map m has len(m) / 6.5 buckets, rounded up to a power of two, and
// a minimum of one bucket. Each bucket is 16 bytes + 8*(keysize + valsize).
//
// We can't tell which keys are in which bucket by reflection, however,
// so here we count the 16-byte header for each bucket, and then just add
// in the computed key and value sizes.
nb := uintptr(math.Pow(2, math.Ceil(math.Log(float64(v.Len())/6.5)/math.Log(2))))
if nb == 0 {
nb = 1
}
base = 16 * nb
for _, key := range v.MapKeys() {
base += valueSize(key, seen)
base += valueSize(v.MapIndex(key), seen)
}
// We have nb buckets of 8 slots each, and v.Len() slots are filled.
// The remaining slots we will assume contain zero key/value pairs.
zk := v.Type().Key().Size() // a zero key
zv := v.Type().Elem().Size() // a zero value
base += (8*nb - uintptr(v.Len())) * (zk + zv)
case reflect.Struct:
// Chase pointer and slice fields and add the size of their members.
for i := 0; i < v.NumField(); i++ {
f := v.Field(i)
switch f.Kind() {
case reflect.Ptr:
p := f.Pointer()
if !seen[p] && !f.IsNil() {
seen[p] = true
base += valueSize(f.Elem(), seen)
}
case reflect.Slice:
base += valueSize(f, seen)
}
}
case reflect.String:
return base + uintptr(v.Len())
}
return base
}
func BenchmarkHashCreate(b *testing.B) {
b.StopTimer()
bitmaps := make([]map[int]bool, 0, 10)
for i := 0; i < 10; i++ {
bitmap := map[int]bool{} // we force dynamic memory allocation
for v := 0; v <= maxvalue; v += step {
bitmap[v] = true
}
bitmaps = append(bitmaps, bitmap)
}
b.Logf("bytes per value %f ", float64(DeepSize(bitmaps))/(10.0*float64(maxvalue)/float64(step)))
b.StartTimer()
}
func BenchmarkBitsetCreate(b *testing.B) {
b.StopTimer()
bitmaps := make([]*bitset.BitSet, 0, 10)
for i := 0; i < 10; i++ {
bitmap := bitset.New(0) // we force dynamic memory allocation
for v := uint(0); v <= maxvalue; v += step {
bitmap.Set(v)
}
bitmaps = append(bitmaps, bitmap)
}
b.Logf("bytes per value %f ", float64(DeepSize(bitmaps))/(10.0*float64(maxvalue)/float64(step)))
b.StartTimer()
}
func BenchmarkNewBitmap(b *testing.B) {
b.StopTimer()
bitmaps := make([]*roaring.Bitmap, 0, 10)
s := uint64(0)
for i := 0; i < 10; i++ {
bitmap := roaring.New()
for v := uint32(0); v <= maxvalue; v += step {
bitmap.Add(v)
}
bitmaps = append(bitmaps, bitmap)
s += bitmap.GetSizeInBytes()
}
b.Logf("bytes per value %f ", float64(s)/(10*float64(maxvalue)/float64(step)))
b.StartTimer()
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment