Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Using item from Array{Any} as bound in for loop results in O(N) allocation #5297

Closed
nalimilan opened this issue Jan 4, 2014 · 9 comments
Closed

Comments

@nalimilan
Copy link
Member

This is something funny which bit me when implementing a frequency table function. It seems that when an element from an Array of type Any is used to construct the range to loop over, like in for i in 1:x[1], x[1] is accessed at each iteration, which means the allocated memory is proportional to the number of iterations. I would have expected some overhead, but only once, to get the value and construct the range.

This is easy to fix by using properly typed arrays, but it was so unexpected that it took me some time to find out where the allocation was coming from.

It doesn't seem to make sense to access x[1] on each iteration, since the actual value is not even used: adding x[1] = 1 in the loop does not have any effect.

Illustration of the problem:

julia> function test1()
           x = {1000000, 2}

           for i in 1:x[1]
           end
       end
test1 (generic function with 1 method)

julia> function test2()
           x = [1000000, 2]

           for i in 1:x[1]
           end
       end
test2 (generic function with 1 method)

julia> precompile(test1, ())

julia> precompile(test2, ())

julia> 

julia> @allocated test1()
15991904

julia> @allocated test2()
64
@Keno
Copy link
Member

Keno commented Jan 4, 2014

The problem is not the allocation of the range. The problem is the allocation of i. Since the compiler cannot possibly know ahead of time, it has to be boxed on every iteration.

@nalimilan
Copy link
Member Author

Ah, indeed. That's the whole problem...

Though there's still something strange: storing the value in an intermediate variable with a type annotation has no effect.

function test3()
    x = {1000000, 2}
    n::Int = x[1]

    for i in 1:n
    end
end
julia> precompile(test3, ())
julia> @allocated test3()
15991936

@nalimilan
Copy link
Member Author

Oh, and maybe it would be possible to box the value only the first time? I understand that for each iteration the check will be slower, but since the value of the upper bound does not change, why do you need to allocate it again and again?

@Keno
Copy link
Member

Keno commented Jan 4, 2014

That last one looks like it should work. Not sure what the problem with that is. I'll have a look later.

@timholy
Copy link
Member

timholy commented Jan 4, 2014

Put the ::Int after the x[1], i.e., x[1]::Int.

--Tim

On Saturday, January 04, 2014 08:59:00 AM Milan Bouchet-Valat wrote:

Ah, indeed. That's the whole problem...

Though there's still something strange: storing the value in an intermediate
variable with a type annotation has no effect. ```julia
function test3()
x = {1000000, 2}
n::Int = x[1]

for i in 1:n
end

end
julia> precompile(test3, ())
julia> @allocated test3()
15991936


---
Reply to this email directly or view it on GitHub:
https://github.com/JuliaLang/julia/issues/5297#issuecomment-31582888

@JeffBezanson
Copy link
Member

n::Int should work too; I think that is issue #271

@nalimilan
Copy link
Member Author

@timholy @JeffBezanson Indeed, with x[1]::Int it works.

Do you think my hypothesis that it would be possible to box the value only once make sense, or should we close the issue?

@JeffBezanson
Copy link
Member

We could check the possible "escape" bit to see if the box is free to be reused, and then overwrite it instead of allocating a new one. But that's pretty fancy.

@JeffBezanson
Copy link
Member

Closing since this behavior is not unexpected.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants