dimanche 10 juin 2018

One simple 'if' statement in Julia increases the run-time of my prime sieve by a factor of 15 – why?

I've been experimenting with various prime sieves in Julia with a view to finding the fastest. This is my simplest, if not my fastest, and it runs in around 5-6 ms on my 1.80 GHz processor for n = 1 million. However, when I add a simple 'If' statement to take care of the cases where n <= 1 or s (the start number) > n, the run-time increases by a factor of 15 to around 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)

Output with the 'if' statement commented out, as above, is:

5.752 ms (25 allocations: 2.95 MiB)

Output with the 'if' statement included is:

86.496 ms (2121646 allocations: 35.55 MiB)

I'm probably embarrassingly ignorant or being terminally stupid, but if someone could point out what I'm doing wrong it would be very much appreciated.

Aucun commentaire:

Enregistrer un commentaire