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

Question

我一直在朱莉娅试验各种主要的筛子,以期找到最快的.这是我最简单的,如果不是我最快的话,它在我的1.80 GHz处理器上运行大约5-6 ms,n = 100万.但是,当我添加一个简单的"if"语句来处理n <= 1或s(起始编号)> n的情况时,运行时间增加15倍到大约80-90 ms.

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代码性能最重要的问题.希望将来编译器会更聪明.