julia - 为什么这两段 Julia 代码的表现如此不同？

Question

function c1()
        x::UInt64 = 0
        while x<= (10^8 * 10)
                x+=1
        end
end

function c2()
        x::UInt64 = 0
        while x<= (10^9)
                x+=1
        end
end

function c3()
        x::UInt64 = 0
        y::UInt64 = 10^8 * 10
        while x<= y
                x+=1
        end
end

function c4()
        x::UInt64 = 0
        y::UInt64 = 10^9
        while x<= y
                x+=1
        end
end

应该是一样的吧？

@time c1()

0.019102 seconds (40.99 k allocations: 2.313 MiB)

@time c1()

0.000003 seconds (4 allocations: 160 bytes)

@time c2()

9.205925 seconds (47.89 k allocations: 2.750 MiB)

@time c2()

9.015212 seconds (4 allocations: 160 bytes)

@time c3()

0.019848 seconds (39.23 k allocations: 2.205 MiB)

@time c3()

0.000003 seconds (4 allocations: 160 bytes)

@time c4()

0.705712 seconds (47.41 k allocations: 2.719 MiB)

@time c4()

0.760354 seconds (4 allocations: 160 bytes)

Answer 1

这是关于 Julia 使用乘方幂对文字进行编译时优化。如果指数可以通过单独的乘方幂或幂为 0、1、2、3 来达到，Julia 能够进行优化。我相信这是通过降低 x^p 完成的至 x^Val{p}对于整数 p并使用编译器特化(或内联加上一种元编程，我不确定这里的正确术语是什么，但它就像你会在 Lisp 中找到的东西；类似的技术用于 Julia 中的源到源自动区分，参见 Zygote.jl ) 如果 p 将代码降低到常量的技术是 0、1、2、3 或 2 的幂。

Julia 降低 10^8内联 literal_pow (然后是 power_by_squaring )，这被降低到一个常数然后 Julia 降低 constant * 10获得另一个常量，然后意识到所有的 while 循环都是不必要的，并在编译时删除循环等等。

如果您更改 10^8与 10^7在 c1您将看到它将在运行时评估数字和循环。但是，如果替换 10^8与 10^4或 10^2您将看到它将在编译时处理所有计算。如果指数是 2 的幂，我认为 julia 没有专门设置为编译时优化，而是编译器结果证明能够针对这种情况优化(将代码降低为常量)代码。
p的情况is 1,2,3 在 Julia 中是硬编码的。这是通过将代码降低到 literal_pow 的内联版本再次优化的。然后编译特化。

您可以使用 @code_llvm和 @code_native宏来看看发生了什么。咱们试试吧。

julia> f() = 10^8*10
julia> g() = 10^7*10

julia> @code_native f()
.text
; Function f {
; Location: In[101]:2
    movl    $1000000000, %eax       # imm = 0x3B9ACA00
    retq
    nopw    %cs:(%rax,%rax)
;}

julia> @code_native g()
.text
; Function g {
; Location: In[104]:1
; Function literal_pow; {
; Location: none
; Function macro expansion; {
; Location: none
; Function ^; {
; Location: In[104]:1
    pushq   %rax
    movabsq $power_by_squaring, %rax
    movl    $10, %edi
    movl    $7, %esi
    callq   *%rax
;}}}
; Function *; {
; Location: int.jl:54
    addq    %rax, %rax
    leaq    (%rax,%rax,4), %rax
;}
    popq    %rcx
    retq
;}

见 f()原来只是一个常数，而 g()将在运行时评估东西。

我认为 Julia 在 this commit 附近开始了这个整数取幂技巧如果你想挖掘更多。

编辑:让我们编译时优化 c2
我还准备了一个函数来计算整数整数指数， Julia 也将用它优化非 2 的幂指数。不过，我不确定它在所有情况下都是正确的。

@inline function ipow(base::Int, exp::Int)
    result = 1;
    flag = true;
    while flag
        if (exp & 1  > 0)
            result *= base;
        end
        exp >>= 1;
        base *= base;
        flag = exp != 0
    end

    return result;
end

现在更换您的 10^9在 c2与 ipow(10,9) ，并享受编译时优化的力量。

另见 this question为幂次方。

请不要按原样使用此函数，因为它会尝试内联所有求幂，无论它是否包含文字。你不会想要那样的。