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 <[email protected]> wrote: > > Le dimanche 07 décembre 2014 à 08:31 -0800, [email protected] 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 >
