Memory size of Java 32-bit system BitSets

Question

How to compute the memory of new BitSet(n) in C++.

What memory takes the new BitSet(1024) in Java.

But it seems the formula for Java is different. I want to compute the memory spent for new BitSet(100000), could you please help?

Answer 1

It is a little more than 100000/8 which basically the same as in C++ assuming N is the number of bits. To measure it exactly you can test it.

public static void main(String... ignored) {
    BitSet warmup = new BitSet(10000);    // load the class etc.

    long before = memoryUsed();
    BitSet bs = new BitSet(100000);
    long size = memoryUsed() - before;
    if (size == 0)
        throw new AssertionError("You need to run this with -XX:-UseTLAB for accurate accounting");
    System.out.printf("BitSet(100000) used %,d bytes%n", size);
}

public static long memoryUsed() {
    return Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
}

prints with -XX:-UseTLAB on the command line

BitSet(100000) used 12,544 bytes

There is two objects created (the BitSet and the long[]) which accounts for the small difference from expected.

Answer 2

BitSet are packed into arrays of "words." A word is (in the current implementation) a long. The single bits inside will be retrieved / set uses masking; therefore it internally packs 64 bits in one single long value, and uses an array of longs to hold all the bits you need.

The dimension of the array will be N (100000) / 64 bytes, or 1563 longs, or 12504 bytes, plus a fixed overhead needed by BitSet for its internal structure/bookeeping.

See http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/BitSet.java for the implementation; counting the fields and summing up the space they need (an int: 4 bytes; a long: 8 bytes, and so on) you can understand how much is the fixed overhead.