From 7f9afbf706f51c5fca1d909eb8cd52cb0c48a8ff Mon Sep 17 00:00:00 2001 From: Andy Ayers Date: Mon, 9 Jan 2017 16:17:27 -0800 Subject: [PATCH] JIT: Add BinaryTrees benchmark variant Add a variant that uses a class and out parameter instead of returning a struct by value. This variant is similar to version 3 from the benchmarks games site, but with validation added and parallelism removed. See related analysis in dotnet/coreclr#8837. According to xunit-perf runs, this version's performance is improved (~10%) by enabling the model inlining policy. When the model policy is enabled the inliner will inline the two outermost calls to `ChildTreeNodes` in the innermlost loop. Also, make sure the new and the original version to build the same way in release and debug. Commit migrated from https://github.com/dotnet/coreclr/commit/f8b89a11985f763aff040875a96c47a166500f25 --- .../binarytrees/binarytrees.csharp.cs | 1 + .../binarytrees/binarytrees.csharp3.cs | 142 +++++++++++++++++++++ .../BenchmarksGame/binarytrees/binarytrees.csproj | 2 + .../BenchmarksGame/binarytrees/binarytrees3.csproj | 46 +++++++ 4 files changed, 191 insertions(+) create mode 100644 src/coreclr/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csharp3.cs create mode 100644 src/coreclr/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees3.csproj diff --git a/src/coreclr/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csharp.cs b/src/coreclr/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csharp.cs index c77e802..05dbe94 100644 --- a/src/coreclr/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csharp.cs +++ b/src/coreclr/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csharp.cs @@ -16,6 +16,7 @@ using Xunit; [assembly: OptimizeForBenchmarks] [assembly: MeasureInstructionsRetired] +[assembly: MeasureGCCounts] namespace BenchmarksGame { diff --git a/src/coreclr/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csharp3.cs b/src/coreclr/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csharp3.cs new file mode 100644 index 0000000..6dcf48a --- /dev/null +++ b/src/coreclr/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csharp3.cs @@ -0,0 +1,142 @@ +// 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. +/* The Computer Language Benchmarks Game + http://benchmarksgame.alioth.debian.org/ + + Based on code originally contributed by Marek Safar + and optimized by kasthack + + modified for use with xunit-performance +*/ + +using Microsoft.Xunit.Performance; +using System; +using System.Runtime.CompilerServices; +using Xunit; + +[assembly: OptimizeForBenchmarks] +[assembly: MeasureInstructionsRetired] +[assembly: MeasureGCCounts] + +namespace BenchmarksGame +{ +public class BinaryTrees3 +{ + private const int minDepth = 4; + private const int Iterations = 1; + + [MethodImpl(MethodImplOptions.NoInlining)] + private static bool Bench(bool verbose = false) + { + int n = 16; + int maxDepth = Math.Max(minDepth + 2, n); + int stretchDepth = maxDepth + 1; + int t = 0; + + int check = (TreeNode.bottomUpTree(0, stretchDepth)).itemCheck(); + if (verbose) + { + Console.WriteLine("stretch tree of depth {0}\t check: {1}", stretchDepth, check); + } + t += check; + + TreeNode longLivedTree = TreeNode.bottomUpTree(0, maxDepth); + + for (int depth = minDepth; depth <= maxDepth; depth += 2) + { + int iterations = 1 << (maxDepth - depth + minDepth); + + check = 0; + for (int i = 1; i <= iterations; i++) + { + check += (TreeNode.bottomUpTree(i, depth)).itemCheck(); + check += (TreeNode.bottomUpTree(-i, depth)).itemCheck(); + } + + if (verbose) + { + Console.WriteLine("{0}\t trees of depth {1}\t check: {2}", + iterations * 2, depth, check); + } + + t += check; + } + + if (verbose) + { + Console.WriteLine("long lived tree of depth {0}\t check: {1}", + maxDepth, longLivedTree.itemCheck()); + } + + t += check; + + return (t == -174785); + } + + private class TreeNode + { + private TreeNode left, right; + private int item; + + private TreeNode(int item) + { + this.item = item; + } + + internal static TreeNode bottomUpTree(int item, int depth) + { + TreeNode t; + ChildTreeNodes(out t, item, depth - 1); + return t; + } + + static void ChildTreeNodes(out TreeNode node, int item, int depth) + { + node = new TreeNode(item); + if ( depth > 0 ) + { + ChildTreeNodes(out node.left, 2 * item - 1, depth - 1); + ChildTreeNodes(out node.right, 2 * item, depth - 1); + } + } + + internal int itemCheck() + { + if (right == null) return item; + else return item + left.itemCheck() - right.itemCheck(); + } + } + + [Benchmark] + public static void Test() + { + foreach (var iteration in Benchmark.Iterations) + { + using (iteration.StartMeasurement()) + { + for (int i = 0; i < Iterations; i++) + { + Bench(); + } + } + } + } + + private static bool TestBase() + { + bool result = true; + for (int i = 0; i < Iterations; i++) + { + result &= Bench(true); + } + return result; + } + + public static int Main() + { + bool result = TestBase(); + return (result ? 100 : -1); + } +} +} diff --git a/src/coreclr/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csproj b/src/coreclr/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csproj index d970a78..257a1d8 100644 --- a/src/coreclr/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csproj +++ b/src/coreclr/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees.csproj @@ -20,6 +20,8 @@ + + pdbonly true diff --git a/src/coreclr/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees3.csproj b/src/coreclr/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees3.csproj new file mode 100644 index 0000000..169e33d --- /dev/null +++ b/src/coreclr/tests/src/JIT/Performance/CodeQuality/BenchmarksGame/binarytrees/binarytrees3.csproj @@ -0,0 +1,46 @@ + + + + + Debug + AnyCPU + 2.0 + {95DFC527-4DC1-495E-97D7-E94EE1F7140D} + Exe + Properties + 512 + {786C830F-07A1-408B-BD7F-6EE04809D6DB};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC} + $(ProgramFiles)\Common Files\microsoft shared\VSTT\11.0\UITestExtensionPackages + ..\..\ + 7a9bfb7d + .NETStandard,Version=v1.4 + true + + + + + + + + pdbonly + true + + + + False + + + + + + + + + + $(JitPackagesConfigFileDirectory)benchmark\project.json + $(JitPackagesConfigFileDirectory)benchmark\project.lock.json + + + + + -- 2.7.4