Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

Is Julia not evaluating the Function?

I’m playing around with the Collatz conjecture (see below), and I have this function:

function txpo(max_n)
    for n ∈ 1:max_n
        x = n
        while x ≥ n  &&  x != 1
            x = iseven(x) ? x÷2 : 3x+1
        end
    end
end

On purpose I don’t return anything or check anything, to make it as fast as possible. And boy, is it fast… – actually too fast, I think.

using BenchmarkTools
@btime txpo(100_000_000_000_000_000_000_000_000_000_000_000_000)

2.337 ns (0 allocations: 0 bytes)

Running through 10^38 while loops takes only 2ns? Julia is fast, but I would be surprised if it was that fast. It seems like the code is not evaluated. Or what am I missing here?

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel


Collatz Conjecture
Take a whole number and build a series by using the following rule: if the number is even divide by 2; if the number is odd multiply by 3 and add 1. Conjecture: every series will end up in the loop 4-2-1-4.

>Solution :

Indeed, the whole function body is optimized out:

julia> function txpo(max_n)
           for n ∈ 1:max_n
               x = n
               while x ≥ n  &&  x != 1
                   x = iseven(x) ? x÷2 : 3x+1
               end
           end
       end
txpo (generic function with 1 method)

julia> @code_llvm txpo(100000000000)
;  @ REPL[1]:1 within `txpo`
define void @julia_txpo_179(i64 signext %0) #0 {
top:
;  @ REPL[1]:5 within `txpo`
  ret void
}

If you use 10^38, this only changes the function signature to accept 128-bit integers.

The LLVM IR code is basically the same as this Julia code:

julia_txpo_179(_0::Int64) = nothing

This makes perfect sense because why execute a function that doesn’t return anything that depends on its computations and has no side-effects?

Finally, the native code that your CPU executes is literally retq, a.k.a. "return to caller":

julia> @code_native txpo(100000000000)
    .section    __TEXT,__text,regular,pure_instructions
; ┌ @ REPL[1]:5 within `txpo`
    retq
    nopw    %cs:(%rax,%rax)
; └

julia> 
Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading