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  
   *reset*
   concurrency added by Peperud
*/

using System;
using System.Threading.Tasks;

class BinaryTrees
{
    const int MinDepth = 4;

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

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

        var tcheck = new[]
        {
            Task.Run(() => TreeNode.BottomUpTree(stretchDepth).ItemCheck()),
            Task.Run(() => TreeNode.BottomUpTree(maxDepth).ItemCheck())
        };

        var results = new Task<string>[(maxDepth - MinDepth) / 2 + 1];

        for (int depth = MinDepth; depth <= maxDepth; depth += 2)
        {
            int iterations = 1 << (maxDepth - depth + MinDepth);

            int check = 0, safeDept = depth;

            results[(safeDept - MinDepth) / 2] = Task.Run(() =>
            {
                //for (var i = 1; i <= iterations; i++)
                //{
                //    check += (TreeNode.BottomUpTree(safeDept)).ItemCheck();
                //}

                // 
                // This is a somewhat silly, however overparallelizing towards 
                // the end gave me a little better numbers on average
                //
                int i = 1;
                while (i <= iterations)
                {
                    if (safeDept > 18)
                    {
                        var split = new[]
                        {
                            Task.Run(() => (TreeNode.BottomUpTree(safeDept)).ItemCheck()),
                            Task.Run(() => (TreeNode.BottomUpTree(safeDept)).ItemCheck())
                        };

                        i += 2;
                        Task.WaitAll(split);
                        check += split[0].Result + split[1].Result;
                    }
                    else
                    {
                        check += (TreeNode.BottomUpTree(safeDept)).ItemCheck();
                        i++;
                    }
                }

                return $"{iterations}\t trees of depth {safeDept}\t check: {check}";
            });
        }

        tcheck[0].Wait();
        Console.WriteLine("stretch tree of depth {0}\t check: {1}",
            stretchDepth, tcheck[0].Result);

        for (int i = 0; i < results.Length; i++)
        {
            results[i].Wait();
            Console.WriteLine(results[i].Result);
        }

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

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

        private Next next;

        internal static TreeNode BottomUpTree(int depth)
        {
            if (depth > 0)
            {
                return new TreeNode(BottomUpTree(depth - 1), BottomUpTree(depth - 1));
            }
            else
            {
                return new TreeNode();
            }
        }

        TreeNode(TreeNode left, TreeNode right)
        {
            next = new Next
            {
                left = left,
                right = right
            };
        }

        internal int ItemCheck()
        {
            // if necessary deallocate here
            if (next == null)
            {
                return 1;
            }
            else
            {
                return 1 + next.left.ItemCheck() + next.right.ItemCheck();
            }
        }
    }
}
    

notes, command-line, and program output

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


Mon, 14 Aug 2017 18:55:49 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.3.409.57025 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:03.70

6.40s 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