Alternative to Java Bitset with array like performance?

java arrays bitset
rreyes1979 picture rreyes1979 · Jan 10, 2012 · Viewed 12.1k times · Source

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

βξhrαng picture βξhrαng · Jan 10, 2012

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.

Related questions

How do I declare and initialize an array in Java?

How do I declare and initialize an array in Java?

Read More
What's the simplest way to print a Java array?

In Java, arrays don't override toString(), so if you try to print one directly, you get the className + '@' + the hex of the hashCode of the array, as defined by Object.toString(): int[] intArray = new int[] {1, 2, 3, 4, 5}; System.out.println(…

Read More
How do I determine whether an array contains a particular value in Java?

I have a String[] with values like so: public static final String[] VALUES = new String[] {"AB","BC","CD","AE"}; Given String s, is there a good way of testing whether VALUES contains s?

Read More