Catching stackoverflow error in recursive function

General Usage
1

Given the fact that

A=Any[]
push!(A,A)
hash(A)
ERROR: StackOverflowError:

I thought it a nice exercise to try to handle recursive data structures. Since most use-cases are not recursive, let’s try to do this with an exception (try-catch should be cheap, right?). First, can I catch StackOverflow?

function recurse_(n) 
    try
        return recurse_(n+1)
   catch x
        return x
   end
end
dump(recurse_(0))
StackOverflowError StackOverflowError()

Ok, nice. Unfortunately, rethrowing is not help-full; I need to investigate the stacktrace in order to see how far to unwind. For a little debug purpose:

function recurse2_(n) 
    try
        return recurse2_(n+1)
   catch x
        println(n)
        return x
   end
end
recurse2_(0)
Segmentation fault (core dumped)

Hmm, not sure that I intended that (what I did hope for is that the innermost println throws again, I go up in the stack until the println succeeds and afterwards I return normally – and this was supposed to work regardless how deep println goes— the printed n should be recursion depth minus stack space needed for println).

So examining the stacktrace is probably impossible if I am sitting at the bottom of the recursion limit?

Is there a reasonable try-catch construction for “unwind until the topmost occurence of this instruction pointer, skipping catch handlers in between”? Is there a reasonable way of seeing exception handlers above me in the stack, if I had a stacktrace/backtrace and was not at the limit?

(sorry for the possible notational confusion; for the purposes of this post, the stack grows from top to bottom, intel-style)

2

try-catch is not super cheap (at the very least it needs to do a full register-state dump - more than 4K of memory on recent intel chips). There’s ways to optimize it, but we don’t do that at the moment. Unwinding is also supremely expensive at the moment (esp on Windows).

Throwing StackOverflowError is mostly best effort at the moment. We need to make use of probe stack support in LLVM do make it reliable. Catching StackOverFlowError (at any place other than the toplevel to display the error) is a different matter entirely and not really something that the system is equipped to handle at this point.

3

I expected that the throw() and the actual catch() is expensive; but, if no actual exception happens it is basically free, right?

I see; thanks!

4

No, we use a fairly simple setjmp/jongjmp based exception system, so there’s overhead to entering an exception frame. We could eventually switch to a fancier exception system, but it hasn’t been a priority and would require accurate unwinding, which isn’t always possible since some C libraries have broken unwind info. There’s the hybrid approach where we setjmp/jongjmp over stack frames of known-usafe C libraries, but all of that is quite a bit of engineering effort.

1 Like
5

It’s bad but not THAT bad. Only the callee saved ones needs to be saved.

6

Ah, fair enough ;). My memory was of the state capture routines in the debugger which actually do need to capture the full state, since they can be at arbitrary points.

7

Yes, throw is cheaper than rr replay ;-p

8

and the actual size we use is 256 bytes on x64. Still pretty bad of course, but it’s 1/4K rather than 4K…