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

Stack overflow in compiler #5925

Closed
vicuna opened this Issue Feb 18, 2013 · 6 comments

Comments

Projects
None yet
2 participants
@vicuna
Copy link
Collaborator

vicuna commented Feb 18, 2013

Original bug ID: 5925
Reporter: smimram
Assigned to: @gasche
Status: resolved (set by @gasche on 2013-02-18T10:31:10Z)
Resolution: suspended
Priority: normal
Severity: crash
Platform: amd64
OS: Linux
OS Version: 3.2.0
Version: 4.00.1
Category: ~DO NOT USE (was: OCaml general)
Related to: #4405 #5626 #5844 #5920 #6364
Monitored by: "Richard Jones" smimram

Bug description

Compiling the attached file with ocamlopt or ocamlopt.opt results in

Fatal error: exception Stack_overflow

Obviously this code was generated... It is not incredibly long (less than 4000 lines), but contains quite large expressions. Excepting by removing a few random lines, all my attempts to get a significantly simpler example have failed, sorry.

File attachments

@vicuna

This comment has been minimized.

Copy link
Collaborator Author

vicuna commented Feb 18, 2013

Comment author: @gasche

This is an instance of the well-known issue of "compiler code not being tail-recursive". Marking "resolved > suspended" as this is extremely low-priority. The advice for now is to fix code generators to avoid too deep nestings, or contribute patches that solve the issue without degrading code readability (not necessarily easy).

@vicuna vicuna closed this Feb 18, 2013

@vicuna

This comment has been minimized.

Copy link
Collaborator Author

vicuna commented Feb 22, 2013

Comment author: bvaugon

To solve your compilation problems, I wrote two patches on OCaml 4.00.1 distribution:

  • long-bytecode.diff: it makes possible to compile programs like yours in bytecode on 32 bits architectures (without Invalid_argument("String.create")). It uses string arrays instead of strings to store bytecode at compile time and link time.
  • tailrec-asmcomp.diff: it makes possible to compile programs like yours in native code (without StackOverflow). It is just a tail recursive version of the ocamlopt assembler generator using continuation passing style. The source code size and readability are not very degradated, and compilation performances seems to be similar.
@vicuna

This comment has been minimized.

Copy link
Collaborator Author

vicuna commented Feb 28, 2013

Comment author: smimram

Hi,

Would it be possible to reopen this bug so that Benoit's patches are reviewed (and hopefully integrated)? It is quite important, when developping a library, to know that OCaml can reliably used as a target language and that the work won't have to be done again in C (or some other language whose compiler does not have stack overflows)...

Thanks!

@vicuna

This comment has been minimized.

Copy link
Collaborator Author

vicuna commented Feb 28, 2013

Comment author: @gasche

I had a look at Benoît's patches, but thanks for the ping, I had forgotten to add some feedback here.

The long-bytecode patch is short and self-contained. I'm wondering what the performance implications of such a change are (my first reaction was: if it's so simple, why don't we define strings in this way in the standard library?). Besides this unknown (Benoît, if you have data on this, do not hesitate to share), it suffers from the problem of only making sense on 32 bits architecture, which makes it quite hard to convince maintainers that it's worth the (even small) increase in code size.

The other patch is a typical example of the easy and boring transformation that does hurt readability, and is also relatively invasive. My strictly personal dream is that, someday, we have a reliable monadic notation for OCaml (or a syntax extension mechanism for that that I could use on the compiler itself without getting killed), and that would make the CPS version readable and reasonable to use. It's not the case for now.

I'm keeping the bug "resolved > suspended" (means: meh, we probably won't do anything) for now. It's good that the patches are here so that users that really need them can consider using them, but I would still advise you to fix the code generator for now. Sorry.

@vicuna

This comment has been minimized.

Copy link
Collaborator Author

vicuna commented Mar 1, 2013

Comment author: smimram

Thanks for your answer! I personally find the CPS quite readable, but I guess there is very little I can argue about style...

@vicuna

This comment has been minimized.

Copy link
Collaborator Author

vicuna commented Apr 17, 2013

Comment author: @gasche

Small update: with help/review from chetsky in #5957, I commited the long-bytecode patch. This unfortunately will not alone resolve the issue at hand, but may help with similar code-generation settings -- and affected human users as well.

Thanks, Benoît, for your patch!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.