A Compressed Bitset Class

Introduction

The Standard Template Library bitset class is a useful class suitable for most bitset operations, but if you are dealing with lots of large bitsets, it may be that the stl bitset class is missing a trick.

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.

We have tested the class in the WhereWasI product and seen dramatic reductions in memory usages and very significant speed increases.

It is also notable that some operations with CMJBitset are dramatically faster than bitset. flip(), for example, simply needs to invert the full and sparse representation types.

At the top of the source file, there are a number of compilation options that affect the way CMJBitset allocates memory; the key option is set by default and reserves space within the class for bitsets with up to 4 bits set/unset. This often avoids the overhead of time and memory of using malloc/free, and in our examples is a definite performance bonus. Your mileage may vary and you may want to tune performance by changing some of these values.

History

  • June 14th, 2004 - 1.00 Released.
  • June 18th, 2004 - 1.01 Released. - Contains a number of optimisations
  • June 22nd, 2004 - 1.02 Released. - Fixes compilation bug with VC7.0. Fixes operator precedence bug that would effect normal bitset performance


Downloads

Comments

  • There are no comments yet. Be the first to comment!

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • You probably have several goals for your patient portal of choice. Is "community" one of them? With a bevy of vendors offering portal solutions, it can be challenging for a hospital to know where to start. Fortunately, YourCareCommunity helps ease the decision-making process. Read this white paper to learn more. "3 Ways Clinicians can Leverage a Patient Portal to Craft a Healthcare Community" is a published document owned by www.medhost.com

  • Live Event Date: May 6, 2014 @ 1:00 p.m. ET / 10:00 a.m. PT While you likely have very good reasons for remaining on WinXP after end of support -- an estimated 20-30% of worldwide devices still are -- the bottom line is your security risk is now significant. In the absence of security patches, attackers will certainly turn their attention to this new opportunity. Join Lumension Vice President Paul Zimski in this one-hour webcast to discuss risk and, more importantly, 5 pragmatic risk mitigation techniques …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds