[maxbond]

I think the VM is operative here. My native Rust implementation found fib(35) in 51ms, but my Python implementation took about 1500ms (similar to their measurements).

(I eyeballed the assembly to make sure the native implementation was recursive, but that's the extent of my rigor - consider these napkin numbers.)

[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.)