Return back to the blog

Hidden evils of Java’s boolean array (boolean[])

Posted by Prashant Deva on February 2, 2012

Consider this piece of code which allocates a boolean array of 100,00:

boolean[] array = new boolean[100000];

What should the size of this array be?

Considering that a boolean can just be either true or false, every element in the array only needs a single bit of space each. Thus, the size of our boolean array in bytes should be:

 

100,000/8 + (overhead of array object) = 12,500 bytes + (overhead of array object)

But there lies the hidden evil….

The Evil Inside

As it turns out, when you allocate a boolean array, Java uses an entire byte for each element in the boolean array!

Thus the size of the boolean array is in fact:

100,000 bytes + (overhead of array object)

Remedy

So is there any way not to use the 7 extra bytes when you only need the 1 bit? Its here that the java.util.BitSet class comes to rescue.

The BitSet class does indeed use a single bit to represent a true/false boolean value. Its implementation uses an array of ‘long’ values, where each bit of the long value can be individually manipulated to set any position in the entire BitSet to true or false.

The BitSet implementation does add a bit of cpu overhead since it has to shift and or bits together to set the value of the bit in the correct position. Thus you need to weigh the cost of memory savings versus the extra cpu overhead when using this class.

Benchmark

As an example, here is a screenshot from the YourKit profiler, showing the memory used by a boolean array and a bitset object, both 100000 element long:

Benchmark

As can be be seen:

The boolean array takes:
100,000 + 16 (array overhead) = 100,016 bytes

The BitSet object only takes :

 

100,000 / 64 (size of long) = 1562.5 = 1563 long values after rounding
1563*8 + 16 (array overhead) = 12, 520 bytes

A few extra bytes are added for the BitSet object itself and the extra 2 fields that it contains.

To put things in perspective, here is a graph showing the space occupied by both for 100,000 elements:

Size-graph

Conclusion

As can be seen from the graph above, using the BitSet instead of a boolean[] can save you tons of memory at the cost of just a few extra cpu cycles

Tagged 7 Comments |

7 thoughts on “Hidden evils of Java’s boolean array (boolean[])

  1. Yeah, how many boolean[100000] do you have in your code? Or even, how many of boolean[] at all ?It’s nice to know, but i think it;s useless knowledge.

  2. konradkg: we use it tons in Chronon to save on memory usage. I can imagine tons of compute intensive programs which would benefit from the memory savings. Wouter: Actually in the case of a boolean array, the jvm only has the BALOAD and BASTORE instructions which load and store a byte. There is no array instruction to load/store a value < a byte.

  3. I think it would be interesting to make some perfomance benchmarks, comparing usual array and bitset operations: copy, search, get and the like.Quite often we face a compromise between speed and memory usage.

  4. These is nothing java specific here, cpp also uses a byte per boolean. Still good to keep in mind though when creating boolean arrays.

  5. I wouldn’t call 100KB "tons of memory". Calling it "The Evil Inside" sounds a tad too dramatic!

Comments are closed.