fiber(cooperative multi-threading)

[Akihiro KAYAMA]

Hi all.

I found cooperative multi-threading(only one thread runs at once,
explicit thread switching) is useful for writing some simulators.
With it, I'm able to be free from annoying mutual exclusion, and make
results deterministic.

For this purpose, and inspired by Ruby(1.9) fiber, I wrote my own
version of fiber in Python.

It just works, but using native Python threads for non-preemptive
threading is not cost-effective. Python has generator instead but it
seemed to be very restricted for general scripting. I wish I could
write nested (generator) functions easily at least.

Is there any plan of implementing real (lightweight) fiber in Python?

------------------------------------------------------------
import threading

class Fiber(threading.Thread):
def __init__(self):
threading.Thread.__init__(self)

self.semaphore_running = threading.Semaphore(0)
self.semaphore_finish = None
self.val = None

self.setDaemon(True)
self.start()
self.start = self.start_fiber

def start_fiber(self):
self.semaphore_finish = threading.Semaphore(0)
self.semaphore_running.release()
self.semaphore_finish.acquire()

def run(self): # override
self.semaphore_running.acquire()
self.main()
if self.semaphore_finish is not None:
self.semaphore_finish.release()

def switchto(self, fiber, val=None):
fiber.val = val
fiber.semaphore_running.release()
self.semaphore_running.acquire()
return self.val

def main(self): # should be overridden
pass

class F1(Fiber):
def main(self):
print "f1 start"
self.switchto(f2)
print "f1 foo"
v = self.switchto(f2)
print "f1 v=%s world" % v
self.switchto(f2, "OK")
print "f1 end"

class F2(Fiber):
def main(self):
print "f2 start"
self.switchto(f1)
print "f2 bar"
result = self.switchto(f1, "Hello, ")
print "f2 result=%s" % result
print "f2 end"
self.switchto(f1)

f1 = F1()
f2 = F2()

print "start"
f1.start()
print "end"

-- kayama

[Arnaud Delobelle]

On Dec 22, 12:10*pm, Akihiro KAYAMA <[e-mail]:

Hi all.

I found cooperative multi-threading(only one thread runs at once,
explicit thread switching) is useful for writing some simulators.
With it, I'm able to be free from annoying mutual exclusion, and make
results deterministic.

For this purpose, and inspired by Ruby(1.9) fiber, I wrote my own
version of fiber in Python.

It just works, but using native Python threads for non-preemptive
threading is not cost-effective. Python has generator instead but it
seemed to be very restricted for general scripting. I wish I could
write nested (generator) functions easily at least.

Is there any plan of implementing real (lightweight) fiber in Python?

------------------------------------------------------------
import threading

class Fiber(threading.Thread):
* * def __init__(self):
* * * * threading.Thread.__init__(self)

* * * * self.semaphore_running = threading.Semaphore(0)
* * * * self.semaphore_finish = None
* * * * self.val = None

* * * * self.setDaemon(True)
* * * * self.start()
* * * * self.start = self.start_fiber

* * def start_fiber(self):
* * * * self.semaphore_finish = threading.Semaphore(0)
* * * * self.semaphore_running.release()
* * * * self.semaphore_finish.acquire()

* * def run(self): * * * * * * *# override
* * * * self.semaphore_running.acquire()
* * * * self.main()
* * * * if self.semaphore_finish is not None:
* * * * * * self.semaphore_finish.release()

* * def switchto(self, fiber, val=None):
* * * * fiber.val = val
* * * * fiber.semaphore_running.release()
* * * * self.semaphore_running.acquire()
* * * * return self.val

* * def main(self): * * * * * * # should be overridden
* * * * pass

class F1(Fiber):
* * def main(self):
* * * * print "f1 start"
* * * * self.switchto(f2)
* * * * print "f1 foo"
* * * * v = self.switchto(f2)
* * * * print "f1 v=%s world" % v
* * * * self.switchto(f2, "OK")
* * * * print "f1 end"

