Alternative to Java Bitset with array like perform

Question

I am looking for an alternative to Java Bitset implementation. I am implementing a high performance algorithm and seems like using a Bitset object is killing its performance. Any ideas?

Answer 1

If you really must squeeze the maximum performance out of this thing, and if memory does not matter, you can try storing each one of your flags in an integer whose bit size is equal to the width of the data bus of your CPU.

You are probably on a 64-bit data bus CPU, so try long integers.

Answer 2

Someone here has compared boolean[] to BitSet and concluded with:

BitSet is more memory efficient than boolean[] except for very small sizes. Each boolean in the array takes a byte. The numbers from runtime.freeMemory() are a bit muddled for BitSet, but less.

boolean[] is more CPU efficient except for very large sizes, where they are about even. E.g., for size 1 million boolean[] is about four times faster (e.g. 6ms vs 27ms), for ten and a hundred million they are about even.

If you Google, you can find some alternative implementations as well, like JavaEWAH, used by Apache Hive, Apache Spark and Eclipse JGit. It claims:

The goal of word-aligned compression is not to achieve the best compression, but rather to improve query processing time. Hence, we try to save CPU cycles, maybe at the expense of storage. However, the EWAH scheme we implemented is always more efficient storage-wise than an uncompressed bitmap as implemented in the BitSet class). Unlike some alternatives, javaewah does not rely on a patented scheme.

Answer 3

Look at Javolution FastBitSet : A high-performance bitset integrated with the collection framework as a set of indices and obeying the collection semantic for methods such as FastSet.size() (cardinality) or FastCollection.equals(java.lang.Object) (same set of indices).

See also http://code.google.com/p/guava-libraries/issues/detail?id=724#c3.

Answer 4

There are a number of compressed alternatives to the BitSet class. EWAH was already mentioned (https://github.com/lemire/javaewah). More recent additions include Roaring bitmaps (https://github.com/RoaringBitmap/RoaringBitmap) that are used by Apache Lucene, Apache Spark, Elastic Search, and so forth.

Answer 5

While searching an answer for my question single byte comparison vs multiple boolean comparison, I found OpenBitSet

They claim to be faster than Java BitSet and direct access to the array of words storing the bits.

I am definitely gonna try that. See if it solve your purpose too.