# Allocations when manipulating an iterator

**URL:** <https://discourse.julialang.org/t/allocations-when-manipulating-an-iterator/17405>\
**Category:** Performance\
**Created:** [November 11, 2018, 6:14pm UTC](https://discourse.julialang.org/t/allocations-when-manipulating-an-iterator/17405 "2018-11-11T18:14:13Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![miles.lubin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/miles.lubin/32/279_2.png) [@miles.lubin](https://discourse.julialang.org/u/miles.lubin)\
**Post date:** [November 11, 2018, 6:14pm UTC](https://discourse.julialang.org/t/allocations-when-manipulating-an-iterator/17405/1 "2018-11-11T18:14:13Z")

</div>

I distilled a significant performance issue in JuMP 0.19-alpha ([https://github.com/JuliaOpt/JuMP.jl/issues/1403#issuecomment-437630140](https://github.com/JuliaOpt/JuMP.jl/issues/1403#issuecomment-437630140)) to the following standalone example:

```julia
using BenchmarkTools

struct FlippedDictIterator{K,V}
    d::Dict{K,V}
end

reorder_iterator(::Nothing) = nothing
reorder_iterator(p::Pair, state::Int) = ((p.second, p.first), state)
reorder_iterator(x) = reorder_iterator(x...)

Base.iterate(fi::FlippedDictIterator) = reorder_iterator(iterate(fi.d))
Base.iterate(fi::FlippedDictIterator, state) = reorder_iterator(iterate(fi.d, state))

# The behavior isn't affected by these 4 lines, but I thought they could help.
Base.IteratorSize(fi::FlippedDictIterator) = Base.IteratorSize(fi.d)
Base.length(fi::FlippedDictIterator) = length(fi.d)
Base.IteratorEltype(fi::FlippedDictIterator) = Base.IteratorEltype(fi.d)
Base.eltype(fi::FlippedDictIterator{K,V}) where {K,V} = Tuple{V, K} 

function loop1(d)
    s = 0
    for (key, val) in d
        s += key * length(val)
    end
    return s
end

function loop2(d)
    s = 0
    for (val, key) in FlippedDictIterator(d)
        s += key * length(val)
    end
    return s
end

d = Dict{Int, String}()
for i in 1:1000
    d[i] = "test"
end

@show loop1(d)
@show loop2(d)

@btime loop1($d)
@btime loop2($d)

```

Yields (on Julia 1.0.1):

```julia
loop1(d) = 2002000
loop2(d) = 2002000
  14.323 μs (0 allocations: 0 bytes)
  20.913 μs (2000 allocations: 62.50 KiB)

```

Why are there two allocations per call to `iterate(fi::FlippedDictIterator, state)`?

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [November 11, 2018, 6:40pm UTC](https://discourse.julialang.org/t/allocations-when-manipulating-an-iterator/17405/2 "2018-11-11T18:40:40Z")

</div>

The optimiser has to chase `nothing` through too many levels: try

```julia
julia> Base.iterate(fi::FlippedDictIterator, state) = let ϕ = iterate(fi.d, state); if !( ϕ === nothing ) return reverse(ϕ[1]), ϕ[2] else return nothing end end

julia> Base.iterate(fi::FlippedDictIterator) = let ϕ = iterate(fi.d); if !( ϕ === nothing ) return reverse(ϕ[1]), ϕ[2] else return nothing end end

```

---

<div class="post-metadata">

**Author:** ![miles.lubin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/miles.lubin/32/279_2.png) [@miles.lubin](https://discourse.julialang.org/u/miles.lubin)\
**Post date:** [November 11, 2018, 8:31pm UTC](https://discourse.julialang.org/t/allocations-when-manipulating-an-iterator/17405/3 "2018-11-11T20:31:45Z")

</div>

That [worked](https://github.com/JuliaOpt/JuMP.jl/pull/1604). Thanks!

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [November 12, 2018, 7:10am UTC](https://discourse.julialang.org/t/allocations-when-manipulating-an-iterator/17405/4 "2018-11-12T07:10:58Z")

</div>

> [@mschauer](#):
>
> The optimiser has to chase `nothing` through too many levels

Can you please describe how you found this out? It would be useful to learn to do this systematically.

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [November 12, 2018, 8:38am UTC](https://discourse.julialang.org/t/allocations-when-manipulating-an-iterator/17405/5 "2018-11-12T08:38:03Z")

</div>

> systematically

Uh, unfortunately that was more intuition than science, but the gist is to bail early when an iterator returns `nothing` and not to delay handling of `nothing`s to later instances.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [November 12, 2018, 8:53am UTC](https://discourse.julialang.org/t/allocations-when-manipulating-an-iterator/17405/6 "2018-11-12T08:53:52Z")

</div>

Currently, my way of dealing with these things is to make small functions, stare at `@code_warntype`, and try patterns I have seen in `Base`; I was hoping I would learn something more organized 😉