Created
November 15, 2019 02:12
Star
You must be signed in to star a gist
Memory usage in Go
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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