[Python-ideas] A Continuations Compromise in Python

[Steven D'Aprano]

On Sun, 3 May 2009 10:30:55 pm Antoine Pitrou wrote:
> Steven D'Aprano <steve at ...> writes:
> > It's hardly "premature" to notice that recursive code in Python is
> > significantly slower and less efficient than in other languages.
> > This is a known problem, or at least issue, since some people
> > consider that the solution (tail-recursion optimization) is worse
> > that the problem.
>
> Is there some evidence that this "known issue" has been popping up in
> real-world production Python code (I am not talking about Lisp, C, or
> any other language), rather than academic discussions?
>
> Premature optimization is trying to optimize something which is not a
> significant contributor to execution time.

People spend time trying to speed up general purpose code in the 
standard library, to save 1% or 2% on benchmarks. I'm sure I don't need 
to google for examples -- you've been around the Python-Dev list long 
enough to see plenty of examples, and I for one haven't seen anyone 
objecting to improving Python's general execution speed.

In this case, the speed-up could (in principle) be by up to a factor of 
five or so, not a mere couple of percent. Recursion in Python is quite 
slow compared to iteration. Here's a real (albeit trivial) example: the 
Towers of Hanoi.


def move(n, a, b, c):  # Version using tail recursion.
    "Move n disks from needle a to b using c as temporary storage."
    if n > 0:
        for t in move(n-1, a, c, b):
            yield t
        yield (a, b)
        for t in move(n-1, c, b, a):
            yield t

def move2(n, a, b, c):  # Non-tail recursive version.
    while n > 0:
        for t in move2(n-1, a, c, b):
            yield t
        yield (a, b)
        n -= 1
        a, c = c, a

And in use:

>>> assert list(move(15, 1, 2, 3)) == list(move2(15, 1, 2, 3))
>>> from time import time
>>> t = time(); L = list(move(15, 1, 2, 3)); t = time() - t; print t
0.40623497963
>>> t = time(); L = list(move2(15, 1, 2, 3)); t = time() - t; print t
0.261477947235

Okay, this toy program isn't exactly a mission-critical application, but 
it does demonstrate a genuine performance penalty when using recursion. 
In this case, two recursive calls (one of which is a tail-call) takes 
nearly 60% more time than a single recursive call in a while loop.

But more importantly, execution time is not the only resource that needs 
to be optimized. Programmer effort is an important resource that many 
people wish to optimize. Removing tail-call recursion is a simple 
algorithm quite well suited to be done by the machine, but tedious and 
sometimes tricky for the average programmer to do correctly.

Another is stack space -- hence the relatively low default recursion 
limit. Anyone who has ever seen "maximum recursion depth exceeded" in 
real-world code has a real problem which (if the function is 
tail-recursive) could be fixed by a hypothetical optimizer.



-- 
Steven D'Aprano