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.

Sign up for GitHub

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

Jump to bottom

[BUG] Don't rely on browsers to implement tail-call optimizations / have large stacks #1530

Closed
JasonGross opened this issue Nov 19, 2023 · 6 comments
Closed

[BUG] Don't rely on browsers to implement tail-call optimizations / have large stacks #1530

JasonGross opened this issue Nov 19, 2023 · 6 comments
Labels
bug

Comments

@JasonGross
Copy link

Describe the bug
This js_of_ocaml output fails on Chrome and Firefox with a "too much recursion" or "maximum call stack size exceeded", but (I believe) works fine on Safari which implements tail-call optimization (or provides a larger stack).

Here's a self-contained version of the webpage and the OCaml source file:
fiat-html.tar.gz
Working on autodeployment at mit-plv/fiat-crypto#1737, so you can see the build on CI there.
Warning: it takes about 30 seconds to compile the bytecode (-package js_of_ocaml -package unix -w -20 -g -linkpkg), and about 10 minutes to run js_of_ocaml (with --source-map --no-inline; about twice that without any arguments).

Expected behavior
It should be possible to instruct js_of_ocaml to produce javascript that uses less stack.

Versions
Version of packages used to reproduce the bug

$ ocamlc -v
The OCaml compiler, version 4.14.1
Standard library directory: /home/jgross/.opam/4.14.1+fp/lib/ocaml
$ js_of_ocaml --version
5.4.0
@JasonGross JasonGross added the bug label Nov 19, 2023
@hhugo
Copy link
Member

hhugo commented Nov 19, 2023

To give a bit more context to other readers, the code mentioned here consist of a generated file (using coq) of over a million lines (74Mb).

The following actions should be able to fix your issue:

  • You can fix the compilation time by passing --disable compact.
  • You can fix the stack overflow by using --enable effects.

@JasonGross
Copy link
Author

Ah, neat, somehow I missed --enable=effects, this is exactly what I was looking for, thanks! (The naming seems a bit strange though.)

Is --disable compact documented?

JasonGross added a commit to JasonGross/fiat-crypto that referenced this issue Nov 19, 2023
@JasonGross
js_of_ocaml --enable=effects
bfd7cb6 
As per https://ocsigen.org/js_of_ocaml/latest/manual/tailcall and ocsigen/js_of_ocaml#1530 (comment)
@hhugo
Copy link
Member

hhugo commented Nov 19, 2023

Ah, neat, somehow I missed --enable=effects, this is exactly what I was looking for, thanks! (The naming seems a bit strange though.)

The naming is a bit strange because the it is supposed to be used when using ocaml 5 effects only. We should probably advertise it in other cases and rename it.

Is --disable compact documented?

I don't think and I suspect end-user should not use it. I'll file a bug-report to track the quadratic behavior.

@hhugo hhugo mentioned this issue Nov 19, 2023
Closed
@JasonGross
Copy link
Author

Is this also related to having a heavy memory footprint? I'm seeing ~4.4GB RAM (real: 190.10, user: 185.48, sys: 3.84, mem: 4476016 kb) even with --disable compact. (Also is --disable compact supposed to significantly increase .js file size? I'm seeing 13MB with --disable compact or 9.3MB without, which I guess is somewhat bigger but is not really much compared to the 79MB .map file or the 74MB source file.)

JasonGross added a commit to JasonGross/fiat-crypto that referenced this issue Nov 19, 2023
@JasonGross
Add js_of_ocaml build and deployment
0f1088d 
We `--enable=effects` as per
https://ocsigen.org/js_of_ocaml/latest/manual/tailcall and
ocsigen/js_of_ocaml#1530 (comment)

Some comparison of different arguments we could pass:
```
''
(real: 1247.15, user: 1237.92, sys: 8.82, mem: 3524544 ko)
--pretty --no-inline --debug-info --source-map
(real: 554.62, user: 545.29, sys: 9.31, mem: 4551068 ko)
--source-map --no-inline
(real: 431.91, user: 428.62, sys: 3.26, mem: 4588916 ko)
--source-map
(real: 599.19, user: 597.36, sys: 1.82, mem: 4528112 ko)
```

