Re: Bitsets

[Michael Matz]

On Thu, 12 Jun 2003, Michael Hayes wrote:

> Hi Michael,

Dito ;-)

> > remembers the "current" list element it accessed the last time.
>
> Yes, but this takes two calls to access.

That's true.  The actual implementation of bitmap.h is not the fastest
possible either because of multiple calls in the fast path of the
bit-set/test/clear functions.

>  > [... lbitset as index list for iterator ...]
>
> 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.

Which is basically what the EXECUTE_IF_...BITMAP macros indeed do.  Or do
you mean the iterator bitset_list (i.e. the bitset-individual thing which
"fills" the iterator structure)?  I.e. do you suggest to replace the index
array with an index bitmap of fixed size (instead of an index lbitset)?
I think that would also help a bit, although the number of calls to the
index filler should be kept low.

> Where this becomes tricky is if we allow iteration starting from an
> arbitrary bit.

You anyway need an "offset" field in the iterator struct which says
what real index in the original bitset the first bit in the index bitset
had.

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

I see.  I just wanted to mention, that if the bit access pattern is "nice"
enough, even lbitsets are extremely fast for bit-wise work.  For instance
in the register allocator I use some bitmaps for remembering basically
integer IDs.  The way I walk through the code makes the sequence of IDs
that I see highly uniform.  So even if the current bitmap element needs to
be changed the new one is often the next or previous one.

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

Hmm, I don't see bitmap or regset used in cse.c.  combine.c only fiddles
with the basic_block->global_live_at_{start,end} but doesn't create
bitmaps on it's own.  Of course passes which mostly create bitsets with
one bit set should be changed to not use bitsets at all in that special
case ;-)


Ciao,
Michael.