JSTests/microbenchmarks/richards-empty-try-catch.js

   1 // Copyright 2006-2008 the V8 project authors. All rights reserved.
   2 // Redistribution and use in source and binary forms, with or without
   3 // modification, are permitted provided that the following conditions are
   4 // met:
   5 //
   6 //     * Redistributions of source code must retain the above copyright
   7 //       notice, this list of conditions and the following disclaimer.
   8 //     * Redistributions in binary form must reproduce the above
   9 //       copyright notice, this list of conditions and the following
  10 //       disclaimer in the documentation and/or other materials provided
  11 //       with the distribution.
  12 //     * Neither the name of Google Inc. nor the names of its
  13 //       contributors may be used to endorse or promote products derived
  14 //       from this software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27
  28
  29 // This is a JavaScript implementation of the Richards
  30 // benchmark from:
  31 //
  32 //    http://www.cl.cam.ac.uk/~mr10/Bench.html
  33 //
  34 // The benchmark was originally implemented in BCPL by
  35 // Martin Richards.
  36
  37
  38 /**
  39  * The Richards benchmark simulates the task dispatcher of an
  40  * operating system.
  41  **/
  42 function runRichards() {
  43     try {
  44         var scheduler = new Scheduler();
  45         scheduler.addIdleTask(ID_IDLE, 0, null, COUNT);
  46
  47         var queue = new Packet(null, ID_WORKER, KIND_WORK);
  48         queue = new Packet(queue,  ID_WORKER, KIND_WORK);
  49         scheduler.addWorkerTask(ID_WORKER, 1000, queue);
  50
  51         queue = new Packet(null, ID_DEVICE_A, KIND_DEVICE);
  52         queue = new Packet(queue,  ID_DEVICE_A, KIND_DEVICE);
  53         queue = new Packet(queue,  ID_DEVICE_A, KIND_DEVICE);
  54         scheduler.addHandlerTask(ID_HANDLER_A, 2000, queue);
  55
  56         queue = new Packet(null, ID_DEVICE_B, KIND_DEVICE);
  57         queue = new Packet(queue,  ID_DEVICE_B, KIND_DEVICE);
  58         queue = new Packet(queue,  ID_DEVICE_B, KIND_DEVICE);
  59         scheduler.addHandlerTask(ID_HANDLER_B, 3000, queue);
  60
  61         scheduler.addDeviceTask(ID_DEVICE_A, 4000, null);
  62
  63         scheduler.addDeviceTask(ID_DEVICE_B, 5000, null);
  64
  65         scheduler.schedule();
  66
  67         if (scheduler.queueCount != EXPECTED_QUEUE_COUNT ||
  68                 scheduler.holdCount != EXPECTED_HOLD_COUNT) {
  69             var msg =
  70                 "Error during execution: queueCount = " + scheduler.queueCount +
  71                 ", holdCount = " + scheduler.holdCount + ".";
  72             throw new Error(msg);
  73         }
  74     } catch(e) { }
  75 }
  76
  77 var COUNT = 1000;
  78
  79 /**
  80  * These two constants specify how many times a packet is queued and
  81  * how many times a task is put on hold in a correct run of richards.
  82  * They don't have any meaning a such but are characteristic of a
  83  * correct run so if the actual queue or hold count is different from
  84  * the expected there must be a bug in the implementation.
  85  **/
  86 var EXPECTED_QUEUE_COUNT = 2322;
  87 var EXPECTED_HOLD_COUNT = 928;
  88
  89
  90 /**
  91  * A scheduler can be used to schedule a set of tasks based on their relative
  92  * priorities.  Scheduling is done by maintaining a list of task control blocks
  93  * which holds tasks and the data queue they are processing.
  94  * @constructor
  95  */
  96 function Scheduler() {
  97     try {
  98         this.queueCount = 0;
  99         this.holdCount = 0;
 100         this.blocks = new Array(NUMBER_OF_IDS);
 101         this.list = null;
 102         this.currentTcb = null;
 103         this.currentId = null;
 104
 105     } catch(e) { }
 106 }
 107
 108 var ID_IDLE       = 0;
 109 var ID_WORKER     = 1;
 110 var ID_HANDLER_A  = 2;
 111 var ID_HANDLER_B  = 3;
 112 var ID_DEVICE_A   = 4;
 113 var ID_DEVICE_B   = 5;
 114 var NUMBER_OF_IDS = 6;
 115
 116 var KIND_DEVICE   = 0;
 117 var KIND_WORK     = 1;
 118
 119 /**
 120  * Add an idle task to this scheduler.
 121  * @param {int} id the identity of the task
 122  * @param {int} priority the task's priority
 123  * @param {Packet} queue the queue of work to be processed by the task
 124  * @param {int} count the number of times to schedule the task
 125  */
 126 Scheduler.prototype.addIdleTask = function (id, priority, queue, count) {
 127     try {
 128         this.addRunningTask(id, priority, queue, new IdleTask(this, 1, count));
 129     } catch(e) { }
 130 };
 131
 132 /**
 133  * Add a work task to this scheduler.
 134  * @param {int} id the identity of the task
 135  * @param {int} priority the task's priority
 136  * @param {Packet} queue the queue of work to be processed by the task
 137  */
 138 Scheduler.prototype.addWorkerTask = function (id, priority, queue) {
 139     try {
 140         this.addTask(id, priority, queue, new WorkerTask(this, ID_HANDLER_A, 0));
 141     } catch(e) { }
 142 };
 143
 144 /**
 145  * Add a handler task to this scheduler.
 146  * @param {int} id the identity of the task
 147  * @param {int} priority the task's priority
 148  * @param {Packet} queue the queue of work to be processed by the task
 149  */
 150 Scheduler.prototype.addHandlerTask = function (id, priority, queue) {
 151     try {
 152         this.addTask(id, priority, queue, new HandlerTask(this));
 153     } catch(e) { }
 154 };
 155
 156 /**
 157  * Add a handler task to this scheduler.
 158  * @param {int} id the identity of the task
 159  * @param {int} priority the task's priority
 160  * @param {Packet} queue the queue of work to be processed by the task
 161  */
 162 Scheduler.prototype.addDeviceTask = function (id, priority, queue) {
 163     try {
 164         this.addTask(id, priority, queue, new DeviceTask(this))
 165     } catch(e) { }
 166 };
 167
 168 /**
 169  * Add the specified task and mark it as running.
 170  * @param {int} id the identity of the task
 171  * @param {int} priority the task's priority
 172  * @param {Packet} queue the queue of work to be processed by the task
 173  * @param {Task} task the task to add
 174  */
 175 Scheduler.prototype.addRunningTask = function (id, priority, queue, task) {
 176     try {
 177         this.addTask(id, priority, queue, task);
 178         this.currentTcb.setRunning();
 179     } catch(e) { }
 180 };
 181
 182 /**
 183  * Add the specified task to this scheduler.
 184  * @param {int} id the identity of the task
 185  * @param {int} priority the task's priority
 186  * @param {Packet} queue the queue of work to be processed by the task
 187  * @param {Task} task the task to add
 188  */
 189 Scheduler.prototype.addTask = function (id, priority, queue, task) {
 190     try {
 191         this.currentTcb = new TaskControlBlock(this.list, id, priority, queue, task);
 192         this.list = this.currentTcb;
 193         this.blocks[id] = this.currentTcb;
 194     } catch(e) { }
 195 };
 196
 197 /**
 198  * Execute the tasks managed by this scheduler.
 199  */
 200 Scheduler.prototype.schedule = function () {
 201     this.currentTcb = this.list;
 202     while (this.currentTcb != null) {
 203         try {
 204             if (this.currentTcb.isHeldOrSuspended()) {
 205                 this.currentTcb = this.currentTcb.link;
 206             } else {
 207                 this.currentId = this.currentTcb.id;
 208                 this.currentTcb = this.currentTcb.run();
 209             }
 210         } catch(e) { }
 211     }
 212 };
 213
 214 /**
 215  * Release a task that is currently blocked and return the next block to run.
 216  * @param {int} id the id of the task to suspend
 217  */
 218 Scheduler.prototype.release = function (id) {
 219     try {
 220         var tcb = this.blocks[id];
 221         if (tcb == null) return tcb;
 222         tcb.markAsNotHeld();
 223     } catch(e) { }
 224     try {
 225         if (tcb.priority > this.currentTcb.priority) {
 226             return tcb;
 227         } else {
 228             return this.currentTcb;
 229         }
 230     } catch(e) { }
 231 };
 232
 233 /**
 234  * Block the currently executing task and return the next task control block
 235  * to run.  The blocked task will not be made runnable until it is explicitly
 236  * released, even if new work is added to it.
 237  */
 238 Scheduler.prototype.holdCurrent = function () {
 239     try {
 240         this.holdCount++;
 241         this.currentTcb.markAsHeld();
 242     } catch(e) { }
 243     return this.currentTcb.link;
 244 };
 245
 246 /**
 247  * Suspend the currently executing task and return the next task control block
 248  * to run.  If new work is added to the suspended task it will be made runnable.
 249  */
 250 Scheduler.prototype.suspendCurrent = function () {
 251     try {
 252         this.currentTcb.markAsSuspended();
 253     } catch(e) { }
 254     try {
 255         return this.currentTcb;
 256     } catch(e) { }
 257 };
 258
 259 /**
 260  * Add the specified packet to the end of the worklist used by the task
 261  * associated with the packet and make the task runnable if it is currently
 262  * suspended.
 263  * @param {Packet} packet the packet to add
 264  */
 265 Scheduler.prototype.queue = function (packet) {
 266     try {
 267         var t = this.blocks[packet.id];
 268         if (t == null) return t;
 269         this.queueCount++;
 270         packet.link = null;
 271     } catch(e) { }
 272     packet.id = this.currentId;
 273     return t.checkPriorityAdd(this.currentTcb, packet);
 274 };
 275
 276 /**
 277  * A task control block manages a task and the queue of work packages associated
 278  * with it.
 279  * @param {TaskControlBlock} link the preceding block in the linked block list
 280  * @param {int} id the id of this block
 281  * @param {int} priority the priority of this block
 282  * @param {Packet} queue the queue of packages to be processed by the task
 283  * @param {Task} task the task
 284  * @constructor
 285  */
 286 function TaskControlBlock(link, id, priority, queue, task) {
 287     try {
 288         this.link = link;
 289         this.id = id;
 290         this.priority = priority;
 291         this.queue = queue;
 292         this.task = task;
 293     } catch(e) { }
 294     try {
 295         if (queue == null) {
 296             this.state = STATE_SUSPENDED;
 297         } else {
 298             this.state = STATE_SUSPENDED_RUNNABLE;
 299         }
 300     } catch(e) { }
 301 }
 302
 303 /**
 304  * The task is running and is currently scheduled.
 305  */
 306 var STATE_RUNNING = 0;
 307
 308 /**
 309  * The task has packets left to process.
 310  */
 311 var STATE_RUNNABLE = 1;
 312
 313 /**
 314  * The task is not currently running.  The task is not blocked as such and may
 315  * be started by the scheduler.
 316  */
 317 var STATE_SUSPENDED = 2;
 318
 319 /**
 320  * The task is blocked and cannot be run until it is explicitly released.
 321  */
 322 var STATE_HELD = 4;
 323
 324 var STATE_SUSPENDED_RUNNABLE = STATE_SUSPENDED | STATE_RUNNABLE;
 325 var STATE_NOT_HELD = ~STATE_HELD;
 326
 327 TaskControlBlock.prototype.setRunning = function () {
 328     try {
 329         this.state = STATE_RUNNING;
 330     } catch(e){}
 331 };
 332
 333 TaskControlBlock.prototype.markAsNotHeld = function () {
 334     try {
 335         this.state = this.state & STATE_NOT_HELD;
 336     } catch(e) { }
 337 };
 338
 339 TaskControlBlock.prototype.markAsHeld = function () {
 340     try {
 341         this.state = this.state | STATE_HELD;
 342     } catch(e) { }
 343 };
 344
 345 TaskControlBlock.prototype.isHeldOrSuspended = function () {
 346     try {
 347         return (this.state & STATE_HELD) != 0 || (this.state == STATE_SUSPENDED);
 348     } catch(e) {
 349         return (this.state & STATE_HELD) != 0 || (this.state == STATE_SUSPENDED);
 350     }
 351 };
 352
 353 TaskControlBlock.prototype.markAsSuspended = function () {
 354     try {
 355         this.state = this.state | STATE_SUSPENDED;
 356     } catch(e) {
 357         this.state = this.state | STATE_SUSPENDED;
 358     }
 359 };
 360
 361 TaskControlBlock.prototype.markAsRunnable = function () {
 362     try {
 363         this.state = this.state | STATE_RUNNABLE;
 364     } catch(e) {
 365         this.state = this.state | STATE_RUNNABLE;
 366     }
 367 };
 368
 369 /**
 370  * Runs this task, if it is ready to be run, and returns the next task to run.
 371  */
 372 TaskControlBlock.prototype.run = function () {
 373     var packet;
 374     try {
 375         if (this.state == STATE_SUSPENDED_RUNNABLE) {
 376             packet = this.queue;
 377             this.queue = packet.link;
 378             if (this.queue == null) {
 379                 this.state = STATE_RUNNING;
 380             } else {
 381                 this.state = STATE_RUNNABLE;
 382             }
 383         } else {
 384             packet = null;
 385         }
 386     } catch(e) { }
 387     return this.task.run(packet);
 388 };
 389
 390 /**
 391  * Adds a packet to the worklist of this block's task, marks this as runnable if
 392  * necessary, and returns the next runnable object to run (the one
 393  * with the highest priority).
 394  */
 395 TaskControlBlock.prototype.checkPriorityAdd = function (task, packet) {
 396     try {
 397         if (this.queue == null) {
 398             this.queue = packet;
 399             this.markAsRunnable();
 400             if (this.priority > task.priority) return this;
 401         } else {
 402             this.queue = packet.addTo(this.queue);
 403         }
 404
 405         return task;
 406     } catch(e) {
 407         return task;
 408     }
 409 };
 410
 411 TaskControlBlock.prototype.toString = function () {
 412     try {
 413         return "tcb { " + this.task + "@" + this.state + " }";
 414     } catch(e) {
 415         return "tcb { " + this.task + "@" + this.state + " }";
 416     }
 417 };
 418
 419 /**
 420  * An idle task doesn't do any work itself but cycles control between the two
 421  * device tasks.
 422  * @param {Scheduler} scheduler the scheduler that manages this task
 423  * @param {int} v1 a seed value that controls how the device tasks are scheduled
 424  * @param {int} count the number of times this task should be scheduled
 425  * @constructor
 426  */
 427 function IdleTask(scheduler, v1, count) {
 428     try {
 429         this.scheduler = scheduler;
 430         this.v1 = v1;
 431         this.count = count;
 432     } catch(e) {
 433         this.count = count;
 434     }
 435 }
 436
 437 IdleTask.prototype.run = function (packet) {
 438     try {
 439         this.count--;
 440         if (this.count == 0) return this.scheduler.holdCurrent();
 441     } catch(e) { }
 442
 443     try {
 444         if ((this.v1 & 1) == 0) {
 445             this.v1 = this.v1 >> 1;
 446             return this.scheduler.release(ID_DEVICE_A);
 447         } else {
 448             this.v1 = (this.v1 >> 1) ^ 0xD008;
 449             return this.scheduler.release(ID_DEVICE_B);
 450         }
 451     } catch(e) { }
 452 };
 453
 454 IdleTask.prototype.toString = function () {
 455     try {
 456         return "IdleTask"
 457     } catch(e) {
 458         return "IdleTask"
 459     }
 460 };
 461
 462 /**
 463  * A task that suspends itself after each time it has been run to simulate
 464  * waiting for data from an external device.
 465  * @param {Scheduler} scheduler the scheduler that manages this task
 466  * @constructor
 467  */
 468 function DeviceTask(scheduler) {
 469     try {
 470         this.scheduler = scheduler;
 471         this.v1 = null;
 472     } catch(e) { }
 473 }
 474
 475 DeviceTask.prototype.run = function (packet) {
 476     if (packet == null) {
 477         try {
 478             if (this.v1 == null) return this.scheduler.suspendCurrent();
 479             var v = this.v1;
 480             this.v1 = null;
 481         } catch(e) { }
 482         return this.scheduler.queue(v);
 483     } else {
 484         try {
 485             this.v1 = packet;
 486         } catch(e) { }
 487         return this.scheduler.holdCurrent();
 488     }
 489 };
 490
 491 DeviceTask.prototype.toString = function () {
 492     try {
 493         return "DeviceTask";
 494     } catch(e) { }
 495 };
 496
 497 /**
 498  * A task that manipulates work packets.
 499  * @param {Scheduler} scheduler the scheduler that manages this task
 500  * @param {int} v1 a seed used to specify how work packets are manipulated
 501  * @param {int} v2 another seed used to specify how work packets are manipulated
 502  * @constructor
 503  */
 504 function WorkerTask(scheduler, v1, v2) {
 505     try {
 506         this.scheduler = scheduler;
 507         this.v1 = v1;
 508         this.v2 = v2;
 509     } catch(e) { }
 510 }
 511
 512 WorkerTask.prototype.run = function (packet) {
 513     if (packet == null) {
 514         return this.scheduler.suspendCurrent();
 515     } else {
 516         try {
 517             if (this.v1 == ID_HANDLER_A) {
 518                 this.v1 = ID_HANDLER_B;
 519             } else {
 520                 this.v1 = ID_HANDLER_A;
 521             }
 522             packet.id = this.v1;
 523             packet.a1 = 0;
 524         } catch(e) { }
 525         for (var i = 0; i < DATA_SIZE; i++) {
 526             try {
 527                 this.v2++;
 528                 if (this.v2 > 26) this.v2 = 1;
 529                 packet.a2[i] = this.v2;
 530             } catch(e) { }
 531         }
 532         return this.scheduler.queue(packet);
 533     }
 534 };
 535
 536 WorkerTask.prototype.toString = function () {
 537     try {
 538         return "WorkerTask";
 539     } catch(e) { }
 540 };
 541
 542 /**
 543  * A task that manipulates work packets and then suspends itself.
 544  * @param {Scheduler} scheduler the scheduler that manages this task
 545  * @constructor
 546  */
 547 function HandlerTask(scheduler) {
 548     try {
 549         this.scheduler = scheduler;
 550         this.v1 = null;
 551         this.v2 = null;
 552     } catch(e) { }
 553 }
 554
 555 HandlerTask.prototype.run = function (packet) {
 556     try {
 557         if (packet != null) {
 558             if (packet.kind == KIND_WORK) {
 559                 this.v1 = packet.addTo(this.v1);
 560             } else {
 561                 this.v2 = packet.addTo(this.v2);
 562             }
 563         }
 564     } catch(e) { }
 565
 566     try {
 567         if (this.v1 != null) {
 568             var count = this.v1.a1;
 569             var v;
 570             if (count < DATA_SIZE) {
 571                 if (this.v2 != null) {
 572                     v = this.v2;
 573                     this.v2 = this.v2.link;
 574                     v.a1 = this.v1.a2[count];
 575                     this.v1.a1 = count + 1;
 576                     return this.scheduler.queue(v);
 577                 }
 578             } else {
 579                 v = this.v1;
 580                 this.v1 = this.v1.link;
 581                 return this.scheduler.queue(v);
 582             }
 583         }
 584     } catch(e) { }
 585     return this.scheduler.suspendCurrent();
 586 };
 587
 588 HandlerTask.prototype.toString = function () {
 589     try {
 590         return "HandlerTask";
 591     } catch(e) { }
 592 };
 593
 594 /* --- *
 595  * P a c k e t
 596  * --- */
 597
 598 var DATA_SIZE = 4;
 599
 600 /**
 601  * A simple package of data that is manipulated by the tasks.  The exact layout
 602  * of the payload data carried by a packet is not importaint, and neither is the
 603  * nature of the work performed on packets by the tasks.
 604  *
 605  * Besides carrying data, packets form linked lists and are hence used both as
 606  * data and worklists.
 607  * @param {Packet} link the tail of the linked list of packets
 608  * @param {int} id an ID for this packet
 609  * @param {int} kind the type of this packet
 610  * @constructor
 611  */
 612 function Packet(link, id, kind) {
 613     try {
 614         this.link = link;
 615         this.id = id;
 616         this.kind = kind;
 617         this.a1 = 0;
 618         this.a2 = new Array(DATA_SIZE);
 619     } catch(e) { }
 620 }
 621
 622 /**
 623  * Add this packet to the end of a worklist, and return the worklist.
 624  * @param {Packet} queue the worklist to add this packet to
 625  */
 626 Packet.prototype.addTo = function (queue) {
 627     this.link = null;
 628     if (queue == null) return this;
 629     var peek, next = queue;
 630     while ((peek = next.link) != null) {
 631         try {
 632             next = peek;
 633         } catch(e) { }
 634     }
 635     next.link = this;
 636     return queue;
 637 };
 638
 639 Packet.prototype.toString = function () {
 640     try {
 641         return "Packet";
 642     } catch(e) { }
 643 };
 644
 645 for (let i = 0; i < 350; ++i)
 646   runRichards();