class F2(Fiber):
* * def main(self):
* * * * print "f2 start"
* * * * self.switchto(f1)
* * * * print "f2 bar"
* * * * result = self.switchto(f1, "Hello, ")
* * * * print "f2 result=%s" % result
* * * * print "f2 end"
* * * * self.switchto(f1)

f1 = F1()
f2 = F2()

print "start"
f1.start()
print "end"

-- kayama

I am not really familiar with ruby but these fibers seem to be some
sort of coroutines. Since python 2.5, generators can be sent values,
this can be used to implement what you want. I have had a got at it
for fun and this is what I came up with: note that there is no need
for a specific class, or for threads. I have tested this only on your
example, but it gives the same result as your code :)

-------------------------------------

# A 'fiber' is a generator function that yields tuples (fiber, value)
# or (fiber,). The 'run' function starts the the fiber and carries on
# with the fiber it yields. If the fiber also yields a value, then
# this value is sent to the 'next' fiber.

def run(fiber):
it, val = fiber(), []
fibers = { fiber: it }
try:
while True:
n = it.send(*val) if val else it.next()
co, val = n[0], n[1:]
it = fibers.get(co)
if it is None:
fibers[co] = it = co()
except StopIteration:
return val[0] if val else None

# Now the two 'fibers'

def f1():
print "f1 start"
yield f2,
print "f1 foo"
v = yield f2,
print "f1 v=%s world" % v
yield f2, "OK"
print "f1 end"

def f2():
print "f2 start"
yield f1,
print "f2 bar"
result = yield f1, "Hello, "
print "f2 result=%s" % result
print "f2 end"
yield f1,

print "start"
run(f1)
print "end"

--------------------------------------

HTH

--
Arnaud

[Duncan Booth]

Arnaud Delobelle <ar*****@googlemail.comwrote:

I am not really familiar with ruby but these fibers seem to be some
sort of coroutines. Since python 2.5, generators can be sent values,
this can be used to implement what you want. I have had a got at it
for fun and this is what I came up with: note that there is no need
for a specific class, or for threads. I have tested this only on your
example, but it gives the same result as your code :)

I think it was Microsoft who invented the term 'fiber' as a synonym for
coroutine. See http://msdn2.microsoft.com/en-us/library/ms682661.aspx

Unfortunately generators only save a single level of stack-frame, so they
are not really a replacement for fibers/coroutines. The OP should perhaps
look at Stackless Python or Greenlets. See
http://codespeak.net/py/dist/greenlet.html

[Arnaud Delobelle]

On Dec 22, 2:37*pm, Duncan Booth <[e-mail]:

Arnaud Delobelle <[e-mail]:

I am not really familiar with ruby but these fibers seem to be some
sort of coroutines. *Since python 2.5, generators can be sent values,
this can be used to implement what you want. *I have had a got at it
for fun and this is what I came up with: note that there is no need
for a specific class, or for threads. *I have tested this only on your
example, but it gives the same result as your code :)

I think it was Microsoft who invented the term 'fiber' as a synonym for
coroutine. Seehttp://msdn2.microsoft.com/en-us/library/ms682661.aspx

OK

Unfortunately generators only save a single level of stack-frame, so they
are not really a replacement for fibers/coroutines. The OP should perhaps
look at Stackless Python or Greenlets. Seehttp://codespeak.net/py/dist/greenlet.html

Still what I am proposing offers a level of cooperative multi-
threading which may be enough for the OP. In fact it is not clear to
me at the moment what can be done (sensibly :) with the OP's Fiber
class that cannot be achieved with the run() function I suggested.
This makes me think that there is something important that I am
failing to take into consideration; I would be grateful if it was
pointed out to me.

--
Arnaud

[Akihiro KAYAMA]

Thanks for your replies.

In article <37**********************************@i72g2000hsd. googlegroups.com>,
Arnaud Delobelle <ar*****@googlemail.comwrites:

