|Anonymous | Login | Signup for a new account||2013-05-21 13:08 CEST|
|Main | My View | View Issues | Change Log | Roadmap|
|View Issue Details|
|ID||Project||Category||View Status||Date Submitted||Last Update|
|0005500||OCaml||OCaml backend (code generation)||public||2012-02-05 07:49||2012-04-04 17:25|
|Priority||normal||Severity||minor||Reproducibility||have not tried|
|Target Version||Fixed in Version|
|Summary||0005500: compilation of "module rec" makes runtime assumptions on closure representation|
|Description||When compiling "module rec", the compiler makes assumptions on the fact that "camlinternalMod.ml" will be able to patch the closure in place.|
This assumption prevents correct compilation of projects containing "module rec" with compilers changing the representation of closures (js_of_ocaml in my case).
The attached patch fixes the problem, by using references instead. Each closure is compiled as (fun _ -> ! (prototypes.(pos)) ), where prototypes.(pos) is initialized as (ref (fun _ -> raise (Undefined_recursive_module ..))). Then, the reference is modified when the final closure is known. This process makes no assumption on the representation of closures.
I didn't do any performance test, as I was only interested in having the application compiled, but I assume that the extra indirection is not very expensive with modern processors.
|Tags||No tags attached.|
|Attached Files|| ocaml-module-rec-2012-02-05v2.patch [^] (6,550 bytes) 2012-02-05 07:49 [Show Content]
modrecBench.ml [^] (1,222 bytes) 2012-02-05 19:12
The current compilation scheme for recursive modules goes out of its way to ensure that recursive functions thus defined run as fast as functions defined using "let rec". Your patch breaks this optimization completely, and I am pretty sure it degrades performance significantly for programs that use recursive modules. So, I cannot accept this patch.
I don't know how js_of_ocaml works, but would it be possible to achieve correct results by providing an alternative implementation of camlinternalMod to be used for js_of_ocaml-ized code, without changing the OCaml compiler?
Do you have benchmarks for "module rec", or applications where performance of "module rec" is critical ? I would like to measure the difference of performance between the two implementations.
|Alain has his patch to turn any module into a self-recursive one for backward declarations. I suppose he's therefore an heavy user of recursive modules and could provide you with the necessary performance information.|
The "A / ASet" example of recursive modules from the OCaml manual (section 7.8) could make a decent microbenchmark.
Discussing the issue with the js_of_ocaml developers would help, too.
edited on: 2012-04-05 06:00
[edit: english translation below]
Comme il ne contient rien de personnel, je recopie la réponse de jérôme à mon mail l'informant du problème et du patch:
> > Juste pour info, j'ai essayé de compiler un programme avec un "module
> > rec" avec js_of_ocaml, et ça ne marche pas car camlinternalMod.ml fait
> > des hypothèses sur la représentation des fermetures, qui ne doivent pas
> > correspondre à la représentation des fermetures de js_of_ocaml (je n'ai
> > pas exploré).
Exactement. Pour l'interpréteur de bytecode, les fermetures sont des
blocs comme les autres, et camlinternalMod.ml se permet de remplacer
le contenu d'un de ces blocs par celui d'un autre bloc. Avec
On a le même genre de problème avec les récursions entre fonctions et
valeurs non-fonctionnelles. Mais dans ce dernier cas, on arrive à s'en
tirer car le code qui effectue la copie est en C ('caml_update_dummy'),
et donc on peut le changer.
Ce serait bien si ton patch arrive à passer. :-)
As it is not intended to be private, I quote here Jérôme's answer to my email about the issue and this patch:
> Hi Fabrice,
> > Just for information, I tried to compile a program using "module rec"
> > with js_of_ocaml. It doesn't work because camlinternalMod.ml makes
> > assumptions on the representation of closures, that may not be satisfied
> > by js_of_ocaml's closure representation -- I haven't tried yet.
> Exactly. As far as the bytecode interpreter is concerned, closures
> are usual OCaml blocks, and camlinternalMod just replaces the content of
> one of these block by another block. In js_of_ocaml, they are represented
> We have the same kind of problems with the compilation of mutual recursion
> between functions and non-function values. But in this case we can pull
> it off because it is a C primitive, 'caml_update_dummy', which does the
> It would be nice if your patch were accepted :-)
|Gabriel: Alain uses recursive modules only for typing, not for compiling, so the "module rec" compilation scheme does not apply in his case, I think.|
|I ran the attached micro-benchmark (you know what I think about such benchmarks ;-) ), using the manual example. The new version is only 25% slower than the old one.|
Julien Signoles (reporter)
|only 25% slower? That is huge!|
|The micro-benchmark is 25% slower, which means that a real application would probably not see any difference (when I have speed-up of 200% on micro-benchmarks, people usually tell me that it means only a few % on a real application, so it is the same reasoning... ;-) )|
The problem with the reasoning in this case is that recursive functions are at the heart of quite a lot of performance-critical code paths (while that is much less clear with recursive values). Your "micro-benchmark" is actually a very reasonable use of recursive modules for a non-stupid purpose (mutually recursively defining datatypes and balanced set of those datatypes) which may be representative of real-world code. Indeed I have myself observed comparison functions to be the bottleneck of very real code examples.
I'm wondering whether it is possible to fix this issue without impacting performances as your current patch does. If I understand correctly, recursive closure compilation does not use a backpatching semantics, it uses absolute position prediction to generate a shared closure for the mutually defined functions. Would it be possible to use the same trick for mixed function/value recursion, or module recursions? Define the values first then build a shared closure for the functions.
I'm really not sure of the absolute feasability of this, and I'm sure that getting a good patch, giving the subtlety and importance of those parts of the compiler, would be *a lot* of work.
|2012-02-05 07:49||lefessan||New Issue|
|2012-02-05 07:49||lefessan||File Added: ocaml-module-rec-2012-02-05v2.patch|
|2012-02-05 11:20||xleroy||Note Added: 0006880|
|2012-02-05 11:20||xleroy||Status||new => resolved|
|2012-02-05 11:20||xleroy||Resolution||open => suspended|
|2012-02-05 11:33||lefessan||Note Added: 0006882|
|2012-02-05 16:14||gasche||Note Added: 0006883|
|2012-02-05 18:41||xleroy||Note Added: 0006884|
|2012-02-05 18:50||lefessan||Note Added: 0006885|
|2012-02-05 18:52||lefessan||Note Added: 0006886|
|2012-02-05 19:12||lefessan||Note Added: 0006887|
|2012-02-05 19:12||lefessan||File Added: modrecBench.ml|
|2012-04-04 16:23||Julien Signoles||Note Added: 0007276|
|2012-04-04 16:43||lefessan||Note Added: 0007277|
|2012-04-04 17:25||gasche||Note Added: 0007278|
|2012-04-05 06:00||gasche||Note Edited: 0006885||View Revisions|
|Copyright © 2000 - 2011 MantisBT Group|