tests/src/JIT/Performance/CodeQuality/BenchI/Puzzle/Puzzle.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 Puzzle
  16 {
  17 #if DEBUG
  18     public const int Iterations = 1;
  19 #else
  20     public const int Iterations = 400;
  21 #endif
  22
  23     private const int PuzzleSize = 511;
  24     private const int ClassMax = 3;
  25     private const int TypeMax = 12;
  26     private const int D = 8;
  27
  28     private int[] _pieceCount = new int[ClassMax + 1];
  29     private int[] _class = new int[TypeMax + 1];
  30     private int[] _pieceMax = new int[TypeMax + 1];
  31     private bool[] _puzzle = new bool[PuzzleSize + 1];
  32     private bool[][] _p;
  33     private int _count;
  34
  35     private static T[][] AllocArray<T>(int n1, int n2)
  36     {
  37         T[][] a = new T[n1][];
  38         for (int i = 0; i < n1; ++i)
  39         {
  40             a[i] = new T[n2];
  41         }
  42
  43         return a;
  44     }
  45
  46     private bool Fit(int i, int j)
  47     {
  48         for (int k = 0; k <= _pieceMax[i]; k++)
  49         {
  50             if (_p[i][k])
  51             {
  52                 if (_puzzle[j + k])
  53                 {
  54                     return false;
  55                 }
  56             }
  57         }
  58
  59         return true;
  60     }
  61
  62     private int Place(int i, int j)
  63     {
  64         int k;
  65         for (k = 0; k <= _pieceMax[i]; k++)
  66         {
  67             if (_p[i][k])
  68             {
  69                 _puzzle[j + k] = true;
  70             }
  71         }
  72
  73         _pieceCount[_class[i]] = _pieceCount[_class[i]] - 1;
  74
  75         for (k = j; k <= PuzzleSize; k++)
  76         {
  77             if (!_puzzle[k])
  78             {
  79                 return k;
  80             }
  81         }
  82
  83         return 0;
  84     }
  85
  86     private void RemoveLocal(int i, int j)
  87     {
  88         for (int k = 0; k <= _pieceMax[i]; k++)
  89         {
  90             if (_p[i][k])
  91             {
  92                 _puzzle[j + k] = false;
  93             }
  94         }
  95
  96         _pieceCount[_class[i]] = _pieceCount[_class[i]] + 1;
  97     }
  98
  99     private bool Trial(int j)
 100     {
 101         for (int i = 0; i <= TypeMax; i++)
 102         {
 103             if (_pieceCount[_class[i]] != 0)
 104             {
 105                 if (Fit(i, j))
 106                 {
 107                     int k = Place(i, j);
 108                     if (Trial(k) || (k == 0))
 109                     {
 110                         _count = _count + 1;
 111                         return true;
 112                     }
 113                     else
 114                     {
 115                         RemoveLocal(i, j);
 116                     }
 117                 }
 118             }
 119         }
 120
 121         _count = _count + 1;
 122         return false;
 123     }
 124
 125     private bool DoIt()
 126     {
 127         int i, j, k, m, n;
 128
 129         for (m = 0; m <= PuzzleSize; m++)
 130         {
 131             _puzzle[m] = true;
 132         }
 133
 134         for (i = 1; i <= 5; i++)
 135         {
 136             for (j = 1; j <= 5; j++)
 137             {
 138                 for (k = 1; k <= 5; k++)
 139                 {
 140                     _puzzle[i + D * (j + D * k)] = false;
 141                 }
 142             }
 143         }
 144
 145         for (i = 0; i <= TypeMax; i++)
 146         {
 147             for (m = 0; m <= PuzzleSize; m++)
 148             {
 149                 _p[i][m] = false;
 150             }
 151         }
 152
 153         for (i = 0; i <= 3; i++)
 154         {
 155             for (j = 0; j <= 1; j++)
 156             {
 157                 for (k = 0; k <= 0; k++)
 158                 {
 159                     _p[0][i + D * (j + D * k)] = true;
 160                 }
 161             }
 162         }
 163
 164         _class[0] = 0;
 165         _pieceMax[0] = 3 + D * 1 + D * D * 0;
 166
 167         for (i = 0; i <= 1; i++)
 168         {
 169             for (j = 0; j <= 0; j++)
 170             {
 171                 for (k = 0; k <= 3; k++)
 172                 {
 173                     _p[1][i + D * (j + D * k)] = true;
 174                 }
 175             }
 176         }
 177
 178         _class[1] = 0;
 179         _pieceMax[1] = 1 + D * 0 + D * D * 3;
 180
 181         for (i = 0; i <= 0; i++)
 182         {
 183             for (j = 0; j <= 3; j++)
 184             {
 185                 for (k = 0; k <= 1; k++)
 186                 {
 187                     _p[2][i + D * (j + D * k)] = true;
 188                 }
 189             }
 190         }
 191         _class[2] = 0;
 192         _pieceMax[2] = 0 + D * 3 + D * D * 1;
 193
 194         for (i = 0; i <= 1; i++)
 195         {
 196             for (j = 0; j <= 3; j++)
 197             {
 198                 for (k = 0; k <= 0; k++)
 199                 {
 200                     _p[3][i + D * (j + D * k)] = true;
 201                 }
 202             }
 203         }
 204
 205         _class[3] = 0;
 206         _pieceMax[3] = 1 + D * 3 + D * D * 0;
 207
 208         for (i = 0; i <= 3; i++)
 209         {
 210             for (j = 0; j <= 0; j++)
 211             {
 212                 for (k = 0; k <= 1; k++)
 213                 {
 214                     _p[4][i + D * (j + D * k)] = true;
 215                 }
 216             }
 217         }
 218
 219         _class[4] = 0;
 220         _pieceMax[4] = 3 + D * 0 + D * D * 1;
 221
 222         for (i = 0; i <= 0; i++)
 223         {
 224             for (j = 0; j <= 1; j++)
 225             {
 226                 for (k = 0; k <= 3; k++)
 227                 {
 228                     _p[5][i + D * (j + D * k)] = true;
 229                 }
 230             }
 231         }
 232
 233         _class[5] = 0;
 234         _pieceMax[5] = 0 + D * 1 + D * D * 3;
 235
 236         for (i = 0; i <= 2; i++)
 237         {
 238             for (j = 0; j <= 0; j++)
 239             {
 240                 for (k = 0; k <= 0; k++)
 241                 {
 242                     _p[6][i + D * (j + D * k)] = true;
 243                 }
 244             }
 245         }
 246
 247         _class[6] = 1;
 248         _pieceMax[6] = 2 + D * 0 + D * D * 0;
 249
 250         for (i = 0; i <= 0; i++)
 251         {
 252             for (j = 0; j <= 2; j++)
 253             {
 254                 for (k = 0; k <= 0; k++)
 255                 {
 256                     _p[7][i + D * (j + D * k)] = true;
 257                 }
 258             }
 259         }
 260
 261         _class[7] = 1;
 262         _pieceMax[7] = 0 + D * 2 + D * D * 0;
 263
 264         for (i = 0; i <= 0; i++)
 265         {
 266             for (j = 0; j <= 0; j++)
 267             {
 268                 for (k = 0; k <= 2; k++)
 269                 {
 270                     _p[8][i + D * (j + D * k)] = true;
 271                 }
 272             }
 273         }
 274
 275         _class[8] = 1;
 276         _pieceMax[8] = 0 + D * 0 + D * D * 2;
 277
 278         for (i = 0; i <= 1; i++)
 279         {
 280             for (j = 0; j <= 1; j++)
 281             {
 282                 for (k = 0; k <= 0; k++)
 283                 {
 284                     _p[9][i + D * (j + D * k)] = true;
 285                 }
 286             }
 287         }
 288         _class[9] = 2;
 289         _pieceMax[9] = 1 + D * 1 + D * D * 0;
 290
 291         for (i = 0; i <= 1; i++)
 292         {
 293             for (j = 0; j <= 0; j++)
 294             {
 295                 for (k = 0; k <= 1; k++)
 296                 {
 297                     _p[10][i + D * (j + D * k)] = true;
 298                 }
 299             }
 300         }
 301
 302         _class[10] = 2;
 303         _pieceMax[10] = 1 + D * 0 + D * D * 1;
 304
 305         for (i = 0; i <= 0; i++)
 306         {
 307             for (j = 0; j <= 1; j++)
 308             {
 309                 for (k = 0; k <= 1; k++)
 310                 {
 311                     _p[11][i + D * (j + D * k)] = true;
 312                 }
 313             }
 314         }
 315
 316         _class[11] = 2;
 317         _pieceMax[11] = 0 + D * 1 + D * D * 1;
 318
 319         for (i = 0; i <= 1; i++)
 320         {
 321             for (j = 0; j <= 1; j++)
 322             {
 323                 for (k = 0; k <= 1; k++)
 324                 {
 325                     _p[12][i + D * (j + D * k)] = true;
 326                 }
 327             }
 328         }
 329
 330         _class[12] = 3;
 331         _pieceMax[12] = 1 + D * 1 + D * D * 1;
 332         _pieceCount[0] = 13;
 333         _pieceCount[1] = 3;
 334         _pieceCount[2] = 1;
 335         _pieceCount[3] = 1;
 336         m = 1 + D * (1 + D * 1);
 337         _count = 0;
 338
 339         bool result = true;
 340
 341         if (Fit(0, m))
 342         {
 343             n = Place(0, m);
 344             result = Trial(n);
 345         }
 346         else
 347         {
 348             result = false;
 349         }
 350
 351         return result;
 352     }
 353
 354     [MethodImpl(MethodImplOptions.NoInlining)]
 355     private bool Bench()
 356     {
 357         _p = AllocArray<bool>(TypeMax + 1, PuzzleSize + 1);
 358
 359         bool result = true;
 360
 361         for (int i = 0; i < Iterations; ++i)
 362         {
 363             result &= DoIt();
 364         }
 365
 366         return result;
 367     }
 368
 369     [Benchmark]
 370     public static void Test()
 371     {
 372         Puzzle P = new Puzzle();
 373         foreach (var iteration in Benchmark.Iterations)
 374         {
 375             using (iteration.StartMeasurement())
 376             {
 377                 P.Bench();
 378             }
 379         }
 380     }
 381
 382     private static bool TestBase()
 383     {
 384         Puzzle P = new Puzzle();
 385         bool result = P.Bench();
 386         return result;
 387     }
 388
 389     public static int Main()
 390     {
 391         bool result = TestBase();
 392         return (result ? 100 : -1);
 393     }
 394 }
 395 }