Super bitset class - development log

Coming to this space soon, one of a series of C++ classes that we want to contribute to the wider community.

CMJBitset

is a class that acts as a drop in replacement for the standard template library bitset class.

The difference is that if the bits being represented are sparse e.g. mostly 0's, the the class not only takes up a lot less memory, but will be faster for many operations.

The class is still being developed and tested, we hope benchmarks and a link to the source will be available here by the end of June 2004.

6th June update

The class is now apparently working without issues in a version of a marsjupiter product built using the sparse bitset. The initital results show a 10% drop in performance but a large drop in memory consumption. However the replacement of bitsets in the product was global regardless of whether the bitsets were sparse or not.

Benchmarking performance is we think best done in the context of a product as opposed a contrived test, as the sparse bitset has a totally different performance to a standard bitset, for example a shift left operation on a standard bit set will be massively slower than the same operation of the sparse bitset. conversely setting and resetting bits is much slower in the sparse bitset.

8th June update

One notable issue that has become apparent is that the expression:

bitset1 &= ~bitset2;

is very inefficient in the sparse class, we have added the syntax:

bitset1.reset(bitset2);

to resolve this, but this breaks away a little from the idea of a drop in replacement for bitset.

10th June Update.

The class has moved on a lot, from being a sparse class it now automatically moves between 3 representations of a bitmap (full, normal, sparse).  This should prevent performance degradation and generally make the class faster. No figures are available as yet, since a large amount of testing needs doing. With the new class many operations now have 9 permutations to deal with! this is not likely to be bug free yet a while.

12th June update

The CMJBitset class has now been regressed within our test applications, not surprisingly quite a few bugs were found and resolved.

The speed benchmarks were superficially very impressive with the test application running  35x faster! whilst using a lot less memory.

Looking behind the figures, we see that the massive increase in speed is fundermentally because the CMJBitset makes loading and saving a bitset to file so much faster. Note that the application already used a compressed format for bitset storage, but now that format needs practically no processing for for reading or writing from file.

So what is the underlying speed of the class? at this stage it is hard to tell, all operations (including ~ which was previously a problem) that in the CMJBitset do not need to visit individual bits are in most circumstances much quicker than the bitset class.

thus:

a &= b; // faster in CMJBitset

a.set(position); // faster in bitset.

But CMJBitset also adds significant overheads, it must check the representation type to decide on how to perform each operation and it must sometimes switch the representation, it must also allocate and reallocate memory.

Checking when to change representation relies on the count() function, which is very fast in CMJBitset but very slow in bitset. We avoid making this check all the time if we are using bitset for the representation type as it would slow things significantly. The parameter for how often to check is a pre-processor constant, and tweaking it effects performance considerably.  

This brings us on to an aside about C++ classes in general, we are told to think of them as black boxes, and we protect ourselves from the internals of the classes with private etc. But whilst this has its benefits it does not lead to well optimised code. A good example of this is CString, it allocates short strings into 64 byte buffers as a a strategy to avoid memory fragmentation, a laudable tactic in the average program, but most programs will not be "average" and would benefit from larger buffers, smaller buffers, or precisely allocated buffers.

To conclude for the day though with a summary of where the CMJBitset class stands at the moment. It has been regressed though two (similar) applications and also some specific bitset testing code, and has no known bugs currently. Due to the complexity of the class though, this is far from saying I am confident the class is bug free.