Re: Bitsets

[Michael Hayes <m dot hayes at elec dot canterbury dot ac dot nz>]

Michael Matz writes:

Hi Michael,

> Well, bitmap-like bitsets (I mean the bitmap implemented in bitmap.h, not
> in the general sense) also have such a cache implicitely, because it
> remembers the "current" list element it accessed the last time.

Yes, but this takes two calls to access.

 > No, I don't think that index array is such a good idea at all.  If you
 > really need such a thing make it more like the current bitmap.h (i.e. make
 > your index list in the iterator an instance of your lbitset).
 > Constructing it shouldn't be any slower than filling the array, especially
 > because the cache behaviour is much better.  Additionally you can then
 > reuse the internal representation of lbitset in the iterator, instead of
 > remapping (which would be good, as lbitset is especially good for
 > iterating over it, _even better than an array of indixes_, unlike sbitmaps
 > for instance).

This look like a good idea.  Yes, lbitsets are the best for iterating
over, population counts, empty tests, etc.  It is probably simpler to
have the iterator return each block of 128 bits and have an inner loop
to iterate over each of the bits set in the block.  Where this becomes
tricky is if we allow iteration starting from an arbitrary bit.


 > > 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).
 > 
 > That's true, but our bitsets in GCC don't have O(N) behaviour.  sbitmaps
 > are O(1) for set/reset/test, and bitmaps are cumulatively also O(1) if the
 > access pattern is not too jumpy.

I'm talking about the asymptotic case.  On the profiles that I
gathered before writing the new code, bitmap_find_bit consistently
clocked in as the hungriest (s)bitmap routine.  In many cases this
resulted from uses of bitmaps instead of variable sized sbitmaps since
the access patterns were jumpy.

 > > 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.
 > 
 > Well, surely all the liveness bitsets most commonly have not just one bit
 > set.  So it really depends on the purpose, but yes, better statistics can
 > help.

Most of the time bitmaps are used in GCC for regsets.  CSE in
particular would often create regsets with only a single register
marked.


Michael.