Re: Discovering which optimizations took place

Hi Matthew,

At first, I should thank you for the elaborate answer and the way you
describe, is way more effective than trying naively to figure out things
with .s directly. As I did at first.

As a first step I will try to familiarize myself with the -keep-pass flag.

Thx for the tip with the ordering of .pre vs .post! This will save me some
time!

The name "gen" comes from your
> "Streams.ofArray" implementation and the "Stream.sum",
> "Stream.flatMap", and "Stream.map" code has been inlined and is being
> driven by the source stream --- which I think is precisely what you
> want for a push-based stream library.
>

This is exactly what I was looking for. I will follow the same strategy
with the multiple filters and maps to see what happens there.

And just to clear things up (for me): This is the part that helped me to
see that pattern matching over environments will result in gen_0 only
through the flatMap argument deconstruction (v2). SSA svg really helps!


​
Kind regards and thank u,
Aggelos Biboudis.


On Wed, Nov 12, 2014 at 10:37 PM, Matthew Fluet <[email protected]>
wrote:

> On Wed, Nov 12, 2014 at 8:17 AM, Aggelos Biboudis <[email protected]>
> wrote:
> > recently I developed/ported to SML, a push-based stream processing
> library
> > just to investigate the performance characteristics of such a design
> under
> > MLton. It was an opportunity to learn SML (sry in advance if you notice
> > unidiomatic code) and use MLton for the first time (at last). I was
> amazed
> > by the result, but I am more interested to learn about the optimizations
> > that took place in this particular scenario.
>
> Glad to hear that MLton performed positively with your streaming library.
>
> > For example, in the flatMap/Map case (Cartesian product) did I
> essentially
> > get nested loops?
> >
> > Can you provide me guidelines to further analyze the underlying code, of
> > such an experiment?
> > Which is the preferred way? x86 deep dive or AST-pretty printing somehow?
>
> Generally, most of the significant optimizations are performed on the
> SSA and SSA2 intermediate languages.  You can read more about the ILs
> and the various optimizations passes at:
>   http://mlton.org/SSA
>   http://mlton.org/SSASimplify
>   http://mlton.org/SSA2
>   http://mlton.org/SSA2Simplify
>
> You can keep the various intermediate languages with the "-keep <IL>"
> command-line flag.  For instance:
>   mlton -verbose 2 -keep core-ml -keep xml -keep sxml -keep ssa -keep
> ssa2 -keep rssa -keep machine -keep g
> will dump the program in each of the major intermediate languages (see
> http://mlton.org/IntermediateLanguage) as well as the generated
> assembly ("-keep g").
>
> You can also keep the IL of the program before and after individual
> optimizations with the "-keep-pass <RE>" command-line flag.  For
> instance:
>   mlton -verbose 2 -keep-pass introduceLoops1
> will dump the program before and after the first "introduceLoops"
> optimization pass.  One word of warning when looking at the .pre.ssa
> vs. the .post.ssa files: many of the SSA optimizations effectively
> rewrite the program using a "rev-map" over the collection of
> functions; this is because the order of functions in the program IL
> does not matter and a rev-map is tail-recursive (whereas a map is
> either not tail-recursive or performs an extra reverse).  However, the
> consequence is that a textual diff of .pre.ssa vs. .post.ssa is often
> not particularly helpful to identify what changed.
>
> The "-keep-pass <RE>" command-line flag takes a regular-expression, so
> "-keep-pass '.*'" will effectively dump the program before and after
> every optimization and translation pass.
>
> For the SSA and SSA2 ILs, it is often convenient to see the
> control-flow graph representation of the individual functions; the
> "-keep dot" command-line flag causes any dumped SSA/SSA2/RSSA IL
> program to also dump Graphviz .dot files for the interprocedural
> call-graph and for each of the individual functions.  Sometimes these
> control-flow graphs can be fairly large, but I've had good luck using
> Graphiviz's dot tool to convert them to SVG format and viewing them in
> a recent web-browser.
>
> The "-drop-pass <RE>" command-line flag cab be used to skip a
> particular optimization pass.  This can be useful for seeing the
> impact of a particular optimization pass on a benchmark.  Of course,
> it isn't always easy to isolate the benefit of individual passes;
> often, the benefit is that it enables other optimization passes.
>
>
> With regards to your specific benchmark program, I did the following:
>   make FLAGS="-verbose 2 -keep ssa -keep dot" bench
>   dot -Tsvg bench-streams.ssa.gen_0.cfg.dot >
> bench-streams.ssa.gen_0.cfg.dot.svg
> I believe that the "gen_0" SSA IL function corresponds to the "cart"
> function in bench-streams.sml.  The name "gen" comes from your
> "Streams.ofArray" implementation and the "Stream.sum",
> "Stream.flatMap", and "Stream.map" code has been inlined and is being
> driven by the source stream --- which I think is precisely what you
> want for a push-based stream library.
>
> Note that MLton has a non-trivial implementation of "structure
> LargeInt" (see http://mlton.org/MLtonIntInf).  So, while you can find
> the "IntInf_mul" that corresponds to the "x * y" in the inner
> "Stream.map" and the "IntInf_add" that corresponds to the "a + ss" in
> the "Stream.sum", there is also a lot of supporting code that
> determines whether the operation can be done at a "small"
> fixed-precision or if it needs to be done at a "big"
> arbitrary-precision.  You might find it easier to investigate the
> exact form of the optimized program by switching from LargeInt to Int
> (or to Word, if you don't really care about the arithmetic result,
> since Word operations will silently wrap and not raise Overflow).
>
> If you look at the "gen_0" SSA IL function, you will see a non-tail
> recursive call of "gen_0" (which gives rise to a nested
> interprocedural loop) and a number of nested intraprocedural loops.  I
> would think that the non-tail recursive call corresponds to the
> non-tail call of "innerf(iterf)" in the "Stream.flatMap"
> implementation.  But, there isn't an unbounded stack growth:
>
> [mtf@fenrir sml-streams]$ git diff
> diff --git a/benchmarks/bench-streams.sml b/benchmarks/bench-streams.sml
> index f82cc9c..deb4d02 100644
> --- a/benchmarks/bench-streams.sml
> +++ b/benchmarks/bench-streams.sml
> @@ -67,8 +67,8 @@ fun main () =
>
>         (* Backing Arrays *)
>         val backingArr = Array.tabulate (3000000, fn i => i);
> -       val backingArrCart1 = Array.tabulate (100, fn i => Int.toLarge i);
> -       val backingArrCart2 = Array.tabulate (10, fn i => Int.toLarge i);
> +       val backingArrCart1 = Array.tabulate (10000000, fn i =>
> Int.toLarge i);
> +       val backingArrCart2 = Array.tabulate (100, fn i => Int.toLarge i);
>
>         (* Stream wrapping *)
>         val v = Stream.ofArray backingArr;
> [mtf@fenrir sml-streams]$ make bench
> make dirs
> mkdir -p "/Users/mtf/tmp/sml-streams/build"
> Type checking streams.
> "mlton" -verbose 0 -stop tc /Users/mtf/tmp/sml-streams/streams.mlb
> make dirs
> mkdir -p "/Users/mtf/tmp/sml-streams/build"
> Building bench-streams.
> "mlton" -verbose 0 -output
> /Users/mtf/tmp/sml-streams/build/bench-streams
> /Users/mtf/tmp/sml-streams/benchmarks/bench-streams.mlb
> [mtf@fenrir sml-streams]$ ./build/bench-streams @MLton gc-summary --
> Running
> Streams filters_6 time: 0.011 sec/op
> Baseline filters_6 time: 0.011 sec/op
> Streams cart time: 10.895 sec/op
> Baseline cart time: 7.897 sec/op
>
> Validation
> Streams  filters_6 = 2999984
> Baseline filters_6 = 2999984
> Streams  cart     = 247499975250000000
> Baseline cart     = 247499975250000000
> GC type time ms number  bytes      bytes/sec
> ------------- ------- ------- --------------- ---------------
> copying     50      2     80,031,032  1,600,620,640
> mark-compact      0      0              0              -
> minor      0      0              0              -
> total time: 18,883 ms
> total GC time: 117 ms (0.6%)
> max pause time: 116 ms
> total bytes allocated: 412,022,616 bytes
> max bytes live: 80,016,176 bytes
> max heap size: 640,196,608 bytes
> max stack size: 848 bytes
> num cards marked: 0
> bytes scanned: 0 bytes
> bytes hash consed: 0 bytes
>
> >From the "max stack size: 848 bytes", you can see that that non-tail
> recursive call is not repeated.  What I think you are seeing with the
> non-tail recursive call is that the same "gen_0" function is being
> used to drive the "Stream.map" on the v2 and the "Stream.flatMap" on
> the v1, where a defunctionalized closure ("datatype lambdas_1 = ... "
> in bench-streams.ssa) is being used to distinguish the two uses.
>
> Looking carefully at that defunctionalized closure:
>   lambdas_1 = Env_5 of (intInf array, (word64 * word64), lambdas_1) |
> Env_4 of (intInf, (word64 * word64), lambdas_1) | Env_3 of ((word64 *
> word64))
> we recognize Env_5 as the argument to Stream.flatMap (the "intInf
> array" is the "v2'" free variable) and Env_4 as the argument to
> Stream.map (the "intInf" is the "x" free variable).  More importantly,
> there is only one Env_5 construction in the program, which takes the
> one Env_3 construction as an argument.  Furthermore, all of the Env_4
> constructions are constructed with a lambdas_1 taken from a
> deconstructed Env_5.  So, the lambdas_1 component of all Env_5 and
> Env_4 values in the program are an Env_3.  Furthermore, the non-tail
> recursive call of "gen_0" is reachable only by deconstructing a Env_5,
> which convinces us that there is only ever two "gen_0" frames on the
> call stack.  If we were to unroll "gen_0" once and exploit this fact
> about the lambdas_1 component of Env_4 and Env_5 constructors, then we
> would achieve entirely intraprocedural loops with no non-tail
> recursive calls.
>
> While we wait for the compiler to learn that optimization, we can
> verify that things would be better if we didn't conflate the driving
> of the "Stream.map" on the v2 and the "Stream.flatMap" on the v1.  To
> do so, make a code-clone of "Stream.ofArray" and use one for v1 and
> the other for v2:
>
> [mtf@fenrir sml-streams]$ git diff
> diff --git a/benchmarks/bench-streams.sml b/benchmarks/bench-streams.sml
> index f82cc9c..9b9b83b 100644
> --- a/benchmarks/bench-streams.sml
> +++ b/benchmarks/bench-streams.sml
> @@ -67,13 +67,13 @@ fun main () =
>
>         (* Backing Arrays *)
>         val backingArr = Array.tabulate (3000000, fn i => i);
> -       val backingArrCart1 = Array.tabulate (100, fn i => Int.toLarge i);
> -       val backingArrCart2 = Array.tabulate (10, fn i => Int.toLarge i);
> +       val backingArrCart1 = Array.tabulate (10000000, fn i =>
> Int.toLarge i);
> +       val backingArrCart2 = Array.tabulate (100, fn i => Int.toLarge i);
>
>         (* Stream wrapping *)
>         val v = Stream.ofArray backingArr;
>         val v1 = Stream.ofArray backingArrCart1;
> -       val v2 = Stream.ofArray backingArrCart2;
> +       val v2 = Stream.ofArray2 backingArrCart2;
>
>         (* Stream functions *)
>         fun length values = Stream.length values;
> diff --git a/streams.sig b/streams.sig
> index c4c0426..2720c0b 100644
> --- a/streams.sig
> +++ b/streams.sig
> @@ -5,6 +5,7 @@
>  signature STREAM = sig
>      type 't stream
>      val ofArray : 't array -> 't stream
> +    val ofArray2 : 't array -> 't stream
>      val map    : ('t -> 'r) -> 't stream -> 'r stream
>      val filter : ('t -> bool) -> 't stream -> 't stream
>      val takeWhile : ('t -> bool) -> 't stream -> 't stream
> diff --git a/streams.sml b/streams.sml
> index 5b2e5ba..3e9b9df 100644
> --- a/streams.sml
> +++ b/streams.sml
> @@ -100,4 +100,21 @@ structure Stream : STREAM = struct
>        in
>           Stream gen
>        end
> +
> +  fun ofArray2 arr =
> +      let val gen =
> +          fn iterf =>
> +             let
> +                 val counter = ref 0
> +                 val cont = ref true
> +                 val size = Array.length arr
> +             in
> +                 while !counter < size andalso !cont do (
> +                     cont := iterf (Array.sub(arr, !counter));
> +                     counter := !counter + 1
> +                 )
> +             end
> +      in
> +         Stream gen
> +      end
>  end
> [mtf@fenrir sml-streams]$ make bench
> make dirs
> mkdir -p "/Users/mtf/tmp/sml-streams/build"
> Type checking streams.
> "mlton" -verbose 0 -stop tc /Users/mtf/tmp/sml-streams/streams.mlb
> make dirs
> mkdir -p "/Users/mtf/tmp/sml-streams/build"
> Building bench-streams.
> "mlton" -verbose 0 -output
> /Users/mtf/tmp/sml-streams/build/bench-streams
> /Users/mtf/tmp/sml-streams/benchmarks/bench-streams.mlb
> [mtf@fenrir sml-streams]$ ./build/bench-streams
> Running
> Streams filters_6 time: 0.011 sec/op
> Baseline filters_6 time: 0.011 sec/op
> Streams cart time: 7.269 sec/op
> Baseline cart time: 7.700 sec/op
>
> Validation
> Streams  filters_6 = 2999984
> Baseline filters_6 = 2999984
> Streams  cart     = 247499975250000000
> Baseline cart     = 247499975250000000
>
> Looking at bench-streams.ssa for this version of the program, you'll
> see that there is no "gen_0" function -- the corresponding code is no
> non-recursive and has been inlined into the "main_0" function.  The
> nested loops should be there, but somewhat lost amid all of the
> top-level initialization and exception handling code.  In any case,
> you get an improved throughput.
>
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
>
>
> ------------------------------------------------------------------------------
> Comprehensive Server Monitoring with Site24x7.
> Monitor 10 servers for $9/Month.
> Get alerted through email, SMS, voice calls or mobile push notifications.
> Take corrective actions from your mobile device.
>
> http://pubads.g.doubleclick.net/gampad/clk?id=154624111&iu=/4140/ostg.clktrk
> _______________________________________________
> MLton-user mailing list
> [email protected]; [email protected]
> https://lists.sourceforge.net/lists/listinfo/mlton-user
>

To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].

------------------------------------------------------------------------------
Comprehensive Server Monitoring with Site24x7.
Monitor 10 servers for $9/Month.
Get alerted through email, SMS, voice calls or mobile push notifications.
Take corrective actions from your mobile device.
http://pubads.g.doubleclick.net/gampad/clk?id=154624111&iu=/4140/ostg.clktrk

_______________________________________________
MLton-user mailing list
[email protected]; [email protected]
https://lists.sourceforge.net/lists/listinfo/mlton-user