Lua Coroutines Versus Python Generators

wiki

How do Python generators differ from Lua coroutines? The most important feature is that in Lua, coroutine.yield() is an ordinary function which can be invoked anywhere in the dynamic extent of a coroutine.resume() with the limitation that you cannot yield through a C callback (unless you use MikePall 's [Coco] library.) In Python, yield is syntactic, and can only be in the lexical body of the generator function.

This means that Python generators must be written as generators, and cannot easily be factored into smaller functions; nor can they easily be recursive. You can achieve recursion by a form of chaining; a message on the [Python mailing list] describes both the mechanism:

!Python

def inorder(t):

     if t:

         for x in inorder(t.left):

             yield x

         yield t.label

         for x in inorder(t.right):

             yield x

In Lua, one might write a more agnostic inorder function as a higher-order function:

function inorder(f, t)

  if t then

    inorder(f, t.left)

    f(t.label)

    return inorder(f, t.right)

  end

end

The Lua function could then be used either as the iterator in a for loop:

for label in coroutine.wrap(inorder), coroutine.yield, t do

  -- something with label

end

or as a sort of foreach function:

inorder(print, t)

In an attempt to reduce the comparison of recursive generators to its minimum, I wrote a pair of simple programs which generate the infinite [Ruler function]. (A more interesting page about this function is Michael Naylor's [Abacaba-Dabacaba] which includes a musical exploration.)

The ruler function can be generated non-recursively, but in this example it's standing in for something like a depth-first search, so we'll just look at the recursive implementation. The programs generate the first 2^k values in the sequence and add them up as a sort of validity test, since it's easy to show that the sum of the first 2^k elements of the ruler function is 2^(k+1)-1. Python's built-in functions and standard library were handy here; in Lua, I had to implement the sum and islice (first k elements of a sequence) functions myself, but fortunately that's not difficult.

So here's the Lua implementation:

function ruler(put, k)

  for i = 1, k do

    put(i)

    ruler(put, i-1)

  end

end

 

function eachruler()

  return coroutine.wrap(function()

    return ruler(coroutine.yield, 100)

  end)

end

 

function sumseq(k, f, o, s)

  local sum = 0   

  for v in f, o, s do

    k, sum = k-1, sum + v

    if k <= 0 then break end

  end        

  return sum

end

 

local howmany = tonumber(arg[1]) or 24

local now = os.clock()

local sum = sumseq(2^howmany, eachruler())

local took = os.clock()-now

print(("%2i: %7.3f seconds  %i check %i"):format(howmany, took, sum, 2^(howmany+1)-1))

and the very similar and somewhat shorter Python implementation:

!Python

from itertools import islice

from sys import argv

from time import clock

 

def ruler(k):

  for i in range(1, k+1):

    yield i

    for x in ruler(i-1): yield x

 

howmany = int(argv[1])

now = clock()

total = sum(islice(ruler(100), 2**howmany))

took = clock()-now

print "%2d: %7.3f seconds %d check %d" % (howmany, took, total, 2**(howmany+1)-1)

The slightly odd formulation of the recursion is the result of manually changing the tailcall into a for loop, because Python doesn't do tailcalls, and the original tailcall implementation put Python at even more of a disadvantage.

Since both programs passed the check, I'll only paste the comparative timings here (in seconds as reported above). I don't believe this is simply a "Lua is faster than Python" benchmark; I think it shows that coroutines are inherently faster; the main difference is not having to pass the values up through a chain of yields.

 N      Lua   Python

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

12:   0.000    0.008

13:   0.000    0.023 

14:   0.008    0.055 

15:   0.016    0.109 

16:   0.031    0.227 

17:   0.078    0.469 

18:   0.148    0.961 

19:   0.305    1.961 

20:   0.602    4.000 

21:   1.211    8.148 

22:   2.430   17.211 

23:   4.820   40.094 

24:   9.875   94.992