Re: Bitsets

[Michael Hayes]

Michael Matz writes:
 > 
 > That's cool.  The only thing I'm nervous about is performance.  I care
 > about two cases:
 >  1) performance of set/test/reset for sbitmap-like bitsets
 >  2) performance of iterators over set bits in bitmap-like bitsets
 > 
 > A quick glance over the libbitset sources indicate, that for 2) you use
 > inline functions bitset_{set,reset,test} in bitset.h, which each check for
 > the offset to not overrun the size of the bitset. 

Yes this is a penalty for sbitmap-like bitsets but gives a performance
boost for bitmap-like bitsets since it allows a cache of the last
accessed bits.

 > Regarding 1) you seem to have the BITSET_FOR_EACH{_REVERSE} macros, which
 > involve a call through the vtable for each block of bits, and what's even
 > more use an intermediate array of indexes for set bits, which is 1024(!)
 > elements long, i.e. has very poor cache behaviour.  In contrast the
 > EXECUTE_IF_SET_IN_BITMAP* macros all have no function calls, and don't use
 > any more memory than the list for bitmaps itself.  Have you compared
 > performance of these implementations?

Interestingly, when I wrote this code over a year ago I was getting a
consistent 5% increase in GCC compilation time and that was before
some optimisations I added for the most common cases.

Most of the iterations over bitmaps in GCC involve one or more calls
so there is not a lot gained using macros for
EXECUTE_IF_SET_IN_BITMAP.  The array of indexes is only used once per
iterator.  The size could easily be reduced.  It used to be smaller
but I think it was Zack that encouraged me to make it bigger.  


 > Normally I'm all for abstraction and clean interfaces, but the bitsets are
 > at heart of some of our most performance sensitive parts of the compiler,
 > so we should make sure any abstraction overhead doesn't hit us too hard.

I agree with you.  Unfortunately, what often kills us (apart from a
poor infrastructure) is that it is difficult to experiment with
different bitset implementations or to switch bitset implementation on
the fly depending on the size and density of the bitset.  When the
size of the bitset is small, the choice is not too important.  However
for large bitsets, O(N) time to set a bit really hurts compared to
O(1).

One useful aspect of the bitset implementation is that it is easy to
enable stats gathering and then to select the most appropriate
implementation.  For example, (from memory, my workbook is at home),
the most common bitset population when during a bootstrap of GCC is 1.


Micahel.