Awesome! For those wanting to experiment, you can quickly try this out in OPAM by:

opam update
opam switch 4.03.0+pr132
eval `opam config env`

I'm kicking off an OPAM bulk build with this patch and will report back with a URL with the logs when complete.

The patchset is cleaner than I expected, but it would still help if you tried to rebase to squash/fixup the commits that came during your own rebase to adapt to trunk changes. The idea is that if merging patches A and B together gives a patch that is exactly as simple as A, then the merge should be done.

(It would also be nice to try to ensure that intermediate state compiles (I don't think it is a problem if they emit warnings, however). It both makes the changes easier to review, and will make it easier to bisect the history later on.)

I like having the testsuite. I regret the lack of some text presenting the branch and documenting some of the design choices. I think there was something in this direction used in the previous reviews, would it be possible to update and include it? It's very helpful both for the junior reviewers that don't know what to expect, and for the reviewers that want to be able to check and comment on the general architecture before going into the patch details.

Notice that the flambdasimplify file is not as clean as it should be. There is still quite some work to document the important invariants.

Excellent to see this work progressing. I would like to start with some high-level questions, which I think would need to be explicitly answered before merging could be seriously considered:

• Could you explain the decision to stick so closely to the existing lambda IL? It is a complicated language, close to a lisp source language, and optimising compilers (which your patch is a first-step in turning ocamlopt into) do not generally operate on such source-like languages. In particular, did you consider using something more csp/anf based, which is generally considered easier to implement inlining on?
• Could you explain the decision to use a language in which closure conversion has already been done? Inlining is generally easier on a (sensible) intermediate language before closure conversion because it does not require a value analysis to remove unnecessary closures.
• Could you explain why the compiler needs both clambda and flambda? Could clambda be removed and flambda lowered directly to cmm?

I appreciate that a lot of work has already gone into this patch, and such high level questions would have been better asked at an earlier stage. However, I only recently (a few weeks ago) started to look at the patch (the old version -- I'll have a proper look at the new version soon), so this is my first real opportunity to ask these questions.

I will reply to some questions, although Pierre is probably more competent:

Could you explain the decision to stick so closely to the existing lambda IL?

The goal was to improve the compiler, not to rewrite it completely. Switching to another IL would probably require to implement all subsequent passes on this IL, whereas flambda branches back to clambda to reuse all subsequent existing passes.

Could you explain the decision to use a language in which closure conversion has already been done?

In my own experience, doing inlining before closure conversion is actually more difficult, as the free variables in your inlined function might not be bound in the environment where the function is inlined. This problem disappears after closure conversion. Another reason would be that you want to perform inlining and other optimizations in the same pass, to check if inlining is useful for example, and having done closure conversion can provide opportunities for more optimizations.

Could you explain why the compiler needs both clambda and flambda?

There is still some work done between flambda -> clambda -> cmm. Doing flambda directly to cmm would require flambda to have a different representation for some concepts (variables, if I remember correctly), that would not be the best representation for the optimizations performed in flambda. Going through clambda is simpler and increase utilisation of existing code in the compiler, decreasing the risk to introduce more bugs.

The goal was to improve the compiler, not to rewrite it completely. Switching to another IL would probably require to implement all subsequent passes on this IL, whereas flambda branches back to clambda to reuse all subsequent existing passes.

Surely that is just an argument for using an IL which can be converted to clambda (or a subset of clambda), rather than using a language which closely matches lambda.

In my own experience, doing inlining before closure conversion is actually more difficult, as the free variables in your inlined function might not be bound in the environment where the function is inlined.

This just illustrates that lambda is an inappropriate language for inlining, because it allows full lambda expressions to be bound by let expressions. This allows variables to go out of scope, preventing inlining is some cases. Most ILs do not provide such forms (only allowing let X = V in E where V is a value and E is an expression), and so avoid the problem completely.

Another reason would be that you want to perform inlining and other optimizations in the same pass, to check if inlining is useful for example, and having done closure conversion can provide opportunities for more optimizations.

Could you give an example of the kind of optimisation you have in mind?

Most ILs do not provide such forms (only allowing let X = V in E where V is a value and E is an expression), and so avoid the problem completely.

Isn't it the goal of closure conversion ? Once closure conversion is done, all lambdas are simple values, and can be bound by let without risk.

Could you give an example of the kind of optimisation you have in mind?

Typically, you would perform some inlining, and then go through constant propagation, simplification of expressions, CSE, deadcode elimination, and then check whether the code size has decreased or not, to decide to either backtrack on the decision to inline (if no simplification could be performed) or on the contrary inline even more (if it simplified so much that you are still under some growth threshold). I think Manuel Serrano's paper on Bigloo shows something like that.

Isn't it the goal of closure conversion ? Once closure conversion is done, all lambdas are simple values, and can be bound by let without risk.

Sorry, I was not clear enough in my example. The point is that you do not allow a let form to appear within the expression bound within another let form, that way nothing ever goes out of scope and so the free variables of a function are always in scope if the function is in scope.

The point is you should not need closure conversion to solve this issue, since the issue should not arise in any sensible IL. For a good example of such an IL see "Compiling with continuations continued" by Kennedy.

Typically, you would perform some inlining, and then go through constant propagation, simplification of expressions, CSE, deadcode elimination, and then check whether the code size has decreased or not, to decide to either backtrack on the decision to inline (if no simplification could be performed) or on the contrary inline even more (if it simplified so much that you are still under some growth threshold). I think Manuel Serrano's paper on Bigloo shows something like that.

This either requires implementing these optimisations on flambda, or lowering the flambda to cmm and then performing them. Nothing immediately strikes me as making either of these options easier (or harder) after closure conversion. I'm also a little dubious about how they would affect compilation time and predictability of inlining, but that is a separate concern.

This either requires implementing these optimisations on flambda, or lowering the flambda to cmm and then performing them. Nothing immediately strikes me as making either of these options easier (or harder) after closure conversion.

Constant propagation (in fact a slightly more general value analysis) is currently done during closure conversion. Moving it to flambda is a natural choice that simplifies the closure conversion pass in a non-invasive way. Dead code elimination seems no harder to perform on flambda than another level, but I agree that CSE is probably more useful after cmm (typically to observe bound checks).

Leo, I think (at least on this pull request) it would be sensible to step back a little from the arguments about the form of the intermediate language. There are clearly various possibilities about what form of IL could be used to implement these sorts of middle-end optimizations, and my general sense is that each will ultimately turn out to have its advantages and disadvantages---I suspect it's actually very difficult to label one as particularly more "sensible" than the others in any watertight manner. flambda has chosen to remain close to what the OCaml backend uses at the moment, which is probably sensible from a software engineering point of view (this is enough of an upheaval already).

I'm not an expert at the middle-end of compilers but my general feeling is that if you take the existing lambda/flambda-style of IL as a prior, then it's probably easiest to do some lightweight form of closure conversion (and I think flambda's is fairly lightweight) early and then do the inlining and further analyses afterwards. It would seem to be easier in terms of dealing with free variables, and potentially means that more optimization passes would be able to work on the same form of IL, hopefully leading to more sharing of code. I would be surprised if the value analysis wouldn't be useful for other optimizations too.

Leo, I think (at least on this pull request) it would be sensible to step back a little from the arguments about the form of the intermediate language.

Sure. To be clear I'm not arguing against the merging of flambda. It seems no harder to simplify the middle-end after these changes have been merged, and it is a clear improvement over what exists currently (in terms of performance of code produced -- the complexity and performance of the implementation itself are less clearly improvements). I just think that, before merging, it is important that the design decisions inherent in the change are made clear.

I'm not an expert at the middle-end of compilers but my general feeling is that if you take the existing lambda/flambda-style of IL as a prior, then it's probably easiest to do some lightweight form of closure conversion (and I think flambda's is fairly lightweight) early and then do the inlining and further analyses afterwards.

I agree, but it is the "if you take the existing lambda/flambda-style of IL as a prior" that I'm not sure is the right design long term. I'm also interested if Fabrice or Pierre have reasons beyond this for doing the closure conversion before inlining. Again, it is clarity on the design decisions I am after, rather than any specific changes to this patch.

I just think that, before merging, it is important that the design decisions inherent in the change are made clear.

Along the same lines, it would be useful to have a list of the passes/optimisations that the patch adds. Perhaps they are already listed somewhere in the patch, but I don't remember seeing it when I looked through the old version.

(Even more useful would be a list of all optimisation passes in the compiler both before and after this patch -- but it seems unfair to ask Fabrice and Pierre for this just because they happen to have added some new ones).

Also, are there any benchmark results for the various optimisations? If not, does anyone have good suggestions for benchmarks (a problem Xavier also complained about when he added CSE)?

If not, does anyone have good suggestions for benchmarks (a problem Xavier also complained about when he added CSE)?

Yes: Vincent Bernardoff ( @vbmithr ) worked on a set of benchmarks for OCaml during an internship at OCamlPro. The work is still young and fresh, and I haven't yet had the time to play more with it, but it could be fairly useful to evaluate changes such as this one. I hope to write more about it eventually.

For the record I have played a bit with the flambda branch in the past when asking questions of the form "would {trunk, flambda} be able to optimize this code pattern?" and been generally satisfied with the answers -- for things that wouldn't show up much in benchmarks of existing code, such as functor inlining or code-generation-specific patterns. I think the even more important question is whether the IL makes it easier to implement new optimizations correctly or improve the existing ones.

On 19 Dec 2014, at 09:40, gasche [email protected] wrote:

If not, does anyone have good suggestions for benchmarks (a problem Xavier also complained about when he added CSE)?

Yes: Vincent Bernardoff ( @vbmithr https://github.com/vbmithr ) worked on a set of benchmarks for OCaml during an internship at OCamlPro. The work is still young and fresh, and I haven't yet had the time to play more with it, but it could be fairly useful to evaluate changes such as this one.

Is this work available online anywhere?

Aaah! @bactrian has become sentient.

Gosh darn it, I've been outed! It is actually me, Annnniiiil!

http://github.com/vbmithr/operf-macro
Have a look, and don't hesitate to ask questions. I have completed my "internship" in the end of november, and this is the result. We wanted to use it a bit more with @chambart before announcing it to the world. The doc should be OK though.

I think the main argument against "inlining before closure conversion" is inter-module inlining: to allow inter-module inlining, you have to be able to recover the variables in the environment from another module. Unfortunately, in OCaml (I think it is not true for Haskell), abstraction through module interfaces allows you to hide values, and thus, such values won't be reachable from the inlined code. After closure conversion, the closure is stored somewhere, so you just have to recover it to access all the environment through it.

For operf-macro, you should access it through http://github.com/OCamlPro/operf-macro, as this is the version that we are going to maintain. There is also operf-micro (http://github.com/OCamlPro/operf-micro, with Vincent's work available as a pull-request to be reviewed before inclusion), that provides micro-benchmarks only for the compiler.

On 12/19/2014 07:18 PM, Fabrice Le Fessant wrote:

I think the main argument against "inlining before closure conversion"
is inter-module inlining: to allow inter-module inlining, you have to be
able to recover the variables in the environment from another module.
Unfortunately, in OCaml (I think it is not true for Haskell),
abstraction through module interfaces allows you to hide values, and
thus, such values won't be reachable from the inlined code. After
closure conversion, the closure is stored somewhere, so you just have to
recover it to access all the environment through it.

Is this still true for functions that are not defined in a functor body
(i.e. at toplevel or under sub-modules)?

The current compilations scheme (which you implemented, I believe) adds
extra fields to each compilation unit to store all extra values which
are not exported, and code within the unit accesses those value through
these extra fields. This means that all these functions should be
closed. Is it not the case?

For functors, the alternate compilation which I suggested recently on
Mantis would achieve a similar effect: all functions defined in the
body would actually have a single value in their closure -- the
structure representing the functor's result. And this value would
normally be accessible wherever such a function is required. I.e. after:

module Y = F(X)

a reference to Y.f would be a function whose closure contains only Y (or
perhaps we could even share the block representing Y and the closure,
with inner pointers). So Y.f can be inlined on the call site.

Alain

I have two questions related to shiny new optimizations in OCaml (which I'm truly eager to have):

• will there be a -O flag to have fast compilation and slow binaries during dev, and slow compilation and fast binaries for production?
• will there be annotations ([@inline always], [@specialize] for combinators, [@unroll 3] for recursion/loop unrolling, etc.) to give hints to the optimizer? Sometimes we know better than the optimizer and we should be able to direct it.

Apart from that I'm going to try this on small benchmarks of mine. That branch is great.

@c-cube: there's been some discussion of @inline annotations on the cam-compiler-hacking mailing list.

I just tried a quick benchmark using ocamlgraph, which uses a lot of functors, and the result is great.
Using the sudoku solver found here: https://www.lri.fr/~filliatr/ftp/publis/ocamlgraph-tfp-8.pdf

% opam switch show
4.03.0+trunk
% ocamlfind ocamlopt -inline 99999 -o sudoku.opt -package ocamlgraph -linkpkg sudoku.ml
% ls -l sudoku.opt
-rwxr-xr-x 1 rixed rixed 1754767 Dec 20 19:42 sudoku.opt*
% time ./sudoku.opt < grid1 >/dev/null
0.93s user 0.00s system 99% cpu 0.938 total
% opam switch 4.03.0+pr132
% eval `opam config env`
% ocamlfind ocamlopt -inline 99999 -o sudoku.opt -package ocamlgraph -linkpkg sudoku.ml
% ls -l sudoku.opt
-rwxr-xr-x 1 rixed rixed 3280581 Dec 20 19:43 sudoku.opt*
% time ./sudoku.opt < grid1 >/dev/null
0.59s user 0.00s system 99% cpu 0.599 total

Since we are talking about micro-benchmarks, I wrote a very small one
that tests internal iterators (attached). The output is nice too :)

edit: no attachment on github, check http://cedeela.fr/~simon/files/bench_sequence.sh and http://cedeela.fr/~simon/files/bench_sequence2.sh

The results (computing a mean on a large integer sequence after a few
maps/filters, see bench_sequence.sh) are:

4.02.1:
avg: 50000000

real 3.292s
user 3.283s
sys 0.003s

flambda:
avg: 50000000

real 2.008s
user 1.997s
sys 0.010s

So it looks quite nice.

Note: Running the benchmark will install sequence and create files in
your current directory. It will also produce the clambda output of both
compilers for you to read the diff.

Since they are talking about micro-benchmarks, let's instead bring some macro-benchmarks! I checked the time it takes for trunk and flambda to compile OCaml programs on my machine.

For camlp4, make all takes 1m06s on trunk, and 2m00s on flambda: because of the extra optimization work, the overall compile-time is twice slower. opam install ocamlfind takes 5s in trunk and 10s in flambda: again, twice slower. This just means that the current branch has been optimized with respect to compilation time yet.

Then I tried some bytecode-only compilation to see if the compiler itself had gotten faster thanks to the flambda work. In Batteries, running ocamlbuild src/batteries.cma five times in a row takes 32.5s on trunk, and 37.7s on flambda. It seems that bytecode compilation is slightly slower as well.

I'm not sure that's the right place for reporting bugs, but here we go. I don't know exactly how to get the commit number of an opam switch, sorry, I only know the switch is 4.03.0+pr132.

So I tried to compile my datalog library to check its performance.

opam switch 4.03.0+pr132
eval `opam config env`
git clone https://github.com/c-cube/datalog.git
cd datalog
make all

It fails as follows:

ocamlfind ocamlopt -c -g -I src -package unix -package str -package num -inline 10 -I src -o src/topDownCli.cmx src/topDownCli.ml
Value unknown: (var TopDown.interpret/24656 TopDown.interpret_list/24657
TopDownUnix.inlined_closure/6556)

TopDownCli.inlined_closure/5736

TopDownUnix.inlined_closure/6556

Fatal error: exception File "asmcomp/flambdasimplify.ml", line 685, characters 12-18: Assertion failed
Command exited with code 2.

For camlp4, make all takes 1m06s on trunk, and 2m00s on flambda:
because of the extra optimization work, the overall compile-time is twice slower

Meh. How much faster is the camlp4 generated by flambda compared to the one generated by trunk?

How much faster is the camlp4 generated by flambda compared to the one generated by trunk?

They're about the same speed. Maybe most Camlp4 workflows are IO and GC-bound?

We discussed flambda in general in the developer meeting today, and there was agreement on trying to get it in the next release if it is ready on time. Mark was aiming for the 4th of December as a landing date.

@gasche Why did you close this PR? Should we look at another branch?

I suspect that the in-development branch is chambart/ocaml-1#flambda_trunk, but I am not sure Mark and Pierre are expecting us to pry on their development history. Having a separate "clean" branch for review made sense at some point, but it looks like the release timeline is too short for this to be effective in practice.

I just closed the PR as a issue-handling reaction: my idea is to maximize, among the open PRs, the proportion of those that require review/decisions, in order to direct the attention of interested contributors (core team or external contributors alike). The writing is already on the wall for this one, so I closed it. If you think (even as a mild intuition) that keeping it open is the better thing to do (encourage the miraculous review from someone?), I'm fine with reopening.

No, no, I was just wondering.