Performance of nested yield in a tree
c#, ienumerable, performance, yield
Solution
It's certainly not ideal in terms of performance - you end up creating a lot of iterators for large trees, instead of a single iterator which knows how to traverse efficiently.
Some blog entries concerning this:
- Wes Dyer: All about iterators
- Eric Lippert: Immutability in C#, part 6
- Eric again: Immutability in C#, part 7
It's worth noting that F# has the equivalent of the proposed "`yield foreach`" with "`yield!`"
Problem
I've got a tree-like structure. Each element in this structure should be able to return a Enumerable of all elements it is root to. Let's call this method `IEnumerable<Foo> GetAll()`. So if we have ``` A <-- topmost root / \ / \ B C / \ / \ D E F G ``` a call to `GetAll` on element `C` returns `{C, F, G}` (fixed order of elements would be nice, but is not needed). I guess everybody knew that already. The current implementation of `GetAll` looks like this: ``` public IEnumerable<Foo> GetAll () { yield return this; foreach (Foo foo in MyChildren) { foreach (Foo f in foo.GetAll ()) { yield return f; } } } ``` In an earlier implementation, I returned a List and added the child-foos using `List.AddRange()`. My question is if the version using yield is correcly implemented or if it should be improved (esp. in terms of performance). Or is this just bad and I should stick to `List`s (or `ReadOnlyCollections`) instead?