Re: Bitsets

[Michael Matz <matz at suse dot de>]

Hi,

On Sun, 8 Jun 2003, Michael Hayes wrote:

> I have attached a new version of a bitset library for review.  The
> goal is to replace the sbitmap and bitmap routines used in GCC with a
> common interface that will support multiple bitset implementations.

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.  This would be slower
than what we have now for sbitmaps which simply do basically:
  (BITMAP)->elms [(BITNO) / SBITMAP_ELT_BITS]
   |= (SBITMAP_ELT_TYPE) 1 << (BITNO) % SBITMAP_ELT_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?

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.


Ciao,
Michael.