Ruby 1.9.2-p-180 failing with 'illegal instruction' or 'stack level too deep (SystemStackError)'

Question

The behavior: Ruby 1.9.2p180 fails with 'Illegal Instruction' and no other details. Ruby 1.9.1p378 runs with no problems at all.

The failure happens in the line pin = fronto.index(k), on only some iterations.

from and into are both arrays of objects, by is an attribute (either x or y) of that object.

The code:

  def add_from_to_by from, into, by
    nto = into.sort_by{|k| k.send(by)}
    fronto = (from + nto).sort_by{|k| k.send(by)}
    dict = {}
    nto.each{|k| dict[k] = []}
    nto.each do |k|
      pin = fronto.index(k)
      up = pin+1
      down = pin-1
      while up < fronto.length and ((fronto[pin].send(by)) - (fronto[up].send(by))).abs <= $sensor_range
        if fronto[up].kind_of?(BasicNode) then 
          dict[k].push(fronto[up]) 
        end
        up += 1
      end
      while down >= 0 and ((fronto[pin].send(by)) - (fronto[down].send(by))).abs <= $sensor_range
        if fronto[down].kind_of?(BasicNode)
          dict[k].push(fronto[down])
        end
        down -= 1
      end
    end
    return dict
  end 

I'm using rvm to manage ruby versions on Mac 10.6.6. Any idea why this is happening?

REVISION:

If the code above is reduced to this:

def add_from_to_by from, into, by
        nto = into.sort_by{|k| k.send(by)}
        fronto = (from + nto).sort_by{|k| k.send(by)}
        dict = {}
        nto.each{|k| dict[k] = []}
        x = nto.select{|k| !fronto.include?(k)}
end

This reproduces the bug on the last line. In the input that crashes, into and from are disjoint sets of points. A class definition that should work is:

class BasicNode
    attr_reader :x, :y
    def initialize x, y
        @x = x
        @y = y
    end
end

where x and y are numbers. In the test that crashes there are 15 nodes in into and 5 nodes in from.

EDIT:

I do get a stack level too deep (System Stack Error) when I isolate the code somewhat. However, I'm not sure why this should be, since there are no recursive calls in this code or in the C implementation for array index.

ADDENDUM: The complete source code for this question can be found here: http://code.google.com/p/graphcomplexity/

repository: rvertex branch: default test file: test/test_deeps_hypersim.rb

Answer 1

using 1.9.2-p180 on linux, I haven't been able to reproduce your problem. here's my test setup:

$sensor_range=5
list1=Array.new(1000) {|i| BasicNode.new(rand(100),rand(100))}
list2=Array.new(1000) {|i| BasicNode.new(rand(100),rand(100))}
res=add_from_to_by(list1,list2,:x);

does your bug still occur with that set of instructions? If you're still getting the bug, but not with those instructions, could you provide some example data and function call that demonstrates the problem? (if it's huge, you can use a service like pastebin.com)

---

also, I'm not 100% sure if it's exactly the same, but this might be a more straightforward way to write the same function (your program might be easier to debug with simpler code):

def add_from_to_modified(from,into,sensor_range,&block)
  into.inject({}) do |result,key|
    result.merge({key=>(into+from).select {|check| (yield(check)-yield(key)).abs <= sensor_range}})
  end
end

add_from_to_modified(list1,list2,5,&:x)

it can be rewritten with the yield()s outside of the loop if that's too inefficient. this implementation also lets you pass an arbitrary block instead of just a function to call

add_from_to_modified(list1,list2,5) {|node| node.x*3-node.y}