CODEWITHSUNDEEP
optimizationcompilationjulia
Remi.b
Remi.b

Reputation: 18219

Why doesn't the Julia compiler optimise this loop?

I know very little about compiling but I was surprised to see that Julia compiler doesn't optimize several processes.

Let's consider Julia (that is a Just-in-Time compiler) and let's consider these two pieces of code that do essentially the same thing.

n=1
@time for i = 1:10^8 n=n+1 end
elapsed time: 3.535394087 seconds (0 bytes allocated)

n=1
@time n=n+10^8
elapsed time: 6.599e-6 seconds (112 bytes allocated)

Why is a modern compiler not able to understand that this long loop will do nothing but adding 10^8 to n?

The following example is even more striking I think

n=1
@time for i = 1:10^9 n=n end
elapsed time: 3.496573198 seconds (0 bytes allocated)

Upvotes: 2

Views: 273

Answers (2)

user9712582
user9712582

Reputation: 1683

A let block can also be used to define a local variable n, avoiding globally scoped n. In this case it looks like the compiler computes the result at compile time.

@time let n = 1
        for i = 1:10^8
          n = n + 1
        end
        n
      end                    # 0.000000 seconds

code_native requires a function:

function f()
  let n = 1
    for i = 1:10^8
      n = n + 1
    end
    n
  end
end

code_native(f, ())

        push    rbp
        mov     rbp, rsp
        mov     eax, 100000001
        pop     rbp
        ret

Upvotes: 0

waTeim
waTeim

Reputation: 9225

This is a problem when executing in global scope and is connected with optimizing under conditions where types could change, but given the right circumstances, the situation changes. Constraining the evaluation within a function allows the compiler to do much more. Consider the same thing but in a function.

function f(n::Int64)
   x = 0;
   for i = 1:n
      x = x + 1;
   end
   return x;
end


julia> @time f(100)
elapsed time: 2.93e-6 seconds (80 bytes allocated)
100

julia> @time f(Int64(1e11))
elapsed time: 4.632e-6 seconds (112 bytes allocated)
100000000000

By checking the compiler output using code_native, you can see that the loop is optimized out

julia> code_native(f,(Int64,)) 

Source line: 6
    push    RBP
    mov RBP, RSP
    test    RDI, RDI
    jg  L15
    xor EDI, EDI
Source line: 6
L15:    mov RAX, RDI 
    pop RBP
    ret

Upvotes: 11

Related Questions