# Why does my iterable allocate?

**URL:** <https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216>\
**Category:** Performance\
**Tags:** type-stability\
**Created:** [August 23, 2022, 5:46pm UTC](https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216 "2022-08-23T17:46:25Z")\
**Posts on this page:** 19\
**Page:** 1

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [August 23, 2022, 5:46pm UTC](https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216/1 "2022-08-23T17:46:25Z")

</div>

I ran into unexpected allocations in a complex iterator and was able to simplify it down into this MWE which uses complex logic to always yield nothing.

```julia
struct MyIter end

Base.iterate(::MyIter) = (nothing, [true])
function Base.iterate(::MyIter, i)
    for j in reverse(eachindex(i)) # 1:-1:1
        if i[j] # true
            for _ in 0:1 end # Empty loop
            return nothing, i
        end
    end
end

f(n) = for x in zip(MyIter(), 1:n) end

@time f(1_000_000)
# 0.024644 seconds (1.00 M allocations: 15.259 MiB)

```

I can eliminate the allocations in this case by deleting the empty loop. My question is why are there allocations in the first place?

---

<div class="post-metadata">

**Author:** ![giordano](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/giordano/32/2166_2.png) [@giordano](https://discourse.julialang.org/u/giordano)\
**Post date:** [August 23, 2022, 5:48pm UTC](https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216/2 "2022-08-23T17:48:19Z")

</div>

`[true]`?

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [August 23, 2022, 5:48pm UTC](https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216/3 "2022-08-23T17:48:24Z")

</div>

> [@Lilith](#):
>
> `(nothing, [true])`

`[true]` allocates a vector. You iterate 1 million times, you get 1 million allocations.

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [August 23, 2022, 6:06pm UTC](https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216/4 "2022-08-23T18:06:16Z")

</div>

That’s not it because that function is only called once:

```julia
Base.iterate(::MyIter) = (nothing, (println("Once"); [true]))
@time f(1_000_000)
#Once
# 0.023507 seconds (1.00 M allocations: 15.259 MiB)
```

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [August 23, 2022, 6:20pm UTC](https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216/5 "2022-08-23T18:20:08Z")

</div>

> [@Lilith](#):
>
> My question is why are there allocations in the first place?

The problem is that your `iterate` function is [not type-stable](https://docs.julialang.org/en/v1/manual/performance-tips/#Write-%22type-stable%22-functions):

```jl
julia> iterate(MyIter(), [true])
(nothing, Bool[1])

julia> iterate(MyIter(), [false])
nothing

```

That means that the compiler doesn’t know (until runtime) what _type_ the return value will be, and has to allocate a “box” to hold the return value + type tag on every call.

`@code_warntype iterate(MyIter(), [true])` would also have told you this.

Add a `return nothing, i` line to the end of the `iterate` function an the allocations go away.

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [August 23, 2022, 6:25pm UTC](https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216/6 "2022-08-23T18:25:10Z")

</div>

Is it possible to write a type stable `iterate` function for an iterable with 10 elements?

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [August 23, 2022, 6:33pm UTC](https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216/7 "2022-08-23T18:33:06Z")

</div>

> [@stevengj](#):
>
> The problem is that your `iterate` function is [not type-stable](https://docs.julialang.org/en/v1/manual/performance-tips/#Write-%22type-stable%22-functions):

My bad, `iterate` functions are essentially never type stable — they either return `nothing` or a tuple — but since there are only two possible return types the compiler handles it efficiently (or is supposed to).

---

<div class="post-metadata">

**Author:** ![giordano](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/giordano/32/2166_2.png) [@giordano](https://discourse.julialang.org/u/giordano)\
**Post date:** [August 23, 2022, 6:36pm UTC](https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216/8 "2022-08-23T18:36:54Z")

</div>

```julia
julia> Base.iterate(::MyIter) = (nothing, (true,))

julia> @time f(1_000_000)
  0.029855 seconds

```

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [August 23, 2022, 6:37pm UTC](https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216/9 "2022-08-23T18:37:11Z")

</div>

> [@Lilith](#):
>
> I can eliminate the allocations in this case by deleting the empty loop.

Yeah, that’s a bit weird.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [August 23, 2022, 6:40pm UTC](https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216/10 "2022-08-23T18:40:54Z")

</div>

> [@Lilith](#):
>
> I can eliminate the allocations in this case by deleting the empty loop.

Looks like it’s just the inlining heuristic (the empty loop is making the function “too complex” to automatically inline) — if you add `@inline` to your `iterate` definition then the allocations go away.

(I think that in order for the compiler to eliminate the allocations from the inherently non-typestable `iterate` function it needs to be inlined?)

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [August 23, 2022, 6:48pm UTC](https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216/11 "2022-08-23T18:48:39Z")

</div>

Thanks! That explains why my example here allocates and adding an `@inline` annotation fixes the real example that was too complicated to post here.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [August 23, 2022, 7:04pm UTC](https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216/12 "2022-08-23T19:04:19Z")

</div>

> [@stevengj](#):
>
> I think that in order for the compiler to eliminate the allocations from the inherently non-typestable `iterate` function it needs to be inlined?

Is this really the case? I was under the impression that small inferred type Unions were optimized to type-stable branches a.k.a. [Union-splitting](https://julialang.org/blog/2018/08/union-splitting/) (second to last paragraph mentions Union{Nothing, T} in particular). It seems like it would work even without inlining.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [August 23, 2022, 7:20pm UTC](https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216/13 "2022-08-23T19:20:45Z")

</div>

> [@Benny](#):
>
> I was under the impression that small inferred type Unions were optimized to type-stable branches a.k.a. [Union-splitting](https://julialang.org/blog/2018/08/union-splitting/) (second to last paragraph mentions Union{Nothing, T} in particular). It seems like it would work even without inlining.

The problem is maybe how the return value of the function is represented if it’s not inlined. If it’s not inlined, the function is compiled without knowing the context in which it is called — what does the return value look like for a `Union` if not a pointer to a box?

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [August 23, 2022, 7:53pm UTC](https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216/14 "2022-08-23T19:53:18Z")

</div>

giordano’s earlier comment just replaced `[true]` with `(true,)` in the original code, and that removes the allocations even though the Union{Nothing, T} instability is still there. `iterate` generally infers as Union{Nothing, T} so I expect this generally happens, just something unusual is happening this time.

> [@stevengj](#):
>
> what does the return value look like for a `Union` if not a pointer to a box?

I expect that there is something like that prior to the type-checking, type-stable branches. But I wouldn’t expect it to be reallocated each iteration. This also isn’t entirely because `[true]` is mutable, using a `Dict(1 => true)` and some associated edits to `iterate` only uses 4 allocations for the 1 dictionary (Julia v1.7.3 to be clear).

```julia
...
       Base.iterate(::MyIter) = (nothing, Dict(1 => true))
       function Base.iterate(::MyIter, i)
           for j in 1:-1:1 # Dict doesn't have eachindex
...
julia> @time f(1_000_000)
  0.003991 seconds (4 allocations: 432 bytes)

julia> @time Dict(1 => true)
  0.000004 seconds (4 allocations: 432 bytes)

```

EDIT: okay turns out the replacement of `reverse(eachindex(i))` in the original code with `1:-1:1`, `eachindex(i)`, or `1:length(i)` also reduces allocations to 1. Conversely, replacing `1:-1:1` in the Dict version above with `1:length(i)`, which itself should not allocate, makes `f(1_000_000)` do 1M allocations again. “Too complex to inline” really sounds like an explanation for how several single changes to `iterate` would cause an extra allocation, maybe Union-splitting type inference is a separate thing from however boxes are implemented. Also forget what I said about the `(true,)` version, the `@code_llvm f(1_000_000)` was just optimized to just returning nothing.

---

<div class="post-metadata">

**Author:** ![HenrikM](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrikm/32/17975_2.png) [@HenrikM](https://discourse.julialang.org/u/HenrikM)\
**Post date:** [March 22, 2025, 7:46pm UTC](https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216/15 "2025-03-22T19:46:48Z")

</div>

I think this should be in the documentation. I couldn’t make a non-allocating iterator until I read this. Now I moved the stepping code into an own function and the `Base.iterate` is an inlined three-liner that either returns `nothing` or calls the stepping function and returns a tuple.

---

<div class="post-metadata">

**Author:** ![matthias314](https://avatars.discourse-cdn.com/v4/letter/m/a88e4f/32.png) [@matthias314](https://discourse.julialang.org/u/matthias314)\
**Post date:** [March 22, 2025, 8:18pm UTC](https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216/16 "2025-03-22T20:18:45Z")

</div>

> [@HenrikM](#):
>
> I think this should be in the documentation.

I agree. On top of that, there are quite a few `iterate` methods in `Base.Iterators` that are defined without `@inline`. Their performance could be _much_ improved by adding `@inline`.

---

<div class="post-metadata">

**Author:** ![jakobnissen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakobnissen/32/13477_2.png) [@jakobnissen](https://discourse.julialang.org/u/jakobnissen)\
**Post date:** [March 22, 2025, 8:22pm UTC](https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216/17 "2025-03-22T20:22:36Z")

</div>

It would be better to improve the Julia ABI to stack allocate the return type instead of messing with inlining. That will probably happen at some point once the compiler devs has time to tackle it.

---

<div class="post-metadata">

**Author:** ![matthias314](https://avatars.discourse-cdn.com/v4/letter/m/a88e4f/32.png) [@matthias314](https://discourse.julialang.org/u/matthias314)\
**Post date:** [March 22, 2025, 9:17pm UTC](https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216/18 "2025-03-22T21:17:28Z")

</div>

> [@jakobnissen](#):
>
> That will probably happen at some point

Let’s hope that this point is not the point at infinity …

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [March 22, 2025, 11:25pm UTC](https://discourse.julialang.org/t/why-does-my-iterable-allocate/86216/19 "2025-03-22T23:25:47Z")

</div>

> [@HenrikM](#):
>
> I think this should be in the documentation.

Feel free to submit a PR.