Recurse Vs Stack Benchmark

Test.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TestRunner
{
    public class Test
    {
        private readonly Random _random = new Random();
        private const int Iter = 100; // number of iterations, adjust if necessary

        // creates a random graph
        public Thing BuildThing()
        {
            var id = 1;
            return BuildThing(ref id, 0);
        }

        // creates a random graph
        public Thing BuildThing(ref int id, int depth)
        {
            var mdepth = _random.Next(4, 8); // depth
            if (depth > mdepth)
                return new Thing(id++, depth, new Thing[0]);

            var ccount = _random.Next(4, 8); // between 4 and 8 children
            var things = new List<Thing>();
            for (var i = 0; i < ccount; i++)
                things.Add(BuildThing(ref id, depth+1));
            return new Thing(id++, depth, things.ToArray());
        }

        // document order:
        // if tree is...
        // 1 -> 2, 3
        // 2 -> 4, 5
        // then document order is 1, 2, 4, 5, 3

        // enumerate in "document order" using recursive method
        public IEnumerable<Thing> EnumerateRecursive(Thing thing)
        {
            yield return thing;

            foreach (var child in thing.Children)
                foreach (var child2 in EnumerateRecursive(child))
                    yield return child2;
        }

        // enumerate in "document order" using stack
        public IEnumerable<Thing> EnumerateStack(Thing thing)
        {
            var s = new Stack<Thing>();
            s.Push(thing);
            while (s.Count > 0)
            {
                var t = s.Pop();
                yield return t;
                foreach (var child in t.Children.Reverse()) // must reverse to obtain document order
                    s.Push(child);
            }
        }

        // benchmarks
        public void Run()
        {
            var thing = BuildThing();
            var sw = new Stopwatch();

            Thing[] things1 = null, things2 = null;

            sw.Reset();
            sw.Start();
            for (var i = 0; i < Iter; i++)
            {
                things1 = EnumerateRecursive(thing).ToArray();
            }
            sw.Stop();
            var time1 = sw.ElapsedMilliseconds;
            Console.WriteLine("Recursive: {0}ms", time1);

            sw.Reset();
            sw.Start();
            for (var i = 0; i < Iter; i++)
            {
                things2 = EnumerateStack(thing).ToArray();
            }
            sw.Stop();
            var time2 = sw.ElapsedMilliseconds;
            Console.WriteLine("Stack: {0}ms ie {1:#0}%", time2, (double)time2 / (double)time1 * 100);

            var diffs2 = things1.Zip(things2, (thing1, thing2) => thing1.Id != thing2.Id)
                .Any(x => x);
            if (diffs2)
                Console.WriteLine("Stack produces wrong order!");

            Console.WriteLine("Done");
        }
    }

    public class Thing
    {
        public Thing(int id, int depth, IEnumerable<Thing> children)
        {
            Id = id;
            Depth = depth;
            Children = children;
        }

        public int Id { get; private set; }
        public int Depth { get; private set; }
        public IEnumerable<Thing> Children { get; private set; }

        public override string ToString()
        {
            return "#" + Id + " (" + Depth + ")";
        }
    }
}

Interesting tests and observations. Don't think I've ever worked on a project with a structure deeper than 8-10 levels. At least for us, it has been way more common with sites that have a wide graph. So I would agree with Stephan on the typical Umbraco scenario.

Tweaking the depth level to run only 4 levels deep and upping the maximum child count to 50 yielded (See what I did there!) the following results.

Recursive: 115714ms
Recursive memory usage: 15944204 bytes or 15.2055778503418 Mb
Stack: 73009ms ie 63%
Stack memory usage: 15952880 bytes or 15.2138519287109 Mb ie 100%