Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > while/break - The pure-python FSM implementation to Rule Them All.

Reply
Thread Tools

while/break - The pure-python FSM implementation to Rule Them All.

 
 
Carl Cerecke
Guest
Posts: n/a
 
      01-25-2006
Well, it doesn't quite rule them all, but it is fast: About three times
faster than using one function per state. Faster than using generators.
Faster than using code objects.

Some, possibly minor, problems:
1. The generated code is ugly.
2. The generated code can be quite large, depending on the shape of the
FSM (Maximum theoretical size left as an exercise for the reader
3. Not as fast as byte code hacks, or using pyrex/psyco. Peter Hansen is
right. One of those is likely a better solution if you don't need pure
python.

The example FSM has input alphabet ['a','b','c']
and looks like:
state 0:
a -> 1
b -> 2
c -> 1

state 1:
a -> 1
b -> 3
c -> 2

state 2:
a -> 1
b -> 2
c -> 3

state 3:
a -> 2
b -> 3
c -> 0

The algorithm basically transforms the FSM into a tree of while loops,
with breaks letting us go back up the tree, and a variable ("goto"!)
telling us where the chain of breaks should stop.

Note:
1. It would be more efficient with a labelled break (or a labelled
continue) such as is available in Java.
2. There are some opportunities for optimisation of the generated code.

Running this code will print out the generated FSM code for both a
while/break implementation of the FSM and a function-based
implementation. It then does some timing measurements.

Cheers,
Carl.

#!/usr/bin/env python

from StringIO import StringIO

# number of random inputs fed to the FSM (if we are using that input
generator)
r = 1000000
#r = 10

# specific string of input chars (if we are using the appropriate input
generator)
inp = ['a','a','b','a','a','c','b','c','b','c','c','c','c ','c','b']

# list of states, each state is a dict describing transitions to other
states.
states = [
{'a':1,'b':2,'c':1},
{'a':1,'b':3,'c':2},
{'a':1,'b':2,'c':3},
{'a':2,'b':3,'c':0}]

ind = " "

class State(object):
def __init__(self, num):
self.num = num
self.gotos = {}

def show(self, indent = ""):
'''
Representaion of this state, and the states 'underneath' it
'''
print indent+`self.num`+':'
for i,g in self.gotos.items():
if type(g) == State:
print indent+"-"+i+"->"
g.show(indent+" ")
else:
print indent+"-"+i+"-> "+`g`

def code(self, out, lvl):
'''
Spit out code for a while/break based state machine
'''
print >>out,lvl+"while 1: # state",self.num
print >>out,lvl+ind+"#print '%d'"%self.num
print >>out,lvl+ind+"n = next()"
for i,g in self.gotos.items():
print >>out,lvl+ind+"if n == '"+i+"':"
if type(g) == State:
g.code(out,lvl+ind+ind)
else:
if g != self.num:
print >>out,lvl+ind+ind+"goto = "+`g`
print >>out,lvl+ind+ind+"break"
else:
print >>out,lvl+ind+ind+"continue"
print >>out,lvl+ind+"if n == None: return",self.num
print >>out,lvl+ind+"if goto != "+`self.num`+":"
print >>out,lvl+ind+ind+"break"

def functions(out,states, lvl = ""):
'''
Spit out code for a function-based state machine
'''
for num,transitions in enumerate(states):
print >>out,lvl+"def state_"+`num`+"():"
print >>out,lvl+ind+"#print '%d'"%num
print >>out,lvl+ind+"n = next()"
for i,g in transitions.items():
print >>out,lvl+ind+"if n == '"+i+"':"
print >>out,lvl+ind+ind+"return state_"+`g`
print >>out,lvl+ind+"if n == None: return None"


start = State(0)

# set up the hierarchy of State objects
def dfs(state, history):
for i,s in states[state.num].items():
if s in history:
state.gotos[i] = s
else:
child = State(s)
state.gotos[i] = child
dfs(child, history+[s])

dfs(start,[start.num])

#print start
#start.show()
fun = StringIO()
print >>fun,"def fsm():"
start.code(fun," ")
functions(fun,states)
def next_gen(): # for when we want specific input
for i in inp:
print i
yield i
yield None

import random
def next_genr(): # for when we want lots of input
for i in range(r):
n = random.choice(['a','b','c'])
#print n
yield n
yield None

next = next_genr().next

# show the generated code of both FSM implementations
print fun.getvalue()

exec fun.getvalue()
import time

# we want to ignore the cost of getting input, so we measure that first.
a = time.clock()
n = 1
while n:
n = next()
z = time.clock()
in_time = z-a
print "input time:",in_time


print "--"
next = next_genr().next
a = time.clock()
f = fsm()
z = time.clock()
print "while/break:",z-a-in_time

next = next_genr().next
a = time.clock()
state = state_0
while state:
state = state()
z = time.clock()
print "functions:",z-a-in_time
 
Reply With Quote
 
 
 
 
Paul Rubin
Guest
Posts: n/a
 
      01-25-2006
Carl Cerecke <(E-Mail Removed)> writes:
> 3. Not as fast as byte code hacks, or using pyrex/psyco. Peter Hansen
> is right. One of those is likely a better solution if you don't need
> pure python.


If you don't need pure python than your approach still beats
everything else. Just generate C code (or assembly code) instead of
Python.
 
Reply With Quote
 
 
 
 
Carl Cerecke
Guest
Posts: n/a
 
      01-25-2006
Paul Rubin wrote:
> Carl Cerecke <(E-Mail Removed)> writes:
>
>>3. Not as fast as byte code hacks, or using pyrex/psyco. Peter Hansen
>>is right. One of those is likely a better solution if you don't need
>>pure python.

>
>
> If you don't need pure python than your approach still beats
> everything else. Just generate C code (or assembly code) instead of
> Python.


If you are generating C code, then you can, instead, use the much
maligned goto to jump directly between states. All this
while/break/continue hackery is just to emulate the humble goto.

Using gotos is probably about as fast as you can get.

Cheers,
Carl.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
New implementation of FSM using functions returning pointers tofunctions of the same type! Eric des Courtis C Programming 10 03-11-2008 01:40 PM
how to add validation rule for url in the validation-rule.xml ,I added some thing like this but......... shailajabtech@gmail.com Java 0 10-12-2006 08:36 AM
Nested FSM implementation Polomora C Programming 6 09-09-2006 02:34 AM
One combo DVD player to rule them all. Allan DVD Video 0 01-15-2006 09:11 PM
FSM implementation WittyGuy C++ 3 08-04-2005 10:23 AM



Advertisments