if-statement - Julia 中的一个简单的 'if' 语句将我的主筛的运行时间增加了 15 倍——为什么？

Question

我一直在 Julia 中试验各种主要筛子，以期找到最快的筛子。这是我最简单的，如果不是我最快的话，它在我的 1.80 GHz 处理器上运行大约 5-6 毫秒，n = 100 万。但是，当我添加一个简单的“if”语句来处理 n <= 1 或 s(起始编号)> n 的情况时，运行时间会增加 15 倍，达到 80-90 毫秒左右。

using BenchmarkTools

function get_primes_1(n::Int64, s::Int64=2)::Vector{Int64}
    #=if n <= 1 || s > n
        return []
    end=#
    sieve = fill(true, n)
    for i = 3:2:isqrt(n) + 1
        if sieve[i]
            for j = i ^ 2:i:n
                sieve[j]= false
            end
        end
    end
    pl = [i for i in s - s % 2 + 1:2:n if sieve[i]]
    return s == 2 ? unshift!(pl, 2) : pl
end

@btime get_primes_1(1_000_000)

如上所述，注释掉“if”语句的输出是:

5.752 ms (25 allocations: 2.95 MiB)

包含“if”语句的输出是:

86.496 ms (2121646 allocations: 35.55 MiB)

我可能非常无知或非常愚蠢，但如果有人能指出我做错了什么，我们将不胜感激。

Answer 1

这个函数的问题在于，当你的函数中出现闭包时，Julia 编译器在类型推断方面存在问题。在这种情况下，闭包是一个理解，问题是 if声明使sieve只能有条件地定义。

移动sieve可以看到向上:

function get_primes_1(n::Int64, s::Int64=2)::Vector{Int64}
    sieve = fill(true, n)
    if n <= 1 || s > n
        return Int[]
    end
    for i = 3:2:isqrt(n) + 1
        if sieve[i]
            for j = i ^ 2:i:n
                sieve[j]= false
            end
        end
    end
    pl = [i for i in s - s % 2 + 1:2:n if sieve[i]]
    return s == 2 ? unshift!(pl, 2) : pl
end

但是，这使得 sieve也将在 n<1 时创建我猜你想避免 :)。

你可以通过包装sieve来解决这个问题在 let像这样阻止:

function get_primes_1(n::Int64, s::Int64=2)::Vector{Int64}
    if n <= 1 || s > n
        return Int[]
    end
    sieve = fill(true, n)
    for i = 3:2:isqrt(n) + 1
        if sieve[i]
            for j = i ^ 2:i:n
                sieve[j]= false
            end
        end
    end
    let sieve = sieve
        pl = [i for i in s - s % 2 + 1:2:n if sieve[i]]
        return s == 2 ? unshift!(pl, 2) : pl
    end
end

或者避免像这样的内部闭包:

function get_primes_1(n::Int64, s::Int64=2)::Vector{Int64}
    if n <= 1 || s > n
        return Int[]
    end
    sieve = fill(true, n)
    for i = 3:2:isqrt(n) + 1
        if sieve[i]
            for j = i ^ 2:i:n
                sieve[j]= false
            end
        end
    end
    pl = Int[]
    for i in s - s %2 +1:2:n
        sieve[i] && push!(pl, i)
    end
    s == 2 ? unshift!(pl, 2) : pl
end

现在您可能会问如何检测此类问题并确保某些解决方案可以解决这些问题？答案是使用 @code_warntype在一个函数上。在您的原始功能中，您会注意到 sieve是Core.Box这表明存在问题。

参见 https://github.com/JuliaLang/julia/issues/15276了解详情。总的来说，在我看来，这是 Julia 代码性能最重要的问题，很容易被忽略。希望将来编译器会更聪明。