Re: Compile-time v. execution-time tradeoff

On Sat, Feb 20, 2016 at 8:38 AM, Rob Arthan <[email protected]> wrote:
> Thanks for the suggestions. The results are interesting ...
>
>> On 17 Feb 2016, at 11:55, Matthew Fluet <[email protected]> wrote:
>>
>> On Tue, Feb 16, 2016 at 8:49 AM, Rob Arthan <[email protected]> wrote:
>>> Does MLton have any options that let me trade off execution time against compile time? The scenario is that I have a parser generator that I have recently ported to run on MLton. The parser generator itself is very efficient when built with MLton, but the test suite runs slowly because of the time taken to compile the generated parsers. As the tests only run each parser once, it would be nice if I could speed up the tests by opting for less optimisation. I tried -inline 0, but it didn’t make much difference.
>>
>> MLton doesn't currently have distinct optimization levels.  The
>> "-drop-pass" option can be used to skip a particular optimization
>> pass.  The "-ssa-passes" option (and similarly for the other IRs) can
>> be used to set a particular sequence of optimization passes;
>> "-ssa-passes minimal" is recognized and will only execute those passes
>> necessary for correctness.  Unfortunately, while this speeds up the
>> time in the SSA optimizations, it tends to slow down the codegen
>> significantly, since the program hasn't be simplified.
>>
>> There is also a minimum of time that any compile takes, due to the
>> whole-program compilation requiring scanning, parsing, and elaborating
>> the whole Basis Library in addition to the program of interest.
>>
>> You could try compiling one of your representative tests with
>> "-verbose 2", which will give timings for all of the optimization
>> passes.  If a particular pass is taking very long, then you can use
>> "-drop-pass" to skip that one.  Occasionally, performance bugs in the
>> optimization passes have turned up, especially when presented with
>> stylistically distinct code, such as might appear in parser generator
>> output.
>>
>
> If I am interpreting the results of "-verbose 2” correctly it looks like
> the bulk of the time is spent in code generation. I think this extract
> from the output summarises what is going on.
>
>       pre codegen finished in 20.36 + 4.95 (20% GC)
>       amd64 code gen finished in 51.92 + 3.38 (6% GC)
> MLton finished in 75.31 + 8.34 (10% GC)
>
> That means that of the total 84 seconds it took to compile
> the test, 30% was in pre code gen (which is where the
> optimisation passes happen, I think) and 66% was in code gen.

That's a correct interpretation.  There is some amount of low-level
optimization done in the native codegens (peephole optimization,
register allocation, ...), but we expect the bulk of the optimization
benefit to occur in the pre-codegen.

> However, because this is a test, the code is highly atypical of
> ordinary use of the parser generator: The test generates parsers
> for 5 different grammars for real languages (Ada95, two different
> grammars for C, Java and Pascal) and concatenates them
> all in one file interleaved with some code to run the
> parsers on some sample inputs and to check the results.
>
> If I compile the parsers for the 5 grammars separately, the
> time taken for the code generation is no longer dominant.
>
> ada95:      pre codegen finished in 7.25 + 2.39 (25% GC)
> ada95:      amd64 code gen finished in 5.89 + 1.03 (15% GC)
> ada95:MLton finished in 14.14 + 3.42 (19% GC)
>
> c1:      pre codegen finished in 4.14 + 1.54 (27% GC)
> c1:      amd64 code gen finished in 2.89 + 0.59 (17% GC)
> c1:MLton finished in 7.66 + 2.13 (22% GC)
>
> c2:      pre codegen finished in 4.84 + 1.59 (25% GC)
> c2:      amd64 code gen finished in 4.38 + 0.91 (17% GC)
> c2:MLton finished in 10.07 + 2.50 (20% GC)
>
> java:      pre codegen finished in 5.97 + 2.13 (26% GC)
> java:      amd64 code gen finished in 5.68 + 1.07 (16% GC)
> java:MLton finished in 12.54 + 3.20 (20% GC)
>
> pascal:      pre codegen finished in 4.45 + 1.65 (27% GC)
> pascal:      amd64 code gen finished in 2.39 + 0.30 (11% GC)
> pascal:MLton finished in 7.41 + 1.96 (21% GC)
>
> Adding these up gives a total compilation time of 65
> seconds of which 36 seconds (55%) is in pre code gen
> and 25 seconds (39%) is in code gen.
>
> I am intrigued that the code generation time is far from
> linear in the number of lines of code. However, as my test
> is so untypical, I don’t feel there is much to worry about here,
> unless you feel that the above timings are not satisfactory.
> (In which case, I can let you have the ML to experiment with.)

I'd love to take a look at the SML source.

There are probably some non-linearities in the native codegen,
especially non-linearity with respect to the length of basic blocks.
We actually special case the "function" that initializes the global
data --- it is essentially one very long basic block that does little
more than allocate a bunch of objects; but, all of those moves look
"tempting" to the peephole optimizer, with a lot of partial peephole
pattern matches.  I could well imagine that your generated code might
have a similar behavior.

Here are a couple of other things that you might try, since you've
narrowed things down to the codegen.

You could try "-native-optimize 0", which will disable most of the
codegen specific optimizations.  But, like "-ssa-passes minimal", by
skipping the optional optimization passes, there might be more work
left for the required passes; e.g., without some peephole
optimizations and copy propagation, there will be many extra
temporaries for the register allocator to handle.

You could also try the C codegen, rather than the native amd64 codgen.
That is, compile with "-codegen c" or "-codegen c -cc-opt -O0".  The
former would use the C codgen with a default set of flags, including
"-O1", passed to gcc, while the latter would add in an additional
"-O0" flag to gcc, which might speedup the time compiling with gcc.
In either case, the "C code gen" time should be nearly zero (it is
just writing a C file), but you would want to watch "Compile and
Assemble" time, which will go up as it will be gcc doing the real work
of lowering to native instructions.

> I did try “-ssa-passes minimal” and you are dead right that it
> slows up the code generation. Here are the figures for
> doing the full test with all 5 grammars.
>
>       pre codegen finished in 18.96 + 4.03 (18% GC)
>       amd64 code gen finished in 1222.61 + 10.11 (1% GC)
> MLton finished in 1248.90 + 14.58 (1% GC)
>
> Not a good trade-off!

Indeed!

-- 
You received this message because you are subscribed to the Google Groups "MLton-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].


------------------------------------------------------------------------------
Site24x7 APM Insight: Get Deep Visibility into Application Performance
APM + Mobile APM + RUM: Monitor 3 App instances at just $35/Month
Monitor end-to-end web transactions and take corrective actions now
Troubleshoot faster and improve end-user experience. Signup Now!
http://pubads.g.doubleclick.net/gampad/clk?id=272487151&iu=/4140
_______________________________________________
MLton-user mailing list
[email protected]; [email protected]
https://lists.sourceforge.net/lists/listinfo/mlton-user