Одно простое утверждение «если» в Юлии увеличивает время работы моего основного сита в 15 раз - почему?

Question

Я экспериментировал с различными простыми ситами в Юлии, чтобы найти самое быстрое.Это мой самый простой, если не самый быстрый, и он работает примерно за 5-6 мс на моем процессоре с частотой 1,80 ГГц для n = 1 миллиона.Тем не менее, когда я добавляю простой оператор 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.В целом, на мой взгляд, это самая важная проблема с производительностью кода Джулии, которую легко не заметить.Надеюсь, что в будущем компилятор будет умнее с этим.

Answer 2

Редактировать: Мое предложение фактически не помогает.Я пропустил вашу выходную аннотацию, так что тип возвращаемого значения, кажется, все-таки правильно выведен.На данный момент я в тупике.

Оригинальный ответ:

Проблема не в том, что существует оператор if, а в том, что вы вводите нестабильность типавнутри этого if заявления.Вы можете прочитать о нестабильности типов в разделе производительности руководства Julia здесь .

Пустой массив, определенный следующим образом: [], имеет тип, отличный от вектора целых чисел:

> typeof([1,2,3])
Array{Int64,1}

> typeof([])
Array{Any,1}

Компилятор не может предсказать, каким будет тип вывода функции, и поэтому выдает защитный медленный код.

Попробуйте изменить

return []

на

return Int[]