Re: Discovering which optimizations took place

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