So two days ago I wrote a an article on traversal algorithms using delegates. One of the commenters (I’m looking at you Mart) mentioned a different approach using the yield keyword, which generates a state machine underneath.
I had heard of the yield keyword before, but I’ve never used it so far. I was thrilled to work out his comment, to find out how it works, et voila ,this blog-post was written.
I first wrote this generic Node class which allowed me to build a tree like structure.
Depth first traversal of this tree is easily done using yield.
When compiled, this piece of code generates a thread-safe state machine (very nifty) but thanks to the abstraction that yield gives us we don’t have to worry about. We can just interact with this method as if the result is an IEnumerable
But what are the performance implications of this hidden state machine? To test this I’ve adapted the previous post’s traversal algorithm to be as similar as possible:
Performing a given action for each item in our tree (depth first) is done like this:
Using a recursive algorithm I constructed a tree (of ints) with a depth of 10, where each node has 2 child nodes. I then benchmarked how long it took to add each item in the tree to a list like this:
After 100.000 iterations the result was the following:
So the yield approach is more then two times as slow as the delegate approach to a depth first traversal, which isn’t surprising since we’re talking state machine vs method+virtual lookup. Still it was interesting to see how yield works. For more in depth info about yield see this article by Jon Skeet.
See the code for this benchmark here