From: Robert Feldt <feldt@...>
Date: 2001-11-22T20:22:13+09:00
Subject: [ruby-talk:26130] Community spike: Fast-state-machines/goto challenge

Hi,
 
I'm contemplating the fastest way to implement state-machines and
goto-like structures in Ruby. Don't worry, it's not that I'm reverting to
some old programming style; the code will be auto-generated. However,
there is a performance consideration so I'd like to generate as fast code 
as possible.
 
What's your best ideas for how to implement this? Start brainstorming; 
when/if we get a fairly complete list I'll benchmark the ideas and come 
back with the figures. Or you can write code yourself. This can be fun!

To be concrete we'll consider the code below a simple "testcase". Note
that your idea/code will be tested on other state machines as well so it
will not be ok to simply pass the tests below!

So the requirements for an idea/solution (in order of importance):
 * Should be as fast as possible when running the state machine (time to 
   create/init the machine is not important)
 * Should be general enough to handle "most" state machines that can be
   specified with the interface below. I say "most" since it might be ok
   to limit to some subclass if performance is better.
 * Should pass the tests below.

Try to think out of the box! I haven't even said it must be pure Ruby
and there might be other "holes" to exploit. Please do so... ;-)

Would be fun if someone takes this on. Even if writing code is too much
time please send your ideas. I'd like to get a full view of the
possibilities. And in the end the best ideas will lead to faster code
for some Ruby extensions.

Regards,

Robert



require 'runit/testcase'
require 'runit/testsuite'
require 'runit/cui/testrunner'

class SmgChallengeTest < RUNIT::TestCase
  def initialize
    @cls = !!YourClass!!   # Insert your class here...  
  end

  def setup
    # Arguments is
    #  Start state and transition table
    # where the latter is an Array of sub-arrays, one for each state.
    # Sub-arrays have the state and a hash mapping input symbols to the
    # state to transition to.
    @sm = @cls.new(0, # Start state
                   [[0, {10 => 1, 7 => 2}],
                    [1, {10 => 1, 7 => 2, 3 => 4}],
                    [2, {[3, 7] => 4, 2 => 0}],
                    [4]])
  end
		   
  def test_01_initialize
    assert_kind_of(@cls, @sm)
    assert_equals([0,1,2,4], @sm.states.sort)
    assert_equals(0, @sm.state) 
  end

  def test_02_run
    @sm.run([10])
    assert_equals(1, @sm.state)
    @sm.run([10])
    assert_equals(1, @sm.state)
    @sm.run([7])
    assert_equals(2, @sm.state)   
    @sm.run([7])
    assert_equals(4, @sm.state)   
  end

  def test_03_run_longer
    n = 1000
    @sm.run(([10] * n) + ([7,2] * n) + ([10,7,2] * n) + [7,3])
    assert_equals(4, @sm.state)
  end
end

RUNIT::CUI::TestRunner.new.run(SmgChallengeTest.suite) if $0 == __FILE__