The Computer Language
Benchmarks Game

binary-trees C# .NET Core #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:
64-bit Ubuntu quad core
dotnet 1.0.1 005db40cd1
"System.GC.Server": true


Sun, 26 Mar 2017 03:17:51 GMT

MAKE:
cp binarytrees.csharpcore-4.csharpcore Program.cs
cp Include/csharpcore/tmp.csproj .
cp Include/csharpcore/runtimeconfig.template.json .
mkdir obj
cp Include/csharpcore/tmp.csproj.nuget.g.props ./obj
cp Include/csharpcore/tmp.csproj.nuget.g.targets ./obj
/usr/bin/dotnet build -c Release
Microsoft (R) Build Engine version 15.1.548.43366
Copyright (C) Microsoft Corporation. All rights reserved.

  tmp -> /home/dunham/benchmarksgame_quadcore/binarytrees/tmp/bin/Release/netcoreapp1.1/tmp.dll

Build succeeded.
    0 Warning(s)
    0 Error(s)

Time Elapsed 00:00:03.70
4.18s to complete and log all make actions

COMMAND LINE:
/usr/bin/dotnet ./bin/Release/netcoreapp1.1/tmp.dll 7

UNEXPECTED OUTPUT 

1,4c1,4
< stretch tree of depth 8	 check: -1
< 128	 trees of depth 5	 check: -128
< 32	 trees of depth 7	 check: -32
< long lived tree of depth 7	 check: -1
---
> stretch tree of depth 8	 check: 511
> 128	 trees of depth 4	 check: 3968
> 32	 trees of depth 6	 check: 4064
> long lived tree of depth 7	 check: 255

PROGRAM OUTPUT:
stretch tree of depth 8	 check: -1
128	 trees of depth 5	 check: -128
32	 trees of depth 7	 check: -32
long lived tree of depth 7	 check: -1