Memory usage of []bool

[Deleplace]

While a []bool is great for simplicity, I suspect it takes much more space in memory than a "compact" Bitset. This would be caused by the memory layout of the underlying array, where each bool is individually addressable.

This is important because Bloom filters are designed specifically to be space-efficient, storing only the conflated Bitset instead all the elements themselves, or even all the hash values.

Go has no built-in Bitset type, but it seems that a common and efficient ready-to-use Bitset implementation is *big.Int. (I created an idiomatic snippet here).

It would be interesting to run a "memory usage" benchmark of []bool vs *big.Int. The speed performance results would be interesting as well (I have no idea which one wins on speed!). Fanis, what do you think?

[theodesp]

Hello @Deleplace. Yes, I think []bool is not the most space efficient model for that. If you check some other implementations of Bloom Filters they use either the @willf one:

https://github.com/willf/bitset/blob/master/bitset.go

or a plain []uint64 slice with the rationale that they are more space efficient.

For me, as you said I only did it as a simplified example as It would be strange to talk about boolean values and not use a boolean slice.

I have a relevant article on medium on that>
https://codeburst.io/lets-implement-a-bloom-filter-in-go-b2da8a4b849f

[Deleplace]

Great article :) that's where I came from initially

[Deleplace]

I didn't know about willf/bitset, cool. More complex than *big.Int, but also more performant (I measured).