Sitemap

McMillan Enterprises, Inc.
Python Pages
  Sockets HOWTO
  Distributing Python Programs
  A Python C++ API
  Embedding Python
  Stackless Python
    Getting Started with Stackless
    Fibonacci Generators
    Walking the Leaves of a Tree
    Parsing
    SelectDispatcher
  MkSQL
  Import Hooks
Java Samples
About ME Inc.

More Fibonacci Generators Than You Ever Wanted

Note: These examples are based on release version 1.1.1 (3/29/00) of stackless. Some samples may require tweaking for release 1.2; I don't know. You can be fairly sure that sooner or later, these examples will become obsolete.

First, a normal Python Fibonacci sequence generator, using a class:


        class ClassicFibGen:
            def __init__(self):
                self.x = 0
                self.y = 1
            def __getitem__(self, n):
                x = self.x
                self.x = self.y
                self.y = self.x + x
                return self.y
        

Now, something with exactly the same interface, using continuations:


        import continuation
        


        class ContFibGen1:
            def __init__(self):
                self.cont = self._get
            def __getitem__(self, n):
                self.cont, val = self.cont()
                return val
            def _get(self):
                x = 0
                y = 1
                caller = continuation.caller()
                while 1:
                    n = x + y
                    x = y
                    y = n
                    caller.jump_cv(y) 
        

Finally, the test bed:


        def testFG(klass, verbose=0):
          fg = klass()
          for n in fg:
              if verbose:
                print n,
              if n > 100:
                  if verbose:
                    print
                  break
        

They produce the same results (whew!), but the continuation version is significantly slower (almost twice as slow)! Why? Because we still had to use a class. We needed to conform to the for protocol: that is, we needed to implement __getitem__, which continuation objects don't know how to do, (and that's one argument for getting stackless into core Python - the possibility of extending the for protocol so continuations can be called directly).

So let's forgo the __getitem__ and use a different idiom:


        def fibfunc():
            x = 0
            y = 1
            caller = continuation.caller()
            while 1:
                n = x + y
                x = y
                y = n
                caller.jump_cv(y)
        


        def testfibfunc(verbose=0):
            next, val = fibfunc()
            while 1:
                if verbose:
                    print val,
                if val > 100:
                    if  verbose:
                        print
                    next.link = None
                    break
                next, val = next()
        

This is similar to where we left off on the silly example (generating 7 numbers). The difference here is the fibfunc is not in charge of its own lifetime. The code using it has to kill it. That's what the next.link = None does - it breaks a reference in the continuation object, which allows it to destruct. Without that, we'd have a leak. The continuation object would not be destroyed after going out of scope (note: this is 1.5.2 code; Christian is fixing this problem, and / or Python 2.0's garbage collection may also fix it).

Now this is more like it. It's about 20% faster than the normal Python version.

Let's try another pattern:


        def fibfunc2():
            x = 0
            y = 1
            continuation.return_current(1)
            while 1:
                n = x + y
                x = y
                y = n
                continuation.caller()(y)
        


        def testfibfunc2(verbose=0):
            fib = fibfunc2()
            while 1:
                fib.update()
                val = fib()
                if verbose:
                    print val,
                if val > 100:
                    if  verbose:
                        print
                    fib.link = None
                    break
        

This one uses update to force the generator to stay up to date. The generator doesn't bother to remember who called him - he get's a fresh continuation every time. In some ways, that makes this a safer pattern than what we did above - there's less linkage between the generator and the code using the generator.

Alas, it's also slow - about 20% slower than the pure Python at the top. Why? Because of grabbing a new continuation every time with that continuation.caller()(y). That's expensive. That doesn't mean you should avoid continuation.caller - far from it. It is a very useful call. But inside a tight loop, there are better ways to do it.


        def fibfunc3():
            x = 0
            y = 1
            back, _ = continuation.return_current(3)  # call_cv
            while 1:
                n = x + y
                x = y
                y = n
                back, _ = back(y)
        


        def testfibfunc3(verbose=0):
            fib = fibfunc3()
            while 1:
                val = fib()
                if verbose:
                    print val,
                if val > 100:
                    if  verbose:
                        print
                    fib.link = None
                    break
        

That one takes the cake. It's about 33% faster than the pure Python, and 20% faster than fibfunc. Why? Because we've exploited the fact that fibfunc3 doesn't need to stay up to date - all the state that matters is in locals. Or, to put it another way, we've cheated, and fibfunc is really the best of the lot. Using the patterns demonstrated in fibfunc and fibfunc2, you can create generators of arbitrary complexity, and it will still work, while fibfunc3 would break.

Actually, fibfunc2 is a coroutine pattern, not simply a generator (which is called a semi-coroutine in some literature). Coroutines can transfer control back and forth with the two sides acting as peers, while with generators, one side is always the "caller" and the other the "callee". In this case, fibfunc2 always transfers control back to his caller, but his caller in round n+1 need not be the same caller he had in round n.

Next: a truly perverse "generator".

copyright 1999-2002
McMillan Enterprises, Inc.