[MLton] Scaling issue during refFlatten when building the type dependencies graph

[Matthew Fluet]

On Wed, 10 Sep 2008, Vesa Karvonen wrote:
> On Tue, Sep 9, 2008 at 5:12 AM, Matthew Fluet <fluet at tti-c.org> wrote:
>> On Mon, 8 Sep 2008, Nicolas Bertolotti wrote:
> [...change to ref-flatten...]
>>> This change drastically reduced the memory usage (from millions of edges
>>> to one thousand edges) and solved the problem.
>>
>> Wow!  That is quite a difference (and suggests a large number of
>> datatype/variants in the input program).
> [...]
>
> This also seems to reduce space requirements when compiling mlkit with
> mlton.  Without this change, compiling mlkit with ref-flatten takes a
> lot of memory (8GB is not enough on a 64-bit machine).  With this
> change it is possible to compile mlkit with ref-flatten (max live was
> about 2.5GB (IIRC)), but it takes a very long time, about 11 hours
> (IIRC), almost all of it in ref-flatten, on a C2Q machine clocked at
> 2GHz.  (The numbers 2.5GB and 11 hours are approximate as someone
> managed to close the console window when I left the machine for 2
> minutes.)

I don't doubt your numbers, but this might not be the whole story on the 
RefFlatten scaling issue.  The graph construction to avoid flattening into 
(mutually) recursive data-structures was added by r6395 (20080213), and, 
IIRC, the MLKit has had scaling issues with the RefFlatten and DeepFlatten 
passes from before the 20070826 release.  OTOH, by excluding (mutually) 
recursive data-structures, there are less candidates for flattening in the 
main body of the RefFlatten pass, so there is probably some help from 
that.