Friday, December 20, 2024

Getting deep recursion to work in a simple Ruby program

As part of one of my Advent of Code 2024 solutions, I wrote a small program that included a fairly deep level of recursion. 

When run on my Mac, using Ruby 2.7.2, the program failed to run to completion, generating a stack trace like this (shown in part for brevity):

Traceback (most recent call last):
    3304: from day-16/day-16-part-1-dfs.rb:125:in `<main>'
    3303: from day-16/day-16-part-1-dfs.rb:86:in `explore_map'
    3302: from day-16/day-16-part-1-dfs.rb:86:in `each'
    3301: from day-16/day-16-part-1-dfs.rb:96:in `block in explore_map'
    3300: from day-16/day-16-part-1-dfs.rb:86:in `explore_map'
     ... 3292 levels...
day-16/day-16-part-1-dfs.rb:87:in `key?': stack level too deep (SystemStackError)

I could have fixed this by rewriting my recursive function to use a queue instead, but I wanted to see if I could change my runtime configuration to get my program to run as-is; and I was able to do so! I ended up needing to change TWO things to get the program to run successfully.

First, I needed to increase the system stack size limit for my Mac, for the current terminal session. For my particular program, I needed to set it near my machine's max:

ulimit -s 65520

(The default stack size limit had been 8176.)

Making just that change allowed my program (when run from that terminal session -- not from my IDE) to reach a deeper count of recursions; but it still failed with a similar error:

Traceback (most recent call last):
    10920: from day-16/day-16-part-1-dfs.rb:125:in `<main>'
    10919: from day-16/day-16-part-1-dfs.rb:86:in `explore_map'
    10918: from day-16/day-16-part-1-dfs.rb:86:in `each'
    10917: from day-16/day-16-part-1-dfs.rb:96:in `block in explore_map'
    10916: from day-16/day-16-part-1-dfs.rb:86:in `explore_map'
     ... 10908 levels...

day-16/day-16-part-1-dfs.rb:32:in `hash': stack level too deep (SystemStackError)

Second, I needed to set an environment variable to increase the Ruby VM's maximum allowed stack size. For this "toy" program, I just picked an arbitrary very large value:

export RUBY_THREAD_VM_STACK_SIZE=50000000

With that change also in place, my program was able to successfully run to completion!

I did end up refactoring my solution from using a depth-first search to a breadth-first search, which, in addition to not needing to deal with Ruby's limit on recursion stack depth, was a lot more efficient for solving that particular problem.

I wanted to make a note on what I did, though, so that if I ever face a situation again where I'm bumping up against a Ruby stack depth limit (and a solution other than increasing the limit isn't called for), then I'll be able to remember what I did this last time!