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();
}

Answer 1

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.