1

I'm generating a list of random numbers:

let gen n =
    let rec pom l n =
        match n with
        | 0 -> l
        | _ ->
            let el = Random.int 20000000
            in pom (el::l) (n-1)
    in
        pom [] n

let lo = gen 1000000

What I get is 

Fatal error: exception Stack_overflow

Why? I'm using tail recursion (and an accumulator)

EDIT:

You're right, the stack overflows on both sorts.

But if my code had a zillion lines, it would be a pain to debug it this way. I'd like to use ocamldebug here, just as a learning experience. I ran ocamldebug this way:

(ocd) r
Loading program... done.
Time: 88089944
Program end.
Uncaught exception: Stack_overflow
(ocd) b
Time: 88089943 - pc: 52 - module Pervasives
214   | hd :: tl -> <|b|>hd :: (tl @ l2)
(ocd) bt
#0  Pc: 52  Pervasives char 7700
#1  Pc: 64  Pervasives char 7715
#2  Pc: 64  Pervasives char 7715
#3  Pc: 64  Pervasives char 7715
#4  Pc: 64  Pervasives char 7715
#5  Pc: 64  Pervasives char 7715
#6  Pc: 64  Pervasives char 7715
// and so it goes on forever

This tells me nothing why my program has crashed. How could I debug it with ocamldebug?

(meta: should I post a separate thread for it or should I stay here)

Improve this question
6
  • which configuration are you using ? (on T40 , 1GB, Ubuntu 12.0x -utop version 1.18.1 (using OCaml version 4.02.1); no issue, even 10 more, let lo = gen 10000000;;). Commented Nov 21, 2015 at 18:40
  • Asus R556LB, 8G RAM, Mint 17.2 Cnnamon, OCaml 4.01 Commented Nov 21, 2015 at 19:58
  • I have a Stack overflow not in gen but in quick_sort. Commented Nov 22, 2015 at 0:54
  • How do you perform quicksort on List ? (normally quicksort rely on mutable array). Or are you using List.sort (fun x y -> compare x y) ? This later works fine on my pc. Commented Nov 22, 2015 at 7:38
  • I implemented my own sorts and use List.sort for correctness check Commented Nov 22, 2015 at 7:40

3 Answers 3

Reset to default
2

Since the error was in a different function, here is how you can debug this kind of thing quicker in the future.

  1. You can turn on backtraces. Either call Printexc.record_backtrace true at the beginning of your program, or run it with the environment variable OCAMLRUNPARAM set to b, as in OCAMLRUNPARAM=b ./a.out. This should tell you where the error occurred, although sometimes it skips parts of what you would expect to be the call stack – I believe this is due to optimizations such as inlining. It is generally useful, though. For this, the program must have been compiled with the flag -g.

  2. You can still find the source of the exception, even in a bunch of function calls as in your program, by doing a binary search. First wrap half the function calls in a handler. If the exception occurs there, unwrap those, then wrap half of them in a handler again, and so on, until you drill down to the source. It is still somewhat labor intensive, but you can debug this way in O(log n) time, and the log of a zillion is not that much :)

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Note that @ivg has a much more definitive answer from a similar starting point to this one. Please see it instead if you intend to use backtraces to debug this.
1

Printing a backtrace of Stack_overflow exception usually somewhat useless, because the number of calls that leads to the overflow exceeds the size of backtrace buffer. For example if you take the following program (backtrace.ml):

let init n =
  let rec loop xs x =
    if x >= 0 then loop (x::xs) (x-1) else xs in
  loop [] (n-1)

let sum = function
  | [] -> 0
  | x :: xs -> List.fold_right (+) xs x

let () =
  let xs = init 10000000 in
  let y = sum xs in
  print_int y

and execute it with

 OCAMLRUNPARAM=b ocamlbuild backtrace.d.byte --

you will get a useless backtrace of a form:

Fatal error: exception Stack_overflow
Raised by primitive operation at file "list.ml", line 89, characters 16-37
Called from file "list.ml", line 89, characters 16-37
Called from file "list.ml", line 89, characters 16-37
...

We can't increase the internal backtrace buffer, but we can decrease the stack size, thus limiting the size of backtrace, so it can fit into the buffer. So, if we run the program, within a limited stack, we will get a much better backtrace:

OCAMLRUNPARAM="b,l=100" ocamlbuild backtrace.d.byte --
Fatal error: exception Stack_overflow
Raised by primitive operation at file "list.ml", line 89, characters 16-37
Called from file "list.ml", line 89, characters 16-37
Called from file "list.ml", line 89, characters 16-37
...
Called from file "backtrace.ml", line 18, characters 10-16

Bingo. The source of a problem is pinpointed up to a callsite.

Note: the l option of OCAMLRUNPARAM is understood only by the bytecode runtime. In order to repeat the same trick for a native code, one should limit the stack using mechanisms provided by an operating system. For unices it is usually ulimit -s shell primitive.

Improve this answer

Comments

0

I ran your code on my Mac Pro and don't get a stack overflow. As you say your code looks perfectly fine.

Possible explanations:

  1. You're running in an environment with limited memory.

  2. You had some old definitions of parts of your code. Maybe try re-running in a new OCaml toplevel.

Update

I think @antron has an excellent point. If you're running compiled code you most likely don't know exactly where the problem is. Add some tracing and you will very likely find the stack overflow is elsewhere.

Improve this answer

3 Comments

I'm compiling my code with OCamlMakefile (ocamlc). The whole code is here: paste.ubuntu.com/13403578
Are you sure it isn't one of the other functions that is causing the stack overflow?
@JeffreyScofield to add to your edit, you may be able to pin it down by wrapping various function calls in exception handlers and seeing where you are able to catch the exception. It's like an analog to debugging with prints.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.