<p>In Graydon Hoare's blogpost <a href="https://graydon2.dreamwidth.org/307291.html" rel="noreferrer">The Rust I Wanted Had No Future</a>, they state that:</p>
<blockquote>
<p>Iteration used to be by stack / non-escaping coroutines, which we also called &quot;interior&quot; iteration, as opposed to &quot;exterior&quot; iteration by pointer-like things that live in variables you advance. Such coroutines are now finally supported by LLVM (they weren't at the time) and are actually a fairly old and reliable mechanism for a linking-friendly, not-having-to-inline-tons-of-library-code abstraction for iteration.</p>
</blockquote>
<p>Why would external iterators require lots of inlining to be performant relative to internal iteration?</p>

<optimization><iterators>
Why would external iteration require lots of code inlining relative to internal iteration?
CC BY-SA 4.0
2023-08-06T13:54:11.110Z
This is likely a Rust question and not a programming languages question because it cannot be answered in general. It has a lot to do with how iteration on containers is done and there are examples that implementing iterator interfaces still results in good code generation. Hence, it should be moved to stack overflow and tagged as rust.
feldentm
CC BY-SA 4.0
2023-08-06T15:46:55.743Z
@feldentm Questions about the design or implementation of specific languages [are on-topic here](https://langdev.meta.stackexchange.com/q/96/89). We already have a [tag:rust] tag for questions about the design and implementation of Rust; I'm not convinced this question *is* specific to Rust, but if it is then that is fine. If the answer is *"this only matters in Rust, because ..."* then that is fine too.
kaya3
<p>Internal iteration has good codegen. Consider this simple iteration:</p>
<pre class="lang-csharp prettyprint-override"><code>    void InternalIterationOnArray(string[] array, Action&lt;string&gt; action)
    {
        for (int index = 0; index &lt; length; index++)
        {
            var current = array[index];
            action(current);
        }
    }
</code></pre>
<p>There are only efficient operations here. In constrast, with external iteration, all the work is done in the functions that implement your iterator's interface.
Consider the C# desugared equivalent of a foreach loop:</p>
<pre class="lang-csharp prettyprint-override"><code>    void ExternalIterationOnArray(string[] array, Action&lt;string&gt; action)
    {
        List&lt;int&gt;.Enumerator e = array.GetEnumerator();
        string current;
        while (e.MoveNext())
        {
            current = e.Current;
            action(current);
        }
        // (try-finally and IDisposable omitted)
    }
</code></pre>
<p><code>IEnumerable.GetEnumerator()</code>: Creates an iterator object (for example,  <a href="https://github.com/dotnet/runtime/blob/main/src/libraries/System.Private.CoreLib/src/System/Array.Enumerators.cs" rel="nofollow noreferrer">ArrayEnumerator</a>) that contains a reference to <code>array</code> and the declaration of <code>index</code>.</p>
<p><code>Iterator.MoveNext()</code>: Does <code>index++</code> and <code>index &lt; length</code>.</p>
<p><code>Iterator.Current</code>: Does <code>array[i]</code>.</p>
<p>To get something as efficient as the internal iteration, ideally you'd want not only this scattered code to be inlined all in one place, but you'd also want the iterator object to be allocated on the stack and not on the heap, which could also avoid having a separate reference to <code>array</code>.</p>

CC BY-SA 4.0
2023-08-06T02:57:26.697Z
2023-08-06T04:27:10.510Z
2023-08-06T04:27:10.510Z
Eldritch Conundrum
CC BY-SA 4.0
2023-08-06T03:16:54.980Z
I think this answer needs to address the stack coroutine side of the question and not just point at procedural for loops directly.
Michael Homer
CC BY-SA 4.0
2023-08-06T03:38:17.063Z
I don't know about LLVM's support for stack coroutines and its impact on inlining. But I would love to read a more detailed answer about it :)
Eldritch Conundrum
CC BY-SA 4.0
2023-08-06T03:46:31.187Z
I *think* it doesn't address the question, then, because I don't believe it's asking about that trivial case, and this doesn't address *any* sort of internal iteration regardless.
Michael Homer
CC BY-SA 4.0
2023-08-06T04:07:40.283Z
If by trivial case you mean simple iteration on an array, I think it's the most relevant example for this question, because inlining is about performance, and virtually all programs benefit from optimized iteration on arrays.
Eldritch Conundrum
CC BY-SA 4.0
2023-08-06T04:17:41.887Z
But procedural for loops are not what "internal iteration" is, nor what is being described as "interior iteration" in the quote or referenced post; internal iterators are what you may have seen in Ruby, for example (though theirs don't exactly match the old Rust design). I don't think that example is relevant at all because it is not related at all to what's in the question.
Michael Homer
CC BY-SA 4.0
2023-08-06T04:23:11.820Z
I clarified my code examples. I believe the first example actually is how one would implement internal iteration on an array. I also believe it showcases why would external iterators require inlining to be performant relative to internal iteration.
Eldritch Conundrum
CC BY-SA 4.0
2023-08-06T10:01:46.980Z
Inlining `InternalIterationOnArray` into the calling code isn't as performance-critical because it's a once-per-loop cost, not once-per-element. However, I think you're right: as written, my example is unfair because `ExternalIterationOnArray` should be using `current` directly instead of calling `action`.
Eldritch Conundrum
CC BY-SA 4.0
2023-08-07T20:36:48.717Z
Your answer seems to be using "internal" and "external" in the opposite sense than the Hoare quote. He says that external iteration is the form with an iteration variable that you increment.
Barmar
CC BY-SA 4.0
2023-08-07T23:17:20.333Z
@Barmar it's more about where the increment is done, see https://langdev.stackexchange.com/questions/2670/what-are-interior-iteration-and-exterior-iteration
Eldritch Conundrum
<h3>Context</h3>
<p>First of all, Graydon clarified the implementation they were thinking of <a href="https://old.reddit.com/r/ProgrammingLanguages/comments/141qm6g/the_rust_i_wanted_had_no_future_graydon_hoare/jna4zu3/" rel="noreferrer">on reddit</a>:</p>
<blockquote>
<p>This is in fact what I was talking about -- not separate stacks, but a persistent portion of the shared stack carved out for the iteratee. actually implemented in rustboot, but abandoned along the way when we moved to rustc, in part because llvm didn't support anything like it at the time. It does now.</p>
</blockquote>
<p>The idea is to avoid function call overhead <em>without</em> inlining by jumping back and forth between coroutine code and iterator code during iteration.</p>
<h3>External woes: stack of calls</h3>
<p>It is common, in Rust, to create <em>pipelines</em> of iterators. Imagine something like:</p>
<pre><code> collection
     .into_iter()    //  Returns Person elements
     .enumerate()    //  Returns a tuple (index, Person)
     .filter(|i| i.1.age &gt;= 18)
     .filter(|i| i.1.address.zip % 100 == 63)
     .for_each(|i| send_letter(i.0, i.1)); // or a for loop, for external.
</code></pre>
<p>With external iteration, however, this will result in:</p>
<ul>
<li>N calls to the age predicate.</li>
<li>N' calls to the zip predicate.</li>
<li>N'' calls to the send letter callback.</li>
<li>N'' calls to Filter's next (zip).</li>
<li>N' calls to Filter's next (age).</li>
<li>N calls to Enumerate next.</li>
<li>N calls to Iterator next.</li>
<li>(3 calls to iterator methods (1 each): enumerate, filter, filter, no for_each)</li>
</ul>
<p>With internal iteration (naive), this will result in:</p>
<ul>
<li>N calls to the age predicate.</li>
<li>N' calls to the zip predicate.</li>
<li>N'' calls to the send letter callback.</li>
<li>N' calls to the wrapper around the zip predicate + tail.</li>
<li>N calls to the wrapper around the age predicate + tail.</li>
<li>(4 calls to iterator methods (1 each): enumerate, filter, filter, for_each)</li>
</ul>
<p>With internal iteration (Graydon style), this will result in:</p>
<ul>
<li>N calls to the age predicate.</li>
<li>N' calls to the zip predicate.</li>
<li>N'' calls to the send letter callback.</li>
<li>(4 calls to iterator methods (1 each): enumerate, filter, filter, for_each)</li>
</ul>
<p>So, just comparing the number of non-user function calls:</p>
<ul>
<li>External: N + N + N' + N'' + 3.</li>
<li>Internal (naive): N + N' + 4.</li>
<li>Internal (Graydon): 4.</li>
</ul>
<p>The number of function calls of external iteration is just much greater... especially when compared to Graydon-style internal iteration.</p>
<p>Since inlining is <em>the</em> optimization which allows eliminating function call overhead, it benefits external iteration disproportionally.</p>
<h3>External woes: lost context</h3>
<p>This is best illustrated, I find, using the <a href="https://doc.rust-lang.org/std/iter/struct.Chain.html" rel="noreferrer"><code>Chain</code></a> iterator. A <code>Chain</code> iterator is simple: it takes two iterators, and chains them together in a single one, first yielding all elements of the first then yielding all elements of the second.</p>
<p>With internal iteration, it's quite simple; in Python:</p>
<pre><code>class Chain:
    ...

    def for_each(self, callback):
        self.first.for_each(callback)
        self.second.for_each(callback)
</code></pre>
<p>And that's it.</p>
<p>With external iteration, however, every time the next element is queried, one must check which iterator to yield from:</p>
<pre><code>class Chain:
    ...

    def next(self):
        if self.use_second == False:
            n = self.first.next()

            if n:
                return n

            self.use_second = True

        return self.second.next()
</code></pre>
<p>The reason is that for any complex iteration protocol, the <em>context</em> is lost in between each query to <code>next</code>, and therefore (1) must be saved internally and (2) must be reconstructed with every call.</p>
<p>The only way to avoid saving + reconstructing at every call... is to eliminate the call by inlining it, and then have the optimizer optimize those out<sup>1</sup>.</p>
<p>Once again, inlining benefits external iteration more than it does internal iteration.</p>
<p><sup>1</sup> <em>As of LLVM 16, LLVM still doesn't optimize chain iterators <code>next</code> calls, and instead keeps a single loop with a flag check at every iteration...</em></p>
<h3>Appendix: why External?</h3>
<p>One key advantage of External iteration manifests itself with non-trivial loops: since using external iteration the control-flow is in the hands of the caller, they can do <em>a lot</em>: <code>continue</code>/<code>break</code> (potentially to other loops), <code>return</code>, <code>zip</code>, etc...</p>
<p>External iteration offers more flexibility, and the greater implementation complexity cost does not necessarily result in a performance loss with contemporary optimizers -- at least on the simpler iterators. This makes it a good trade-off, but it <em>is</em> a trade-off.</p>

CC BY-SA 4.0
2023-08-08T09:42:21.407Z
2023-08-08T09:42:21.407Z
Matthieu M.
# Why would external iteration require lots of code inlining relative to internal iteration?
Posted by: username_0 on 2023-08-06
In Graydon Hoare's blogpost [The Rust I Wanted Had No Future](https://graydon2.dreamwidth.org/307291.html), they state that:

> Iteration used to be by stack / non-escaping coroutines, which we also called "interior" iteration, as opposed to "exterior" iteration by pointer-like things that live in variables you advance. Such coroutines are now finally supported by LLVM (they weren't at the time) and are actually a fairly old and reliable mechanism for a linking-friendly, not-having-to-inline-tons-of-library-code abstraction for iteration.

Why would external iterators require lots of inlining to be performant relative to internal iteration?
**Tags:** optimization iterators
> **Comments:**
> **username_1**: This is likely a Rust question and not a programming languages question because it cannot be answered in general. It has a lot to do with how iteration on containers is done and there are examples that implementing iterator interfaces still results in good code generation. Hence, it should be moved to stack overflow and tagged as rust.  
> **username_2**: @feldentm Questions about the design or implementation of specific languages [are on-topic here](https://langdev.meta.stackexchange.com/q/96/89). We already have a [tag:rust] tag for questions about the design and implementation of Rust; I'm not convinced this question *is* specific to Rust, but if it is then that is fine. If the answer is *"this only matters in Rust, because ..."* then that is fine too.  
---
## 2 answers
### Answer by username_6 on 2023-08-08. Score: 5 | Accepted answer
Context
First of all, Graydon clarified the implementation they were thinking of on reddit:

This is in fact what I was talking about -- not separate stacks, but a persistent portion of the shared stack carved out for the iteratee. actually implemented in rustboot, but abandoned along the way when we moved to rustc, in part because llvm didn't support anything like it at the time. It does now.

The idea is to avoid function call overhead without inlining by jumping back and forth between coroutine code and iterator code during iteration.
External woes: stack of calls
It is common, in Rust, to create pipelines of iterators. Imagine something like:
 collection
     .into_iter()    //  Returns Person elements
     .enumerate()    //  Returns a tuple (index, Person)
     .filter(|i| i.1.age >= 18)
     .filter(|i| i.1.address.zip % 100 == 63)
     .for_each(|i| send_letter(i.0, i.1)); // or a for loop, for external.

With external iteration, however, this will result in:

N calls to the age predicate.
N' calls to the zip predicate.
N'' calls to the send letter callback.
N'' calls to Filter's next (zip).
N' calls to Filter's next (age).
N calls to Enumerate next.
N calls to Iterator next.
(3 calls to iterator methods (1 each): enumerate, filter, filter, no for_each)

With internal iteration (naive), this will result in:

N calls to the age predicate.
N' calls to the zip predicate.
N'' calls to the send letter callback.
N' calls to the wrapper around the zip predicate + tail.
N calls to the wrapper around the age predicate + tail.
(4 calls to iterator methods (1 each): enumerate, filter, filter, for_each)

With internal iteration (Graydon style), this will result in:

N calls to the age predicate.
N' calls to the zip predicate.
N'' calls to the send letter callback.
(4 calls to iterator methods (1 each): enumerate, filter, filter, for_each)

So, just comparing the number of non-user function calls:

External: N + N + N' + N'' + 3.
Internal (naive): N + N' + 4.
Internal (Graydon): 4.

The number of function calls of external iteration is just much greater... especially when compared to Graydon-style internal iteration.
Since inlining is the optimization which allows eliminating function call overhead, it benefits external iteration disproportionally.
External woes: lost context
This is best illustrated, I find, using the Chain iterator. A Chain iterator is simple: it takes two iterators, and chains them together in a single one, first yielding all elements of the first then yielding all elements of the second.
With internal iteration, it's quite simple; in Python:
class Chain:
    ...

    def for_each(self, callback):
        self.first.for_each(callback)
        self.second.for_each(callback)

And that's it.
With external iteration, however, every time the next element is queried, one must check which iterator to yield from:
class Chain:
    ...

    def next(self):
        if self.use_second == False:
            n = self.first.next()

            if n:
                return n

            self.use_second = True

        return self.second.next()

The reason is that for any complex iteration protocol, the context is lost in between each query to next, and therefore (1) must be saved internally and (2) must be reconstructed with every call.
The only way to avoid saving + reconstructing at every call... is to eliminate the call by inlining it, and then have the optimizer optimize those out1.
Once again, inlining benefits external iteration more than it does internal iteration.
1 As of LLVM 16, LLVM still doesn't optimize chain iterators next calls, and instead keeps a single loop with a flag check at every iteration...
Appendix: why External?
One key advantage of External iteration manifests itself with non-trivial loops: since using external iteration the control-flow is in the hands of the caller, they can do a lot: continue/break (potentially to other loops), return, zip, etc...
External iteration offers more flexibility, and the greater implementation complexity cost does not necessarily result in a performance loss with contemporary optimizers -- at least on the simpler iterators. This makes it a good trade-off, but it is a trade-off.
---
### Answer by username_3 on 2023-08-06. Score: 1
Internal iteration has good codegen. Consider this simple iteration:
    void InternalIterationOnArray(string[] array, Action action)
    {
        for (int index = 0; index < length; index++)
        {
            var current = array[index];
            action(current);
        }
    }

There are only efficient operations here. In constrast, with external iteration, all the work is done in the functions that implement your iterator's interface.
Consider the C# desugared equivalent of a foreach loop:
    void ExternalIterationOnArray(string[] array, Action action)
    {
        List.Enumerator e = array.GetEnumerator();
        string current;
        while (e.MoveNext())
        {
            current = e.Current;
            action(current);
        }
        // (try-finally and IDisposable omitted)
    }

IEnumerable.GetEnumerator(): Creates an iterator object (for example,  ArrayEnumerator) that contains a reference to array and the declaration of index.
Iterator.MoveNext(): Does index++ and index < length.
Iterator.Current: Does array[i].
To get something as efficient as the internal iteration, ideally you'd want not only this scattered code to be inlined all in one place, but you'd also want the iterator object to be allocated on the stack and not on the heap, which could also avoid having a separate reference to array.
> **Comments:**
> **username_4** (2023-08-06): I think this answer needs to address the stack coroutine side of the question and not just point at procedural for loops directly.  
> **username_3** (2023-08-06): I don't know about LLVM's support for stack coroutines and its impact on inlining. But I would love to read a more detailed answer about it :)  
> **username_4** (2023-08-06): I *think* it doesn't address the question, then, because I don't believe it's asking about that trivial case, and this doesn't address *any* sort of internal iteration regardless.  
> **username_3** (2023-08-06): If by trivial case you mean simple iteration on an array, I think it's the most relevant example for this question, because inlining is about performance, and virtually all programs benefit from optimized iteration on arrays.  
> **username_4** (2023-08-06): But procedural for loops are not what "internal iteration" is, nor what is being described as "interior iteration" in the quote or referenced post; internal iterators are what you may have seen in Ruby, for example (though theirs don't exactly match the old Rust design). I don't think that example is relevant at all because it is not related at all to what's in the question.  
> **username_3** (2023-08-06): I clarified my code examples. I believe the first example actually is how one would implement internal iteration on an array. I also believe it showcases why would external iterators require inlining to be performant relative to internal iteration.  
> **username_3** (2023-08-06): Inlining `InternalIterationOnArray` into the calling code isn't as performance-critical because it's a once-per-loop cost, not once-per-element. However, I think you're right: as written, my example is unfair because `ExternalIterationOnArray` should be using `current` directly instead of calling `action`.  
> **username_5** (2023-08-07): Your answer seems to be using "internal" and "external" in the opposite sense than the Hoare quote. He says that external iteration is the form with an iteration variable that you increment.  
> **username_3** (2023-08-07): @Barmar it's more about where the increment is done, see https://langdev.stackexchange.com/questions/2670/what-are-interior-iteration-and-exterior-iteration  
---
