The Computer Language
Benchmarks Game

binary-trees C# Mono LLVM #3 program

source code


namespace BenchmarkGameBTrees
{
    /*
          The Computer Language Benchmarks Game
          http://benchmarksgame.alioth.debian.org/ 

          contributed by Marek Safar  
          optimized by kasthack
    */
    using System;
    using System.Threading;
    using System.Threading.Tasks;

    class BinaryTrees
    {
        const int minDepth = 4;
        public static void Main(String[] args)
        {
            int n = 0;
            if (args.Length > 0) n = Int32.Parse(args[0]);
            int maxDepth = Math.Max(minDepth + 2, n);
            int stretchDepth = maxDepth + 1;
            int check = (TreeNode.bottomUpTree(0, stretchDepth)).itemCheck();
            Console.WriteLine("stretch tree of depth {0}\t check: {1}", stretchDepth, check);
            TreeNode longLivedTree = TreeNode.bottomUpTree(0, maxDepth);
            for (int depth = minDepth; depth <= maxDepth; depth += 2)
            {
                int iterations = 1 << (maxDepth - depth + minDepth);
                check = 0;
                /*
                for (int i = 1; i <= iterations; i++)
                {
                    check += (TreeNode.bottomUpTree(i, depth)).itemCheck();
                    check += (TreeNode.bottomUpTree(-i, depth)).itemCheck();
                }
                */
                Parallel.For(1, iterations + 1,
                    () => 0,
                    (i, loop, localCheck) =>
                    {
                        return localCheck + (TreeNode.bottomUpTree(i, depth)).itemCheck() + (TreeNode.bottomUpTree(-i, depth)).itemCheck();
                    },
                    localCheck => Interlocked.Add(ref check, localCheck)
                );

                Console.WriteLine("{0}\t trees of depth {1}\t check: {2}",
                    iterations * 2, depth, check);
            }
            Console.WriteLine("long lived tree of depth {0}\t check: {1}",
                maxDepth, longLivedTree.itemCheck());
        }

        class TreeNode
        {
            private TreeNode left, right;
            private int item;
            TreeNode(int item)
            {
                this.item = item;
            }
            internal static TreeNode bottomUpTree(int item, int depth)
            {
                TreeNode t;
                // ChildTreeNodes(out t, item, depth - 1);
                ChildTreeNodes(out t, item, depth);
                return t;
            }
            static void ChildTreeNodes(out TreeNode node, int item, int depth)
            {
                node = new TreeNode(item);
                if (depth > 0)
                {
                    ChildTreeNodes(out node.left, 2 * item - 1, depth - 1);
                    ChildTreeNodes(out node.right, 2 * item, depth - 1);
                }
            }
            internal int itemCheck()
            {
                if (right == null) return item;
                else return item + left.itemCheck() - right.itemCheck();
            }
        }
    }
}
    

notes, command-line, and program output

NOTES:
32-bit Ubuntu one core
Mono JIT compiler version 4.5.1 (master/3e844dd Fri May  6 19:24:07 PDT 2016)
	LLVM:          yes(3.6.0svn-mono-master/9f79399)
	GC:            sgen



Tue, 28 Jun 2016 18:03:00 GMT

MAKE:
mv binarytrees.csharpllvm-3.csharpllvm binarytrees.csharpllvm-3.cs
/usr/local/bin/mcs  -optimize+ -platform:x86 -out:binarytrees.csharpllvm-3.csharpllvm_run binarytrees.csharpllvm-3.cs
rm binarytrees.csharpllvm-3.cs
0.28s to complete and log all make actions

COMMAND LINE:
/usr/local/bin/mono --llvm --gc=sgen binarytrees.csharpllvm-3.csharpllvm_run 20

PROGRAM OUTPUT:
stretch tree of depth 21	 check: -1
2097152	 trees of depth 4	 check: -2097152
524288	 trees of depth 6	 check: -524288
131072	 trees of depth 8	 check: -131072
32768	 trees of depth 10	 check: -32768
8192	 trees of depth 12	 check: -8192
2048	 trees of depth 14	 check: -2048
512	 trees of depth 16	 check: -512
128	 trees of depth 18	 check: -128
32	 trees of depth 20	 check: -32
long lived tree of depth 20	 check: -1