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

• Boolean[] uses about 4-20 bytes per boolean value.
• boolean[] uses about 1 byte per boolean value.
• BitSet uses about 1 bit per boolean value.

Memory size might not be an issue for you in which case boolean[] might be simpler to code.

From some benchmarks with Sun JDK 1.6 computing primes with a sieve (best of 10 iterations to warm up, give the JIT compiler a chance, and exclude random scheduling delays, Core 2 Duo T5600 1.83GHz):

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.

Here you can see a Memory/Time benchmark comparing a boolean[][] trianguar matrix versus BitSet[] triangular matrix.

I create, set and read the (size * (size-1) / 2) values and compare memory usage and time...

Hope this help...

Here the code... (just a quikly dirty test code, sorry ;)

import java.util.BitSet;import java.util.Date;public class BooleanBitSetProfiler {    Runtime runtime;    int sum = 0;    public void doIt() {        runtime = Runtime.getRuntime();        long[][] bitsetMatrix = new long[30][2];        long[][] booleanMatrix = new long[30][2];        int size = 1000;        for (int i = 0; i < booleanMatrix.length; i++) {            booleanMatrix[i] = testBooleanMatrix(size);            bitsetMatrix[i] = testBitSet(size);            size += 2000;        }        int debug = 1;        for (int j = 0; j < booleanMatrix.length; j++){            System.out.print(booleanMatrix[j][0] + ";");        }        System.out.println();        for (int j = 0; j < booleanMatrix.length; j++){            System.out.print(booleanMatrix[j][1] + ";");        }        System.out.println();        for (int j = 0; j < bitsetMatrix.length; j++){            System.out.print(bitsetMatrix[j][0] + ";");        }        System.out.println();        for (int j = 0; j < bitsetMatrix.length; j++){            System.out.print(bitsetMatrix[j][1] + ";");        }        System.out.println();    }    private long memory () {        return runtime.totalMemory() - runtime.freeMemory();    }    private long[] testBooleanMatrix(int size) {        runtime.gc();        long startTime = new Date().getTime();        long startMemory = memory();        boolean[][] matrix = new boolean[size][];        for (int i = 0; i < size; i++) {            matrix[i] = new boolean[size - i - 1];        }        long creationMemory = memory();        long creationTime = new Date().getTime();        for (int i = 0; i < size; i++)  {            for (int j = 0; j < matrix[i].length; j++) {                matrix[i][j] = i % 2 == 0;            }        }        long setMemory = memory();        long setTime = new Date().getTime();        for (int i = 0; i < size; i++)  {            for (int j = 0; j < matrix[i].length; j++) {                if (matrix[i][j]) sum++;            }        }        long readTime = new Date().getTime();        System.out.println("Boolean[][] (size " + size + ")");        System.out.println("Creation memory " + printMem(creationMemory-startMemory) + ", set memory " + printMem(setMemory-startMemory));        System.out.println("Creation time " + printTime(creationTime-startTime) + ", set time " + printTime(setTime - creationTime) + " read time " + printTime(readTime - setTime) + "\n");        runtime.gc();        return new long[]{(setMemory-startMemory)/(1024*1024), (readTime-startTime)};    }    private long[] testBitSet(int size) {        runtime.gc();        long startTime = new Date().getTime();        long startMemory = memory();        BitSet[] matrix = new BitSet[size];        for (int i = 0; i < size; i++) {            matrix[i] = new BitSet(size - i - 1);        }        long creationMemory = memory();        long creationTime = new Date().getTime();        for (int i = 0; i < size; i++)  {            for (int j = 0; j < matrix[i].size(); j++) {                matrix[i].set(j, (i % 2 == 0));            }        }        long setMemory = memory();        long setTime = new Date().getTime();        for (int i = 0; i < size; i++)  {            for (int j = 0; j < matrix[i].size(); j++) {                if (matrix[i].get(j)) sum++;            }        }        long readTime = new Date().getTime();        System.out.println("BitSet[] (size " + size + ")");        System.out.println("Creation memory " + printMem(creationMemory-startMemory) + ", set memory " + printMem(setMemory-startMemory));        System.out.println("Creation time " + printTime(creationTime-startTime) + ", set time " + printTime(setTime - creationTime) + " read time " + printTime(readTime - setTime) + "\n");        runtime.gc();        return new long[]{(setMemory-startMemory)/(1024*1024), (readTime-startTime)};    }    private String printMem(long mem) {        mem = mem / (1024*1024);        return mem + "MB";    }    private String printTime(long milis) {        int seconds = (int) (milis / 1000);        milis = milis % 1000;        return seconds > 0 ? seconds + "s " + milis + "ms" : milis + "ms";    }}