In many applications using bitsets, you will find that a typical bitset is either sparsely populated with bits, or conversely almost fully set. In these cases, a large bitset can use a lot of memory for what is actually being represented.

To overcome this, we have developed the CMJBitset class as a plug-in replacement for bitset. The CMJBitset classm depending on compilation optionsm may take as little as 7 bytes to represent a bitset of any size, assuming all the bits are set or reset. In comparision, a 1024 bitset will take 128 bytes. In essence, the CMJBitset operates by run length encoding a bitset if the bitset is either almost all set/reset, but otherwise uses the STL bitset class. We will refer to the different encodings as normal, sparse, and full.

Using the Code

General usage

Using the CMJBitset class should be simple. Replace bitset<N> in your code with CMJBitset<N> and include the CMJBitset.h header file. Because CMJBitset presents the same interface as bitset, this should be enough to get things working.

Loading/Saving the bitset

The class would not give a fraction of its potential benefit if you were unable to save and load the bitset to and from file. Hence, these member functions:

bool load(FILE *)

and

bool save(FILE *)

are provided; but perhaps more to the point, all members of the class are public, enabling you to load and save at will.

Compilation Options

If you examine MJBitset.h, there are a number of compilation options.

For debugging

This is used by the example project to test the CMJBitset class. I would also recommend that when trying out the CMJBitset class you do some testing with this as well. As of the current date, a "full coverage" test has not been carried out on the class; therefore, bugs are a definite possibility.

//
// When DEBUG_CMMJBITSET is defined, a shadow bitset is kept and
// validated against operations. This is obviously very slow
// uses loads of memory and defeats any purpose in using this
// class and hence should never be used outside of a debug session.
//
//
//#define DEBUG_CMJBITSET

The maximum bitset size you need to deal with

The default is for a maximum of 0xffff.

//
// data representation type for bitsets <= 256
// CMJBITSET_USE_CHAR should be defined
//

//#define CMJBITSET_USE_CHAR
#define CMJBITSET_USE_SHORT
//#defineCMJBITSET_USE_LONG

The Example Project

The example project is a simple win32 console application that attempts to regress the CMJBitset by creating a succession of bitmaps with random population levels and performing a reasonably comprehensive set of operations on the bitsets.

You easily may alter the regression test to compare performance between CMJBitset and bitset.

Points of Interest

Performance

The performance of the CMJBitset class is quite hard to quantify. For bitsets that it does not encode because they are neither full ror sparse, the CMJBitset class is clearly several times slower than bitset.

If you run the example regression test and make it use sparse bitsets, the times will still be a little faster than bitset. But, the comparitive speed will dramatically increase once the operations cease to be completely in memory either due to paging or loading/saving to files.