This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

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




On Sat, 10 Feb 2001, Michael Matz wrote:

> Hi,
>
>
> On Fri, 9 Feb 2001, Daniel Berlin wrote:
> >
> > This reminds me, I have a compressed bitvectors class i implemened to
> > fix the huge memory usage problem for the interference graph.
> > [.. description of it ...]
>
> I once (looong ago, as I wrote still DOS demos ;) ) had something similar
> (although in Pascal).  We could very well use such a thing.  I guess,
> we'll want to conditionalize it's use on max_reg_no being too big (as,
> say, 1000 pseudos are taking only 122 KB in the interference graph, which
> is acceptable IMHO).  To test for membership more quickly we could even
> employ a small hash-table mapping from (0..max_regno-1) to
> (0..small_number), and a [small_number] bitset (so that, if bit[hash(i)]
> is _not_ set, than i is not in the list; if bit[has(i)] is set, nothing is
> known, and it must be searched)
>
> > 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.

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

So iteration is necessary through the list of integers used to represent
the bits.

:)

However, since the numbers are just the numbers of 1's and 0's, and it's
applying boolean logic,  it's certainly a bitvector, and not something
else.
It walks like a bitvector, talks like a bitvector, it's just not
implemented as a bunch of words representing bits.


http://users.pandora.be/koen.vandamme1/c_tools/bitplatforms/article.txt


Before bothering to implement it in C, I made the ra.c output the
intereference graphs in a machine readable format, and tested it, to make
sure it wasn'tslow.

It's not.
And the C implementation isn't either.

This is mainly because the worst case (alternating ones and zeros) never
occurs, and igraphs have *very* long parts at the beginning with no
conflicts, then a bunch of interspersed conflicts/no conflicts, then no
conflicts again.

So even though you have to iterate through the list to get to the bit, we
iterate through an average of 4 numbers before getting to that bit, and
the whole iteration gets translated into a bunch of pointer arithmetic
anyway.

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

For our purposes, it's usable without any speed loss. Especially since it
general fits in the l2 cache, whereas a 300 meg sbitmap doesn't.

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"

 --Dan



Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]