Recursive Iterators (aka Perf killers)

Technically this isn't specific to iterators, but its so much easier to do with iterators that I thought I'd mention it.  Some languages are smart enough to 'flatten' iterators, such that if an iterator is called insde of another iterator, only one iteration object exists.  C# is not one of those languages (at least not yet).  Generally if you see any sort of recursion inside an iterator, you're asking for performance problems, simply because each time it recurses, it's going to create a whole new iteration object on the GC heap.

Consider this binary tree:

---

public class BinaryTree<DataType> {    public DataType Data;    public BinaryTree LeftChild;    public BinaryTree RightChild;    public IEnumerable<DataType> InOrder {        get {            if (LeftChild != null)                foreach (DataType d in LeftChild.InOrder)                    yield return d;            yield return Data;            if (RightChild != null)``                foreach (DataType d in RightChild.InOrder)                    yield return d;        }    }}

---

Now assume the class is properly done up with properties, and accessors and is always kept balanced.  How many objects are created when walking different sized trees?  With just 1 element, the answer is 1.  With 2 you get 2, 3 -> 3, 4 -> 4, 5 -> 5, etc.  You can keep doing the math, but allocation wise, this neat, clean, and simple code is O(n).  That's a pretty heavy burden on the CG if you ask me.  If that's a tax you're willing to bear, then by all means keep this clean and clear code.

--Grant

Comments

• Anonymous
  November 17, 2007
  I was playing around with generic iterators in C# this morning. The 2.0 compiler does so much of the

• Anonymous
  December 16, 2007
  I was playing around with generic iterators in C# this morning. The 2.0 compiler does so much of the