Unnecessary(?) tuple allocation

General Usage
1

Hi,

I’m implementing a Monte Carlo algorithm in which the Markov chain state is defined by a site index (in two dimensions to be more concrete). The site index performs a random walk according to some given rules. The current and suggested states types are, as far as I understand, NTuple{2,Int64}.
The code is quite involved but I believe I have managed to isolate the “problematic” section, see below. Basically, “hop” generates the site index of the next state and “jump” rejects or accepts.

function hop(index::NTuple{2,Int64},input_leg::Int64,output_leg::Int64,L::Int64,M::Int64)
    if input_leg==1
      if output_leg==2
        (index[1]==L ? 1 :index[1]+1,index[2])
      elseif output_leg==3
        (index[1],index[2]==2*M ? 1 : index[2]+1)
      else # output_leg==4
        (index[1]==L ? 1 :index[1]+1,index[2]==2*M ? 1 : index[2]+1)
      end
    elseif input_leg==2
      if output_leg==1
        (index[1]==1 ? L :index[1]-1,index[2])
      elseif output_leg==3
        (index[1]==1 ? L :index[1]-1,index[2]==2*M ? 1 : index[2]+1)
      else # output_leg==4
        (index[1],index[2]==2*M ? 1 : index[2]+1)
      end
    elseif input_leg==3
      if output_leg==1
        (index[1],index[2]==1 ? 2*M : index[2]-1)
      elseif output_leg==2
        (index[1]==L ? 1 :index[1]+1,index[2]==1 ? 2*M : index[2]-1)
      else # output_leg==4
        (index[1]==L ? 1 :index[1]+1,index[2])
      end
    else # input_leg==4
      if output_leg==1
        (index[1]==1 ? L :index[1]-1,index[2]==1 ? 2*M : index[2]-1)
      elseif output_leg==2
        (index[1],index[2]==1 ? 2*M : index[2]-1)
      else # output_leg==3
        (index[1]==1 ? L :index[1]-1,index[2])
      end
    end
end

function jump()
  index=(5,6)
  i=0
  while i<100000
    nn=hop(index,rand(1:4),rand(1:4),4,6)
    if rand()<0.5
      index=nn
    end
    i+=1
  end
end

jump()

It seems like a lot of memory is being allocated (see below a julia run using --track-allocation=user)

      - function jump()
        -   index=(5,6)
   724746   i=0
        0   while i<100000
        0     nn=hop(index,rand(1:4),rand(1:4),4,6)
        0     if rand()<0.5
        0       index=nn
        -     end
        0     i+=1
        -   end
        - end
        - 
        - jump()

I’m pretty sure that the allocation report doesn’t correctly indicate the line in which memory allocation occurs. My best bet is that “nn” is being allocated at each step. Is that expected? If so, how to avoid this?

Thanks!

Snir

2

I get 0 allocations on 0.5 and 0.6. I think --track-allocation=user removes inlining which can cause spurious allocations.

3

Thanks!
Indeed, when using “@time” I see no allocated memory.
So I guess my question is somewhat different now – how can I tell if and where memory is actually allocated?
In the full code, which is unfortunately too long to display meaningfully, I do see substantial memory allocated when using “@time”

4

Ok, I believe I have managed to reproduce the spurious memory allocation.
I now define the state of the random walk inside a type. This leads to a linearly increasing memory allocation with respect to the number of steps.

See below,

type State
  index::NTuple{2,Int64}
end

function hop(index::NTuple{2,Int64},input_leg::Int64,output_leg::Int64,L::Int64,M::Int64)
    if input_leg==1
      if output_leg==2
        (index[1]==L ? 1 :index[1]+1,index[2])
      elseif output_leg==3
        (index[1],index[2]==2*M ? 1 : index[2]+1)
      else # output_leg==4
        (index[1]==L ? 1 :index[1]+1,index[2]==2*M ? 1 : index[2]+1)
      end
    elseif input_leg==2
      if output_leg==1
        (index[1]==1 ? L :index[1]-1,index[2])
      elseif output_leg==3
        (index[1]==1 ? L :index[1]-1,index[2]==2*M ? 1 : index[2]+1)
      else # output_leg==4
        (index[1],index[2]==2*M ? 1 : index[2]+1)
      end
    elseif input_leg==3
      if output_leg==1
        (index[1],index[2]==1 ? 2*M : index[2]-1)
      elseif output_leg==2
        (index[1]==L ? 1 :index[1]+1,index[2]==1 ? 2*M : index[2]-1)
      else # output_leg==4
        (index[1]==L ? 1 :index[1]+1,index[2])
      end
    else # input_leg==4
      if output_leg==1
        (index[1]==1 ? L :index[1]-1,index[2]==1 ? 2*M : index[2]-1)
      elseif output_leg==2
        (index[1],index[2]==1 ? 2*M : index[2]-1)
      else # output_leg==3
        (index[1]==1 ? L :index[1]-1,index[2])
      end
    end
end


function next_move!(state)
  nn=hop(state.index,rand(1:4),rand(1:4),4,6)
  if rand()<0.5
    state.index=nn
  end
end

function jump(n)
  c_state=State((5,6))
  i=0
  while i<n
    next_move!(c_state)
    i+=1
  end
end

jump(10)
@time jump(1000)
@time jump(10000)
@time jump(100000)

and the allocated memory –

  0.000185 seconds (622 allocations: 23.125 KB)
  0.001100 seconds (4.98 k allocations: 155.781 KB)
  0.012340 seconds (50.06 k allocations: 1.528 MB)

What goes wrong?

Thanks

5

To note, on Julia 0.6 this does not allocate.

6

I think the problem is that next_move! has an unstable return type. Depending on the value of rand(), the if statement either evaluates to a tuple (right hand side of assignment) or nothing (no else branch). Since that is the last expression of the function that’s what’s returned. Since the return value is discarded, there’s no reason for this to matter, which Julia 0.6 understands but apparently not Julia 0.5. The workaround is simple though, add an explicit return nothing to the end of next_move!.

Addendum: @code_warntype next_move!(State((5, 6))) gives an indication of the problem.

1 Like
7

Thanks!

Indeed, that helps.
Unfortunately, going back to the full code it still seems like there is a sizeable memory allocation. It is very difficult to pinpoint the problem since --track-allocation=user produces very unclear results (similar to the ones I have cited above).
I have explicitly verified that all function are “type safe” both in terms of allocated variables and return variables.
Any ideas on how to debug this?

More generally, if any one of the developers is interested in the full code (it is not that long) I will be happy to provide it.

Thanks