# The default iteration interface can cause memory leak?
**URL:** https://discourse.julialang.org/t/the-default-iteration-interface-can-cause-memory-leak/88986
**Category:** Internals & Design
**Tags:** iterative, iterators
**Created:** [October 20, 2022, 12:27am UTC](https://discourse.julialang.org/t/the-default-iteration-interface-can-cause-memory-leak/88986 "2022-10-20T00:27:10Z")
**Posts on this page:** 6
**Page:** 1
### Author:  [@singularitti](https://discourse.julialang.org/u/singularitti)
#### Post date: [October 20, 2022, 12:27am UTC](https://discourse.julialang.org/t/the-default-iteration-interface-can-cause-memory-leak/88986/1 "2022-10-20T00:27:10Z")
I just read about the post [“Iterate on it”](https://mikeinnes.io/2020/06/04/iterate) which says the current implementation of `iterate` could cause a memory leak since the `xs` must remain alive over the entire loop and that is uneconomic for linked lists:
```julia
next = iterate(xs)
while next != nothing
x, state = next
# do something with x
next = iterate(xs, state)
end
```
And the author suggested using the following protocol:
```julia
itr = iterator(xs)
while true
next = iterate(itr)
next == nothing && break
x, itr = next
# do something with x
end
```
Is it still true as of 2022? If so, will there be an improvement in the future?
---
### Author:  [@Sukera](https://discourse.julialang.org/u/Sukera)
#### Post date: [October 20, 2022, 6:24am UTC](https://discourse.julialang.org/t/the-default-iteration-interface-can-cause-memory-leak/88986/2 "2022-10-20T06:24:42Z")
This behavior is not a memory leak, since the object is (intentionally) still accessible. A memory leak would be if you can’t access the object anymore in your code, but the corresponding memory is not being freed. This being uneconomic for linked lists is unfortunate, but not really a problem (as the article says - it’s a minor optimization at most).
What I’m missing from the article though his some more details on this paragraph:
> In many cases, this is a minor missed optimisation opportunity. If you have very large functional data structures, [even infinite ones](https://github.com/MikeInnes/Lazy.jl) (the functional equivalent of an indefinitely long generator / channel), it’s a disaster.
What I think the author is getting at is that in their particular implementation of lazy datastructures, they’ve chosen to represent infinite lists as linked lists and would like them freed eagerly when iterating over them (but only in same cases, and cache the computed elements in others?). So knowing when to throw elements away and when not to is a property that can’t be deduced just from looking at the loop itself.
It also seems to me that it would have been better to represent such infinite lists as almost-no-state iterables, where the produced list elements are passed along in the `state` variable of `iterate`, instead of caching them explicitly in the `List` struct itself.
---
### Author:  [@thautwarm](https://discourse.julialang.org/u/thautwarm)
#### Post date: [October 20, 2022, 7:13am UTC](https://discourse.julialang.org/t/the-default-iteration-interface-can-cause-memory-leak/88986/3 "2022-10-20T07:13:41Z")
This is not a memory leak because Julia still release the memory if it got unused.
> [@singularitti](#):
>
> `xs` must remain alive over the entire loop
Julia’s iteration interface does not cause more memory assumption than other programming languages (Python/Java/C++/C#). Just like in other programming languages, Julia’s iterable object itself (`xs` in your example) should usually keep alive during the iteration, and a specified iteration interface creates a helper object (traditionally called `iterator`) to perform the following 4 operations:
1. `getiterator`: create an iterator from the iterable object
2. `current`: get the current element from the iterator
3. `movenext`: move the iterator to the next
4. `hasnext`: check if the iterator has ended
Java uses exactly 4 methods for the above 4 operations, C# and Python uses 2 methods (combine `movenext`, `hasnext` and `current` together).
Julia also uses 2 methods (`iterate(itr)` and `iterate(itr, state)`), which is not that different from those in other languages. This is to say, the following statement might not be appropriate:
> [@singularitti](#):
>
> that is uneconomic for linked lists:
`state` here can be regarded as the `iterator`, and we can implement the iteration interface for LinkedList this way:
```julia
# return iterator
function iterate(itr)
if itr is empty
return nothing
else
return (the first element, the second node of the linked list)
end
end
# hasnext + movenext + current
function iterate(itr #= unused =#, node)
if node has next
return (the value of the node, the next node)
else
return nothing
end
end
#
```
Such implementation iterates LinkedLists in O(n) time.
Specifically, using above implementation, Julia is smart enough to not remain `xs` alive by inlining the code. As can be seen, the `itr` argument from `iterate(itr, node)` method is unused, hence disappear after inlined. If there is no use of `itr` after the iteration, Julia can release `itr` before stopping the iteration, if needed.
---
### Author:  [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)
#### Post date: [October 20, 2022, 11:32am UTC](https://discourse.julialang.org/t/the-default-iteration-interface-can-cause-memory-leak/88986/4 "2022-10-20T11:32:47Z")
I think this is a complete non-issue? I.e. both protocols are mostly equivalent under code transformations that the julia compiler is good at. Consider:
```julia
#julia iteration
next = vanilla_iterate(xs)
while next != nothing
x, state = next
# do something with x
next = vanilla_iterate(xs, state)
end
#mikeInnes' original proposal
itr = mi_iterator(xs)
while true
next = mi_iterate(itr) #problematic line
next == nothing && break
x, itr = next
# do something with x
end
#mikeInnes proposal (improved)
itr = mi_iterator(xs)
next = mi_iterate(itr)
while next != nothing
x, itr = next
# do something with x
next = mi_iterate(itr)
end
```
Now suppose we have a code construction that works well with the mikeInnes proposal. Then we can simply define
```julia
@inline vanilla_iterator(xs) = mi_iterate(mi_iterator(xs))
@inline vanilla_iterate(xs, state) = mi_iterate(state)
```
If you plug that into the snippet for vanilla iteration, you get:
```julia
itr = mi_iterator(xs)
next = mi_iterate(itr)
while next != nothing
x, state = next
# do something with x
next = mi_iterate(state)
end
```
So that’s awesome! Julia iteration is at least as good / flexible / performant as Mike’s proposal in cases where type inference works.
Now next: Suppose julia moved to my modification of Mike’s proposal. Then we modify old-style iteration in the following way:
```julia
struct IterHelper{T} item::T end
@inline mi_iterator(xs) = IterHelper(xs)
@inline mi_iterate(wrappedXS::IterHelper) = begin
xs = wrappedXS.item
next = vanilla_iterate(xs)
if next == nothing
nothing
else
nextItem, nextState = next
(nextItem, (xs, nextState))
end
end
@inline mi_iterate(itr) = begin
xs, state = itr
next = vanilla_iterate(xs, state)
if next == nothing
nothing
else
nextItem, nextState = next
(nextItem, (xs, nextState))
end
end
```
then let’s plug that into the modified iteration protocol proposal:
```julia
itr = IterHelper(xs)
next = vanilla_iterate(xs)
if next != nothing
x, state = next
next = (x, (xs, state))
end
while next != nothing
x, itr = next
# do something with x
xs, state = itr
next = vanilla_iterate(xs, state)
if next != nothing
nextItem, nextState = next
next = (nextItem, (xs, nextState))
end
end
```
It is quite clear how the compiler will continue to simplify that and end up with the original vanilla julia iteration protocol.
If you try the same with Mike’s original proposal, then you will encounter a problem in the marked problematic line
```julia
next = mi_iterate(itr) #problematic line
```
The problem is that `itr` is either of type `IterHelper` or of type `typeof((xs, state))`. This is a problematic type instability, because the necessary compiler transforms (e.g. loop rotate) to double this line and make it type stable afaiu only happen after type inference. Maybe julia emits good enough code with suboptimal type inference that llvm can fix that; maybe not. I wouldn’t bet on it.
But maybe the compiler improved in that regard since I last looked?
cc @MikeInnes since you disabled comments on your blog post.
---
### Author:  [@MikeInnes](https://discourse.julialang.org/u/MikeInnes)
#### Post date: [October 20, 2022, 1:30pm UTC](https://discourse.julialang.org/t/the-default-iteration-interface-can-cause-memory-leak/88986/5 "2022-10-20T13:30:07Z")
Languages have to be a bit cautious about what they promise as an optimisation. Whatever benefit is given when the compiler works, is taken away when it fails. It’s usually not the end of the world to lose a constant speed factor, but changes in time or space complexity are a bigger deal: they can make the difference between a valid, working program and a failing one.
This is an example of that. Sure, in simple cases the list will almost always be optimised away, but it’s not guaranteed, and it’s not hard to foil that optimisation. Julia’s heuristics are also not formally part of its guaranteed API/spec, so if you rely on this then in principle a change of compiler version could break your code (admittedly that’s unlikely in practice).
I don’t want to overstate the case, though. This is (just about) a real technical problem, but also a minor one. I don’t think anyone desperately wants to build web servers that iterate over lazy lists of requests or whatever in Julia. Stateful, self-destructing iterators are idiomatic and unproblematic. The blog post is more about obscure language design nerdery than any kind of critical flaw. The vast majority of people need not worry about it.
---
### Author:  [@Mason](https://discourse.julialang.org/u/Mason)
#### Post date: [October 20, 2022, 10:55pm UTC](https://discourse.julialang.org/t/the-default-iteration-interface-can-cause-memory-leak/88986/6 "2022-10-20T22:55:39Z")
Inspired by the blog post and [this issue](https://github.com/JuliaLang/julia/issues/46802) I made [SetupIterators.jl](https://github.com/MasonProtter/SetupIterator.jl) which I beleive addresses the concerns brought up here and is compatible with Julia’s current lowering with no language changes required