{"id":349,"date":"2009-04-20T17:07:51","date_gmt":"2009-04-20T16:07:51","guid":{"rendered":"http:\/\/fiber-space.de\/wordpress\/?p=349"},"modified":"2009-04-20T17:07:51","modified_gmt":"2009-04-20T16:07:51","slug":"tail-recursion-decorator-revisited","status":"publish","type":"post","link":"http:\/\/fiber-space.de\/wordpress\/2009\/04\/20\/tail-recursion-decorator-revisited\/","title":{"rendered":"Tail recursion decorator revisited"},"content":{"rendered":"

A while ago some of us tried to find the best solution for a tail recursion decorator<\/a>. The story began when Crutcher Dunnavant came up with a surprising decorator<\/a> that was able to eliminate tail recursion<\/a>. His solution used stack inspections and could flatten the call stack s.t. the maximum height of the stack became 2. I gave an alternative, faster implementation that omitted stack inspections. This solution was further improved by Michele Simionato and George Sakkis. The story already ends here because the performance penalty of those decorators was still quite considerable. On the samples we used the undecorated recursive function was more than twice as fast as the decorated one. So the decorator added more than 100% overhead.<\/p>\n

Today I tried something new. I reimplemented Georges decorator in Cython which is considerably faster than Python and then I compared the performance of undecorated code, code that is decorated with the pure Python decorator and the Cython version of it.<\/p>\n

Here<\/a> you can download the relevant source code for the decorators.<\/p>\n

The following implementation shows the Cython decorator defined in `tail_recursive.pyx`<\/p>\n

cdef class tail_recursive:\r\n    cdef int firstcall\r\n    cdef int CONTINUE\r\n    cdef object argskwd\r\n    cdef object func\r\n\r\n    def __init__(self, func):\r\n        self.func = func\r\n        self.firstcall = True\r\n        self.CONTINUE = id(object())\r\n\r\n    def __call__(self, *args, **kwd):\r\n        if self.firstcall:\r\n            self.firstcall = False\r\n            try:\r\n                while True:\r\n                    result = self.func(*args, **kwd)\r\n                    if result == self.CONTINUE: # update arguments\r\n                        args, kwd = self.argskwd\r\n                    else: # last call\r\n                        return result\r\n            finally:\r\n                self.firstcall = True\r\n        else: # return the arguments of the tail call\r\n            self.argskwd = args, kwd\r\n            return self.CONTINUE<\/pre>\n
Here are some performance tests.<\/p>\n
As a sample function I used a tail recursive factorial<\/p>\n
def factorial(n, acc=1):\r\n    \"calculate a factorial\"\r\n    return (acc if n == 0 else factorial(n-1, n*acc))<\/pre>\n
The timining function is defined by<\/p>\n
import time\r\ndef mtime(foo):\r\n    a = time.time()\r\n    for j in range(10):\r\n        for i in range(900):\r\n            foo(i)\r\n    return time.time()-a<\/pre>\n
The results I got were:<\/p>\n
8.484 -- undecorated\r\n9.405 -- with Cython decorator   + 10%\r\n17.93 -- with Python decorator   + 111%<\/pre>\n
Next I checked out a pair of mutual recursive functions. Notice that in those pairs only <\/em>one<\/em> function may be decorated by `tail_recursive`.<\/p>\n
def even(n):\r\n    if n == 0:\r\n        return True\r\n    else:\r\n        return odd(n-1)\r\n\r\ndef odd(n):\r\n    if n == 0:\r\n        return False\r\n    else:\r\n        return even(n-1)<\/pre>\n
Here are the results:<\/p>\n
2.969 -- undecorated\r\n3.312 -- with Cython decorator   + 11%\r\n7.437 -- with Python decorator   + 150%<\/pre>\n
These are about the same proportions as for `factorial` example.<\/p>\n
My conclusion is that one can expect about 10% performance penalty for Cythons `tail_recursive` decorator. This is a quite good result and I don’t shy away from recommending it.<\/p>\n
<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
A while ago some of us tried to find the best solution for a tail recursion decorator. The story began when Crutcher Dunnavant came up with a surprising decorator that was able to eliminate tail recursion. His solution used stack … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[4],"tags":[],"_links":{"self":[{"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/posts\/349"}],"collection":[{"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/comments?post=349"}],"version-history":[{"count":22,"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/posts\/349\/revisions"}],"predecessor-version":[{"id":371,"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/posts\/349\/revisions\/371"}],"wp:attachment":[{"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/media?parent=349"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/categories?post=349"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/tags?post=349"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}