Why is one memoization strategy slower than the other?

Question

So this page about memoization got me curious. I ran my own benchmarks.

1) Mutable default dictionary:

%%timeit
def fibo(n, dic={}) :
    if n not in dic :
        if n in (0,1) :
            dic[n] = 1
        else :
            dic[n] = fibo(n-1)+fibo(n-2)
    return dic[ n ]
fibo(30)

Out:

100000 loops, best of 3: 18.3 µs per loop

2) Same idea, but following the principle “Easier to ask forgiveness than permission”:

In [21]:

%%timeit
def fibo(n, dic={}) :
    try :
        return dic[n]
    except :
        if n in (0,1) :
            dic[n] = 1
        else :
            dic[n] = fibo(n-1)+fibo(n-2)
        return dic[ n ]
fibo(30)

Out:

10000 loops, best of 3: 46.8 µs per loop

My questions

• Why is 2) so slow compared to 1)?

Edit

As @kevin suggest in the comments, I got the decorator completely wrong so I removed it. The remainder is still valid! (I hope)

Answer 1

Catching exception means stack tracing which can be very expensive:

https://docs.python.org/2/faq/design.html#how-fast-are-exceptions

Exceptions are very efficient in two cases:

1. try ... finally
2. try ... except, providing that no exception is thrown

However, when exception occured and caught the required stack tracing adds great overhead.