Memory allocation issue with iterator type

question
memory-allocation

#1

Happy labor day!

Anyone around that could help with the following issue? Consider this simple snippet:

# DOMAIN

abstract type AbstractDomain{T<:Real,N} end

struct RegularGrid{T<:Real,N} <: AbstractDomain{T,N}
  dims::Dims{N}
  origin::NTuple{N,T}
  spacing::NTuple{N,T}

  function RegularGrid{T,N}(dims, origin, spacing) where {N,T<:Real}
    @assert all(dims .> 0) "dimensions must be positive"
    @assert all(spacing .> 0) "spacing must be positive"
    new(dims, origin, spacing)
  end
end

RegularGrid{T}(dims::Dims{N}) where {N,T<:Real} =
  RegularGrid{T,N}(dims, (zeros(T,length(dims))...), (ones(T,length(dims))...))

RegularGrid{T}(dims::Vararg{<:Integer,N}) where {N,T<:Real} = RegularGrid{T}(dims)

npoints(grid::RegularGrid) = prod(grid.dims)

# PATH

abstract type AbstractPath{D<:AbstractDomain} end

struct RandomPath{D<:AbstractDomain} <: AbstractPath{D}
  domain::D
  permut::Vector{Int}

  function RandomPath{D}(domain, permut) where {D<:AbstractDomain}
    @assert length(permut) == npoints(domain) "incorrect dimension"
    new(domain, permut)
  end
end
RandomPath(domain) = RandomPath{typeof(domain)}(domain, randperm(npoints(domain)))
Base.start(p::RandomPath)       = Base.start(p.permut)
Base.next(p::RandomPath, state) = Base.next(p.permut, state)
Base.done(p::RandomPath, state) = Base.done(p.permut, state)
Base.length(p::RandomPath)      = npoints(p.domain)

# MAIN SCRIPT

grid = RegularGrid{Float64}(100,100)
path = RandomPath(grid)

for location in path
  location
end

Profile.clear_malloc_data()

for location in path
  location
end

All it does is loop over a grid in random order. However, I am wondering why the done method of the iterator is allocating memory:

        - struct RandomPath{D<:AbstractDomain} <: AbstractPath{D}
        -   domain::D
        -   permut::Vector{Int}
        - 
        -   function RandomPath{D}(domain, permut) where {D<:AbstractDomain}
        0     @assert length(permut) == npoints(domain) "incorrect dimension"
        0     new(domain, permut)
        -   end
        - end
        0 RandomPath(domain) = RandomPath{typeof(domain)}(domain, randperm(npoints(domain)))
        - Base.start(p::RandomPath)       = Base.start(p.permut)
        0 Base.next(p::RandomPath, state) = Base.next(p.permut, state)
   654016 Base.done(p::RandomPath, state) = Base.done(p.permut, state)
        - Base.length(p::RandomPath)      = npoints(p.domain)

cc: @kristoffer.carlsson, @cstjean


#2

What @kristoffer.carlsson is saying is that this is not a simple snippet. It requires understanding your entire code base. You’re essentially asking for contributors, which is fine, but I wouldn’t expect a lot of random people to start jumping in to contribute for you off of this. A simple example should isolate what’s going on to not use a bunch of functionality in the package.

But in this case we know that the allocations are because you have inferrability issues that have already been mentioned, at least in part due to untyped fields in types which has already been shown.


#3

Thank you @ChrisRackauckas, I am not asking for contributions, sorry if it is looking like it is.

I will copy/paste the definitions inside of the package to outside of it and see if it makes a difference.


#4

Fixed the example @ChrisRackauckas, it is self-contained now.


#5

That works! But the way it’s reduced now, it looks like using globals causes the allocation. If I rewrite it as

function f(path)
    for location in path
        location
    end
end

using BenchmarkTools
@benchmark f(path)

then it reports no allocation.