It might be useful to put a bit about Julia being lexically scoped into the
manual and refer to the Wikipedia article on scope.
— John
> On Dec 7, 2014, at 9:05 AM, Milan Bouchet-Valat <nalimi...@club.fr> wrote:
>
> 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
>
