The Power of Yield

Generating all the permutations of a set is a little bit dry and academic but it illustrates some of the power that yield gives us.


To start here is the code which will ask for all the permutations and print them out.

///////////

        static void Main(string[] args)
        {
            foreach (List permutation in permutations(9))
            {
                string result = string.Empty;
                foreach (int number in permutation)
                {
                    result += number.ToString();
                }
                Console.WriteLine(result);                         
            }
            Console.ReadLine();
        }

///////////

If you use the refactor tools of Visual Studio it will generate the shell of the following function.
For the body, recursively call the permutations(int) function, then place the current item in all positions of resulting permutations. Of course the recursions have to stop somewhere so on the smallest set, a set of one, just return the list with one item.

///////////

        private static IEnumerable permutations(int size)
        {
            if (size == 1)
            {
                List list = new List();
                list.Add(1);
                yield return list;
            }
            else
            {
                foreach (List permutation in permutations(size - 1))
                {
                    for (int i = 0; i <> list = new List(permutation);                         list.Insert(i, size);                         yield return list;                     }                 }             }         } 

///////////

If you run this code, it generates all permutations as expected.

What is surprising is some of the performance aspects of this code.
Even though there is recursion involved here the recursion is only invoked 'n' times.
At the same time the memory being used is also a constant times 'n' squared.
And an additional kicker the number of cycles of execution is a constant (I think between 3 and 4) times 'n' factorial.
(The last is actually pretty good. If you had a really long program that hardcoded each permutation it would take 'n' factorial lines of code.)

If you study your Knuth you could probably unearth some code that performs better on one or more of these aspects. But the readability of such code is a bit obtuse and slight changes result in disasterous results where the errors are not obvious.

Compare this to how natural it was to write this code. The code reads as a description of how to generate permutations.

The performance comes from the strange nature of yield. It converts the method into a Generator instead of a Subroutine.

permalink

Coroutines in C#

There are numerous statements that the yield statement in C# uses Coroutines or results in Coroutines. This is not precisely correct. What the yield statement creates are Generators.

To recap some terminology, Generators like Coroutines are generalizations of Subroutines. Both Coroutines and Generators allow multple entry points to allow execution to be temporarly suspended and then later resumed. Whereas a Subroutine have only one point of entry and they return only once.

What distinguishes Coroutines from Generators is what is returned in the yield. Coroutines yield the next Coroutine to be invoked (or resumed). Generators yield a value to be returned to the parent function.

When yield is used it must be within an iterator block or a function which return IEnumerable. As such the resulting function is a Generator and not a Coroutine.

The good news is that Coroutines can be created or emulated from Generators by using a Dispatching function.

Consider the following code in C#:

  class Program

    {

        static List stringBuffer;



        enum NextMethod

        {

            Produce,

            Consume

        }



        static void Main(string[] args)

        {

            stringBuffer = new List();

            Dispatcher();

        }



        private static void Dispatcher()

        {

            IEnumerator enumeratorProduce = produceCollection().GetEnumerator();

            IEnumerator enumeratorConsume = consumeCollection().GetEnumerator();



            IEnumerator enumerator = enumeratorProduce;

            while (enumerator.MoveNext())

            {

                NextMethod next = enumerator.Current;

                if (next == NextMethod.Produce)

                {

                    enumerator = enumeratorProduce;

                }

                if (next == NextMethod.Consume)

                {

                    enumerator = enumeratorConsume;

                }

            }

        }



        private static IEnumerable produceCollection()

        {

            int i = 0;

            while (true)

            {

                stringBuffer.Add(i.ToString());

                i++;

                yield return NextMethod.Consume;

            }

        }



        private static IEnumerable consumeCollection()

        {

            int i = 0;

            while (true)

            {

                Console.WriteLine(stringBuffer[0]);

                stringBuffer.RemoveAt(0);

                yield return NextMethod.Produce;

            }

        }

    }

Ideally we would like produceCollection and consumeCollection to yield control to each other.

Here the same effect is accomplished by yielding an enum that is then interpreted by the Dispatcher function to invoke the correct Generator. If you set breakpoints on all the lines of the code you will see that execution within the Generator routines produceCollection and consumeCollection picks up on the line where it last left off.

permalink