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.

    public class Node<T>
    {
        public Node(T self, List<Node<T>> children)
        {
            this.self = self;
            this.children = children;
        }
        public T self;
        public List<Node<T>> children;
    }

Depth first traversal of this tree is easily done using yield.

        public static IEnumerable<T> Traverse<T>(Node<T> root)
        {
            Stack<Node<T>> stack = new Stack<Node<T>>();
            stack.Push(root);
            while (stack.Count > 0)
            {
                Node<T> n = stack.Pop();
                yield return n.self;
                foreach (Node<T> child in n.children)
                {
                    stack.Push(child);
                }
            }
        }

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 (as indicated/expected), so we can use this method like this:

                foreach (int i in DepthFirstTraversal.Traverse<int>(rootNode))
                {
                     //DoSomethingWith(i);
                }

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:

        public static void Traverse<T>(Node<T> root, Action<T> action)
        {
            Stack<Node<T>> stack = new Stack<Node<T>>();
            stack.Push(root);

            while (stack.Count > 0)
            {
                Node<T> n = stack.Pop();
                action(n.self);
                foreach (Node<T> child in n.children)
                {
                    stack.Push(child);
                }
            }
        }

Performing a given action for each item in our tree (depth first) is done like this:

DepthFirstTraversal.Traverse<int>(rootNode, (i) => DoSomethingWith(i));

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:

List<int> results = new List<int>(41);
//Yield approach
                foreach (int i in DepthFirstTraversal.Traverse<int>(rootNode))
                {
                    results.Add(i);
                }
//Action approach
                DepthFirstTraversal.Traverse<int>(rootNode, (i) => results.Add(i));

After 100.000 iterations the result was the following:

Average milliseconds for yield approach:            0.01265
Average milliseconds for delegate/Action<> approach 0.00578

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

As many of you I enjoy solving a very complex problem, however sometimes it’s finding new ways todo simple things that really excites me! This happened again today, I was working on a simple Depth-First-Search traversal algorithm when it suddenly doomed to me that I was duplicating a lot of code because I had to do DFS multiple times, with the only difference the action to take at each node.

Pondering about this for a few minutes and I thought about using a delegate as a sort of method pointer to tell the DFS algorithm what action to take for each node. I wrote a quick delegate and named it Action, but then I remembered that C# has the built in Action delegate.

With these techniques in mind I quickly wrote the following code:

public void DFS<T>(T node, Action<T> action) where T : IHasChildren<T>
{
    Stack<T> stack = new Stack<T>();
    action(node);
    stack.PushMany<T>(node.Children);
    while (stack.Count > 0)
    {
        T n = stack.Pop();
        action(n);
        stack.PushMany<T>(n.Children);
    }
}

public interface IHasChildren<T>
{
    List<T> Children;
}

This way you can use DFS on any type of node as long as it implements IHasChildren, and you can use any Action too, saves a lot of duplicate code !

Edit:

Stack.PushMany is my own extension method that allows a list to be put on a stack (just a simple for each).

In XNA shaders are processed into Effect objects by the content pipeline. These effect objects are not really ‘first class citizens’ because, contrarily to most C# classes, these classes have a lot of loosely-typed features. To remedy this I’m going to show you how I wrap these effect objects into their own wrapper, when we see the differences I’ll explain the pros and cons of my approach.

For this tutorial we’re going to use a part of a shader I use for deferred rendering:

float4x4 World : WORLD;
float specularIntensity = 0.8f;
texture Texture : TEXTURE;

As said, the content processor wraps this nicely into an Effect object. Now if we’d like to draw something with this effect it would probably be done something like this:

Effect effect = Content.Load<Effect>("myEffect");
//Draw:
effect.Parameters.GetParameterBySemantic("World") = Matrix.Identity;
effect.Parameters["specularIntensity"] = 0.5f;
effect.Parameters["texture"] = 56;
effect.Techniques["technique1"].Passes[0].Apply();

Given the rest of the code is correct this will compile nicely, however during runtime we will receive an exception. Because we set the effect parameter “texture” to 56, which is not a proper texture value. Due to the loose typing this error could not be detected by the compiler, so it could sneak up on us. Also it’s a bit hard to remember all the parameters an effect has, because we cant see that without opening the .fx file, I’d argue that the effect class is not a proper class as we know other classes to be in C#. And it can’t be, because it has to be compatible with so many different shaders. Therefor I push forward my approach.

For the above shader I would write the following class:

    public class MyEffect
    {
        public MyEffect(Effect effect)
        {
            worldMatrix = effect.Parameters.GetParameterBySemantic("World");
            texture = effect.Parameters.GetParameterBySemantic("Texture");
            specularIntensity = effect.Parameters["specularIntensity"];

            technique1 = effect.Techniques["Technique1"];
        }

        public void Apply()
        {
            technique1.passes[0].Apply();
        }

        #region FieldsAndProperties
        private EffectTechnique technique1;        

        private EffectParameter worldMatrix;
        public Matrix WorldMatrix { set { worldMatrix.SetValue(value); } }

        private EffectParameter texture;
        public Texture2D Texture { set { texture.SetValue(value); } }

        private EffectParameter specularIntensity;
        public Texture2D SpecularIntensity { set { specularIntensity.SetValue(value); } }
        #endregion

    }

Using this code drawing an object would look like this:

MyEffect effect = new MyEffect(Content.Load<Effect>("myEffect"));
//Draw:
effect.World = Matrix.Identity;
effect.SpecularIntensity = 0.5f;
effect.Texture = 56;
effect.Apply();

In my opinion this is a lot more readable and we now get an error while compiling that 56 does not match the type “Texture” also the new wrapper is more of an interface for the effect file. If we change one of the variable names in the effect file, we now only have to make a change at one place in our code base, even if we change the type of a parameter using some logic in the property we might still not have to change all the code. And if we really have to we will get a lot of helpful compiler warnings. We can now also find all references to a specific parameter. However the big downside is that Effect works for all effects (well you still have to remember the parameters and techniques which differ per shader), and this approach requires you to write a class per shader.

Anyway this is my approach, I’d love to know how other people handle this problem, and if you have any comments.

Update 7-2-2011:
After discussing alternative approaches (thanks Flashed!) I would like to give everybody a tip to try an extend this system. How about have a content pipeline project that automatically matches an effect file with an effect wrapper? You can use metadata in the .fx files todo this!