Why does Python's decorator syntax give faster memoization code than plain wrapper syntax?

Question

I've been trying to understand the section on memoization in Chapter 8 of Real World OCaml (RWO). I wasn't getting it, so I decided to translate the OCaml code into Python. This exercise turned out to be useful, because (1) I did finally understand what RWO was saying, and (2) I wrote some faster Python code that seems to work. However, in writing the Python code, I tried to perform the memoization two different ways: once using a plain call to a wrapping function and once using Python's decorator syntax.

I memoized the Fibonacci function three different ways and measured how long each one took to compute the 32nd Fibonacci number twice on my 2.9 GHz Intel core i7 MacBook Pro with 8 GB RAM and OS 10.9.2, running Python 2.7. This gave me a surprising result:

1. No memoization at all: 2 s
2. Regular memoization: 1 s
3. RWO-style mutually recursive memoization using plain syntax: 2 s
4. RWO-style mutually recursive memoization using decorator syntax: 0.0001 s

Everything I've read says that the decorator syntax is really just syntactic sugar for saying:

memoFib = memoize(Fib)

So why is #4 so much faster than #3?

from time import time

def unfib(n):
    '''Unmemoized Fibonacci'''
    if n <= 1: return 1
    else: return unfib(n-1) + unfib(n-2)

def memoize(f):
    '''A simple memoization function'''
    hash = {}
    def memo_f(x):
        if not hash.has_key(x):
            res = f(x)
            hash[x] = res
        return hash[x]
    return memo_f

# Simple approach to memorizing Fibonacci (#2 from the list above)
memoFib1 = memoize(unfib)

# Simple approach to timing functions
def timeit(its,f,arg):
    zero = time()
    for i in range(its):
        res = f(arg)
    one = time()
    print res, one - zero

# A non-recursive form of Fibonacci
# that expects the remainder of the 
# function to be passed as an argument.
# Together, they make a pair of mutually
# recursive functions. Real World Ocaml
# refers to this as 'tying the recursive
# knot' (Ch. 8, Imperative programming).
def fib_norec(fib,x):
    if x <= 1: return 1
    else: return fib(x-1) + fib(x-2)

def memo_rec(f_norec):
    '''A memoizing version of make_rec,
    but using the plain wrapper
    syntax of the memoize function'''
    def f(x):
        return f_norec(f,x)
    return memoize(f)

# #3 from list above: memoized using plain call to wrapping function
memoFib2 = memo_rec(fib_norec)

def memo_rec2(f_norec):
    '''A second memoizing version of
    make_rec (from RWO), but using 
    the decorator syntax'''
    @memoize
    def f(x):
        return f_norec(f,x)
    return f

# #4 from list above, memoized using decorator syntax
memoFib3 = memo_rec2(fib_norec)

print 'no memo\t\t\t\t\t',
timeit(2,unfib,32)
print 'basic memo\t\t\t\t',
timeit(2,memoFib1,32)
print 'mutually recursive memo, plain wrapper syntax',
timeit(2,memoFib2,32)
print 'mutually recursive memo, decorator syntax',
timeit(2,memoFib3,32)

Answer 1

def f(x):
    return f_norec(f,x)
return memoize(f)

Here, the returned function is the one produced by memoized, but the local name f still refers to the non-memoized function defined in the above snippet, hence none of the recursive calls benefit from memoization. The call graph goes like this:

<memoized f>
  f
    f_noref
      f
        f_norec
          ...

Here on the other hand,

@memoize
def f(x):
    return f_norec(f,x)
return f

The local name f refers to the memoized function, so you get a call graph like this:

<memoized f>
  f
    f_norec
      <memoized f>
        f
          f_norec
            <memoized f>
              ...

(It looks like more calls, and it is. I only show the first of the two recursive calls per level, so you don't see how the memoization shortens the second.)

If you manually wrote that the decorator syntax actually desugars to (f = memoize(f); return f), you'd see identical behavior and performance.