0005500: compilation of "module rec" makes runtime assumptions on closure representation

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

Relationships