How to make Python run as fast (or faster) than Julia

[Steven D'Aprano]

On Thu, 22 Feb 2018 12:03:09 +0000, bartc wrote:

> The idea of the Fibonacci benchmark is to test how effectively an
> implementation manages large numbers of recursive function calls. Then,
> fib(36) would normally involve 48,315,633 calls.
> 
> This version does only 37, giving a misleading impression.

Who cares if it only does 37? There is *absolutely no benefit* to those 
additional 48,315,596 calls, and thanks to the benchmark I discovered 
that.[1]

I want to know what is the fastest implementation of Fibonacci I can 
write. I'm not married to the idea that I have to make a ludicrous 48 
million function calls just to get the 36th Fibonacci number.


> (It then goes on to suggest using 'numba', and using its JIT compiler,
> and using on that on an /iterative/ version of fib(). Way to miss the
> point.

Indeed, you certainly have.


> It might be a technique to bear in mind, but it is nonsensical to say
> this gives a 17,000 times speed-up over the original code.

That's *exactly what it did*.

How many years, decades, have you been programming? Have you not realised 
yet that the best way to optimize code is to pick the fastest algorithm 
you can that will do the job? There's no law that says because you 
started with a slow, inefficient algorithm you have to stay with it.


> Here's another speed-up I found myself, although it was only 50 times
> faster, not 17,000: just write the code in C, and call it via
> os.system("fib.exe").

Did you include the time taken to capture the text output from stdout, 
parse it, and convert to an int?

Did your C code support numbers greater than 2**64? My fibonacci function 
can calculate the 10,000th Fibonacci number in a blink of the eye:

py> fibi(10000)
336447648764317832666216120051075...976171121233066073310059947366875

Output truncated for brevity, it is a 2090-digit number.

Admittedly it did take about a minute and a half to generate all 208988 
digits of the one millionth Fibonacci number, but the performance is fast 
enough for my needs.




[1] Actually I already knew it, but then I didn't perform these 
benchmarks, I'm just linking to them.


-- 
Steve