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

General Usage Performance
,
42

The AI generated code wasn’t bad but insisted on a nested function:

function fib(n::Int64)::Int64
    function fib_helper(n::Int64, a::Int64, b::Int64)::Int64

I tried just to move the nested function out, and then the allocations went away, and that version is fastest yet (30% faster than the other Julia version, if I recall, I found this out immediately, just forgot to post until now).

I’m not sure this code might be faster than from Mojo, or at least match. You could say it’s unfair since it’s a different algorithm, but I’m not so sure about that. The matrix version for sure is, this seems like an optimization a “sufficiently clever” optimizer could do.

I usually wouldn’t expect the optimizer to do such transformation, i.e. add the helper function, nested or not, but it could, and if not if someone can be nerd-sniped to add a compiler step, that calls OpenAI API (already possible with a Julia package), that asks for “give me the verbatim version back of the following function, in case you can’t improve it, but otherwise a TCO version, which is allowed to have non-nested helper function”, then that would be great!

It’s not immediately obvious to me why having the helper nested mean allocations, maybe that can be improved in Julia. It’s semantically equivalent otherwise, except that name fib_helper will be added to the global scope, which is non-ideal but not too bad. I at least think that will not happen with a nested function (their point?). [An anonymous function can’t be used I think since recursive.]

1 Like
43

Sure you can. Looks a bit weird but shows no allocations for me:

function fib(n::Int64)::Int64
    fib_helper = (f, n::Int64, a::Int64, b::Int64) -> begin
        n <= 2 && return b
        f(f, n - 1, b, a + b)
    end
           
    n <= 2 && return 1
    n == 3 && return 2
    fib_helper(fib_helper, n - 1, 1, 2)
end
3 Likes
44

Or like this:

function fib(n::Int64)::Int64
    fib_helper = (n::Int64, a::Int64, b::Int64) -> begin
        n <= 2 && return b
        var"#self#"(n - 1, b, a + b)
    end

    n <= 2 && return 1
    n == 3 && return 2
    fib_helper(n - 1, 1, 2)
end

(Not that I recommend it.)

4 Likes
45

This topic bothers me. What optimization do we have to do at what level to achieve the same or better result with the proposed first solution?
I saw many different solution and an explanation, it is because of an “inlined” / “non-inlined” function extra overhead for GC housekeeping?

46

Algorithmically, do not use the naive algorithm for calculating Fibonacci numbers, use a different algorithm (that advice is independent of the language).

Engineeringly, for a given algorithm, and specifically for julia, use iterative forms of algorithms, not the recursive form. They have the same asymptotic scaling (big-O), but the iterative form has smaller constant overhead in julia (and is more amenable to vectorization and optimization in most languages).

4 Likes