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