Indeed, this is the case. That n is coming from global scope and isn't a constant when the code is generated, so the generated code has to be able to deal with the type of n being anything at all. The type of n affects the type of i, so the compiler also can't know the type of i and must, just to be safe, heap allocate each value of i.
On Sun, Dec 7, 2014 at 12:05 PM, 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 > >