```
     Time |   Peak Mem | File Name
---------------------------------------------------------------------------
29m31.04s | 4582528 ko | Total Time / Peak Mem
---------------------------------------------------------------------------
10m11.06s | 4187496 ko | ExtractionJsOfOCaml/fiat_crypto.js
 7m04.23s | 4582528 ko | ExtractionJsOfOCaml/bedrock2_fiat_crypto.js
 7m03.61s | 4553728 ko | ExtractionJsOfOCaml/with_bedrock2_fiat_crypto.js
 1m23.70s | 2376368 ko | ExtractionJsOfOCaml/with_bedrock2_fiat_crypto.ml
 1m02.46s | 2376740 ko | ExtractionJsOfOCaml/bedrock2_fiat_crypto.ml
 0m58.92s | 2324704 ko | ExtractionJsOfOCaml/fiat_crypto.ml
 0m36.52s | 2840248 ko | ExtractionJsOfOCaml/with_bedrock2_fiat_crypto.byte
 0m30.87s | 2893620 ko | ExtractionJsOfOCaml/fiat_crypto.byte
 0m30.58s | 2839784 ko | ExtractionJsOfOCaml/bedrock2_fiat_crypto.byte
 0m02.66s | 1047220 ko | Bedrock/Standalone/StandaloneJsOfOCamlMain.vo
 0m02.52s | 1014884 ko | StandaloneMonadicUtils.vo
 0m02.30s | 1017460 ko | StandaloneJsOfOCamlMain.vo
 0m00.61s |  103496 ko | ExtractionJsOfOCaml/with_bedrock2_fiat_crypto.cmi
 0m00.51s |  103272 ko | ExtractionJsOfOCaml/bedrock2_fiat_crypto.cmi
 0m00.50s |  100760 ko | ExtractionJsOfOCaml/fiat_crypto.cmi
 ```
JasonGross added a commit to mit-plv/fiat-crypto that referenced this issue Nov 19, 2023
@JasonGross
Add js_of_ocaml build and deployment (#1737)
4915831 
Add js_of_ocaml build and deployment

js_of_ocaml --enable=effects as per https://ocsigen.org/js_of_ocaml/latest/manual/tailcall and ocsigen/js_of_ocaml#1530 (comment)

Some comparison of different arguments we could pass:
```
''
(real: 1247.15, user: 1237.92, sys: 8.82, mem: 3524544 ko)
--pretty --no-inline --debug-info --source-map
(real: 554.62, user: 545.29, sys: 9.31, mem: 4551068 ko)
--source-map --no-inline
(real: 431.91, user: 428.62, sys: 3.26, mem: 4588916 ko)
--source-map
(real: 599.19, user: 597.36, sys: 1.82, mem: 4528112 ko)
```

```
     Time |   Peak Mem | File Name
---------------------------------------------------------------------------
29m31.04s | 4582528 ko | Total Time / Peak Mem
---------------------------------------------------------------------------
10m11.06s | 4187496 ko | ExtractionJsOfOCaml/fiat_crypto.js
 7m04.23s | 4582528 ko | ExtractionJsOfOCaml/bedrock2_fiat_crypto.js
 7m03.61s | 4553728 ko | ExtractionJsOfOCaml/with_bedrock2_fiat_crypto.js
 1m23.70s | 2376368 ko | ExtractionJsOfOCaml/with_bedrock2_fiat_crypto.ml
 1m02.46s | 2376740 ko | ExtractionJsOfOCaml/bedrock2_fiat_crypto.ml
 0m58.92s | 2324704 ko | ExtractionJsOfOCaml/fiat_crypto.ml
 0m36.52s | 2840248 ko | ExtractionJsOfOCaml/with_bedrock2_fiat_crypto.byte
 0m30.87s | 2893620 ko | ExtractionJsOfOCaml/fiat_crypto.byte
 0m30.58s | 2839784 ko | ExtractionJsOfOCaml/bedrock2_fiat_crypto.byte
 0m02.66s | 1047220 ko | Bedrock/Standalone/StandaloneJsOfOCamlMain.vo
 0m02.52s | 1014884 ko | StandaloneMonadicUtils.vo
 0m02.30s | 1017460 ko | StandaloneJsOfOCamlMain.vo
 0m00.61s |  103496 ko | ExtractionJsOfOCaml/with_bedrock2_fiat_crypto.cmi
 0m00.51s |  103272 ko | ExtractionJsOfOCaml/bedrock2_fiat_crypto.cmi
 0m00.50s |  100760 ko | ExtractionJsOfOCaml/fiat_crypto.cmi
 ```
@OlivierNicole
Copy link
Contributor

Ah, neat, somehow I missed --enable=effects, this is exactly what I was looking for, thanks! (The naming seems a bit strange though.)

For the record, it fixes stack overflows because it installs a trampoline, which is a mechanism that clears the call stack every time it grows beyond a fixed threshold.

@JasonGross JasonGross mentioned this issue Nov 21, 2023
Open
@hhugo hhugo mentioned this issue Feb 21, 2024
Merged
@hhugo
Copy link
Member

hhugo commented Feb 23, 2024

I've pushed a change on master. You hopefully won't need --disable compact anymore (with the master branch).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@JasonGross @hhugo @OlivierNicole