allocateRegisters.toLiveness absurdly slow

[Wesley W. Terpstra]

I have a project where allocateRegisters.toLiveness takes 220s out of a total build time of 240s. I'm not sure what exactly causes this, and would be happy to send the project privately. The problem has been getting progressively worse as our project grows. I built a MLton with -profile true and have attached the results. It seems x86AllocateRegisters.Liveness.predict.sawUse is called an awful lot. Any help getting our compile times back down to a manageable level would be appreciated!





_______________________________________________
MLton mailing list
MLton@...
http://mlton.org/mailman/listinfo/mlton

[Wesley W. Terpstra]

On Wed, Sep 9, 2009 at 10:41 PM, Wesley W. Terpstra <wesley@...> wrote:

I have a project where allocateRegisters.toLiveness takes 220s out of a total build time of 240s. I'm not sure what exactly causes this...

In case it's not obvious, this only happens with the x86/amd64 codegens. C and bytecode compile just fine. I'd try and solve it myself, but I haven't a clue where to even begin. That 240s total was on the fastest machine available to me; on my laptop it takes 20 minutes... What algorithm is toLiveness using? Does it have exponential complexity in the number of variables?

_______________________________________________
MLton mailing list
MLton@...
http://mlton.org/mailman/listinfo/mlton

[Wesley W. Terpstra]

On Sun, Sep 13, 2009 at 9:49 PM, Wesley W. Terpstra <wesley@...> wrote:

 Does it have exponential complexity in the number of variables?

The answer to this question appears to be: YES!

I've found a point in my project where adding one element to the record (more than) doubles the compile time. I'm using the FunctionalRecordUpdate pattern with this record. At this point my compile times have gone up to 25 minutes on the fastest computer available to me (my laptop now takes 1.4 hours)... It had 22 elements for a compile time of 10:30 minutes then I increased it to 23 elements (plus some code to force the element to be used) and the compile time went up to 24:46 minutes

At least now that I know what causes the problem, I can work around it, but it seems pretty unfortunate that MLton has an exponential time liveness calculation. Can this be fixed?

 

_______________________________________________
MLton mailing list
MLton@...
http://mlton.org/mailman/listinfo/mlton

[Wesley W. Terpstra]

On Mon, Sep 14, 2009 at 1:49 PM, Wesley W. Terpstra <wesley@...> wrote:

On Sun, Sep 13, 2009 at 9:49 PM, Wesley W. Terpstra <wesley@...> wrote:

 Does it have exponential complexity in the number of variables?

The answer to this question appears to be: YES!

I've found a point in my project where adding one element to the record (more than) doubles the compile time. I'm using the FunctionalRecordUpdate pattern with this record. At this point my compile times have gone up to 25 minutes on the fastest computer available to me (my laptop now takes 1.4 hours)... It had 22 elements for a compile time of 10:30 minutes then I increased it to 23 elements (plus some code to force the element to be used) and the compile time went up to 24:46 minutes

At least now that I know what causes the problem, I can work around it, but it seems pretty unfortunate that MLton has an exponential time liveness calculation. Can this be fixed?

Good lord. Don't blame MLton, blame sweeks and vesa!

The FunctionalRecordUpdate on the wiki has exponential type explosion. This makes it pretty useless in practice. Also, the code size still grows quadratically due to the list of 'A's that one has to make.

I've made a work-alike version that has linear code growth and no explosion. This is it:
(* Briefly, if you have a record { foo: int, bar: real, baz: word }...
 * fun updateRecord z =
 *    let
 *       fun from v1 v2 v3 = {foo = v1, bar = v2, baz = v3}
 *       fun to f {foo = v1, bar = v2, baz = v3} = f v1 v2 v3
 *    in
 *       makeUpdate3 (from, from, to) z
 *    end
 *
 * You can then update records with: updateRecord record (set#bar 1.0) $
 *)
structure FunctionalRecordUpdate =
   struct
      local
         (* The user supplies us with these two functions:
          *   to f { a, b, c } = f a b c
          *   from a b c = { a, b, c }
          *
          * The goal is to create a family of functions like:
          *   f0 (f, z) a b c = f (z a) b c
          *   f1 (f, z) a b c = f a (z b) c
          *   f2 (f, z) a b c = f a b (z c)
          *
          * These functions are passed as arguments via selector:
          *   c3 g = g f0 f1 f2
          *
          * We can thus set g=from to get a record of functional updates.
          * Use the update function as: to (record, upd (from, z))
          *)
        
        
         fun next g (f, z) x = g (f x, z)
         fun f1 (f, z) x = f (z x)
         fun f2  z = next f1  z
         fun f3  z = next f2  z
         fun f4  z = next f3  z
         fun f5  z = next f4  z
         fun f6  z = next f5  z
         fun f7  z = next f6  z

_______________________________________________
MLton mailing list
MLton@...
http://mlton.org/mailman/listinfo/mlton

[Wesley W. Terpstra]

On Mon, Sep 14, 2009 at 5:36 PM, Wesley W. Terpstra <wesley@...> wrote:

I've made a work-alike version that has linear code growth and no explosion. This is it: ...

Urp, google mail sent before I was done. :p I've attached the file this time.

_______________________________________________
MLton mailing list
MLton@...
http://mlton.org/mailman/listinfo/mlton

[Wesley W. Terpstra]

On Mon, Sep 14, 2009 at 5:36 PM, Wesley W. Terpstra <wesley@...> wrote:

Good lord. Don't blame MLton, blame sweeks and vesa!

I've updated the wiki at <http://mlton.org/FunctionalRecordUpdate>.
Hopefully other people can avoid the problems I had.


_______________________________________________
MLton mailing list
MLton@...
http://mlton.org/mailman/listinfo/mlton