The Computer Language
Benchmarks Game

binary-trees C# Mono LLVM #4 program

source code

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

   contributed by Marek Safar  
   concurrency added by Peperud
*/

using System;
using System.Collections.Generic;
using System.Threading.Tasks;

class BinaryTrees
{
    const int MIN_DEPTH = 4;

    public static void Main(string[] args)
    {
        int n = 0;
        if (args.Length > 0) n = int.Parse(args[0]);

        int maxDepth = n < (MIN_DEPTH + 2) ? MIN_DEPTH + 2 : n;
        int stretchDepth = maxDepth + 1;

        Task<int>[] Tcheck =
        {
                Task.Run(() => TreeNode.bottomUpTree(0, stretchDepth).itemCheck()),
                Task.Run(() => TreeNode.bottomUpTree(0, maxDepth).itemCheck())
        };

        string[] results = new string[(maxDepth - MIN_DEPTH) / 2 + 1];

        var depts = new List<Action>(maxDepth);

        for (int d = maxDepth; d >= MIN_DEPTH; d -= 2)
        {
            var depth = d;
            depts.Add(() =>
            {
                int iterations = 1 << (maxDepth - depth + MIN_DEPTH);

                int check = 0;
                for (int i = 1; i <= iterations; i++)
                {
                    Task<int>[] btm =
                    {
                        Task.Run(() => TreeNode.bottomUpTree(i, depth).itemCheck()),
                        Task.Run(() => TreeNode.bottomUpTree(-i, depth).itemCheck())
                    };

                    Task.WaitAll(btm);

                    check += btm[0].Result + btm[1].Result;
                }

                results[(depth - MIN_DEPTH) / 2] = (iterations * 2) + "\t trees of depth " + depth + "\t check: " + check;
            });
        }

        Parallel.Invoke(new ParallelOptions { MaxDegreeOfParallelism = Environment.ProcessorCount + 1 }, depts.ToArray());

        Task.WaitAll(Tcheck);

        Console.WriteLine("stretch tree of depth {0}\t check: {1}", stretchDepth, Tcheck[0].Result);
        foreach (var result in results)
        {
            Console.WriteLine(result);
        }

        Console.WriteLine("long lived tree of depth {0}\t check: {1}", maxDepth, Tcheck[1].Result);
    }

    struct TreeNode
    {
        sealed class Next
        {
            public TreeNode left, right;
        }

        private Next next;

        private int item;

        TreeNode(int item)
        {
            this.item = item;
            this.next = null;
        }

        TreeNode(TreeNode left, TreeNode right, int item)
        {
            this.next = new Next();
            this.next.left = left;
            this.next.right = right;
            this.item = item;
        }

        internal static TreeNode bottomUpTree(int item, int depth)
        {
            if (depth > 0)
            {
                int i1, i2, d;

                i2 = 2 * item;
                i1 = i2 - 1;
                d = depth - 1;

                var left = bottomUpTree(i1, d);
                var right = bottomUpTree(i2, d);
                return new TreeNode(left, right, item);
            }
            else
            {
                return new TreeNode(item);
            }
        }

        internal int itemCheck()
        {
            if (next == null)
            {
                return item;
            }
            return item + next.left.itemCheck() - next.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, 30 Aug 2016 21:35:49 GMT

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

COMMAND LINE:
/usr/local/bin/mono --llvm --gc=sgen binarytrees.csharpllvm-4.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