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

Reply via email to