tests/src/JIT/Performance/CodeQuality/BenchI/TreeSort/TreeSort.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 TreeSort
  16 {
  17
  18 #if DEBUG
  19     public const int Iterations = 1;
  20 #else
  21     public const int Iterations = 1200;
  22 #endif
  23
  24     const int SortElements = 5000;
  25     const int Modulus = 65536;
  26
  27     sealed class Node
  28     {
  29         public Node Left;
  30         public Node Right;
  31         public int Val;
  32         public Node(int n)
  33         {
  34             Left = null;
  35             Right = null;
  36             Val = n;
  37         }
  38     }
  39
  40     static int s_biggest;
  41     static int s_littlest;
  42     static int s_seed;
  43
  44     static void InitRand() {
  45         s_seed = 33;
  46     }
  47
  48     static int Rand(ref int seed) {
  49         int multiplier = 25173;
  50         int increment = 13849;
  51         seed = (multiplier * seed + increment) % Modulus;
  52         return seed;
  53     }
  54
  55     static void InitArray(int[] sortList) {
  56         InitRand();
  57         s_biggest = 0;
  58         s_littlest = Modulus;
  59         for (int i = 1; i <= SortElements; i++) {
  60             sortList[i] = Rand(ref s_seed) - 1;
  61             if (sortList[i] > s_biggest) {
  62                 s_biggest = sortList[i];
  63             }
  64             else if (sortList[i] < s_littlest) {
  65                 s_littlest = sortList[i];
  66             }
  67         }
  68     }
  69
  70     static void Insert(int n, Node t) {
  71         if (n > t.Val) {
  72             if (t.Left == null) {
  73                 t.Left = new Node(n);
  74             }
  75             else {
  76                 Insert(n, t.Left);
  77             }
  78         }
  79         else if (n < t.Val) {
  80             if (t.Right == null) {
  81                 t.Right = new Node(n);
  82             }
  83             else {
  84                 Insert(n, t.Right);
  85             }
  86         }
  87     }
  88
  89     static bool CheckTree(Node p) {
  90         bool result = true;
  91         if (p.Left != null) {
  92             if (p.Left.Val <= p.Val) {
  93                 result = false;
  94             }
  95             else {
  96                 result &= CheckTree(p.Left);
  97             }
  98         }
  99
 100         if (p.Right != null) {
 101             if (p.Right.Val >= p.Val) {
 102                 result = false;
 103             }
 104             else {
 105                 result &= CheckTree(p.Right);
 106             }
 107         }
 108
 109         return result;
 110     }
 111
 112     static bool Trees(int[] sortList) {
 113         InitArray(sortList);
 114         Node tree = new Node(sortList[1]);
 115         for (int i = 2; i <= SortElements; i++) {
 116             Insert(sortList[i], tree);
 117         }
 118         bool result = CheckTree(tree);
 119         return result;
 120     }
 121
 122     [MethodImpl(MethodImplOptions.NoInlining)]
 123     static bool Bench() {
 124         int[] sortList = new int[SortElements + 1];
 125         bool result = Trees(sortList);
 126         return result;
 127     }
 128
 129     [Benchmark]
 130     public static void Test() {
 131         foreach (var iteration in Benchmark.Iterations) {
 132             using (iteration.StartMeasurement()) {
 133                 for (int i = 0; i < Iterations; i++) {
 134                     Bench();
 135                 }
 136             }
 137         }
 138     }
 139
 140     static bool TestBase() {
 141         bool result = true;
 142         for (int i = 0; i < Iterations; i++) {
 143             result &= Bench();
 144         }
 145         return result;
 146     }
 147
 148     public static int Main() {
 149         bool result = TestBase();
 150         return (result ? 100 : -1);
 151     }
 152 }
 153 }