Using a bitset instead of boolean[]

[koliver]

Hi there,

I've just started benchmarking hppc's LongOpenHashSet and have been
pleased by its speed and memory usage. One thing I did notice is that
it uses a boolean[] for marking which slots have been allocated. I was
wondering, why not use a java.util.BitSet or an
com.carrotsearch.hppc.BitSet?

I believe the space savings would be significant. I have not
benchmarked the performance impact of it.

Any thoughts?

[Dawid Weiss]

> I've just started benchmarking hppc's LongOpenHashSet and have been
> pleased by its speed and memory usage. One thing I did notice is that
> it uses a boolean[] for marking which slots have been allocated. I was
> wondering, why not use a java.util.BitSet or an
> com.carrotsearch.hppc.BitSet?

This is a deliberate choice. A bitset would be more memory-consuming
but it would be much slower compared to a single byte access (even
with native intrinsics the overhead is visible). Memory is cheaper
nowadays so we've decided to go with bytes. It shouldn't be too hard
to generate a bitset version if you feel desperate to conserve some
memory.

> I believe the space savings would be significant. I have not

Well, it would be 1/8th on the average, but taking into account keys
and values it would be much less...

Dawid

[koliver]

Yep, that all sounds reasonable to me.

For now, we're fine with it as is -- thanks.