Re: Bitsets

[Michael Matz <matz at suse dot de>]

Hi,

On Wed, 11 Jun 2003, Michael Hayes wrote:

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

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.

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

I tend to agree that the call overhead is probably not that high.

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

I thought more about this index array while trying to sleep.  I think it
could result in fairly heavy slowdowns.  For instance in our current
bitmaps there are 128 bits per list element (which then needs 28 bytes on
a 32bit arch).  Suppose only half of them are set.  Then we need for each
of those elements 64 ints for the index array, making it need 256 bytes
just to represent the set bits which would only need 28 bytes when used in
the original form.

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

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

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


Ciao,
Michael.