[Karellen]

Yeah, it was using the naive recursive implementation instead of a tail-call recursive variant that I wasn't expecting.

I should have been expecting it. You're testing the performance of the runtime, not the program, so of course you want a bad implementation of the algorithm to stress the runtime as much as possible.

(My tail-call Python implementation tops out at fib(997) in 720ms. Calling fib(998) gives me a "RecursionError: maximum recursion depth exceeded". AIUI python is never going to optimise away tail calls, but because the tail-call variant is O(n) anyway it still works out orders of magnitude faster.)