# Unnecessary(?) tuple allocation

**URL:** <https://discourse.julialang.org/t/unnecessary-tuple-allocation/3589>\
**Category:** General Usage\
**Created:** [May 8, 2017, 10:44am UTC](https://discourse.julialang.org/t/unnecessary-tuple-allocation/3589 "2017-05-08T10:44:52Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![Snir\_Gazit](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/snir_gazit/32/11027_2.png) [@Snir\_Gazit](https://discourse.julialang.org/u/Snir_Gazit)\
**Post date:** [May 8, 2017, 10:44am UTC](https://discourse.julialang.org/t/unnecessary-tuple-allocation/3589/1 "2017-05-08T10:44:52Z")

</div>

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.

```julia
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)

```julia
      - 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

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [May 8, 2017, 11:52am UTC](https://discourse.julialang.org/t/unnecessary-tuple-allocation/3589/2 "2017-05-08T11:52:19Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Snir\_Gazit](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/snir_gazit/32/11027_2.png) [@Snir\_Gazit](https://discourse.julialang.org/u/Snir_Gazit)\
**Post date:** [May 8, 2017, 12:30pm UTC](https://discourse.julialang.org/t/unnecessary-tuple-allocation/3589/3 "2017-05-08T12:30:53Z")

</div>

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”

---

<div class="post-metadata">

**Author:** ![Snir\_Gazit](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/snir_gazit/32/11027_2.png) [@Snir\_Gazit](https://discourse.julialang.org/u/Snir_Gazit)\
**Post date:** [May 10, 2017, 2:20pm UTC](https://discourse.julialang.org/t/unnecessary-tuple-allocation/3589/4 "2017-05-10T14:20:32Z")

</div>

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,

```julia
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 –

```julia
  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

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [May 10, 2017, 2:50pm UTC](https://discourse.julialang.org/t/unnecessary-tuple-allocation/3589/5 "2017-05-10T14:50:30Z")

</div>

To note, on Julia 0.6 this does not allocate.

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [May 10, 2017, 3:07pm UTC](https://discourse.julialang.org/t/unnecessary-tuple-allocation/3589/6 "2017-05-10T15:07:46Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Snir\_Gazit](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/snir_gazit/32/11027_2.png) [@Snir\_Gazit](https://discourse.julialang.org/u/Snir_Gazit)\
**Post date:** [May 10, 2017, 9:02pm UTC](https://discourse.julialang.org/t/unnecessary-tuple-allocation/3589/7 "2017-05-10T21:02:55Z")

</div>

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