arnodeldef f1():
arnodel print "f1 start"
arnodel yield f2,
arnodel print "f1 foo"
arnodel v = yield f2,
arnodel print "f1 v=%s world" % v
arnodel yield f2, "OK"
arnodel print "f1 end"
arnodel>
arnodeldef f2():
arnodel print "f2 start"
arnodel yield f1,
arnodel print "f2 bar"
arnodel result = yield f1, "Hello, "
arnodel print "f2 result=%s" % result
arnodel print "f2 end"
arnodel yield f1,

This is the most simple example. In real programming, things are more
complicate so I will want to refactor it like below:

def foo(fiber, s, arg=None)
print s
return yield fiber, arg

def f1():
foo(f2, "start") # XXX returns generator object
v = foo(f2, "foo")
foo(f2, "v=%s world" % v, "OK")

But current Python generator specification requires me:

def f1():
for x in foo(f2, "foo"): yield x
for x in foo(f2, "foo"): yield x
# XXX v = ... (I don't know how to do this)
for x in foo(f2, "v=%s world" % v, "OK"): yield x

I think it is not straitforward. Single level function which generator
impose is impractical for real use.

In article <Xn*************************@127.0.0.1>,
Duncan Booth <du**********@invalid.invalidwrites:

duncan.boothUnfortunately generators only save a single level of stack-frame, so they
duncan.boothare not really a replacement for fibers/coroutines. The OP should perhaps
duncan.boothlook at Stackless Python or Greenlets. See
duncan.boothhttp://codespeak.net/py/dist/greenlet.html

I am happy if I could use convenient coroutine features via standard
or simple extension library. py.magic.greenlet may be what I'm
looking for, but I wonder why this is named "magic" :-)

-- kayama

[Duncan Booth]

Akihiro KAYAMA <ka****@st.rim.or.jpwrote:

Thanks for your replies.

But current Python generator specification requires me:

def f1():
for x in foo(f2, "foo"): yield x
for x in foo(f2, "foo"): yield x
# XXX v = ... (I don't know how to do this)
for x in foo(f2, "v=%s world" % v, "OK"): yield x

I think it is not straitforward. Single level function which generator
impose is impractical for real use.

Not just impractical, there are plenty of situations where you simply
cannot do that at all.

Here's a greenlet example (from
http://socal-piggies.org/presentatio.../2005_07_21/):

from py.magic import greenlet
import xml.parsers.expat

def send(arg):
greenlet.getcurrent().parent.switch(arg)

def start_element(name, attrs):
send(('START', name, attrs))
def end_element(name):
send(('END', name))
def char_data(data):
data = data.strip()
if data: send(('DATA', data))

def greenparse(xmldata):
p = xml.parsers.expat.ParserCreate()
p.StartElementHandler = start_element
p.EndElementHandler = end_element
p.CharacterDataHandler = char_data
p.Parse(xmldata, 1)

def iterxml(xmldata):
g = greenlet(greenparse)
data = g.switch(xmldata)
while data is not None:
yield data
data = g.switch()

if __name__ == "__main__":
for data in iterxml("somexmldata"):
# do something with data
The greenlet here calls expat, but the 'yield' happens inside an expat
callback. To get this to work you would need to rewrite expat to use its
callback as a generator. Expat is coded in C, so you also need to find
some way to get it to save the state of the C functions when it has
yielded.

I think this example should answer Arnaud's question ("In fact it is not
clear to me at the moment what can be done (sensibly :) with the OP's
Fiber class that cannot be achieved with the run() function I
suggested.") Arnaud's run function cannot be used by anything which needs
to save C stack state.

I am happy if I could use convenient coroutine features via standard
or simple extension library. py.magic.greenlet may be what I'm
looking for, but I wonder why this is named "magic" :-)

I think it is called "magic" because it does something which is at first
glance impossible: saving the C stack state as well as the Python stack.
Possibly it does something underhand to achieve an impressive effect.
I haven't looked at the implementation to see how it does it: creating
threads and then scheduling them cooperatively would be one way but I
expect it just switches the C stack around between different areas of
memory.

A long time ago I ported the BCPL coroutine library and there is one
function in the middle (the one which does the stack switch) that
definitely felt like magic.

