Various sorting benchmarks

TreeSort, HeapSort, QuickSort, BubbleSort, BubbleSort2

10 files changed, 785 insertions, 0 deletions

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 0000000000..51a020e3cf
--- /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 0000000000..dbf39d75ee
--- /dev/null
+++ b/tests/src/JIT/Performance/CodeQuality/BenchI/BubbleSort/BubbleSort.csproj
@@ -0,0 +1,45 @@
+<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="12.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <Import Project="$([MSBuild]::GetDirectoryNameOfFileAbove($(MSBuildThisFileDirectory), dir.props))\dir.props" />
+  <PropertyGroup>
+    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+    <SchemaVersion>2.0</SchemaVersion>
+    <ProjectGuid>{95DFC527-4DC1-495E-97D7-E94EE1F7140D}</ProjectGuid>
+    <OutputType>Exe</OutputType>
+    <AppDesignerFolder>Properties</AppDesignerFolder>
+    <FileAlignment>512</FileAlignment>
+    <ProjectTypeGuids>{786C830F-07A1-408B-BD7F-6EE04809D6DB};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}</ProjectTypeGuids>
+    <ReferencePath>$(ProgramFiles)\Common Files\microsoft shared\VSTT\11.0\UITestExtensionPackages</ReferencePath>
+    <SolutionDir Condition="$(SolutionDir) == '' Or $(SolutionDir) == '*Undefined*'">..\..\</SolutionDir>
+    <NuGetPackageImportStamp>7a9bfb7d</NuGetPackageImportStamp>
+  </PropertyGroup>
+  <!-- Default configurations to help VS understand the configurations -->
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+    <DebugType>pdbonly</DebugType>
+    <Optimize>true</Optimize>
+  </PropertyGroup>
+  <ItemGroup>
+    <CodeAnalysisDependentAssemblyPaths Condition=" '$(VS100COMNTOOLS)' != '' " Include="$(VS100COMNTOOLS)..\IDE\PrivateAssemblies">
+      <Visible>False</Visible>
+    </CodeAnalysisDependentAssemblyPaths>
+  </ItemGroup>
+  <ItemGroup>
+    <None Include="$(JitPackagesConfigFileDirectory)benchmark\project.json" />
+  </ItemGroup>
+  <ItemGroup>
+    <Service Include="{82A7F48D-3B50-4B1E-B82E-3ADA8210C358}" />
+  </ItemGroup>
+  <ItemGroup>
+    <Compile Include="BubbleSort.cs" />
+  </ItemGroup>
+  <PropertyGroup>
+    <ProjectJson>$(JitPackagesConfigFileDirectory)benchmark\project.json</ProjectJson>
+    <ProjectLockJson>$(JitPackagesConfigFileDirectory)benchmark\project.lock.json</ProjectLockJson>
+  </PropertyGroup>
+  <Import Project="$([MSBuild]::GetDirectoryNameOfFileAbove($(MSBuildThisFileDirectory), dir.targets))\dir.targets" />
+  <PropertyGroup Condition=" '$(MsBuildProjectDirOverride)' != '' ">
+  </PropertyGroup>
+</Project>
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 0000000000..03d85a01b4
--- /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 0000000000..490664f078
--- /dev/null
+++ b/tests/src/JIT/Performance/CodeQuality/BenchI/BubbleSort2/BubbleSort2.csproj
@@ -0,0 +1,45 @@
+<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="12.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <Import Project="$([MSBuild]::GetDirectoryNameOfFileAbove($(MSBuildThisFileDirectory), dir.props))\dir.props" />
+  <PropertyGroup>
+    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+    <SchemaVersion>2.0</SchemaVersion>
+    <ProjectGuid>{95DFC527-4DC1-495E-97D7-E94EE1F7140D}</ProjectGuid>
+    <OutputType>Exe</OutputType>
+    <AppDesignerFolder>Properties</AppDesignerFolder>
+    <FileAlignment>512</FileAlignment>
+    <ProjectTypeGuids>{786C830F-07A1-408B-BD7F-6EE04809D6DB};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}</ProjectTypeGuids>
+    <ReferencePath>$(ProgramFiles)\Common Files\microsoft shared\VSTT\11.0\UITestExtensionPackages</ReferencePath>
+    <SolutionDir Condition="$(SolutionDir) == '' Or $(SolutionDir) == '*Undefined*'">..\..\</SolutionDir>
+    <NuGetPackageImportStamp>7a9bfb7d</NuGetPackageImportStamp>
+  </PropertyGroup>
+  <!-- Default configurations to help VS understand the configurations -->
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+    <DebugType>pdbonly</DebugType>
+    <Optimize>true</Optimize>
+  </PropertyGroup>
+  <ItemGroup>
+    <CodeAnalysisDependentAssemblyPaths Condition=" '$(VS100COMNTOOLS)' != '' " Include="$(VS100COMNTOOLS)..\IDE\PrivateAssemblies">
+      <Visible>False</Visible>
+    </CodeAnalysisDependentAssemblyPaths>
+  </ItemGroup>
+  <ItemGroup>
+    <None Include="$(JitPackagesConfigFileDirectory)benchmark\project.json" />
+  </ItemGroup>
+  <ItemGroup>
+    <Service Include="{82A7F48D-3B50-4B1E-B82E-3ADA8210C358}" />
+  </ItemGroup>
+  <ItemGroup>
+    <Compile Include="BubbleSort2.cs" />
+  </ItemGroup>
+  <PropertyGroup>
+    <ProjectJson>$(JitPackagesConfigFileDirectory)benchmark\project.json</ProjectJson>
+    <ProjectLockJson>$(JitPackagesConfigFileDirectory)benchmark\project.lock.json</ProjectLockJson>
+  </PropertyGroup>
+  <Import Project="$([MSBuild]::GetDirectoryNameOfFileAbove($(MSBuildThisFileDirectory), dir.targets))\dir.targets" />
+  <PropertyGroup Condition=" '$(MsBuildProjectDirOverride)' != '' ">
+  </PropertyGroup>
+</Project>
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 0000000000..11c6484c42
--- /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 0000000000..b65cce0786
--- /dev/null
+++ b/tests/src/JIT/Performance/CodeQuality/BenchI/HeapSort/HeapSort.csproj
@@ -0,0 +1,45 @@
+<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="12.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <Import Project="$([MSBuild]::GetDirectoryNameOfFileAbove($(MSBuildThisFileDirectory), dir.props))\dir.props" />
+  <PropertyGroup>
+    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+    <SchemaVersion>2.0</SchemaVersion>
+    <ProjectGuid>{95DFC527-4DC1-495E-97D7-E94EE1F7140D}</ProjectGuid>
+    <OutputType>Exe</OutputType>
+    <AppDesignerFolder>Properties</AppDesignerFolder>
+    <FileAlignment>512</FileAlignment>
+    <ProjectTypeGuids>{786C830F-07A1-408B-BD7F-6EE04809D6DB};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}</ProjectTypeGuids>
+    <ReferencePath>$(ProgramFiles)\Common Files\microsoft shared\VSTT\11.0\UITestExtensionPackages</ReferencePath>
+    <SolutionDir Condition="$(SolutionDir) == '' Or $(SolutionDir) == '*Undefined*'">..\..\</SolutionDir>
+    <NuGetPackageImportStamp>7a9bfb7d</NuGetPackageImportStamp>
+  </PropertyGroup>
+  <!-- Default configurations to help VS understand the configurations -->
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+    <DebugType>pdbonly</DebugType>
+    <Optimize>true</Optimize>
+  </PropertyGroup>
+  <ItemGroup>
+    <CodeAnalysisDependentAssemblyPaths Condition=" '$(VS100COMNTOOLS)' != '' " Include="$(VS100COMNTOOLS)..\IDE\PrivateAssemblies">
+      <Visible>False</Visible>
+    </CodeAnalysisDependentAssemblyPaths>
+  </ItemGroup>
+  <ItemGroup>
+    <None Include="$(JitPackagesConfigFileDirectory)benchmark\project.json" />
+  </ItemGroup>
+  <ItemGroup>
+    <Service Include="{82A7F48D-3B50-4B1E-B82E-3ADA8210C358}" />
+  </ItemGroup>
+  <ItemGroup>
+    <Compile Include="HeapSort.cs" />
+  </ItemGroup>
+  <PropertyGroup>
+    <ProjectJson>$(JitPackagesConfigFileDirectory)benchmark\project.json</ProjectJson>
+    <ProjectLockJson>$(JitPackagesConfigFileDirectory)benchmark\project.lock.json</ProjectLockJson>
+  </PropertyGroup>
+  <Import Project="$([MSBuild]::GetDirectoryNameOfFileAbove($(MSBuildThisFileDirectory), dir.targets))\dir.targets" />
+  <PropertyGroup Condition=" '$(MsBuildProjectDirOverride)' != '' ">
+  </PropertyGroup>
+</Project>
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 0000000000..ea06ab37da
--- /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 0000000000..37f3d1386d
--- /dev/null
+++ b/tests/src/JIT/Performance/CodeQuality/BenchI/QuickSort/QuickSort.csproj
@@ -0,0 +1,45 @@
+<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="12.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <Import Project="$([MSBuild]::GetDirectoryNameOfFileAbove($(MSBuildThisFileDirectory), dir.props))\dir.props" />
+  <PropertyGroup>
+    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+    <SchemaVersion>2.0</SchemaVersion>
+    <ProjectGuid>{95DFC527-4DC1-495E-97D7-E94EE1F7140D}</ProjectGuid>
+    <OutputType>Exe</OutputType>
+    <AppDesignerFolder>Properties</AppDesignerFolder>
+    <FileAlignment>512</FileAlignment>
+    <ProjectTypeGuids>{786C830F-07A1-408B-BD7F-6EE04809D6DB};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}</ProjectTypeGuids>
+    <ReferencePath>$(ProgramFiles)\Common Files\microsoft shared\VSTT\11.0\UITestExtensionPackages</ReferencePath>
+    <SolutionDir Condition="$(SolutionDir) == '' Or $(SolutionDir) == '*Undefined*'">..\..\</SolutionDir>
+    <NuGetPackageImportStamp>7a9bfb7d</NuGetPackageImportStamp>
+  </PropertyGroup>
+  <!-- Default configurations to help VS understand the configurations -->
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+    <DebugType>pdbonly</DebugType>
+    <Optimize>true</Optimize>
+  </PropertyGroup>
+  <ItemGroup>
+    <CodeAnalysisDependentAssemblyPaths Condition=" '$(VS100COMNTOOLS)' != '' " Include="$(VS100COMNTOOLS)..\IDE\PrivateAssemblies">
+      <Visible>False</Visible>
+    </CodeAnalysisDependentAssemblyPaths>
+  </ItemGroup>
+  <ItemGroup>
+    <None Include="$(JitPackagesConfigFileDirectory)benchmark\project.json" />
+  </ItemGroup>
+  <ItemGroup>
+    <Service Include="{82A7F48D-3B50-4B1E-B82E-3ADA8210C358}" />
+  </ItemGroup>
+  <ItemGroup>
+    <Compile Include="QuickSort.cs" />
+  </ItemGroup>
+  <PropertyGroup>
+    <ProjectJson>$(JitPackagesConfigFileDirectory)benchmark\project.json</ProjectJson>
+    <ProjectLockJson>$(JitPackagesConfigFileDirectory)benchmark\project.lock.json</ProjectLockJson>
+  </PropertyGroup>
+  <Import Project="$([MSBuild]::GetDirectoryNameOfFileAbove($(MSBuildThisFileDirectory), dir.targets))\dir.targets" />
+  <PropertyGroup Condition=" '$(MsBuildProjectDirOverride)' != '' ">
+  </PropertyGroup>
+</Project>
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 0000000000..a1af0d1572
--- /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 0000000000..65f435e17a
--- /dev/null
+++ b/tests/src/JIT/Performance/CodeQuality/BenchI/TreeSort/TreeSort.csproj
@@ -0,0 +1,45 @@
+<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="12.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <Import Project="$([MSBuild]::GetDirectoryNameOfFileAbove($(MSBuildThisFileDirectory), dir.props))\dir.props" />
+  <PropertyGroup>
+    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+    <SchemaVersion>2.0</SchemaVersion>
+    <ProjectGuid>{95DFC527-4DC1-495E-97D7-E94EE1F7140D}</ProjectGuid>
+    <OutputType>Exe</OutputType>
+    <AppDesignerFolder>Properties</AppDesignerFolder>
+    <FileAlignment>512</FileAlignment>
+    <ProjectTypeGuids>{786C830F-07A1-408B-BD7F-6EE04809D6DB};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}</ProjectTypeGuids>
+    <ReferencePath>$(ProgramFiles)\Common Files\microsoft shared\VSTT\11.0\UITestExtensionPackages</ReferencePath>
+    <SolutionDir Condition="$(SolutionDir) == '' Or $(SolutionDir) == '*Undefined*'">..\..\</SolutionDir>
+    <NuGetPackageImportStamp>7a9bfb7d</NuGetPackageImportStamp>
+  </PropertyGroup>
+  <!-- Default configurations to help VS understand the configurations -->
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+    <DebugType>pdbonly</DebugType>
+    <Optimize>true</Optimize>
+  </PropertyGroup>
+  <ItemGroup>
+    <CodeAnalysisDependentAssemblyPaths Condition=" '$(VS100COMNTOOLS)' != '' " Include="$(VS100COMNTOOLS)..\IDE\PrivateAssemblies">
+      <Visible>False</Visible>
+    </CodeAnalysisDependentAssemblyPaths>
+  </ItemGroup>
+  <ItemGroup>
+    <None Include="$(JitPackagesConfigFileDirectory)benchmark\project.json" />
+  </ItemGroup>
+  <ItemGroup>
+    <Service Include="{82A7F48D-3B50-4B1E-B82E-3ADA8210C358}" />
+  </ItemGroup>
+  <ItemGroup>
+    <Compile Include="TreeSort.cs" />
+  </ItemGroup>
+  <PropertyGroup>
+    <ProjectJson>$(JitPackagesConfigFileDirectory)benchmark\project.json</ProjectJson>
+    <ProjectLockJson>$(JitPackagesConfigFileDirectory)benchmark\project.lock.json</ProjectLockJson>
+  </PropertyGroup>
+  <Import Project="$([MSBuild]::GetDirectoryNameOfFileAbove($(MSBuildThisFileDirectory), dir.targets))\dir.targets" />
+  <PropertyGroup Condition=" '$(MsBuildProjectDirOverride)' != '' ">
+  </PropertyGroup>
+</Project>