Re: IRA for GCC 4.4

[Vladimir Makarov <vmakarov at redhat dot com>]

Peter Bergner wrote:
> On Thu, 2008-04-24 at 16:33 -0500, Peter Bergner wrote:
>   
> > On Thu, 2008-04-24 at 16:51 +0200, Paolo Bonzini wrote:
> >     
> > > > > (The testcase is 400k lines of preprocessed Fortran code, 16M is size,
> > > > > available here:
> > > > > http://www.pci.unizh.ch/vandevondele/tmp/all_cp2k_gfortran.f90.gz)
> > > > >
> > > > >   
> > > > >           
> > > > Thanks, I'll check it.
> > > >         
> > > Vlad, I think you should also try to understand what does trunk do with 
> > >   global (and without local allocation) at -O0.  That will give a 
> > > measure of the benefit from Peter's patches for conflict graph building.
> > >       
> > I took a patch from Ken/Steven that disabled local_alloc and instead runs
> > global_alloc() at -O0 and summing up all of the bit matrix allocation
> > info we emit into the *.greg output, the new conflict builder saves a lot
> > of space compared to the old square bit matrix (almost 20x less space).
> > Here's the accumulated data for the test case above:
> >
> >     compressed upper triangular:  431210251 bits,   53902848 bytes
> >     upper triangular:            4264666581 bits,  533084851 bytes
> >     square:                      8531372796 bits, 1066423618 bytes
> >     
>
> The SPEC2000 numbers look even better (29x less space):
>
>     compressed upper triangular:  281657797 bits,   35212532 bytes
>     upper triangular             4094809686 bits,  511856604 bytes
>     square:                      8191641644 bits, 1023962188 bytes
>   

Hi, Peter.  The last time I looked at the conflict builder 
(ra-conflict.c), I did not see the compressed matrix.  Is it in the 
trunk?  What should I look at?

I have also another question.  I saw that sparset was used for the 
conflict builder.  I tried that too when I worked on YARA project.  I 
even wanted to contribute a generic sparset implementation.  But I found 
that in general case bitmaps are not worse the sparse sets and much 
better if we take  a needed space into account.  May be you have another 
impression?  It would be very interesting for me to hear it.  I found 
that bitmaps have more advanced design than sparsets.  I always wanted 
to find inventors the bitmaps but never tracked them down.

Vlad