Profiling weirdness: Timer.timeit(), fibonacci and memoization

[Steven D'Aprano]

On Sat, 02 Aug 2008 06:02:02 -0700, ssecorp wrote:

> I am not clear about the results here.
> 
> 
> from timeit import Timer
> import Decorators
> 
> def fib(n):
>     a, b = 1, 0
>     while n:
>         a, b, n = b, a+b, n-1
>     return b

[...]

> s = 100
> 
> t1 = Timer('fib(s)', 'from __main__ import fib, s') 
> t2 = Timer('fibmem(s)', 'from __main__ import fibmem, s') 
> t1.repeat(number=1)
> t2.repeat(number=1)
> print t1.timeit()
> print t2.timeit()
> 
> 
> 35.3092010297
> 1.6516613145
> 
> So memoization is 20+ times faster than the idiomatic way? Or am I
> missing something here?

Memoization *can be* faster, not *is* -- memoization requires work, and 
if it is more work to look something up than to calculate it, then it 
will be a pessimation instead of an optimization. That's probably less of 
an issue with high-level languages like Python, but in low level 
languages you would need to start thinking about processor caches and all 
sorts of complications.

But I digress... in Python, yes, I would expect a significant speedup 
with memoization. That's why people use it.


 
> Ok for fun I added memoization to the idiomatic one:

[...]
 
> didn't think it would make a difference there but it certainly did.
> 
> 1.59592657726
> 1.60179436213

Just curious, but why don't you show the results of the call to repeat()? 
It makes me uncomfortable to see somebody showing only half their output.

But yes, with memoization, the lookup to find the Fibonacci number should 
decrease the time it takes to calculate the Fibonacci number. I'm not 
sure why you are surprised. Regardless of which Fibonacci algorithm you 
are using, the Timer object is essentially timing one million lookups, 
minus 100 calculations of the Fibonacci number. The 999,900 cache lookups 
will dominate the time, far outweighing the 100 calculations, regardless 
of which method of calculation you choose. That's why the results are 
almost identical.



-- 
Steven