Recursive methods crash in Fiber/Thread due to stack size #12

Closed
evnu opened this Issue Oct 25, 2012 · 3 comments

Projects

None yet

2 participants

@evnu
evnu commented Oct 25, 2012

RubyTree uses recursion for methods such as each and detached_subtree_copy. This is ok for smaller well-balanced trees, but fails for unbalanced trees when Fiber or Threads are involved.

Constructing and Walking a Linear Tree

See the following example method to construct a linear tree:

#!/usr/bin/ruby
require "tree"

def run_test(depth=100)
    tree = Tree::TreeNode.new("/")
    current = tree
    depth.times do |i|
        new_node = Tree::TreeNode.new("#{i}")
        current << new_node
        current = new_node
    end
    tree.each{|n| nil}
end

This runs fine when executed in the main thread...

puts "Run test in the main thread"
run_test()

...but fails when a Fiber or Thread is involved:

puts "Run test in a fiber"
begin
    Fiber.new do
        run_test()
    end.resume
rescue SystemStackError
    puts "Fiber died."
end

puts "Run test in a thread"
begin
    Thread.abort_on_exception = true
    Thread.new do
        run_test(600) # 600 is not chosen arbitrary: this is the first number where it fails here.
    end
    sleep(3)
rescue SystemStackError
    puts "Thread died."
end

Note that the recursion depth between Fiber and Thread differs.

Demo Output

The example script above produces the following output with my machine:

% ./example.rb
Run test in the main thread
Run test in a fiber
Fiber died.
Run test in a thread
Thread died.

Possible Solution

This should be resolvable by replacing the recursion in each, detached_subtree_copy and elsewhere with the respective iterative representation. each could possibly be fixed like this:

module Tree
    class TreeNode
        def each(&blk)
            expand_nodes = [self]
            while expand_nodes != []
                current = expand_nodes.shift
                yield current
                expand_nodes = current.children.concat(expand_nodes)
            end
        end
    end
@evolve75 evolve75 was assigned Oct 26, 2012
@evolve75
Owner

Magnus,

Thank you for highlighting this. I was actually planning to replace recursions at some point of time. I will review the issue and put in a few test cases to start with.

Just out of curiosity, would you be able to share the use case where you need this large volume of nodes?

Anupam

@evnu
evnu commented Oct 28, 2012

We are using rubytree to display different kinds of taxonomies. The graphs are built using user input and sometimes users create very long branches (probably by accident). We will eventually filter those branches, but for that we have to find them first. Note that the example above is quite artificial; if the node names are longer, it should crash with a smaller depth. We had one case where it crashed for a tree of depth 40.

@evolve75 evolve75 added a commit that referenced this issue Dec 28, 2013
@evolve75 Changed 'postordered_each' to use iteration.
This change fixes bug #12, where the recursion for deep trees was leading to out
of stack memory errors.
21dd1d8
@evolve75
Owner

Fix is working fine, and will be available in R0.9.0.

@evolve75 evolve75 closed this Dec 28, 2013
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment