ebitmaps were a not-dense and not-sparse bitset representation. At the time they were implemented, none of gcc created the type of bitmaps that it was good at.

The most memory efficient idea is to have a contiguous array of bits, and a mask that specified which words were non-zero. You could then use the population count of the mask to determine where in the array to access. For single bit sets and tests, you need to take the population count up until the word for the bit you are looking for, and use that as the index into the array. For whole-bitmap operations, you know entire words to be zero, which lets you speed up the operation almost as much as you can with a sparse bitmap.

This representation was slightly slower than bitmaps for our bitmap loads. I never tried caching the last population count/index, or the last accessed word, which may have actually made this representation faster than bitmaps.

None: ebitmap (last edited 2008-01-10 19:38:36 by localhost)