Bitset statistics

[Michael Hayes]

Daniel Berlin writes:
 > There are multiple ways to do the ebitmaps, you can trade off speed for 
 > memory usage.

I agree.  One shoe doesn't fit all.

 > > From
 > > my observations the approach has its merits but is not a replacement
 > > for the other bitset implementations (namely a dense array of words of
 > > bits and a linked list of small arrays of words of bits).
 > Sure, it was only meant for large bitsets that are not so dense. In 
 > particularly, dataflow operations and interference graphs.  It gets 
 > killed by bitmap in small bitset cases.

I agree.  The only exception would be large, very sparse, bitsets
where there would only be a few bitmap elements in the chain.

 > You'll note that originally, I wanted to add it as a third option, not 
 > replace either bitmaps or sbitmaps.
 > I was told this was "Not the way to go" (TM).

Yes and I didn't agree with this sentiment.  This is why I've tried to
create a unified interface so that we can bolt in different
implementations, optimised for different types of bitsets.

 > Also, the reason the linked list bitmaps do okay is because of the current 
 > pointer. 
 > In fact, it's almost impossible to beat linked list bitmaps until you 
 > start getting weird looking bitmaps or non-standard operation
 > sequences.

Yes, spatial locality helps here.  This is why I cache the current
element to avoid performing calls for most bit set/test operations.

 > Even doing what would seem to be a reasonable thing, like skiplisting the 
 > bitmaps, slows them down, even in the large, sparse, case. It's odd, but 
 > true.  Their just aren't enough set bits that are far apart for it to be 
 > worth it.

This is what I have noticed as well.

 > > To get a handle on things, I have profiled GCC many times using
 > > different bitset implementations.  The bitset operation that dominates
 > > timing profiles in all cases is the determination of which bits are
 > > set in a bitset. 
 > Which is why i made it constant time with ebitmaps.

We still have to search through the table of pointers to find the
non-null pointers when looking for bits that are set.

 > You'll note, however, that this doesn't help as much as you'd imagine, 
 > which i found strange.
 > I tracked it down to the fact that bitmaps get much the same result 
 > through the use of the current pointer.
 > It takes just as long to perform the ebitmap math and dereference as it 
 > does to walk a few pointers in either direction.

Hang on, aren't you talking about bit setting/testing?  I've found
that ebitmaps are always faster for these operations but when spatial
locality applies, the speed difference is small.

Things are not so obvious when it comes to finding the set bits.
With bitmaps we have to traverse a list of pointers, with ebitmaps
we have to scan a table of pointers.  Making each block of bits
larger improves memory efficiency and improves the search speed
provided the set bits are clustered.  Someone has surely
done a Monte Carlo simulation of this.

 > It's around now i stopped caring so much, because i didn't feel like 
 > making it auto-convert between representations based on density and size.

While auto-conversion is straightforward, in most cases we are
probably better off by selecting the appropriate bitset representation
when we create it, say based on the class of bitset and the size of
the required bitset.


Michael.