One interesting question raised by all this is whether those of us using
Windows can usefully call Microsoft's Fiber functions through ctypes and
get the benefit of coroutines without having to load any additional C
extensions at all.

[Michael Sparks]

Duncan Booth wrote:

Unfortunately generators only save a single level of stack-frame, so they
are not really a replacement for fibers/coroutines. The OP should perhaps
look at Stackless Python or Greenlets. See

On the surface of things, the single level aspect *LOOKS* like a problem,
but in fact is actually really useful. The reason is because it encourages
a generator to be relatively simple and focused encouraging reuse.

cf the components listed here:
* http://kamaelia.sourceforge.net/Components

Also, because they're simple, you can link every component in that list
either directly with all the others or via a trivial filtering component.

Also the fact that you have to build your own scheduler means you can do the
equivalent of saying to the scheduler "Don't run me next, run this next".
This gives you pretty much the full power of co-routines but allows for
very heavy reusability and independence of testing.

An example application that makes moderate use of this "bounce back"
coroutines is a greylisting server you can find here:
* http://kamaelia.sourceforge.net/KamaeliaGrey

I'd (almost) argue that the single level aspect of generators is perhaps
their best feature.
Michael.
--
http://yeoldeclue.com/blog
http://kamaelia.sourceforge.net/Developers/

[Michael Sparks]

Hi,

It just works, but using native Python threads for non-preemptive
threading is not cost-effective. Python has generator instead but it
seemed to be very restricted for general scripting. I wish I could
write nested (generator) functions easily at least.

Is there any plan of implementing real (lightweight) fiber in Python?

Please take a look at Kamaelia. Generators work extremely well, and are
extremely useful to work with:

* http://kamaelia.sourceforge.net/Home

(I need to update/improve the website...)

If you *must* have nested generators (it's rarely useful) you can do that,
but just need to have your "thing running the generators" understand
a "don't run me next, run this next" message. Our message is called
WaitComplete, and you can see it used here (in a non-trivial useful
system):

https://kamaelia.svn.sourceforge.net...greylisting.py

(I could point at trivial examples, but prefer something real)

The shortest overall description is here:
* http://kamaelia.sourceforge.net/t/TN...ToKamaelia.pdf

Cookbook examples:
* http://kamaelia.sourceforge.net/Cookbook

List of dozens of reusable (all with each other) components:
* http://kamaelia.sourceforge.net/Components

How to build your own (non-optimised) core:
* http://kamaelia.sourceforge.net/MiniAxon/

Ruby (mini) version: (for comparison :-)
https://kamaelia.svn.sourceforge.net...by/miniaxon.rb

Experimental process based (as well as thread & generator based) version:

http://yeoldeclue.com/cgi-bin/blog/b...eid=1196129474

(Going to move to process based components for static segmentation of an
application across process boundaries to give explicit multicore support.
May move to automatic distribution at some point, but static is an easy win
as the above example shows :-)

It's not as lightweight as stackless python's microthreads, but it's pretty
close. The scaling style is pretty similar as well - cf:

http://www.rhonabwy.com/wp/2007/11/1...ing-in-python/
I also blogged about that here:
http://yeoldeclue.com/cgi-bin/blog/b...eid=1195688924

(Someone curious about comparing Kamaelia to stackless. Interesting to see
the same scaling curve, but unsurprisingly stackless wins :-) Kamaelia
however works with standard python from version 2.2.late onwards :-) )

Interestingly recently discovered that Kamaelia's been slowly reinventing a
system the UK's MOD have been using for around 30 years to make concurrent
systems easier to build.... (mascot) :-)

Merry Christmas :-)
Michael
--
http://yeoldeclue.com/blog
http://kamaelia.sourceforge.net/Developers/

[Duncan Booth]

Michael Sparks <[e-mail]:

Duncan Booth wrote:

>Unfortunately generators only save a single level of stack-frame, so
they are not really a replacement for fibers/coroutines. The OP
should perhaps look at Stackless Python or Greenlets. See

