As we've kinda known for too long (and Slawek's excellent analysis shows), our coverage recordings are typically very sparse - particularly the per-test slice recordings. A sparse bitset implementation will hugely reduce both memory consumption and computation required to calculate per-test coverage.

See Slawek's description of a design based on a 2 layer index tree backed by arrays of longs. An implementation using this approach can be found here (we can't use it because it is GPL): http://tinyurl.com/sparsebitset-source The FishEye project also have a sparsebitset implementation: https://extranet.atlassian.com/crucible/browse/FE/trunk/src/java/com/cenqua/fisheye/util/bitset/SegmentedIntSet.java?r=18727

Note though that the FE impl is backed by BidiBitset, which uses cutnpaste JDK code, which isn't kosher.

Some dev notes:

1. I think we should potentially provide a BitSet interface, with two implementations:
   1. java.util.BitSet (via a simple delegate)
   2. our own sparse bitset
2. This will mean we can chop and change bitset impls based on the nature of the recording we are loading
3. the interface should support or() and and() and not() (and trivially andNot() )