In solving Problem 10 from Project Euler manually (instead of simply using Primes
), I implemented a naive Sieve of Eratosthenes in Julia using BitVector
. It produces the correct output, but when I checked its type stability using @code_warntype
, I found that i
was being allocated as Core.Box
, which affects the type of psum
, and that in turn throws the type stability of the whole function away. This is the code used:
function primesum(limit::T = 2_000_000) where T<:Integer
#easy way: using Primes; sum(primes(limit))
#hard way:
is_prime_num = BitVector(limit)
is_prime_num .= true
psum = zero(limit)
for i in 2:limit
if is_prime_num[i]
psum += i
multiples_of_i = [k*i for k in 2:(limit÷i)]
is_prime_num[multiples_of_i] .= false
end
end
psum
end
And here is the Variables part of the code_warntype
output (full output here):
Variables:
#self#::#primesum
limit::Int64
#46::##46#47
i::Core.Box
multiples_of_i::Any
#temp#@_6::Int64
is_prime_num::BitArray{1}
psum::Any
J::Any
#temp#@_10::Any
Overall, a lot of types in the code (including the function's return type) are left as either Any
or a where _
type.
I was able to improve speed (almost 10x) and memory (~3x) by changing the for
loop line to for i::T in 2:limit
- then, i
still gets set as a Core.Box
, but that gets typeassert
ed to Int64 and doesn't propagate the instability to psum
and others. But I'm more interested in why Julia couldn't infer i
's type than in speeding up this specific code. I'm used to type instabilities making sense at least in retrospect, but this one seems pretty clear and simple to infer, so I'd like to know where there is type ambiguity here.
A temporary solution is to wrap
i
inlet
block around the comprehension (I have also proposed some small tweaks in your code that are minor cleanups - I have left creation ofmultiples_of_i
as this was a core of your question but actually using this variable is also inefficient - it would be better to setis_prime_num
vector tofalse
in appropriate places using a loop):Hopefully in the long run the issue https://github.com/JuliaLang/julia/issues/15276 will be fixed and this will not be needed.