The implementation of iterators in C# and its consequences (part 1)

re: The implementation of iterators in C# and its consequences (part 1)

Chris — Tue, 12 Aug 2008 17:26:11 GMT

Because weird things might happen with MoveNext() if it's called more than once?

re: The implementation of iterators in C# and its consequences (part 1)

Chris — Tue, 12 Aug 2008 17:27:03 GMT

(...Past the end of the enumerated collection?)

re: The implementation of iterators in C# and its consequences (part 1)

Damien — Tue, 12 Aug 2008 17:30:21 GMT

Because whatever state it was in might have a non-deterministic path that sometimes leads to a yield break, and other times to a yield return?

re: The implementation of iterators in C# and its consequences (part 1)

Damien — Tue, 12 Aug 2008 17:36:37 GMT

Ooh. Plus, whatever code is in the last but one state might have side effects (might be what Chris was implying)

re: The implementation of iterators in C# and its consequences (part 1)

Gabe — Tue, 12 Aug 2008 19:09:14 GMT

If you don't change the state to n2, you can keep calling MoveNext() on it and always redo the last state.

re: The implementation of iterators in C# and its consequences (part 1)

bahbar — Tue, 12 Aug 2008 19:23:30 GMT

I believe Damien and Chris nailed it.

MoveNext is supposed to keep returning false once it started to do so.

From MSDN "If MoveNext passes the end of the collection, the enumerator is positioned after the last element in the collection and MoveNext returns false. When the enumerator is at this position, subsequent calls to MoveNext also return false"

Imagine the for loop condition is i != limit rather than <=... Then MoveNext will return false then start to return true again.

re: The implementation of iterators in C# and its consequences (part 1)

hova — Tue, 12 Aug 2008 19:59:10 GMT

What do you plan to do with all the excercises when you write your next book? Put a workbook or test section at the end of each chapter?

Why some teacher might even use that book to teach students with!

re: The implementation of iterators in C# and its consequences (part 1)

Michael — Tue, 12 Aug 2008 20:39:58 GMT

> The C# method ... just borrows the stack of the caller

Interesting... When I first saw how iterators were implemented in C#, I saw the "yield" and immediately assumed coroutines. So, I'm surprised to learn .NET iterators are really closer to Java iterator objects than "true" (coroutine-based or thread-based) iterators; it's just that the nice syntax of C# hides this from us.

re: The implementation of iterators in C# and its consequences (part 1)

Eric Lippert — Tue, 12 Aug 2008 22:06:55 GMT

Indeed. You can use iterators as poor-mans coroutines; in fact, the managed robotics framework that Microsoft ships does exactly that!

Thanks for doing this Raymond; this is better than our internal documentation. :-)

re: The implementation of iterators in C# and its consequences (part 1)

philq — Wed, 13 Aug 2008 00:02:29 GMT

Iterators are a really great feature. The only drawback is that making recursive calls in them is n^2. We need a 'yield foreach' statement! Eric please implement this feature immediately.

re: The implementation of iterators in C# and its consequences (part 1)

Ajai Shankar — Wed, 13 Aug 2008 00:19:24 GMT

Hi Raymond

Strange I came across only now across this series on enumerators & fibers.

I'd written an MSDN article way back in '03 on how to get fiber based enumerators to work with .NET using an undocumented hosting API.

Implementing Coroutines for .NET by Wrapping the Unmanaged Fiber API (http://msdn.microsoft.com/en-us/magazine/cc164086.aspx)

Of course now there is a dire warning at the beginning of the article saying it is not supported by Microsoft :-)

Ajai Shankar

Not actually a .Net blog.

Igor Levicki — Wed, 13 Aug 2008 02:28:20 GMT

Not actually a .Net blog but it might occasionally dip its toes in C# it seems.

