Bitset statistics

[Daniel Berlin]

On Fri, 11 Jan 2002, Michael Hayes wrote:

> 
> Hi folks,
> 
> I have implemented Dan Berlin's ebitmap idea (well I think I have) and
> integrated it with the common bitset interface I have written.

There are multiple ways to do the ebitmaps, you can trade off speed for 
memory usage.
> 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.
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).

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.

For what they are used for most, which is setting a few bits, then 
EXECUTE_IF_IN_BITMAP'ing, it's almost impossible to beat them.
Any attempt will actually result in a gcc slowdown (between 5 and 15%, 
depending on how you implement the ebitmaps).

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.

> 
> 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.

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.
So until you get to large, not so dense bitsets, ebitmaps lose.

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.

--Dan