I am using fibonacci function to the compare the performance between Julia and Mojo.
First Julia code:
function fib(n::Int64)::Int64
n <= 2 && return 1
n == 3 && return 2
fib(n - 1) + fib(n - 2)
end
@time fib(50);
21.564018 seconds
Then Mojo code:
from time import now
fn fib(n:Int) -> Int:
if n <= 2:
return 1
if n == 3:
return 2
return fib(n - 1) + fib(n - 2)
var eval_begin = now()
var res = fib(50)
var eval_end = now()
let execution_time_sequential = Float64((eval_end - eval_begin))
print("execution_time sequential in ms:")
print(execution_time_sequential / 1000000)
execution_time sequential in ms:
14253.018341999999
Julia 21s, Mojo 14s (Rust 16s), I can’t believe it, am I doing something wrong?
This isn’t very surprising to me. Julia has a small amount of extra overhead on non-inlined function calls (for GC housekeeping). This tends to only matter for very small recursive functions since otherwise a function this small would have been inlined anyway. As such this benchmark doesn’t do a good job of measuring the performance of normal code.
Not sure if it will change too much, but could you report back statistics with your fibonacci function using BenchmarkTools’s @btime macro? Like this?
using BenchmarkTools
@btime fib(50)
I agree with @Oscar_Smith , shouldn’t matter much but I am just curious.
OP’s implementation could not benefit from tail call optimization, there are 2 recursive calls followed by an addition prior to the return. If that link dies then here’s a Julia version of the implementation that does have a tail call:
"""
FibonacciTailRecursive(n::Int, previous::Int=0, current::Int=1) -> m+n-th number
previous is intended to be the m-th number, and current is intended to be the
m+1-th number. The 0th number is 0.
"""
function FibonacciTailRecursive(n::Int, previous::Int=0, current::Int=1)
if n == 0 return previous end
if n == 1 return current end
FibonacciTailRecursive(n - 1, current, previous + current)
end
To answer the question directly, no @Brian1, you are not doing anything incorrect. Run-time recursion in julia is not something that’s designed to be used in performance sensitive scenarios, and is instead optimized for different things.
It’s not particularly surprising that another language is faster than Julia at doing this. But this also isn’t a very big deal because any algorithm you want to write which makes use of recursion in this way can be rewritten in more performance friendly ways which we do expect Julia to perform well at.
| | |_| | | | (_| | | Version 1.10.0-beta2 (2023-08-17)
_/ |\__'_|_|_|\__'_| | Official https://julialang.org/ release
|__/ |
julia> function FibonacciTailRecursive(n::Int, previous::Int=0, current::Int=1)
if n == 0 return previous end
if n == 1 return current end
FibonacciTailRecursive(n - 1, current, previous + current)
end
FibonacciTailRecursive (generic function with 3 methods)
julia> @time FibonacciTailRecursive(50)
0.000002 seconds
12586269025
Has MoJo v1 been released? Is it approved for production critical results?
Benchmarking is interesting and fun, and probably is the first reason why people get interested in Julia. But too often they probe the tiniest possible detail, providing limited clues on the overall experience.
Still, this is something interesting to re-evaluate when Julia version >= 1.10 is released.
Yes, but note that FibonacciTailRecursive is algorithmically different from the naïve fib implementation. It’s not a better implementation of the same algorithm, but instead a smarter algorithm, so it’s not a very enlightening comparison if you’re trying to compare languages.
fib(50) ends up recursively calling the fib function 12586269025 times, whereas FibonacciTailRecursive only does 50 recursive calls.
No I can not get Mojo. Just wanted to verify the comment from