Permalink
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
134 lines (114 sloc) 4.82 KB
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
// Adapted from binary-trees C# .NET Core #5 program
// http://benchmarksgame.alioth.debian.org/u64q/program.php?test=binarytrees&lang=csharpcore&id=5
// aka (as of 2017-09-01) rev 1.1 of https://alioth.debian.org/scm/viewvc.php/benchmarksgame/bench/binarytrees/binarytrees.csharp-5.csharp?root=benchmarksgame&view=log
// Best-scoring C# .NET Core version as of 2017-09-01
/* 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;
using BenchmarkDotNet.Attributes;
using MicroBenchmarks;
namespace BenchmarksGame
{
[MaxIterationCount(40)] // the default 20 is not enough, the benchmark has multimodal distribution and needs more runs
[BenchmarkCategory(Categories.CoreCLR, Categories.BenchmarksGame)]
public class BinaryTrees_5
{
public const int MinDepth = 4;
[Benchmark(Description = nameof(BinaryTrees_5))]
public int RunBench() => Bench(16, false);
static int Bench(int n, bool verbose)
{
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);
if (verbose)
{
int count = 0;
Action<string> printAndSum = (string s) =>
{
Console.WriteLine(s);
count += int.Parse(s.Substring(s.LastIndexOf(':') + 1).TrimStart());
};
printAndSum(String.Format("stretch tree of depth {0}\t check: {1}",
stretchDepth, stretchDepthTask.Result));
foreach (var task in tasks)
printAndSum(task.Result);
printAndSum(String.Format("long lived tree of depth {0}\t check: {1}",
maxDepth, maxDepthTask.Result));
return count;
}
return 0;
}
}
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();
}
}
}