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 ocamlopt.opt: Comballoc.combine #5626

Closed
vicuna opened this issue May 29, 2012 · 5 comments
Closed

Stack overflow in ocamlopt.opt: Comballoc.combine #5626

vicuna opened this issue May 29, 2012 · 5 comments

Comments

@vicuna
Copy link

vicuna commented May 29, 2012

Original bug ID: 5626
Reporter: Richard Jones
Status: resolved (set by @xavierleroy on 2013-07-19T09:19:57Z)
Resolution: suspended
Priority: low
Severity: minor
Version: 3.12.1
Category: back end (clambda to assembly)
Related to: #5844 #5925 #6364
Monitored by: @gasche smimram @alainfrisch

Bug description

If you have a file with a large number of lines:

let () = ...
let () = ...
let () = ...

then ocamlopt.opt will give a stack overflow trying to compile
it. The stack trace on ppc64 is:

#2222 0x00000000100372b4 in .camlComballoc__combine_restart_1107 ()
#2223 0x0000000010037740 in .camlComballoc__combine_1106 ()
#2224 0x00000000100376a4 in .camlComballoc__combine_1106 ()
#2225 0x00000000100376a4 in .camlComballoc__combine_1106 ()
#2226 0x00000000100376a4 in .camlComballoc__combine_1106 ()
#2227 0x00000000100376a4 in .camlComballoc__combine_1106 ()
#2228 0x00000000100376a4 in .camlComballoc__combine_1106 ()
#2229 0x00000000100376a4 in .camlComballoc__combine_1106 ()
#2230 0x00000000100376a4 in .camlComballoc__combine_1106 ()
#2231 0x00000000100376a4 in .camlComballoc__combine_1106 ()
#2232 0x00000000100376a4 in .camlComballoc__combine_1106 ()
#2233 0x00000000100372b4 in .camlComballoc__combine_restart_1107 ()

repeated for thousands of frames.

Steps to reproduce

On x86-64 you need to use a very large number of lines. The
following causes the stack overflow for me on x86-64 [note:
original problem manifested on ppc64]:

echo "let h = Hashtbl.create 0 let add = Hashtbl.add h" > test.ml
for f in seq 1 50000; do echo "let () = add "$f" "bar"" >> test.ml; done
echo "let () = Gc.compact ()" >> test.ml
ocamlopt.opt test.ml -o test

Additional information

The reproducer code looks strange, but this actually hit in
real code on ppc64 where the stack limits are much
smaller, so you get this with only about 5000 lines of
code (hand written, not generated!)

@vicuna
Copy link
Author

vicuna commented Jun 3, 2012

Comment author: @gasche

As a simple workaround, you can chunk your code in smaller functions.

Basically, ocamlopt works on functions one by one, and some compilation passes are not tail-recursive, but this is not an issue because they run at must on the inner code of a function, not on the whole program or even whole module.

But "let () = ..."-style toplevel expressions are collected in a single "entry point" function that is handled like all other user-defined function. In your example, there are too many of them, and you reach your stack limit.
By splitting these into smaller functions, you can avoid exhausting your stack. I tested for example with the following code adapted from yours, which packs your 50_000 phrases into 500 functions of 100 phrases each, and doesn't raise a Stack Overflow:

echo "let h = Hashtbl.create 0 let add = Hashtbl.add h" > test.ml

for f in seq 1 500
do
echo "let f () =" >> test.ml
for i in seq 1 100
do
echo "let () = add "$f$i" "bar" in" >> test.ml
done
echo "()" >> test.ml

  echo >> test.ml
  echo "let () = f ()" >> test.ml
  echo >> test.ml

done

echo "let () = Gc.compact ()" >> test.ml

Of course, this is only a workaround. A "better" solution would be to rewrite the involved functions to be tail-recursive, but that is a dubious enterprise: the different passes of the compiler are not tail-recursive, and what fails at the Comballoc step today may raise a Stack Overflow somewhere else tomorrow. Maintainers are not fond of chasing such changes through the compiler, when they degrade code readability (and performance) to fix problems that arise only in exceptional cases that can be relatively easily worked around.

@vicuna
Copy link
Author

vicuna commented Jun 3, 2012

Comment author: @gasche

(bug triaging hat on) I mark the bug "acknowledged" as the issue is real and easy to reproduce thanks to the reporter script, but my gut feeling is that this is too low-priority.
If no developer stands up with an opinion on this, I'll probably move it into the "resolved > suspended" realm at some point in the future.

@vicuna
Copy link
Author

vicuna commented Sep 21, 2012

Comment author: @damiendoligez

Setting to "confirmed" because I can reproduce the problem.
Setting the priority to "low" because this impacts so few users.
No idea whether we should spend time fixing this.

@vicuna
Copy link
Author

vicuna commented Feb 28, 2013

Comment author: smimram

A patch has been proposed in #5925

@vicuna
Copy link
Author

vicuna commented Jul 19, 2013

Comment author: @xavierleroy

I am marking this PR as "suspended" for the reasons given in #5925, namely: making the native-code generator tail-recursive is a very invasive change.

For hand-written code, gasche gave good advice on how to circumvent the issue.

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