Re: [new-regalloc] What is the status on current sources

[Michael Matz <matzmich at cs dot tu-berlin dot de>]

Hi,

On Sat, 10 Feb 2001, Daniel Berlin wrote:
> > > The only operation that i slower than uncompresssed bitvectors is
> > > testing/setting individual bts.
> > > (pardon my spelling, i'm being murdered by latency here.)
> > > And this is actually not true if you have very large bitvectors, since
> > > iterating through a short list of integers is faster than iterating
> > > through an array of thousands of wordrs.
> >
> > For testing in bit-vectors no iteration is needed ;)
> 
> In this one, it is.

Misunderstanding.  You: "testing/setting individual bits is slow.  And
this [meaning bit testing] is not true with large vectors"

My argument was, that testing/setting a bit in even mega-large sbitmaps
are constant-time and need no iteration.  For your class iteration is
needed, so for the above operation it's slower in every case.  Note, that
I talk here about _s_bitmaps, not bitmaps. For them also iteration would
be needed, but they are not used in the interference graph.

> It's a bit vector not implemented as a vector of bits, but as a list of
> integers.

I understood perfectly well ;-)

> We also don't force iterating through 300 meg of bits, zeroing them, to
> clear an sbitmap.

Yep, that's nice (although it's the only iteration over the sbitmaps
currently).

> It's one of those "in theory, worst case, it's O(n), and slow. In
> practice, it's lightning fast, on anything we use it for, because we
> generate cases close to optimal"

No no, I never said, it's slow.  It's faster than bitmaps in nearly every
case we have in ra.c.  It's not faster than sbitmaps as they are used now
in ra.c in any case besides clearing.  And for smaller max_reg_no I would
like to have it faster (sbitmaps, as it is currently), but for larger ones
I would like to have it use less memory (so it uses yours) ;)


Ciao,
Michael.