tests/src/JIT/Performance/CodeQuality/Benchstones/BenchI/HeapSort/HeapSort.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 HeapSort
  16 {
  17
  18 #if DEBUG
  19     public const int Iterations = 1;
  20 #else
  21     public const int Iterations = 2500;
  22 #endif
  23
  24     const int ArraySize = 5500;
  25
  26     static void Inner(int[] x, int n) {
  27         int i, j, k, m;
  28
  29         // pass1 -- put vector in heap form
  30         // that is to say, guarantee that x(i)>=x(2*i) and x(i)>=x(2*i+1).
  31         // after pass 1, the largest item will be at x(1).
  32         for (i = 2; i <= n; i++) {
  33             j = i;
  34             k = j / 2;
  35             m = x[i];
  36
  37             // 0 < k <= (n / 2)
  38             // 1 <= j <= n
  39             while (k > 0) {
  40                 if (m <= x[k]) {
  41                     break;
  42                 }
  43                 x[j] = x[k];
  44                 j = k;
  45                 k = k / 2;
  46             }
  47             x[j] = m;
  48         }
  49
  50         // pass 2 --  swap first and last items.  now with the last
  51         // item correctly placed, consider the list shorter by one item.
  52         // restore the shortened list to heap sort, and repeat
  53         // process until list is only two items long.
  54         i = n;
  55         do {
  56             // do i = n to 2 by -1;
  57             m = x[i];
  58             x[i] = x[1];  // last item, i.e. item(i) now correct.
  59             j = 1;        // we now find the appropriate resting point for m
  60             k = 2;
  61
  62             // 2 <= k < i ==> 2 <= k < n
  63             // 1 <= j < n
  64             while (k < i) {
  65                 if ((k + 1) < i) {
  66                     if (x[k + 1] > x[k]) {
  67                         k = k + 1;
  68                     }
  69                 }
  70                 if (x[k] <= m) {
  71                     break;
  72                 }
  73
  74                 x[j] = x[k];
  75                 j = k;
  76                 k = k + k;
  77             }
  78
  79             x[j] = m;
  80             i = i - 1;
  81         } while (i >= 2);
  82     }
  83
  84     [MethodImpl(MethodImplOptions.NoInlining)]
  85     static bool Bench() {
  86         int[] x = new int[ArraySize + 1];
  87         for (int i = 1; i <= ArraySize; i++) {
  88             x[i] = ArraySize - i + 1;
  89         }
  90         Inner(x, ArraySize);
  91         for (int j = 1; j <= ArraySize; j++) {
  92             if (x[j] != j) {
  93                 return false;
  94             }
  95         }
  96         return true;
  97     }
  98
  99     [Benchmark]
 100     public static void Test() {
 101         foreach (var iteration in Benchmark.Iterations) {
 102             using (iteration.StartMeasurement()) {
 103                 for (int i = 0; i < Iterations; i++) {
 104                     Bench();
 105                 }
 106             }
 107         }
 108     }
 109
 110     static bool TestBase() {
 111         bool result = true;
 112         for (int i = 0; i < Iterations; i++) {
 113             result &= Bench();
 114         }
 115         return result;
 116     }
 117
 118     public static int Main() {
 119         bool result = TestBase();
 120         return (result ? 100 : -1);
 121     }
 122 }
 123 }