source code
namespace BenchmarkGameBTrees
{
/*
The Computer Language Benchmarks Game
https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
contributed by Marek Safar
optimized by kasthack
*reset*
*/
using System;
using System.Threading;
using System.Threading.Tasks;
class BinaryTrees
{
const int minDepth = 4;
public static void Main(String[] args)
{
int n = 0;
if (args.Length > 0) n = Int32.Parse(args[0]);
int maxDepth = Math.Max(minDepth + 2, n);
int stretchDepth = maxDepth + 1;
int check = (TreeNode.bottomUpTree(stretchDepth)).itemCheck();
Console.WriteLine("stretch tree of depth {0}\t check: {1}", stretchDepth, check);
TreeNode longLivedTree = TreeNode.bottomUpTree(maxDepth);
for (int depth = minDepth; depth <= maxDepth; depth += 2)
{
int iterations = 1 << (maxDepth - depth + minDepth);
check = 0;
Parallel.For(1, iterations + 1,
() => 0,
(i, loop, localCheck) =>
{
return localCheck +
(TreeNode.bottomUpTree(depth)).itemCheck();
},
localCheck => Interlocked.Add(ref check, localCheck)
);
Console.WriteLine("{0}\t trees of depth {1}\t check: {2}",
iterations, depth, check);
}
Console.WriteLine("long lived tree of depth {0}\t check: {1}",
maxDepth, longLivedTree.itemCheck());
}
class TreeNode
{
private TreeNode left, right;
internal static TreeNode bottomUpTree(int depth)
{
TreeNode t;
ChildTreeNodes(out t, depth);
return t;
}
static void ChildTreeNodes(out TreeNode node, int depth)
{
node = new TreeNode();
if (depth > 0)
{
ChildTreeNodes(out node.left, depth - 1);
ChildTreeNodes(out node.right, depth - 1);
}
}
internal int itemCheck()
{
if (right == null) return 1;
else return 1 + left.itemCheck() + right.itemCheck();
}
}
}
}
notes, command-line, and program output
NOTES:
64-bit Ubuntu quad core
.NET SDK 8.0.204
Host Version: 8.0.4
Commit: 2d7eea2529
<AllowUnsafeBlocks>true
<ServerGarbageCollection>true
<ConcurrentGarbageCollection>true
<PublishAot>false
<OptimizationPreference>Speed
<IlcInstructionSet>native
Fri, 26 Apr 2024 00:33:57 GMT
MAKE:
cp binarytrees.csharpcore-3.csharpcore Program.cs
cp Include/csharpcore/program.csproj .
mkdir obj
cp Include/csharpcore/project.assets.json ./obj
/usr/bin/dotnet build -c Release --use-current-runtime
MSBuild version 17.9.8+b34f75857 for .NET
Determining projects to restore...
Restored /home/dunham/all-benchmarksgame/benchmarksgame_i53330/binarytrees/tmp/program.csproj (in 200 ms).
/home/dunham/all-benchmarksgame/benchmarksgame_i53330/binarytrees/tmp/Program.cs(52,30): warning CS8618: Non-nullable field 'left' must contain a non-null value when exiting constructor. Consider declaring the field as nullable. [/home/dunham/all-benchmarksgame/benchmarksgame_i53330/binarytrees/tmp/program.csproj]
/home/dunham/all-benchmarksgame/benchmarksgame_i53330/binarytrees/tmp/Program.cs(52,36): warning CS8618: Non-nullable field 'right' must contain a non-null value when exiting constructor. Consider declaring the field as nullable. [/home/dunham/all-benchmarksgame/benchmarksgame_i53330/binarytrees/tmp/program.csproj]
program -> /home/dunham/all-benchmarksgame/benchmarksgame_i53330/binarytrees/tmp/bin/Release/net8.0/linux-x64/program.dll
Build succeeded.
/home/dunham/all-benchmarksgame/benchmarksgame_i53330/binarytrees/tmp/Program.cs(52,30): warning CS8618: Non-nullable field 'left' must contain a non-null value when exiting constructor. Consider declaring the field as nullable. [/home/dunham/all-benchmarksgame/benchmarksgame_i53330/binarytrees/tmp/program.csproj]
/home/dunham/all-benchmarksgame/benchmarksgame_i53330/binarytrees/tmp/Program.cs(52,36): warning CS8618: Non-nullable field 'right' must contain a non-null value when exiting constructor. Consider declaring the field as nullable. [/home/dunham/all-benchmarksgame/benchmarksgame_i53330/binarytrees/tmp/program.csproj]
2 Warning(s)
0 Error(s)
Time Elapsed 00:00:04.43
6.07s to complete and log all make actions
COMMAND LINE:
./bin/Release/net8.0/linux-x64/program 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