On the surface of things, the single level aspect *LOOKS* like a
problem, but in fact is actually really useful. The reason is because
it encourages a generator to be relatively simple and focused
encouraging reuse.

Ah, perhaps Python should similarly limit function call nesting to one
level so as to keep things simple and encourage reuse.

[=?ISO-8859-1?Q?=22Martin_v=2E_L=F6wis=22?=]

Is there any plan of implementing real (lightweight) fiber in Python?

I have no such plan, and I don't know of anybody else's plan, either.

Regards,
Martin

[Duncan Booth]

Michael Sparks <[e-mail]:

To be clear - I REALLY didn't like the fact that generators were
single layer when I first saw them - it seemed a huge limitation.
(Indeed as huge a limitation as only having single level function
calls, or only single layer of nesting for namespaces, etc)... I even
asked a question [3] on that point before choosing python to write
Kamaelia in... The fact that it's been a benefit rather than a problem
rather surprised me.

Ok, I've now spent a little while browsing Kamaelia and it does look
impressive. I'll need a bit longer to look at it in more detail.

Let me try again:

There are problems for which generators saving only a single stack frame
are an excellent solution. e.g. a situation like yours where if I
understand it you may have thousands of separate generators all in
existence simultaneously.

There are also problems where full blown coroutines are appropriate. The
example I quoted earlier of turning a parser from one which generates a lot
of callbacks to one which 'yields' tokens is the usual example given.

There are also some situations where threads are appropriate: just not
nearly as many situations as some people think.

I'm happy with generators as they are: they're a great solution to a
problem that most of us didn't realise we had until the solution came
along. That doesn't mean that I wouldn't also like to have a separate
coroutine library, but I would use it to replace situations that might
otherwise have to use threads, not to replace generators.

Incidentally, you may note that you helped me back then (which I'm
thankful for :-), so you can kinda view this as me reporting back
"actually, it's turned out to be helpful rather than a pain" :-) Took
a while to figure that out though ;)

Your mileage may vary :)

Incidentally, it was probably your response (message 7) in that thread
that was responsible for me deciding to see where things could go by
trying python :-)

Thanks you. I really do intend *most* of my posts to be helpful.

[Bjoern Schliessmann]

Michael Sparks wrote:

All that said, my personal primary aim for kamaelia is to try and
make it into a general toolkit for making concurrency easy &
natural (as well as efficient) to work with. If full blown
coroutines turn out to be part of that c'est le vie :-)

