Optimize the cost of allocating empty bitmaps

[anacrolix]

New{,Bitmap} makes 2 heap allocations that become very costly when dealing with a lot of Bitmap allocations, these allocations occur even for empty Bitmaps. I have a wrapper that avoids these allocations where possible, by providing a lazy initialized Bitmap that works as expected with the zero value. It would be great to see this supported in this repo instead.

[maciej]

@anacrolix you're aiming at cutting the allocations from 2 to 1, that's correct?

[anacrolix]

No, to zero unless bits are set. See the referred wrapper package.

[maciej]

OK, from what I understand you're storing the struct by value as opposed to by reference in the parent structure. I don't see a reason why you couldn't do it with roaring.Bitmap.

BTW unless I'm doing my benchmarks wrong, roaring.New() is actually doing only a single allocation:

go test -bench BenchmarkNewBitmap  -benchmem -run -
goos: darwin
goarch: amd64
pkg: github.com/RoaringBitmap/roaring
BenchmarkNewBitmap-4   	20000000	        56.7 ns/op	     112 B/op	       1 allocs/op
PASS
ok  	github.com/RoaringBitmap/roaring	1.208s

var Rb *Bitmap

func BenchmarkNewBitmap(b *testing.B) {
	for i := 0; i < b.N; i++ {
		Rb = New()
	}
}

[anacrolix]

It's not that it's by value, it's that it's lazily allocating to the heap. Also you may want to add that BenchmarkNewBitmap to the standard benchmarks.

[lemire]

I have added benchmarks.

$ go test -bench BenchmarkNewBitmap  -run -
goos: linux
goarch: amd64
pkg: github.com/RoaringBitmap/roaring
BenchmarkNewBitmap-2   	50000000	        38.7 ns/op
PASS
ok  	github.com/RoaringBitmap/roaring	1.982s

$ go test -bench BenchmarkEmptyArray  -run -
goos: linux
goarch: amd64
pkg: github.com/RoaringBitmap/roaring
BenchmarkEmptyArray-2   	200000000	         6.06 ns/op
PASS
ok  	github.com/RoaringBitmap/roaring	1.826s

So creating a Roaring bitmap is about 6x slower than creating an empty slice on my particular system with this benchmark.

It does not sound insanely inefficient. A slice is a simpler thing.

I'm not sure how much the library could/should do here. If you have objects and you expect most of them to be unused... you could just have them initialized as nil and only allocate them as needed.

This being said, if you do have a pull request... you could prove my instincts wrong...