Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

compilation of "module rec" makes runtime assumptions on closure representation #5500

Closed
vicuna opened this issue Feb 5, 2012 · 10 comments
Closed

Comments

@vicuna
Copy link

vicuna commented Feb 5, 2012

Original bug ID: 5500
Reporter: @lefessan
Status: resolved (set by @xavierleroy on 2012-02-05T10:20:49Z)
Resolution: suspended
Priority: normal
Severity: minor
Version: 3.12.1
Category: back end (clambda to assembly)
Monitored by: @gasche @glondu @jberdine "Julien Signoles" @alainfrisch

Bug 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.

File attachments

@vicuna
Copy link
Author

vicuna commented Feb 5, 2012

Comment author: @xavierleroy

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?

@vicuna vicuna closed this as completed Feb 5, 2012
@vicuna
Copy link
Author

vicuna commented Feb 5, 2012

Comment author: @lefessan

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.

@vicuna
Copy link
Author

vicuna commented Feb 5, 2012

Comment author: @gasche

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.

@vicuna
Copy link
Author

vicuna commented Feb 5, 2012

Comment author: @xavierleroy

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.

@vicuna
Copy link
Author

vicuna commented Feb 5, 2012

Comment author: @lefessan

[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

@vicuna
Copy link
Author

vicuna commented Feb 5, 2012

Comment author: @lefessan

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.

@vicuna
Copy link
Author

vicuna commented Feb 5, 2012

Comment author: @lefessan

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.

@vicuna
Copy link
Author

vicuna commented Apr 4, 2012

Comment author: Julien Signoles

only 25% slower? That is huge!

@vicuna
Copy link
Author

vicuna commented Apr 4, 2012

Comment author: @lefessan

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

@vicuna
Copy link
Author

vicuna commented Apr 4, 2012

Comment author: @gasche

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant