Le dimanche 07 décembre 2014 à 08:31 -0800, remi.ber...@gmail.com a
écrit :
>
>
> Hey guys,
>
> I'm currently playing with some Eratosthenes sieving in Julia, and
> found a strange behavior of memory allocation.
> My naive sieve is as follows:
>
> #=
> Naive version of Erato sieve.
> * bitarray to store primes
> * only eliminate multiples of primes
> * separately eliminate even non-primes
> =#
> function erato1(n::Int)
> # Create bitarray to store primes
> primes_mask = trues(n)
> primes_mask[1] = false
>
> # Eliminate even numbers first
> for i = 4:2:n
> primes_mask[i] = false
> end
>
> # Eliminate odd non-primes numbers
> for i = 3:2:n
> if primes_mask[i]
> for j = (i + i):i:n
> primes_mask[j] = false
> end
> end
> end
>
> # Collect every primes in an array
> n_primes = countnz(primes_mask)
> primes_arr = Array(Int64, n_primes)
> collect1!(primes_mask, primes_arr)
> end
>
>
>
> With the collect1! function that takes a BitArray as argument and
> return an Array containing the primes numbers.
>
> function collect1!(primes_mask::BitArray{1}, primes_arr::Array{Int64,
> 1})
> prime_index = 1
> for i = 2:n
> if primes_mask[i]
> primes_arr[prime_index] = i
> prime_index += 1
> end
> end
> return primes_arr
> end
>
>
> The codes works, but is slow because of a lot of memory allocation at
> the line:
> primes_arr[prime_index] = i
>
>
> Here is an extract of the memory allocation profile
> (--track-allocation=user):
>
> - function collect1!(primes_mask::BitArray{1},
> primes_arr::Array{Int64, 1})
> 0 prime_index = 1
> -84934576 for i = 2:n
> 0 if primes_mask[i]
> 184350208 primes_arr[prime_index] = i
> 0 prime_index += 1
> - end
> - end
> 0 return primes_arr
> - end
>
>
>
>
> But, if I inline the definition of collect1! into the erato1, this is
> much faster and the allocation in the loop of collect disapears. Here
> is the code updated:
>
> function erato1(n::Int)
> # Create bitarray to store primes
> primes_mask = trues(n)
> primes_mask[1] = false
>
> # Eliminate even numbers first
> for i = 4:2:n
> primes_mask[i] = false
> end
>
> # Eliminate odd non-primes numbers
> for i = 3:2:n
> if primes_mask[i]
> for j = (i + i):i:n
> primes_mask[j] = false
> end
> end
> end
>
> # Collect every primes in an array
> n_primes = countnz(primes_mask)
> primes_arr = Array(Int64, n_primes)
> prime_index = 1
> for i = 2:n
> if primes_mask[i]
> primes_arr[prime_index] = i
> prime_index += 1
> end
> end
> return primes_arr
> end
>
>
> And the memory profile seems more reasonable:
>
> 0 n_primes = countnz(primes_mask)
> 92183392 primes_arr = Array(Int64, n_primes)
> 0 prime_index = 1
> 0 for i = 2:n
> 0 if primes_mask[i]
> 0 primes_arr[prime_index] = i
> 0 prime_index += 1
> - end
> - end
>
>
>
> So I'm wondering why the simple fact of inlining the code would remove
> the massive memory allocation when assigning to the array.
I think the difference may come from the fact that n is not a parameter
of collect1!(). As a general rule, avoid using global variables (or at
least mark them as const). Anyway it's much clearer when a function only
depends on its arguments, else it's very hard to follow what it does.
In the specific case of your example, Julia looks for n in the global
scope, not even in the parent function erato1(). So with a fresh
session, I get:
julia> erato1(100)
ERROR: n not defined
in collect1! at none:3
in erato1 at none:23
I'm not clear on how variable scoping works with function calls: the
manual says variables are inherited by inner scopes. But I guess it does
not apply to calling a function, only to defining it. Is that right? I
could add a word to the manual if it's deemed useful.
http://docs.julialang.org/en/latest/manual/variables-and-scoping/
Regards
