Re: [perl #32208] [PATCH] Register allocation patch - scales better to more symbols

At 12:30 PM +0200 10/29/04, Leopold Toetsch wrote:
> Bill Coffman (via RT) wrote:
>
> > Patch does the following:
> >
> > - Applied Matula/Chaitin/Briggs algorithm for register allocation.
> > - Color the graph all at once, and spill all symbols with high colors.
> >  Spill all at once to speed things up.
>
> Good. Hopefully Dan can provide some compile number compares.

The numbers are... not good.

I took one of the mid-sized programs and threw it at the new code. 
Parrot in CVS takes about 10 minutes to run through this program. The 
main sub's about 30Klines of code, and the stat from a parrot -v is:

sub _MAIN:
        registers in .imc:       I2875, N0, S868, P7615
        0 labels, 0 lines deleted, 0 if_branch, 0 branch_branch
        0 used once deleted
        0 invariants_moved
        registers needed:        I2883, N0, S873, P7741
        registers in .pasm:      I31, N0, S31, P32 - 37 spilled
        5845 basic_blocks, 47622 edges

I applied the patch to a copy of parrot and ran it. After 37 minutes 
I killed the thing. It had 1.6G of RAM allocated at the time of 
death, too.
--
                                Dan

--------------------------------------it's like this-------------------
Dan Sugalski                          even samurai
dan@xxxxxxxxx                         have teddy bears and even
                                      teddy bears get drunk