From 942676e7982503bd3d20e87b8ed9fb61a4922cce Mon Sep 17 00:00:00 2001 From: Andy Ayers Date: Fri, 4 Dec 2015 15:04:13 -0800 Subject: [PATCH] Various sorting benchmarks TreeSort, HeapSort, QuickSort, BubbleSort, BubbleSort2 --- .../CodeQuality/BenchI/BubbleSort/BubbleSort.cs | 86 ++++++++++++ .../BenchI/BubbleSort/BubbleSort.csproj | 45 +++++++ .../CodeQuality/BenchI/BubbleSort2/BubbleSort2.cs | 89 ++++++++++++ .../BenchI/BubbleSort2/BubbleSort2.csproj | 45 +++++++ .../CodeQuality/BenchI/HeapSort/HeapSort.cs | 120 +++++++++++++++++ .../CodeQuality/BenchI/HeapSort/HeapSort.csproj | 45 +++++++ .../CodeQuality/BenchI/QuickSort/QuickSort.cs | 115 ++++++++++++++++ .../CodeQuality/BenchI/QuickSort/QuickSort.csproj | 45 +++++++ .../CodeQuality/BenchI/TreeSort/TreeSort.cs | 150 +++++++++++++++++++++ .../CodeQuality/BenchI/TreeSort/TreeSort.csproj | 45 +++++++ 10 files changed, 785 insertions(+) create mode 100644 tests/src/JIT/Performance/CodeQuality/BenchI/BubbleSort/BubbleSort.cs create mode 100644 tests/src/JIT/Performance/CodeQuality/BenchI/BubbleSort/BubbleSort.csproj create mode 100644 tests/src/JIT/Performance/CodeQuality/BenchI/BubbleSort2/BubbleSort2.cs create mode 100644 tests/src/JIT/Performance/CodeQuality/BenchI/BubbleSort2/BubbleSort2.csproj create mode 100644 tests/src/JIT/Performance/CodeQuality/BenchI/HeapSort/HeapSort.cs create mode 100644 tests/src/JIT/Performance/CodeQuality/BenchI/HeapSort/HeapSort.csproj create mode 100644 tests/src/JIT/Performance/CodeQuality/BenchI/QuickSort/QuickSort.cs create mode 100644 tests/src/JIT/Performance/CodeQuality/BenchI/QuickSort/QuickSort.csproj create mode 100644 tests/src/JIT/Performance/CodeQuality/BenchI/TreeSort/TreeSort.cs create mode 100644 tests/src/JIT/Performance/CodeQuality/BenchI/TreeSort/TreeSort.csproj diff --git a/tests/src/JIT/Performance/CodeQuality/BenchI/BubbleSort/BubbleSort.cs b/tests/src/JIT/Performance/CodeQuality/BenchI/BubbleSort/BubbleSort.cs new file mode 100644 index 0000000..51a020e --- /dev/null +++ b/tests/src/JIT/Performance/CodeQuality/BenchI/BubbleSort/BubbleSort.cs @@ -0,0 +1,86 @@ +// Copyright (c) Microsoft. All rights reserved. +// Licensed under the MIT license. See LICENSE file in the project root for full license information. +// + +using Microsoft.Xunit.Performance; +using System; +using System.Runtime.CompilerServices; +using Xunit; + +[assembly: OptimizeForBenchmarks] +[assembly: MeasureInstructionsRetired] + +public static class BubbleSort +{ + +#if DEBUG + public const int Iterations = 1; +#else + public const int Iterations = 55000; +#endif + + static void SortArray(int[] tab, int last) { + bool swap; + int temp; + do { + swap = false; + for (int i = 0; i < last; i++) { + if (tab[i] > tab[i + 1]) { + temp = tab[i]; + tab[i] = tab[i + 1]; + tab[i + 1] = temp; + swap = true; + } + } + } + while (swap); + } + + static bool VerifySort(int[] tab, int last) { + for (int i = 0; i < last; i++) { + if (tab[i] > tab[i + 1]) { + return false; + } + } + + return true; + } + + [MethodImpl(MethodImplOptions.NoInlining)] + static public bool Bench() { + int[] tab = new int[100]; + int k = 0; + for (int i = 9; i >= 0; i--) { + for (int j = i * 10; j < (i + 1) * 10; j++) { + tab[k++] = ((j & 1) == 1) ? j + 1 : j - 1; + } + } + SortArray(tab, 99); + bool result = VerifySort(tab, 99); + return result; + } + + [Benchmark] + public static void Test() { + foreach (var iteration in Benchmark.Iterations) { + using (iteration.StartMeasurement()) { + for (int i = 0; i < Iterations; i++) { + Bench(); + } + } + } + } + + static bool TestBase() { + bool result = true; + for (int i = 0; i < Iterations; i++) { + result &= Bench(); + } + return result; + } + + public static int Main() { + bool result = TestBase(); + return (result ? 100 : -1); + } +} diff --git a/tests/src/JIT/Performance/CodeQuality/BenchI/BubbleSort/BubbleSort.csproj b/tests/src/JIT/Performance/CodeQuality/BenchI/BubbleSort/BubbleSort.csproj new file mode 100644 index 0000000..dbf39d7 --- /dev/null +++ b/tests/src/JIT/Performance/CodeQuality/BenchI/BubbleSort/BubbleSort.csproj @@ -0,0 +1,45 @@ + + + + + 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 + + + + + + pdbonly + true + + + + False + + + + + + + + + + + + + $(JitPackagesConfigFileDirectory)benchmark\project.json + $(JitPackagesConfigFileDirectory)benchmark\project.lock.json + + + + + diff --git a/tests/src/JIT/Performance/CodeQuality/BenchI/BubbleSort2/BubbleSort2.cs b/tests/src/JIT/Performance/CodeQuality/BenchI/BubbleSort2/BubbleSort2.cs new file mode 100644 index 0000000..03d85a0 --- /dev/null +++ b/tests/src/JIT/Performance/CodeQuality/BenchI/BubbleSort2/BubbleSort2.cs @@ -0,0 +1,89 @@ +// Copyright (c) Microsoft. All rights reserved. +// Licensed under the MIT license. See LICENSE file in the project root for full license information. +// + +using Microsoft.Xunit.Performance; +using System; +using System.Runtime.CompilerServices; +using Xunit; + +[assembly: OptimizeForBenchmarks] +[assembly: MeasureInstructionsRetired] + +public static class BubbleSort2 +{ + +#if DEBUG + public const int Iterations = 1; + public const int Bound = 5 * Iterations; +#else + public const int Iterations = 15; + public const int Bound = 500 * Iterations; +#endif + + static void Inner(int[] x) { + int limit1 = Bound - 1; + for (int i = 1; i <= limit1; i++) { + for (int j = i; j <= Bound; j++) { + if (x[i] > x[j]) { + int temp = x[j]; + x[j] = x[i]; + x[i] = temp; + } + } + } + } + + [MethodImpl(MethodImplOptions.NoInlining)] + static bool Bench() { + int[] x = new int[Bound + 1]; + int i, j; + int limit; + j = 99999; + limit = Bound - 2; + i = 1; + do { + x[i] = j & 32767; + x[i + 1] = (j + 11111) & 32767; + x[i + 2] = (j + 22222) & 32767; + j = j + 33333; + i = i + 3; + } while (i <= limit); + x[Bound - 1] = j; + x[Bound] = j; + + Inner(x); + + for (i = 0; i < Bound - 1; i++) { + if (x[i] > x[i + 1]) { + return false; + } + } + + return true; + } + + [Benchmark] + public static void Test() { + foreach (var iteration in Benchmark.Iterations) { + using (iteration.StartMeasurement()) { + for (int i = 0; i < Iterations; i++) { + Bench(); + } + } + } + } + + static bool TestBase() { + bool result = true; + for (int i = 0; i < Iterations; i++) { + result &= Bench(); + } + return result; + } + + public static int Main() { + bool result = TestBase(); + return (result ? 100 : -1); + } +} diff --git a/tests/src/JIT/Performance/CodeQuality/BenchI/BubbleSort2/BubbleSort2.csproj b/tests/src/JIT/Performance/CodeQuality/BenchI/BubbleSort2/BubbleSort2.csproj new file mode 100644 index 0000000..490664f --- /dev/null +++ b/tests/src/JIT/Performance/CodeQuality/BenchI/BubbleSort2/BubbleSort2.csproj @@ -0,0 +1,45 @@ + + + + + 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 + + + + + + pdbonly + true + + + + False + + + + + + + + + + + + + $(JitPackagesConfigFileDirectory)benchmark\project.json + $(JitPackagesConfigFileDirectory)benchmark\project.lock.json + + + + + diff --git a/tests/src/JIT/Performance/CodeQuality/BenchI/HeapSort/HeapSort.cs b/tests/src/JIT/Performance/CodeQuality/BenchI/HeapSort/HeapSort.cs new file mode 100644 index 0000000..11c6484 --- /dev/null +++ b/tests/src/JIT/Performance/CodeQuality/BenchI/HeapSort/HeapSort.cs @@ -0,0 +1,120 @@ +// Copyright (c) Microsoft. All rights reserved. +// Licensed under the MIT license. See LICENSE file in the project root for full license information. +// + +using Microsoft.Xunit.Performance; +using System; +using System.Runtime.CompilerServices; +using Xunit; + +[assembly: OptimizeForBenchmarks] +[assembly: MeasureInstructionsRetired] + +public static class HeapSort +{ + +#if DEBUG + public const int Iterations = 1; +#else + public const int Iterations = 2500; +#endif + + const int ArraySize = 5500; + + static void Inner(int[] x, int n) { + int i, j, k, m; + + // pass1 -- put vector in heap form + // that is to say, guarantee that x(i)>=x(2*i) and x(i)>=x(2*i+1). + // after pass 1, the largest item will be at x(1). + for (i = 2; i <= n; i++) { + j = i; + k = j / 2; + m = x[i]; + + // 0 < k <= (n / 2) + // 1 <= j <= n + while (k > 0) { + if (m <= x[k]) { + break; + } + x[j] = x[k]; + j = k; + k = k / 2; + } + x[j] = m; + } + + // pass 2 -- swap first and last items. now with the last + // item correctly placed, consider the list shorter by one item. + // restore the shortened list to heap sort, and repeat + // process until list is only two items long. + i = n; + do { + // do i = n to 2 by -1; + m = x[i]; + x[i] = x[1]; // last item, i.e. item(i) now correct. + j = 1; // we now find the appropriate resting point for m + k = 2; + + // 2 <= k < i ==> 2 <= k < n + // 1 <= j < n + while (k < i) { + if ((k + 1) < i) { + if (x[k + 1] > x[k]) { + k = k + 1; + } + } + if (x[k] <= m) { + break; + } + + x[j] = x[k]; + j = k; + k = k + k; + } + + x[j] = m; + i = i - 1; + } while (i >= 2); + } + + [MethodImpl(MethodImplOptions.NoInlining)] + static bool Bench() { + int[] x = new int[ArraySize + 1]; + for (int i = 1; i <= ArraySize; i++) { + x[i] = ArraySize - i + 1; + } + Inner(x, ArraySize); + for (int j = 1; j <= ArraySize; j++) { + if (x[j] != j) { + return false; + } + } + return true; + } + + [Benchmark] + public static void Test() { + foreach (var iteration in Benchmark.Iterations) { + using (iteration.StartMeasurement()) { + for (int i = 0; i < Iterations; i++) { + Bench(); + } + } + } + } + + static bool TestBase() { + bool result = true; + for (int i = 0; i < Iterations; i++) { + result &= Bench(); + } + return result; + } + + public static int Main() { + bool result = TestBase(); + return (result ? 100 : -1); + } +} diff --git a/tests/src/JIT/Performance/CodeQuality/BenchI/HeapSort/HeapSort.csproj b/tests/src/JIT/Performance/CodeQuality/BenchI/HeapSort/HeapSort.csproj new file mode 100644 index 0000000..b65cce0 --- /dev/null +++ b/tests/src/JIT/Performance/CodeQuality/BenchI/HeapSort/HeapSort.csproj @@ -0,0 +1,45 @@ + + + + + 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 + + + + + + pdbonly + true + + + + False + + + + + + + + + + + + + $(JitPackagesConfigFileDirectory)benchmark\project.json + $(JitPackagesConfigFileDirectory)benchmark\project.lock.json + + + + + diff --git a/tests/src/JIT/Performance/CodeQuality/BenchI/QuickSort/QuickSort.cs b/tests/src/JIT/Performance/CodeQuality/BenchI/QuickSort/QuickSort.cs new file mode 100644 index 0000000..ea06ab3 --- /dev/null +++ b/tests/src/JIT/Performance/CodeQuality/BenchI/QuickSort/QuickSort.cs @@ -0,0 +1,115 @@ +// Copyright (c) Microsoft. All rights reserved. +// Licensed under the MIT license. See LICENSE file in the project root for full license information. +// + +using Microsoft.Xunit.Performance; +using System; +using System.Runtime.CompilerServices; +using Xunit; + +[assembly: OptimizeForBenchmarks] +[assembly: MeasureInstructionsRetired] + +public static class QuickSort +{ + +#if DEBUG + public const int Iterations = 1; +#else + public const int Iterations = 80000; +#endif + + const int MAXNUM = 200; + const int MODULUS = 0x20000; + const int C = 13849; + const int A = 25173; + static int s_seed = 7; + + static int Random(int size) { + unchecked { + s_seed = s_seed * A + C; + } + return (s_seed % size); + } + + static void Quick(int lo, int hi, int[] arr) { + + int i, j; + int pivot, temp; + + if (lo < hi) { + for (i = lo, j = hi, pivot = arr[hi]; i < j;) { + while (i < j && arr[i] <= pivot){ + ++i; + } + while (j > i && arr[j] >= pivot) { + --j; + } + if (i < j) { + temp = arr[i]; + arr[i] = arr[j]; + arr[j] = temp; + } + } + + // need to swap the pivot and a[i](or a[j] as i==j) so + // that the pivot will be at its final place in the sorted array + + if (i != hi) { + temp = arr[i]; + arr[i] = pivot; + arr[hi] = temp; + } + Quick(lo, i - 1, arr); + Quick(i + 1, hi, arr); + } + } + + [MethodImpl(MethodImplOptions.NoInlining)] + static bool Bench() { + + int[] buffer = new int[MAXNUM]; + + for (int j = 0; j < MAXNUM; ++j) { + int temp = Random(MODULUS); + if (temp < 0){ + temp = (-temp); + } + buffer[j] = temp; + } + + Quick(0, MAXNUM - 1, buffer); + + for (int j = 0; j < MAXNUM - 1; ++j) { + if (buffer[j] > buffer[j+1]) { + return false; + } + } + + return true; + } + + [Benchmark] + public static void Test() { + foreach (var iteration in Benchmark.Iterations) { + using (iteration.StartMeasurement()) { + for (int i = 0; i < Iterations; i++) { + Bench(); + } + } + } + } + + static bool TestBase() { + bool result = true; + for (int i = 0; i < Iterations; i++) { + result &= Bench(); + } + return result; + } + + public static int Main() { + bool result = TestBase(); + return (result ? 100 : -1); + } +} diff --git a/tests/src/JIT/Performance/CodeQuality/BenchI/QuickSort/QuickSort.csproj b/tests/src/JIT/Performance/CodeQuality/BenchI/QuickSort/QuickSort.csproj new file mode 100644 index 0000000..37f3d13 --- /dev/null +++ b/tests/src/JIT/Performance/CodeQuality/BenchI/QuickSort/QuickSort.csproj @@ -0,0 +1,45 @@ + + + + + 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 + + + + + + pdbonly + true + + + + False + + + + + + + + + + + + + $(JitPackagesConfigFileDirectory)benchmark\project.json + $(JitPackagesConfigFileDirectory)benchmark\project.lock.json + + + + + diff --git a/tests/src/JIT/Performance/CodeQuality/BenchI/TreeSort/TreeSort.cs b/tests/src/JIT/Performance/CodeQuality/BenchI/TreeSort/TreeSort.cs new file mode 100644 index 0000000..a1af0d1 --- /dev/null +++ b/tests/src/JIT/Performance/CodeQuality/BenchI/TreeSort/TreeSort.cs @@ -0,0 +1,150 @@ +// Copyright (c) Microsoft. All rights reserved. +// Licensed under the MIT license. See LICENSE file in the project root for full license information. +// + +using Microsoft.Xunit.Performance; +using System; +using System.Runtime.CompilerServices; +using Xunit; + +[assembly: OptimizeForBenchmarks] +[assembly: MeasureInstructionsRetired] + +public static class TreeSort +{ + +#if DEBUG + public const int Iterations = 1; +#else + public const int Iterations = 1200; +#endif + + const int SortElements = 5000; + const int Modulus = 65536; + + sealed class Node + { + public Node Left; + public Node Right; + public int Val; + public Node(int n) + { + Left = null; + Right = null; + Val = n; + } + } + + static int s_biggest; + static int s_littlest; + static int s_seed; + + static void InitRand() { + s_seed = 33; + } + + static int Rand(ref int seed) { + int multiplier = 25173; + int increment = 13849; + seed = (multiplier * seed + increment) % Modulus; + return seed; + } + + static void InitArray(int[] sortList) { + InitRand(); + s_biggest = 0; + s_littlest = Modulus; + for (int i = 1; i <= SortElements; i++) { + sortList[i] = Rand(ref s_seed) - 1; + if (sortList[i] > s_biggest) { + s_biggest = sortList[i]; + } + else if (sortList[i] < s_littlest) { + s_littlest = sortList[i]; + } + } + } + + static void Insert(int n, Node t) { + if (n > t.Val) { + if (t.Left == null) { + t.Left = new Node(n); + } + else { + Insert(n, t.Left); + } + } + else if (n < t.Val) { + if (t.Right == null) { + t.Right = new Node(n); + } + else { + Insert(n, t.Right); + } + } + } + + static bool CheckTree(Node p) { + bool result = true; + if (p.Left != null) { + if (p.Left.Val <= p.Val) { + result = false; + } + else { + result &= CheckTree(p.Left); + } + } + + if (p.Right != null) { + if (p.Right.Val >= p.Val) { + result = false; + } + else { + result &= CheckTree(p.Right); + } + } + + return result; + } + + static bool Trees(int[] sortList) { + InitArray(sortList); + Node tree = new Node(sortList[1]); + for (int i = 2; i <= SortElements; i++) { + Insert(sortList[i], tree); + } + bool result = CheckTree(tree); + return result; + } + + [MethodImpl(MethodImplOptions.NoInlining)] + static bool Bench() { + int[] sortList = new int[SortElements + 1]; + bool result = Trees(sortList); + return result; + } + + [Benchmark] + public static void Test() { + foreach (var iteration in Benchmark.Iterations) { + using (iteration.StartMeasurement()) { + for (int i = 0; i < Iterations; i++) { + Bench(); + } + } + } + } + + static bool TestBase() { + bool result = true; + for (int i = 0; i < Iterations; i++) { + result &= Bench(); + } + return result; + } + + public static int Main() { + bool result = TestBase(); + return (result ? 100 : -1); + } +} diff --git a/tests/src/JIT/Performance/CodeQuality/BenchI/TreeSort/TreeSort.csproj b/tests/src/JIT/Performance/CodeQuality/BenchI/TreeSort/TreeSort.csproj new file mode 100644 index 0000000..65f435e --- /dev/null +++ b/tests/src/JIT/Performance/CodeQuality/BenchI/TreeSort/TreeSort.csproj @@ -0,0 +1,45 @@ + + + + + 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 + + + + + + pdbonly + true + + + + False + + + + + + + + + + + + + $(JitPackagesConfigFileDirectory)benchmark\project.json + $(JitPackagesConfigFileDirectory)benchmark\project.lock.json + + + + + -- 2.7.4