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 + ")";
        }
    }
}

Memory usage: the recursive version is impacted by the depth of the graph, whereas the stack version is impacted by the number of children nodes can have (if one node has 100 children we're going to push 100 refs to nodes). We'd need to run benchmarks on shallow but wide graphs (lots of children, no depth) vs. deep and narrow graphs (few children, very deep) to figure things out. Guessing the stack version is going to be better and better as the graph gets deeper & narrower.

As far as Umbraco is concerned, however, I've always assumed that graphs were mostly shallow and wide. Don't think many people have graphs with more that 20 levels, OTOH it may be common to have 50+ children on a node.

Thoughts?

The UaaS folk should be able to shed some light on content tree depth/width, as this is only a concern with mid-size to very large sites?

I added some memory checks to the code and bumped up the number of max number of children to 12 (Any higher and my machine crapped out of memory for some reason)

On average the Stack totalled 57% of the recursive time and around 101% memory which seems a pretty good tradeoff. I'd like to check with larger child counts to be sure though.

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

namespace TestRunner
{
    using System.Threading;

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

        private long memoryStart = 0;

        private long memoryStack = 0;

        private long memoryRecursive = 0;

        // 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, 12); // between 4 and 12 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();

            // Make sure that the compiler can't reorder lines here
            Thread.MemoryBarrier();
            this.memoryStart = GC.GetTotalMemory(true);

            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();

            // Log recursive usage
            Thread.MemoryBarrier();
            this.memoryRecursive = GC.GetTotalMemory(true);

            var time1 = sw.ElapsedMilliseconds;
            Console.WriteLine("Recursive: {0}ms", time1);
            var recursive = this.GetImpactRecursive();
            Console.WriteLine("Recursive memory usage: {0} bytes or {1} Mb", recursive, recursive / (double)1024 / 1024);

            sw.Reset();
            sw.Start();
            for (var i = 0; i < Iter; i++)
            {
                things2 = EnumerateStack(thing).ToArray();
            }
            sw.Stop();

            // Log recursive usage
            Thread.MemoryBarrier();
            this.memoryStack = GC.GetTotalMemory(true);

            var time2 = sw.ElapsedMilliseconds;
            Console.WriteLine("Stack: {0}ms ie {1:#0}%", time2, (double)time2 / (double)time1 * 100d);
            var stack = this.GetImpactStack();
            Console.WriteLine("Stack memory usage: {0} bytes or {1} Mb ie {2:#0}%", stack, stack / (double)1024 / 1024, (double)stack / stack * 100d);

            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");
            Console.Read();
        }

        private long GetImpactRecursive()
        {
            return this.memoryRecursive - this.memoryStart;
        }

        private long GetImpactStack()
        {
            return this.memoryStack - this.memoryRecursive;
        }
    }

    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%