Robust/Transactions/dstm2/src/dstm2/benchmark/IntSetBenchmark.java

   1 /*
   2  * IntSetBenchmark.java
   3  *
   4  * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
   5  * Clara, California 95054, U.S.A.  All rights reserved.
   6  *
   7  * Sun Microsystems, Inc. has intellectual property rights relating to
   8  * technology embodied in the product that is described in this
   9  * document.  In particular, and without limitation, these
  10  * intellectual property rights may include one or more of the
  11  * U.S. patents listed at http://www.sun.com/patents and one or more
  12  * additional patents or pending patent applications in the U.S. and
  13  * in other countries.
  14  *
  15  * U.S. Government Rights - Commercial software.
  16  * Government users are subject to the Sun Microsystems, Inc. standard
  17  * license agreement and applicable provisions of the FAR and its
  18  * supplements.  Use is subject to license terms.  Sun, Sun
  19  * Microsystems, the Sun logo and Java are trademarks or registered
  20  * trademarks of Sun Microsystems, Inc. in the U.S. and other
  21  * countries.
  22  *
  23  * This product is covered and controlled by U.S. Export Control laws
  24  * and may be subject to the export or import laws in other countries.
  25  * Nuclear, missile, chemical biological weapons or nuclear maritime
  26  * end uses or end users, whether direct or indirect, are strictly
  27  * prohibited.  Export or reexport to countries subject to
  28  * U.S. embargo or to entities identified on U.S. export exclusion
  29  * lists, including, but not limited to, the denied persons and
  30  * specially designated nationals lists is strictly prohibited.
  31  */
  32
  33 package dstm2.benchmark;
  34
  35 import TransactionalIO.exceptions.AbortedException;
  36 import TransactionalIO.exceptions.GracefulException;
  37 import TransactionalIO.exceptions.PanicException;
  38 import dstm2.Thread;
  39
  40 import TransactionalIO.benchmarks.benchmark;
  41 import TransactionalIO.core.TransactionalFile;
  42 import dstm2.util.Random;
  43 import java.io.IOException;
  44 import java.util.Iterator;
  45 import java.util.concurrent.Callable;
  46 import java.util.logging.Level;
  47 import java.util.logging.Logger;
  48
  49 /**
  50  * This abstract class is the superclass for the integer set benchmarks.
  51  * @author Maurice Herlihy
  52  * @date April 2004
  53  */
  54 public abstract class IntSetBenchmark implements Benchmark, Iterable<Integer> {
  55
  56   /**
  57    * How large to initialize the integer set.
  58    */
  59   protected final int INITIAL_SIZE = 8;
  60
  61   /**
  62    * After the run is over, synchronize merging statistics with other threads.
  63    */
  64   static final Object lock = new Object();
  65   /**
  66    * local variable
  67    */
  68   int element;
  69   /**
  70    * local variable
  71    */
  72   int value;
  73
  74   /**
  75    * Number of calls to insert()
  76    */
  77   int insertCalls = 0;
  78   /**
  79    * number of calls to contains()
  80    */
  81   int containsCalls = 0;
  82   /**
  83    * number of calls to remove()
  84    */
  85   int removeCalls = 0;
  86   /**
  87    * amount by which the set size has changed
  88    */
  89   int delta = 0;
  90
  91   /**
  92    * Give subclass a chance to intialize private fields.
  93    */
  94   protected abstract void init();
  95
  96   /**
  97    * Iterate through set. Not necessarily thread-safe.
  98    */
  99   public abstract Iterator<Integer> iterator();
 100
 101   /**
 102    * Add an element to the integer set, if it is not already there.
 103    * @param v the integer value to add from the set
 104    * @return true iff value was added.
 105    */
 106   public abstract boolean insert(int v);
 107
 108   /**
 109    * Tests wheter a value is in an the integer set.
 110    * @param v the integer value to insert into the set
 111    * @return true iff presence was confirmed.
 112    */
 113   public abstract boolean contains(int v);
 114
 115   /**
 116    * Removes an element from the integer set, if it is there.
 117    * @param v the integer value to delete from the set
 118    * @return true iff v was removed
 119    */
 120   public abstract boolean remove(int v);
 121
 122   /**
 123    * Creates a new test thread.
 124    * @param percent Mix of mutators and observers.
 125    * @return Thread to run.
 126    */
 127   public Thread createThread(int percent, char sample) {
 128     try {
 129       TestThread testThread = new TestThread(this, percent, sample);
 130       return testThread;
 131     } catch (Exception e) {
 132       e.printStackTrace(System.out);
 133       return null;
 134     }
 135   }
 136
 137   /**
 138    * Prints an error message to <code>System.out</code>, including a
 139    *  standard header to identify the message as an error message.
 140    * @param s String describing error
 141    */
 142   protected static void reportError(String s) {
 143     System.out.println(" ERROR: " + s);
 144     System.out.flush();
 145   }
 146
 147   public void report() {
 148     System.out.println("Insert/Remove calls:\t" + (insertCalls + removeCalls));
 149     System.out.println("Contains calls:\t" + containsCalls);
 150   }
 151
 152   private class TestThread extends Thread {
 153     IntSetBenchmark intSet;
 154     /**
 155      * Thread-local statistic.
 156      */
 157     int myInsertCalls = 0;
 158     /**
 159      * Thread-local statistic.
 160      */
 161     int myRemoveCalls = 0;
 162     /**
 163      * Thread-local statistic.
 164      */
 165     int myContainsCalls = 0;
 166     /**
 167      * Thread-local statistic.
 168      */
 169     int myDelta = 0;        // net change
 170     public int percent = 0; // percent inserts
 171     char sample;
 172     AVLTree tree;
 173
 174     TestThread(IntSetBenchmark intSet, int percent, char sample) {
 175       this.intSet = intSet;
 176       this.percent = percent;
 177       this.sample = sample;
 178     }
 179
 180
 181
 182     public void run() {
 183       Random random = new Random(this.hashCode());
 184       random.setSeed(System.currentTimeMillis()); // comment out for determinstic
 185
 186       boolean toggle = true;
 187       final TransactionalFile f1 = (TransactionalFile)benchmark.TransactionalFiles.get("0");
 188       try {
 189         while (true) {
 190           boolean result = true;
 191           element = random.nextInt();
 192           if (Math.abs(element) % 100 < percent) {
 193             if (toggle) {        // insert on even turns
 194               value = element / 100;
 195               result = Thread.doIt(new Callable<Boolean>() {
 196                 public Boolean call() {
 197                     //////////////////////////////////////////benchmark 1////////////////////////////
 198                       /*  TransactionalFile f1 = (TransactionalFile)benchmark.m.get("2");
 199                         byte[] data = new byte[1];
 200                         char[] holder = new char[10000];
 201                         char[] word = new char[20];
 202                         boolean flag = false;
 203                         long toseek = Integer.valueOf(Thread.currentThread().getName().substring(7)) * 21169;
 204                         f1.seek(toseek);
 205
 206                         data[0] ='a';
 207                         if (toseek != 0) //////////////// skipt the first word since its been read already
 208                             while (data[0] != '\n'){
 209                                 int res;
 210                                 res = f1.read(data);
 211                                 if (res == -1){
 212                                     flag =true;
 213                                     break;
 214                                 }
 215                             }
 216
 217                         boolean completeword = false;
 218                         int counter = 0;
 219                         while (f1.getFilePointer() < toseek +21169)
 220                         {
 221                             if (flag)
 222                                 break;
 223                             data[0] = 'a';
 224                             int i = 0;
 225                             int res;
 226                             while ((data[0] != '\n' || completeword)){
 227
 228                                 //if (completeword){
 229                                  //  String str = Mixedbecnhmark.processInput(String.valueOf(word,0,counter-1));
 230                                    //if (str != null){
 231                                   // update data structure
 232                                   //  byte[] towrite = new byte[String.valueOf(holder,0,i).length()];
 233                                   //  towrite = String.valueOf(holder,0,i).getBytes();
 234                                   //  try {
 235                                  //   ((TransactionalFile) (benchmark.m.get("3"))).write(towrite);
 236
 237                                   //    } catch (IOException ex) {
 238                                   //      Logger.getLogger(TestThread.class.getName()).log(Level.SEVERE, null, ex);
 239                                   //      }
 240                                   //}
 241                                 //}
 242
 243                                if (flag)
 244                                     break;
 245
 246                                if (completeword){
 247                                    synchronized(benchmark.lock){
 248                                   //  if  (!(Character.isWhitespace(word[counter])))
 249                                       //  System.out.println(String.valueOf(word,0,counter-1));
 250                                    }
 251                                     holder[i] = (char)data[0];
 252                                     i++;
 253
 254                                }
 255                                counter = 0;
 256                                completeword= false;
 257                                data[0] = 'a';
 258                                while(Character.isLetter((char)data[0]))
 259                                {
 260
 261                                     res = f1.read(data);
 262                                     if (res == -1){
 263                                         flag = true;
 264                                         break;
 265                                     }
 266                                     word[counter] = (char)data[0];
 267                                     counter++;
 268                                     if (counter > 1)
 269                                         completeword = true;
 270                                     holder[i] = (char)data[0];
 271                                     i++;
 272                                }
 273                             }
 274
 275                         }
 276
 277                         myInsertCalls++;
 278                         return intSet.insert(464);*/
 279                     ////////////////////////benchmark 2///////////////////
 280
 281                     /*    TransactionalFile f1 = (TransactionalFile)benchmark.m.get("0");
 282                         byte[] data = new byte[1];
 283                         char[] holder = new char[10000];
 284                         char[] word = new char[20];
 285                         boolean flag = false;
 286                         long toseek = Integer.valueOf(Thread.currentThread().getName().substring(7)) * 20448;
 287                         f1.seek(toseek);
 288
 289                         data[0] ='a';
 290                         if (toseek != 0) //////////////// skipt the first word since its been read already
 291                             while (data[0] != '\n'){
 292                                 int res;
 293                                 res = f1.read(data);
 294                                 if (res == -1){
 295                                     flag =true;
 296                                     break;
 297                                 }
 298                             }
 299
 300
 301                          while (f1.getFilePointer() < toseek +20448)
 302                         {
 303                             if (flag == true)
 304                                 break;
 305                             data[0] = 'a';
 306                             int i = 0;
 307                             int res;
 308                             while (data[0] != '\n'){
 309                                 res = f1.read(data);
 310                                 if (res == -1){
 311                                     flag = true;
 312                                     break;
 313                                 }
 314
 315                                 holder[i] = (char)data[0];
 316                                 i++;
 317                             }
 318
 319
 320                             byte[] towrite = new byte[String.valueOf(holder,0,i).length()];
 321                             towrite = String.valueOf(holder,0,i).getBytes();
 322                          //   System.out.println(String.valueOf(holder,0,i).toLowerCase().substring(0, 1));
 323
 324                             try {
 325                                 ((TransactionalFile) (benchmark.m.get(String.valueOf(holder,0,i).toLowerCase().substring(0, 1)))).write(towrite);
 326                            //update the memory         //}
 327                             } catch (IOException ex) {
 328                                 Logger.getLogger(TestThread.class.getName()).log(Level.SEVERE, null, ex);
 329                             }
 330                         }  */
 331
 332
 333
 334                     return true;
 335
 336                 }
 337               });
 338               if (result)
 339                 myDelta++;
 340             }
 341             else {
 342                 // remove on odd turns
 343
 344               result = Thread.doIt(new Callable<Boolean>() {
 345                 public Boolean call() {
 346                   return intSet.remove(value);
 347                 }
 348               });
 349               myRemoveCalls++;
 350               if (result)
 351                 this.myDelta--;
 352             }
 353             toggle = !toggle;
 354           } else {
 355             Thread.doIt(new Callable<Void>() {
 356               public Void call() {
 357                 //  return null;
 358                 intSet.contains(element / 100);
 359                 return null;
 360               }
 361             });
 362             myContainsCalls++;
 363           }
 364         }
 365       } catch (GracefulException g) {
 366         // update statistics
 367         synchronized (lock) {
 368
 369           insertCalls   += myInsertCalls;
 370           removeCalls   += myRemoveCalls;
 371           containsCalls += myContainsCalls;
 372           delta         += myDelta;
 373         }
 374         return;
 375       }
 376     }
 377   }
 378
 379   public void sanityCheck() {
 380     long expected = INITIAL_SIZE + delta;
 381     int length = 1;
 382
 383     int prevValue = Integer.MIN_VALUE;
 384     for (int value : this) {
 385       length++;
 386       if (value < prevValue) {
 387         System.out.println("ERROR: set  not sorted");
 388         System.exit(0);
 389       }
 390       if (value == prevValue) {
 391         System.out.println("ERROR: set has duplicates!");
 392         System.exit(0);
 393       }
 394       if (length == expected) {
 395         System.out.println("ERROR: set has bad length!");
 396         System.exit(0);
 397       }
 398
 399     }
 400     System.out.println("Integer Set OK");
 401   }
 402
 403   /**
 404    * Creates a new IntSetBenchmark
 405    */
 406   public IntSetBenchmark() {
 407     int size = 2;
 408     init();
 409     Random random = new Random(this.hashCode());
 410    while (size < INITIAL_SIZE) {
 411       if (insert(random.nextInt())) {
 412         size++;
 413       }
 414     }
 415   }
 416
 417   public void printTree(){};
 418
 419 }