[MLton] Re: allocateRegisters.toLiveness absurdly slow

[Wesley W. Terpstra]

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

> On Sun, Sep 13, 2009 at 9:49 PM, Wesley W. Terpstra <wesley at terpstra.ca>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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mlton.org/pipermail/mlton/attachments/20090914/bde82dc6/attachment.html