Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0005500OCamlOCaml backend (code generation)public2012-02-05 07:492012-04-04 17:25
Reporterlefessan 
Assigned To 
PrioritynormalSeverityminorReproducibilityhave not tried
StatusresolvedResolutionsuspended 
PlatformOSOS Version
Product Version3.12.1 
Target VersionFixed in Version 
Summary0005500: compilation of "module rec" makes runtime assumptions on closure representation
DescriptionWhen 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.
TagsNo tags attached.
Attached Filespatch file icon ocaml-module-rec-2012-02-05v2.patch [^] (6,550 bytes) 2012-02-05 07:49 [Show Content]
? file icon modrecBench.ml [^] (1,222 bytes) 2012-02-05 19:12 [Show Content]

- Relationships

-  Notes
(0006880)
xleroy (administrator)
2012-02-05 11:20

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?
(0006882)
lefessan (developer)
2012-02-05 11:33

I think js_of_ocaml uses Javascript closures to represent OCaml closures. Maybe Javascript has a way to access and modify its own closures, but it would really surprise me (that's the kind of things you don't want to expose to programmers, especially on the web).

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.
(0006883)
gasche (developer)
2012-02-05 16:14

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.
(0006884)
xleroy (administrator)
2012-02-05 18:41

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.
(0006885)
lefessan (developer)
2012-02-05 18:50
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:

Salut Fabrice,

> > 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
js_of_ocaml ce sont des fonctions Javascript.

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. :-)

-- Jerome



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
> by javascript functions.
>
> 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
> update/copying, and we can provide an alternative javascript implementation.
>
> It would be nice if your patch were accepted :-)
>
> Jérôme

(0006886)
lefessan (developer)
2012-02-05 18:52

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.
(0006887)
lefessan (developer)
2012-02-05 19:12

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.
(0007276)
Julien Signoles (reporter)
2012-04-04 16:23

only 25% slower? That is huge!
(0007277)
lefessan (developer)
2012-04-04 16:43

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... ;-) )
(0007278)
gasche (developer)
2012-04-04 17:25

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.

- Issue History
Date Modified Username Field Change
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
Powered by Mantis Bugtracker