The Computer Language
Benchmarks Game

binary-trees C# .NET Core #5 program

source code

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

   contributed by Marek Safar  
   *reset*
   concurrency added by Peperud
   minor improvements by Alex Yakunin
*/

using System;
using System.Runtime.CompilerServices;
using System.Threading.Tasks;

public sealed class BinaryTrees
{
    public const int MinDepth = 4;

    public static void Main(string[] args)
    {
        var n = args.Length == 0 ? 0 : int.Parse(args[0]);
        var maxDepth = n < (MinDepth + 2) ? MinDepth + 2 : n;
        var stretchDepth = maxDepth + 1;

        var stretchDepthTask = Task.Run(() => TreeNode.CreateTree(stretchDepth).CountNodes());
        var maxDepthTask = Task.Run(() => TreeNode.CreateTree(maxDepth).CountNodes());

        var tasks = new Task<string>[(maxDepth - MinDepth) / 2 + 1];
        for (int depth = MinDepth, ti = 0; depth <= maxDepth; depth += 2, ti++) {
            var iterationCount = 1 << (maxDepth - depth + MinDepth);
            var depthCopy = depth; // To make sure closure value doesn't change
            tasks[ti] = Task.Run(() => {
                var count = 0;
                if (depthCopy >= 17) {
                    // Parallelized computation for relatively large tasks
                    var miniTasks = new Task<int>[iterationCount];
                    for (var i = 0; i < iterationCount; i++)
                        miniTasks[i] = Task.Run(() => TreeNode.CreateTree(depthCopy).CountNodes());
                    Task.WaitAll(miniTasks);
                    for (var i = 0; i < iterationCount; i++)
                        count += miniTasks[i].Result;
                }
                else {
                    // Sequential computation for smaller tasks
                    for (var i = 0; i < iterationCount; i++)
                        count += TreeNode.CreateTree(depthCopy).CountNodes();
                }
                return $"{iterationCount}\t trees of depth {depthCopy}\t check: {count}";
            });
        }
        Task.WaitAll(tasks);

        Console.WriteLine("stretch tree of depth {0}\t check: {1}",
            stretchDepth, stretchDepthTask.Result);
        foreach (var task in tasks)
            Console.WriteLine(task.Result);
        Console.WriteLine("long lived tree of depth {0}\t check: {1}",
            maxDepth, maxDepthTask.Result);
    }
}

public struct TreeNode
{
    public sealed class NodeData
    {
        public TreeNode Left, Right;

        public NodeData(TreeNode left, TreeNode right)
        {
            Left = left;
            Right = right;
        }
    }

    public NodeData Data;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public TreeNode(TreeNode left, TreeNode right)
    {
        Data = new NodeData(left, right);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static TreeNode CreateTree(int depth)
    {
        return depth <= 0
            ? default(TreeNode)
            : new TreeNode(CreateTree(depth - 1), CreateTree(depth - 1));
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public int CountNodes()
    {
        if (ReferenceEquals(Data, null))
            return 1;
        return 1 + Data.Left.CountNodes() + Data.Right.CountNodes();
    }
}
    

notes, command-line, and program output

NOTES:
64-bit Ubuntu quad core
2.0.0-preview2-006497
"System.GC.Server": true


Wed, 28 Jun 2017 23:54:21 GMT

MAKE:
cp binarytrees.csharpcore-5.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.3.388.41745 for .NET Core
Copyright (C) Microsoft Corporation. All rights reserved.

  tmp -> /home/dunham/benchmarksgame_quadcore/binarytrees/tmp/bin/Release/netcoreapp2.0/tmp.dll

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

Time Elapsed 00:00:04.24

7.43s to complete and log all make actions

COMMAND LINE:
/usr/bin/dotnet ./bin/Release/netcoreapp2.0/tmp.dll 21

PROGRAM OUTPUT:
stretch tree of depth 22	 check: 8388607
2097152	 trees of depth 4	 check: 65011712
524288	 trees of depth 6	 check: 66584576
131072	 trees of depth 8	 check: 66977792
32768	 trees of depth 10	 check: 67076096
8192	 trees of depth 12	 check: 67100672
2048	 trees of depth 14	 check: 67106816
512	 trees of depth 16	 check: 67108352
128	 trees of depth 18	 check: 67108736
32	 trees of depth 20	 check: 67108832
long lived tree of depth 21	 check: 4194303