Why does using a boolean array take so much longer?

Question

I am working on an assignment for class. I am supposed to create a simple version of Conway's Game of Life. I was doing some experimenting between using an array of boolean values vs using a BitSet. I ended up creating this little test:

After running the test each time for both the BitSet, and the boolean array, bitset had an average of about 6ms, and the boolean array had an average of about 1300ms. So my question is, what exactly is causing the HUGE overhead in times with using booleans over using a BitSet? I expected a difference, but not something this drastic.

Here is the code:

Life.java - main class

public class Life
{
    private final int WIDTH = 100;
    private final int HEIGHT = 100;
    private Board board;

    public static void main(String[] args)
    {
        new Life();
    }

    public Life()
    {
        board = createBoard();

        // populate board with random data
        Random random = new Random();
        for (int j = 0; j < board.length(); j++)
        {
            boolean b = random.nextBoolean();
            board.set(j, b);
        }
        random = null;
        System.gc();


        System.out.println("Starting test...");
        long startTime = System.currentTimeMillis();

        for (int i = 0; i < 10_000; i++)
        {
            Board tempBoard = createBoard();
            for (int j = 0; j < board.length(); j++)
            {
                byte count = getNeighborCount(j);
                boolean value = board.get(j);
                boolean next = value ? count >= 2 && count <= 3 : count == 3;
                tempBoard.set(j, next);
            }
            board = tempBoard;
        }

        long endTime = System.currentTimeMillis();
        System.out.format("Took %d ms", endTime - startTime);
    }

    public Board createBoard()
    {
        return new ArrayBoard(WIDTH * HEIGHT);
        //return new BitBoard(WIDTH * HEIGHT);
    }

    public byte getNeighborCount(int index)
    {
        byte count = 0;

        if (getRelative(index, -1, -1)) count++;
        if (getRelative(index, -1, 0)) count++;
        if (getRelative(index, -1, 1)) count++;

        if (getRelative(index, 0, -1)) count++;
        if (getRelative(index, 0, 0)) count++;
        if (getRelative(index, 0, 1)) count++;

        if (getRelative(index, 1, -1)) count++;
        if (getRelative(index, 1, 0)) count++;
        if (getRelative(index, 1, 1)) count++;

        return count;
    }

    public boolean getRelative(int index, int x, int y)
    {
        int relativeIndex = index + (WIDTH * y) + x;
        return board.get(relativeIndex);
    }
}

Board implementation using BitSet

public class BitBoard implements Board
{
    private BitSet board;

    public BitBoard(int size)
    {
        board = new BitSet(size);
    }

    @Override
    public void set(int index, boolean value)
    {
        if (value) board.set(index);
        else board.clear(index);
    }

    @Override
    public boolean get(int index)
    {
        return board.get(index);
    }

    @Override
    public int length()
    {
        return board.length();
    }
}

Board implementation using an Array

public class ArrayBoard implements Board
{
    private boolean[] board;

    public ArrayBoard(int size)
    {
        board = new boolean[size];
    }

    @Override
    public void set(int index, boolean value)
    {
        board[index] = value;
    }

    @Override
    public boolean get(int index)
    {
        boolean output = false;
        if (index >= 0 && index < board.length)
            output = board[index];
        return output;
    }

    @Override
    public int length()
    {
        return board.length;
    }
}

And finally, Board.java

public interface Board
{
    public boolean get(int index);

    public void set(int index, boolean value);

    public int length();
}

When measuring performance of Java code, please make sure to read (and follow) the recommendations in http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java — NPE, Feb 23 '14 at 08:18
*" Each component of the bit set has a boolean value."*. This was taken from the `BitSet` documentation. Either way, you're using `boolean` values. — christopher, Feb 23 '14 at 08:19
@christopher I am pretty sure that BitSet uses long's to store the values of the bits and not booleans. — user2249516, Feb 23 '14 at 08:21
@JasonC Obviously, but I just wanted to make the point that it's not `boolean` versus `BitSet`, it's more `Array` versus `BitSet`. — christopher, Feb 23 '14 at 08:21
@user2249516 Are you sure something else isn't going on? Traditionally, a `boolean[]` is more CPU efficient for this type of thing, and `BitSet` is more memory efficient. The difference in timing you see seems a bit unusual. — Jason C, Feb 23 '14 at 08:22
@christopher The documentation for `BitSet` makes no claims about how the data is stored at all, only how it is represented -- it is up to the implementation. However if you take a look at [the source code](http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7u40-b43/java/util/BitSet.java?av=f), the implementation uses `long`s. — Jason C, Feb 23 '14 at 08:24
Please post your `Board` interface so we can test this ourselves. (We can guess, but it's nice not to have to.) — Jon Skeet, Feb 23 '14 at 08:38

Jason C · Accepted Answer · 2014-02-23T09:02:54.517

4

Your problem has nothing to do with BitSet vs. boolean[] performance.

In your BitSetBoard, you have length() defined as:

class BitSetBoard {

    ...

    @Override
    public int length()
    {
        return board.length();
    }

}

You mean to return board.size() not board.length(). The BitSet.length() method returns the index of the highest bit set, it does not return the total size. Therefore your main loop isn't actually doing anything, because length() returns 0 when the board is clear.

With this change (and adding bounds checking to BitSetBoard.get()), BitSetBoard runs in just under twice the time as ArrayBoard for me.

edited Feb 23 '14 at 09:02

answered Feb 23 '14 at 08:47

Jason C

38,729
14
126
182

Yep, can't believe I completely overlooked that. Such a silly answer to a question. Thanks – user2249516 Feb 23 '14 at 08:49
2

Well... They really ought to have named `length()` something more reasonable, like `highestSetBit()`. – Jason C Feb 23 '14 at 08:54

score 0 · Answer 2 · edited May 23 '17 at 12:28

0

BitSet is more memory efficient than boolean[] except for very small sizes for further clarification you can read

boolean[] vs. BitSet: Which is more efficient?

BitSet uses about 1 bit per boolean value, and boolean[] uses about 1 byte per boolean value. that also the case that BitSet are more efficient

edited May 23 '17 at 12:28

Community

1
1

answered Feb 23 '14 at 08:20

Girish

1,717
1
18
30

Yeah, I saw that before I posted this. `boolean[]` is supposed to be more CPU efficient, which is one of the reasons that I was very surprised with my result. – user2249516 Feb 23 '14 at 08:35
@user2249516, I thought in any way or other it is explained by Jon Skeet that there can be the case with cache that how your data is cacheable – Girish Feb 23 '14 at 08:48

Why does using a boolean array take so much longer?

2 Answers2