3

I've been considering the optimization of two of my latest data storage techniques in Java, and would like to know which is really the most memory-efficient. Below are descriptions of the two classes. For the sake of argument, assume they have the same methods for interfacing with the data, which allow the user to get or set the state of any of the bits individually or by range via the following methods:

  • public boolean getBitState(byte bitIndex)
    • Detects and returns the state of the bit at index bitIndex
  • public Clazz setBitState(byte bitIndex, boolean newState)
    • Sets the state of the bit at index bitIndex to newState and returns the resulting object
  • public int getStateOfBits(byte startIndex, byte endIndex)
    • Detects and returns the state of all bits between startIndex and endIndex as an int
  • public Clazz setStateOfBits(byte startIndex, byte endIndex, int newState)
    • Sets the state of all bits between startIndex and endIndex to the value provided in newState.
    • If newState has fewer bits than fit, it is made to fit by adding zeros to the left
    • If newState has more bits than fit, the excess bits (on the left side) are cropped

These are the classes I have made to utilize this interface:

IntArray

This class uses an int as a way of storing 32 bits of data through bitwise functions.

Array32

This class uses an array of 32 booleans as its way of storing 32 bits of data through standard array interactions.

Ky -
  • 30,724
  • 51
  • 192
  • 308
  • As with any performance question, test it. Create larger and larger arrays and monitor JVM memory usage under each implementation. – Spike Gronim Sep 06 '11 at 20:32

2 Answers2

6

Use an int and bitwise functions! Most JVMs will represent an array of boolean as an array of bytes. java.util.BitSet uses internally an array of longs to represent it's bits (chunks of 64).

Vlad
  • 10,602
  • 2
  • 36
  • 38
5

Have you considered using the BitSet class? It seems like it does everything you need to do, and is probably well optimized, memory-wise.

Considering your two choices, definitely not an array of booleans. And array of boolean requires extra memory space for the metadata associated to the datatype. Plus, most JVM will allocate 32 bits of memory for each boolean.

Vivien Barousse
  • 20,555
  • 2
  • 63
  • 64
  • Actually [Jon Skeet put up a test](http://stackoverflow.com/questions/383551/what-is-the-size-of-a-boolean-variable-in-java/383597#383597) showing that on SUN's JVM array of boolean are packed as array of byte, not int - as individual booleans are. – Vlad Sep 06 '11 at 20:50