时间戳

首页 > 解决方案 > 为什么这两段 Julia 代码的表现如此不同？

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

问题描述

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)

标签： julia

解决方案

这是关于 Julia 使用平方幂对文字的编译时优化。如果可以仅通过平方幂或幂为 0、1、2、3 来达到指数，则 Julia 能够进行优化。我相信这是通过降低x^p到x^Val{p}整数p和使用编译器专业化（或内联加上一种元编程，我不确定这里的正确术语是什么，但它就像你会在 Lisp 中找到的东西一样；类似的技术用于源代码-to-source auto-differentiation in Julia，请参阅Zygote.jlp ）技术，如果是 0、1、2、3 或 2 的幂，则将代码降低到常数。

Julia 降低10^8到内联 literal_pow（然后power_by_squaring），这被降低到一个常量，然后Julia 降低constant * 10以获得另一个常量，然后意识到所有的 while 循环都是不必要的，并删除了循环等等，所有这些都在 compile-time。

如果你改变in你会10^8看到它会在运行时评估数字和循环。但是，如果您替换为or您将看到它将在编译时处理所有计算。如果指数是 2 的幂，我认为 julia 并没有专门设置为编译时优化，而是编译器证明能够优化（将代码降低到常量）代码只是为了这种情况。10^7c110^810^410^2

1,2,3的情况p在 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
;}

Seef()原来只是一个常数，而g()将在运行时评估内容。

如果你想深入挖掘，我认为 julia 围绕这个提交开始了这个整数求幂技巧。

编辑：让我们编译时优化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^9inc2替换为ipow(10,9)，并享受编译时优化的强大功能。

另请参阅此问题以了解平方幂。

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

推荐阅读