tests/src/JIT/Performance/CodeQuality/Benchstones/BenchI/QuickSort/QuickSort.cs

   1 // Licensed to the .NET Foundation under one or more agreements.
   2 // The .NET Foundation licenses this file to you under the MIT license.
   3 // See the LICENSE file in the project root for more information.
   4 //
   5
   6 using Microsoft.Xunit.Performance;
   7 using System;
   8 using System.Runtime.CompilerServices;
   9 using Xunit;
  10
  11 [assembly: OptimizeForBenchmarks]
  12
  13 namespace Benchstone.BenchI
  14 {
  15 public static class QuickSort
  16 {
  17
  18 #if DEBUG
  19     public const int Iterations = 1;
  20 #else
  21     public const int Iterations = 80000;
  22 #endif
  23
  24     const int MAXNUM = 200;
  25     const int MODULUS = 0x20000;
  26     const int C = 13849;
  27     const int A = 25173;
  28     static int s_seed = 7;
  29
  30     static int Random(int size) {
  31         unchecked {
  32             s_seed = s_seed * A + C;
  33         }
  34         return (s_seed % size);
  35     }
  36
  37     static void Quick(int lo, int hi, int[] arr) {
  38
  39         int i, j;
  40         int pivot, temp;
  41
  42         if (lo < hi) {
  43             for (i = lo, j = hi, pivot = arr[hi]; i < j;) {
  44                 while (i < j && arr[i] <= pivot){
  45                     ++i;
  46                 }
  47                 while (j > i && arr[j] >= pivot) {
  48                     --j;
  49                 }
  50                 if (i < j) {
  51                     temp = arr[i];
  52                     arr[i] = arr[j];
  53                     arr[j] = temp;
  54                 }
  55             }
  56
  57             // need to swap the pivot and a[i](or a[j] as i==j) so
  58             // that the pivot will be at its final place in the sorted array
  59
  60             if (i != hi) {
  61                 temp = arr[i];
  62                 arr[i] = pivot;
  63                 arr[hi] = temp;
  64             }
  65             Quick(lo, i - 1, arr);
  66             Quick(i + 1, hi, arr);
  67         }
  68     }
  69
  70     [MethodImpl(MethodImplOptions.NoInlining)]
  71     static bool Bench() {
  72
  73         int[] buffer = new int[MAXNUM];
  74
  75         for (int j = 0; j < MAXNUM; ++j) {
  76             int temp = Random(MODULUS);
  77             if (temp < 0){
  78                 temp = (-temp);
  79             }
  80             buffer[j] = temp;
  81         }
  82
  83         Quick(0, MAXNUM - 1, buffer);
  84
  85         for (int j = 0; j < MAXNUM - 1; ++j) {
  86             if (buffer[j] > buffer[j+1]) {
  87                 return false;
  88             }
  89         }
  90
  91         return true;
  92     }
  93
  94     [Benchmark]
  95     public static void Test() {
  96         foreach (var iteration in Benchmark.Iterations) {
  97             using (iteration.StartMeasurement()) {
  98                 for (int i = 0; i < Iterations; i++) {
  99                     Bench();
 100                 }
 101             }
 102         }
 103     }
 104
 105     static bool TestBase() {
 106         bool result = true;
 107         for (int i = 0; i < Iterations; i++) {
 108             result &= Bench();
 109         }
 110         return result;
 111     }
 112
 113     public static int Main() {
 114         bool result = TestBase();
 115         return (result ? 100 : -1);
 116     }
 117 }
 118 }