1

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?

Community
  • 1
  • 1
Sophie Sperner
  • 4,428
  • 8
  • 35
  • 55
  • 1
    `100000/1024` times what `new BitSet(1024)` uses? – leppie Apr 16 '13 at 11:37
  • Ye, but this is relative way, I would like to have an exact formula based on number of bits allocated. – Sophie Sperner Apr 16 '13 at 11:38
  • Typically, 100000 / 8 + some overhead. – Fred Foo Apr 16 '13 at 11:41
  • 1
    You can use the sample code provided. But lets just say 1024 bits is 128 bytes, so one can assume 40 bytes of overhead for the rest of the class. So (100000/8 + 40) => 12540 bytes should be the answer. – leppie Apr 16 '13 at 11:41
  • See the following: [BitSet.size()...][1] [1]: http://stackoverflow.com/a/11062638/2274885 If i understand correctly that's what you're looking for.. – M.Bennett Apr 16 '13 at 11:45

2 Answers2

5

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.

Lorenzo Dematté
  • 7,638
  • 3
  • 37
  • 77
  • Mostly right, but as in many cases this is an implementation detail of a specific Java VM. You cannot be sure that all Java VMs implement the BitSet class with such a data structure. Other implementations may use more or less memory. – jarnbjo Apr 16 '13 at 12:01
  • True, more specifically of a specific JDK/SDK: Android, for example, could use a different implementation, and JDK7 or 8 could use a different implementation as well (even if its is unlikely, given that 1.0-6 uses the implementation I linked) – Lorenzo Dematté Apr 16 '13 at 12:34
2

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.

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130