Le dimanche 07 décembre 2014 à 09:12 -0800, John Myles White a écrit :
> It might be useful to put a bit about Julia being lexically scoped
> into the manual and refer to the Wikipedia article on scope.
Ah, that's the term I needed. Opened a pull request here:
https://github.com/JuliaLang/julia/pull/9267
Regards
> — 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
> >
