Performance comparison, Julia is a slower than Mojo, am I doing something wrong?

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?

2 Likes

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.

4 Likes

If you aren’t using 1.10, I would test it because it reduces this overhead quite a bit.

6 Likes

The Julia version I’m using is 1.9.3.

I get about 15.5s on 1.10, which is pretty comparable.

2 Likes

But we have different machine, do your computer have mojo?

1 Like

I get about 15.5s on 1.10, which is pretty comparable.

How can you expect ordinary user to use Julia 1.10 when it is not out yet AND is not approved for production critical results.

But we have different machine, do your computer have mojo?

Good point :slight_smile: No I can not get Mojo. Just wanted to verify the comment from @gbaraldi about this reducing the overhead (I also get about 21s on 1.9).

How can you expect ordinary user to use Julia 1.10 when it is not out yet AND is not approved for production critical results.

I’m not expecting anything of anyone.

29 Likes

Hey @Brian1,

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.

2 Likes

It is the same as before.

In case this was a sincere question, juliaup actually makes it quite straightforward to try out 1.10 :slight_smile:

In either case, I sincerely hope that neither of those fib implementations are used in production-critical contexts!

28 Likes

One of the things julia lacks is tail call optimization unlike (maybe) mojo, AFAIK.

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
8 Likes

It is still tail call but not tail-recursive call in that definition.

I get 29 seconds on 1.9.3, and 33 on 1.10.0-beta2, and pretty much the same as 1.10 on master.

But just to say how much useful is this benchmark, try

1 Like

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.

7 Likes

Is this true?!!!

  | | |_| | | | (_| |  |  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
2 Likes

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.

15 Likes

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.

13 Likes

Yes, I read a bit about the tail call optimizations before and didn’t want to imply that this is the number to be compared with the Mojo’s one.