tests/src/JIT/Performance/CodeQuality/Benchstones/BenchI/TreeInsert/TreeInsert.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 class TreeInsert
  16 {
  17 #if DEBUG
  18     public const int Iterations = 1;
  19 #else
  20     public const int Iterations = 15000;
  21 #endif
  22
  23     private struct Node
  24     {
  25         public int A;
  26         public int L;
  27         public int R;
  28     }
  29
  30     private struct Tree
  31     {
  32         public int Root;
  33         public int NextAvail;
  34         public Node[] Nodes;
  35     }
  36
  37     private Tree _s;
  38
  39     public TreeInsert()
  40     {
  41         _s.Nodes = new Node[10001];
  42     }
  43
  44     private void BenchInner(int x)
  45     {
  46         /* a tree insertion routine from knuth */
  47         int i = _s.Root;
  48         int j = _s.NextAvail;
  49
  50     L10:
  51         /* compare */
  52         if (_s.Nodes[i].A < x)
  53         {
  54             if (_s.Nodes[i].L != 0)
  55             {
  56                 i = _s.Nodes[i].L;
  57                 goto L10;
  58             }
  59             else
  60             {
  61                 _s.Nodes[i].L = j;
  62                 goto L20;
  63             }
  64         }
  65         else
  66         {
  67             if (_s.Nodes[i].R != 0)
  68             {
  69                 i = _s.Nodes[i].R;
  70                 goto L10;
  71             }
  72             else
  73             {
  74                 _s.Nodes[i].R = j;
  75                 goto L20;
  76             }
  77         }
  78
  79     L20:
  80         /* insert */
  81         _s.Nodes[j].A = x;
  82         _s.Nodes[j].L = 0;
  83         _s.Nodes[j].R = 0;
  84         _s.NextAvail = j + 1;
  85     }
  86
  87
  88     [MethodImpl(MethodImplOptions.NoInlining)]
  89     private bool Bench()
  90     {
  91         _s.Root = 1;
  92         _s.NextAvail = 2;
  93         _s.Nodes[1].A = 300;
  94         _s.Nodes[1].L = 0;
  95         _s.Nodes[1].R = 0;
  96
  97         int j = 99999;
  98         for (int i = 1; i <= 900; i++)
  99         {
 100             BenchInner(j & 4095);
 101             j = j + 33333;
 102         }
 103
 104         return (_s.Nodes[500].A == 441);
 105     }
 106
 107     [Benchmark]
 108     public static void Test()
 109     {
 110         TreeInsert T = new TreeInsert();
 111         foreach (var iteration in Benchmark.Iterations)
 112         {
 113             using (iteration.StartMeasurement())
 114             {
 115                 for (int i = 1; i <= Iterations; i++)
 116                 {
 117                     T.Bench();
 118                 }
 119             }
 120         }
 121     }
 122
 123     private static bool TestBase()
 124     {
 125         TreeInsert T = new TreeInsert();
 126         bool result = true;
 127         for (int i = 1; i <= Iterations; i++)
 128         {
 129             result &= T.Bench();
 130         }
 131         return result;
 132     }
 133
 134     public static int Main()
 135     {
 136         bool result = TestBase();
 137         return (result ? 100 : -1);
 138     }
 139 }
 140 }