StackOverflowError vs ulimit -s

recri · July 20, 2020, 6:53pm

I am computing a recursive function which overflows the stack for some argument values. Somewhere I heard that julia on linux uses the system stack size as set by ulimit -s. So why do these two computations, one with ulimit -s of 8192 and the other with ulimit -s 64 times larger, both fail with StackOverflowError and the exact same stack trace?

rec@t490:~$ ulimit -s
8192
rec@t490:~$ julia
               _depth
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _  |  |
  | | |_| | | | (_| |  |  Version 1.4.2 (2020-05-23)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |

julia> include("julia/fuse.jl")
computem (generic function with 1 method)

julia> m(big"2.96678",true)
ERROR: StackOverflowError:
Stacktrace:
 [1] BigFloat(; precision::Int64) at ./mpfr.jl:112
 [2] BigFloat at ./mpfr.jl:112 [inlined]
 [3] -(::BigFloat) at ./mpfr.jl:575
 [4] m(::BigFloat, ::Bool) at /home/rec/julia/fuse.jl:7
 [5] m(::BigFloat, ::Bool) at /home/rec/julia/fuse.jl:10 (repeats 9 times)
 [6] m(::BigFloat, ::Bool) at /home/rec/julia/fuse.jl:9
 [7] m(::BigFloat, ::Bool) at /home/rec/julia/fuse.jl:10 (repeats 10818 times)
 [8] top-level scope at REPL[2]:1

julia> 
rec@t490:~$ ulimit -s $(expr 256 \* 1024)
rec@t490:~$ ulimit -s
262144
rec@t490:~$ julia
               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _  |  |
  | | |_| | | | (_| |  |  Version 1.4.2 (2020-05-23)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |

julia> include("julia/fuse.jl")
computem (generic function with 1 method)

julia> m(big"2.96678",true)
ERROR: StackOverflowError:
Stacktrace:
 [1] BigFloat(; precision::Int64) at ./mpfr.jl:112
 [2] BigFloat at ./mpfr.jl:112 [inlined]
 [3] -(::BigFloat) at ./mpfr.jl:575
 [4] m(::BigFloat, ::Bool) at /home/rec/julia/fuse.jl:7
 [5] m(::BigFloat, ::Bool) at /home/rec/julia/fuse.jl:10 (repeats 9 times)
 [6] m(::BigFloat, ::Bool) at /home/rec/julia/fuse.jl:9
 [7] m(::BigFloat, ::Bool) at /home/rec/julia/fuse.jl:10 (repeats 10818 times)
 [8] top-level scope at REPL[2]:1

julia>

Oscar_Smith · July 20, 2020, 7:24pm

Based on (repeats 10818 times) it looks like you probably have an infinite loop somewhere.

recri · July 20, 2020, 9:04pm

No loops, just recursion:

m(x) = x < 0 ? -x : m(x-m(x-1))/2

increasing the stack size with ulimit -s did not increase the depth of recursion reached when the stack overflowed.

recri · July 25, 2020, 2:38am

The solution is to use julia-1.5.0-rc1.

recri · July 25, 2020, 2:58pm

Oops, but only as a single threaded julia. If you start multiple threads they get 8Mbyte fixed stack segments. If you stay away from threads, then your julia will consume all the stack you can give it.

klaff · July 25, 2020, 3:27pm

Do you know why this is the solution?

recri · July 25, 2020, 6:23pm

Nope, just stumbling around in the dark here. But I do have 16 copies of julia-1.5.0 computing values on an EC2 instance right now, the deepest completed evaluation in the group so far is 1066022.

klaff · July 25, 2020, 8:20pm

Thank you, I was curious.

I’m no computer science expert, but I had reached the conclusion at some point (well before learning Julia) that recursion wasn’t a good idea if the number of recursions wasn’t bounded to be something reasonably small, and that if I felt I was headed in that direction, I should rewrite and make my own stacks as needed for the problem rather than relying on whatever happens under the covers of whatever language I was using.

However, I have not tried to learn about how Julia uses the stack.

recri · July 26, 2020, 12:08pm

That’s generally good advice. In this case the variation in recursive depth of the function is itself interesting, and rewriting to replace the recursion with a different form of evaluation appears to be unnecessary.

At this point I’m merely curious to know whether the current behavior is intended and likely to persist.

And wondering how this core war is going to turn out, each julia process is working on progressively deeper recursions.