[Why is the blog's subtitle "Not actually a .NET blog"? -Raymond]

Iterators and the yield statement - Rory Primrose

Iterators and the yield statement - Rory Primrose — Wed, 13 Aug 2008 03:00:42 GMT

PingBack from http://neovolve.com/archive/2008/08/13/iterators-and-the-yield-statement.aspx

re: The implementation of iterators in C# and its consequences (part 1)

Ian — Wed, 13 Aug 2008 03:09:21 GMT

.net week makes the baby jesus cry.

re: The implementation of iterators in C# and its consequences (part 1)

Miral — Wed, 13 Aug 2008 05:29:08 GMT

My favourite iterator trick is the synchronised foreach:

public IEnumerator<T> GetEnumerator()

{

lock (SyncRoot)

{

foreach (T item in BaseList)

{

yield return item;

}

(Not 100% sure that's the right code; I did it from memory.)

Of course there are drawbacks to doing something like the above, but it *does* mean that your foreach loops on that collection won't get borked by other threads modifying the collection. (It might kill your performance, though.)

My second favourite trick is the way you can now define multiple kinds of enumeration trivially:

// .. in some grid/matrix-like class:

public IEnumerable<T> AcrossThenDown

{

get

{

for (int rowIndex = 0; rowIndex < RowCount; ++rowIndex)

{

for (int colIndex = 0; colIndex < ColCount; ++colIndex)

{

yield return this[row, col];

}

public IEnumerable<T> DownThenAcross

{

get

{

for (int colIndex = 0; colIndex < ColCount; ++colIndex)

{

for (int rowIndex = 0; rowIndex < RowCount; ++rowIndex)

{

yield return this[row, col];

}

re: The implementation of iterators in C# and its consequences (part 1)

Miral — Wed, 13 Aug 2008 05:33:07 GMT

Gah, stuffed that last example up a bit (row => rowIndex, col => colIndex), and the formatting sucks. Still, you get the idea :) (Oh, for an edit button...)

re: The implementation of iterators in C# and its consequences (part 1)

wtroost — Wed, 13 Aug 2008 11:22:48 GMT

Thanks for the great post, I always wondered how the yield statement worked its magic!

re: The implementation of iterators in C# and its consequences (part 1)

SRS — Wed, 13 Aug 2008 11:55:16 GMT

I really wish Sun would put 'yield' into Java. Oh, and fix generics.

Just saying.

A closer look at yield – part 3

Stuart Leeks — Wed, 13 Aug 2008 15:37:24 GMT

This was only going to be two posts, but after my last post I’d been mulling over a post that looks at

re: The implementation of iterators in C# and its consequences (part 1)

Rob — Wed, 13 Aug 2008 17:49:47 GMT

Shouldn't public IEnumerator<int> CountFrom(int start) [fourth line]

public IEnumerable<int> CountFrom(int start)

[Fixed. Thanks. -Raymond]

re: The implementation of iterators in C# and its consequences (part 1)

Ian Marteens — Thu, 14 Aug 2008 11:12:32 GMT

Actually, the translation get trickier when there are try/finally blocks, either explicit or implicit, in the iterator block. That's because you must track iteration state in case the Dispose method of the enumerator must be called. That's also the reason why try/catch is not allowed in iterators: translation becomes even trickier.

There are a couple of enhancements that Microsoft could apply to iterators:

1- With a good peephole optimizer, the target code generated for the compiler can be greatly simplified. Most compiled code have a lot of redundant state assignments that a peephole optimizer could erase. I have done some tests on this with Freya, my own pet language and compiler for .NET.

2- A very simple extension for iterators: allow "yield" to receive a whole iterator call. It would translate as a foreach/yield combo statement, and it would be great for composing iterators, such as in recursive iterators. For simpler composite iterators, we have LINQ, of course.

3- I have read a paper from Microsoft Research where they fiddle with a IEnumerable extension for handling recursive iterators in an efficient manner. It would be great to see that research applied to the .NET compilers. Of course, it's not an easy task.

re: The implementation of iterators in C# and its consequences (part 1)

Andrew — Thu, 14 Aug 2008 13:07:49 GMT

"...Instead it just borrows the stack of the caller, and anything that it needs to save across calls to MoveNext are stored in a helper object (which goes on the heap rather than the stack)..."

I used to think that implementation of an iterator as a value type is more efficient in terms of performance (say, generic list and dictionary have their iterators as structs).

And I used to think that "yield return" just fails to expose a struct since that should be public (to aviod boxing) and that's not appropriate for autogenerated classes.

But Raymond seems to say that heap-based iterators are better, why? Because of possible nesting?

[I believe most people expect reference semantics for iterators, not value semantics.
e = o.GetEnumerator(); DoSomething1(e); DoSomething2(e);
I suspect most people would expect DoSomething2 to continue where DoSomething1 left off. I don't see how nesting is involved. -Raymond]

Visual Studio Links #65

Visual Studio Hacks — Thu, 14 Aug 2008 16:28:50 GMT

My latest in a series of the weekly, or more often, summary of interesting links I come across related to Visual Studio. The Visual C++ Team blog has a post about IconWorkshop Lite , which is available as a free download. Greg Duncan posted a link to

re: The implementation of iterators in C# and its consequences (part 1)

Andrew — Thu, 14 Aug 2008 18:16:42 GMT

[I believe most people expect reference semantics for iterators, not value semantics.]

Vast majority of people writing vernacular C# use them in foreach loops. They never bother about ref/val semantics. Also, you palter a little bit: with a value type enumerator, in your example

e = o.GetEnumerator();

DoSomething1(e);

DoSomething2(e);

e gets boxed, so no difference between a class and a struct iterator. The only benefit for a value type iterator comes from the foreach loop: it uses duck typing against iterators, thus doesn't cast to IEnumerator.

[...I don't see how nesting is involved]

Um, sorry - I meant recursion. If you recursively interate through, all iterators (as far as I understand) should be on the stack that might, eg. cause stack overflow.

[You focused on boxing and missed the original problem. DoSomething2(e) will not resume where DoSomething1(e) left off. And stack overflow is not the issue here either. -Raymond]

Interesting Links – 8/14/2008

Matt Johnson's Technical Adventures — Thu, 14 Aug 2008 20:05:09 GMT

Ask the Directory Services Team : MCS Talks Infrastructure Architecture joeware - never stop exploring…

Today’s Blogs « Roman’s Blog

Today’s Blogs « Roman’s Blog — Thu, 14 Aug 2008 23:11:32 GMT

PingBack from http://rhnatiuk.wordpress.com/2008/08/14/todays-blogs/

Iterators

Alexander Morou — Fri, 15 Aug 2008 00:33:14 GMT

As stated before, the primary reason the state machine transitions into a final state is to prevent pre-final states from being repeated, since the logic of them could alter the state of other objects within the iterator's scope (and potentially even cause run-time errors).

I'm guessing the other reason yield break; transitions into a state, is state reduction, the most optimal state machine is the one with the fewest states. Multiple yield breaks do transition into a single state, don't they? (I haven't actually checked.)

Recursive iterators merely require a more complex approach, but are entirely possible. Instead of being directly recursive, you need to cast part of the logic into a sub-iterator that would effectively emit the transition series of objects used in the recursive approach, then using the flat form of the hierarchy, yield the members respectively. Alternatively you can flatten your recursive approach into a non-recursive solution and yield the members that way.

I found iterators interesting because you can essentially do whatever you want with them. My favorite was creating a multi-dimensional array iterator that iterated the indices of an array, yielding the same array instance each time, just with different values. Good for debugging where you send in a nondescript array and its internals are iterated and logged regardless of the array's dimensional structure.

re: The implementation of iterators in C# and its consequences (part 1)

CodeMage — Fri, 15 Aug 2008 04:56:32 GMT

Another interesting fact about iterators is the garbage they generate, by virtue of implementing IEnumerator<T> and IEnumerable<T>. Every time you use an iterator in a foreach loop, you'll instantiate the implementation of these interfaces. In case of yield return, this implementation is hidden from you by the compiler, but it still creates garbage.

There's a way to avoid that, though. By creating a value type that implements the iterator design contract (GetEnumerator, MoveNext, Reset and Current) without implementing the IEnumerator<T> and IEnumerable<T> interfaces, you can still use it in foreach loops but you don't generate any garbage. The bad news is that you have to implement it by hand: there's no syntactic sugar for this.

re: The implementation of iterators in C# and its consequences (part 1)

Andrew — Fri, 15 Aug 2008 12:35:28 GMT

[You focused on boxing and missed the original problem. DoSomething2(e) will not resume where DoSomething1(e) left off. And stack overflow is not the issue here either. -Raymond]

Wow! Raymond, yep I missed the point - ultimately had to write a small app in VS to get to it, sorry :)

But. Iterators for List<T> and Dictionary<K,V> are public nested structs. Does this mean that perf gain in foreach loops was more important back then, than the continuation idea (implemented in yield return) ?

(just in case you or someone else here has an explanation)

Thanks,

Andrew

re: The implementation of iterators in C# and its consequences (part 1)

Andrew — Fri, 15 Aug 2008 12:41:11 GMT

@CodeMage

> ...By creating a value type that implements the iterator design contract...

Exactly, and that's what bothers me: why didn't they implement 'yield return' to generate structs? Raymond answered above, but it still somehow not quite persuading

(btw - that nested value type iterator should be public, that's possibly something you cannot always afford)

Tricky IEnumerable

the blog => anything goes — Thu, 04 Sep 2008 22:44:56 GMT

Implementing IEnumerable<T> can turned out to be tricky in one particular situation. Consider the

Haugerns Development Escapades » Blog Archive » Beware of the IEnumerables

Fri, 17 Oct 2008 12:00:58 GMT

PingBack from http://www.haugern.net/blog/beware-of-the-ienumerables/

C# Yield Keyword « Vasu Balakrishnan’s Blog

C# Yield Keyword « Vasu Balakrishnan’s Blog — Wed, 20 May 2009 22:36:29 GMT

PingBack from http://vasubalakrishnan.wordpress.com/2009/05/20/c-yield-keyword/