I must admit I mostly didn't follow this thread, but it sparked my
interest in Kamaelia. I already did the MiniAxon tutorial and I
plan to try out Kamaelia with a project I had discussed here a
while ago (which I had to suspend until recently because of not
enough spare time; it's about simulating complex relais circuits).
Please continue the great work.

Regards & merry christmas everyone,
Björn

P.S.: In the MiniAxon tutorial, I noticed a formatting problem and a
bunch of typos on one page but the feedback link doesn't work; are
you interested in a list?

--
BOFH excuse #14:

sounds like a Windows problem, try calling Microsoft support

[iccananea]

Hi!

Since your interest in fibers/coroutines is related to writing
simulators, you should try the SimPy package (simpy.sf.net), which is
a process-based discrete event simulator that uses generators as
processes.

On 22 dez, 09:10, Akihiro KAYAMA <[e-mail]:

Hi all.

I found cooperative multi-threading(only one thread runs at once,
explicit thread switching) is useful for writing some simulators.
With it, I'm able to be free from annoying mutual exclusion, and make
results deterministic.

For this purpose, and inspired by Ruby(1.9) fiber, I wrote my own
version of fiber in Python.

It just works, but using native Python threads for non-preemptive
threading is not cost-effective. Python has generator instead but it
seemed to be very restricted for general scripting. I wish I could
write nested (generator) functions easily at least.

Is there any plan of implementing real (lightweight) fiber in Python?

------------------------------------------------------------
import threading

class Fiber(threading.Thread):
def __init__(self):
threading.Thread.__init__(self)

self.semaphore_running = threading.Semaphore(0)
self.semaphore_finish = None
self.val = None

self.setDaemon(True)
self.start()
self.start = self.start_fiber

def start_fiber(self):
self.semaphore_finish = threading.Semaphore(0)
self.semaphore_running.release()
self.semaphore_finish.acquire()

def run(self): # override
self.semaphore_running.acquire()
self.main()
if self.semaphore_finish is not None:
self.semaphore_finish.release()

def switchto(self, fiber, val=None):
fiber.val = val
fiber.semaphore_running.release()
self.semaphore_running.acquire()
return self.val

def main(self): # should be overridden
pass

class F1(Fiber):
def main(self):
print "f1 start"
self.switchto(f2)
print "f1 foo"
v = self.switchto(f2)
print "f1 v=%s world" % v
self.switchto(f2, "OK")
print "f1 end"

class F2(Fiber):
def main(self):
print "f2 start"
self.switchto(f1)
print "f2 bar"
result = self.switchto(f1, "Hello, ")
print "f2 result=%s" % result
print "f2 end"
self.switchto(f1)

f1 = F1()
f2 = F2()

print "start"
f1.start()
print "end"

-- kayama

[Michael Sparks]

Bjoern Schliessmann wrote:

Michael Sparks wrote:

>All that said, my personal primary aim for kamaelia is to try and
make it into a general toolkit for making concurrency easy &
natural (as well as efficient) to work with. If full blown
coroutines turn out to be part of that c'est le vie :-)

I must admit I mostly didn't follow this thread, but it sparked my
interest in Kamaelia. I already did the MiniAxon tutorial and I
plan to try out Kamaelia with a project I had discussed here a
while ago (which I had to suspend until recently because of not
enough spare time; it's about simulating complex relais circuits).
Please continue the great work.

Many thanks for your kind words - the work is continuing :-)

Also, I'd be interested in hearing how your project gets on - it sounds
like the sort of thing that Kamaelia should be able to help with. (If it
doesn't/can't, then it's a bug IMO :)

Regards & merry christmas everyone,
Björn

P.S.: In the MiniAxon tutorial, I noticed a formatting problem and a
bunch of typos on one page but the feedback link doesn't work; are
you interested in a list?

I'm always interested in feedback! The fact the feedback link doesn't work
for you is particularly useful - I'll look into that!

Best Regards,
Michael.

[Michael Sparks]

Duncan Booth wrote:

There are also problems where full blown coroutines are appropriate. The
example I quoted earlier of turning a parser from one which generates a
lot of callbacks to one which 'yields' tokens is the usual example given.

For completeness, I looked at the other half of the thread at the expat
parser, and decided to write that in the style we use for Kamaelia - it
ends up looking like this:

import xml.parsers.expat
import Axon
from Kamaelia.Chassis.Pipeline import Pipeline
from Kamaelia.Util.Console import ConsoleEchoer

class Parser(Axon.ThreadedComponent.threadedcomponent):
data = "<h1Default </h1>" # Can be overridden by kwargs as normal

def start_element(self, name, attrs):
self.send(("START", name, attrs), "outbox")

def end_element(self, name):
self.send(("END", name), "outbox")

def char_data(self, data):
data = data.strip()
self.send(("DATA", data), "outbox")

def main(self):
p = xml.parsers.expat.ParserCreate()
p.StartElementHandler = self.start_element
p.EndElementHandler = self.end_element
p.CharacterDataHandler = self.char_data
p.Parse(self.data, 1)
self.send(Axon.Ipc.producerFinished(), "signal")

Pipeline(
Parser(data="<body><h1>Hello</h1world <p>Woo</p></body>"),
ConsoleEchoer(),
).run()

You'll note we don't use generators for "Parser" in this context. This also
isn't 100% identical to form you use since we don't turn this into an
iterator (obviously :).

We do also use 1 more thread than the greenlet approach though. Pipeline
& ConsoleEchoer are generator based though, as is the scheduler that
runs them :-)

Have fun :-)
Michael.
--
http://yeoldeclue.com/blog
http://kamaelia.sourceforge.net/Developers/