js/src/metrics/jint/v8/richards.js

   1 // Copyright 2007 Google Inc. 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 var Richards = new BenchmarkSuite('Richards', 34886, [
  39   new Benchmark("Richards", runRichards)
  40 ]);
  41
  42
  43 /**
  44  * The Richards benchmark simulates the task dispatcher of an
  45  * operating system.
  46  **/
  47 function runRichards() {
  48   var scheduler = new Scheduler();
  49   scheduler.addIdleTask(ID_IDLE, 0, null, COUNT);
  50
  51   var queue = new Packet(null, ID_WORKER, KIND_WORK);
  52   queue = new Packet(queue,  ID_WORKER, KIND_WORK);
  53   scheduler.addWorkerTask(ID_WORKER, 1000, queue);
  54
  55   queue = new Packet(null, ID_DEVICE_A, KIND_DEVICE);
  56   queue = new Packet(queue,  ID_DEVICE_A, KIND_DEVICE);
  57   queue = new Packet(queue,  ID_DEVICE_A, KIND_DEVICE);
  58   scheduler.addHandlerTask(ID_HANDLER_A, 2000, queue);
  59
  60   queue = new Packet(null, ID_DEVICE_B, KIND_DEVICE);
  61   queue = new Packet(queue,  ID_DEVICE_B, KIND_DEVICE);
  62   queue = new Packet(queue,  ID_DEVICE_B, KIND_DEVICE);
  63   scheduler.addHandlerTask(ID_HANDLER_B, 3000, queue);
  64
  65   scheduler.addDeviceTask(ID_DEVICE_A, 4000, null);
  66
  67   scheduler.addDeviceTask(ID_DEVICE_B, 5000, null);
  68
  69   scheduler.schedule();
  70
  71   if (scheduler.queueCount != EXPECTED_QUEUE_COUNT ||
  72       scheduler.holdCount != EXPECTED_HOLD_COUNT) {
  73     var msg =
  74         "Error during execution: queueCount = " + scheduler.queueCount +
  75         ", holdCount = " + scheduler.holdCount + ".";
  76     print(msg);
  77   }
  78 }
  79
  80 var COUNT = 1000;
  81
  82 /**
  83  * These two constants specify how many times a packet is queued and
  84  * how many times a task is put on hold in a correct run of richards.
  85  * They don't have any meaning a such but are characteristic of a
  86  * correct run so if the actual queue or hold count is different from
  87  * the expected there must be a bug in the implementation.
  88  **/
  89 var EXPECTED_QUEUE_COUNT = 2322;
  90 var EXPECTED_HOLD_COUNT = 928;
  91
  92
  93 /**
  94  * A scheduler can be used to schedule a set of tasks based on their relative
  95  * priorities.  Scheduling is done by maintaining a list of task control blocks
  96  * which holds tasks and the data queue they are processing.
  97  * @constructor
  98  */
  99 function Scheduler() {
 100   this.queueCount = 0;
 101   this.holdCount = 0;
 102   this.blocks = new Array(NUMBER_OF_IDS);
 103   this.list = null;
 104   this.currentTcb = null;
 105   this.currentId = null;
 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   this.addRunningTask(id, priority, queue, new IdleTask(this, 1, count));
 128 };
 129
 130 /**
 131  * Add a work task to this scheduler.
 132  * @param {int} id the identity of the task
 133  * @param {int} priority the task's priority
 134  * @param {Packet} queue the queue of work to be processed by the task
 135  */
 136 Scheduler.prototype.addWorkerTask = function (id, priority, queue) {
 137   this.addTask(id, priority, queue, new WorkerTask(this, ID_HANDLER_A, 0));
 138 };
 139
 140 /**
 141  * Add a handler task to this scheduler.
 142  * @param {int} id the identity of the task
 143  * @param {int} priority the task's priority
 144  * @param {Packet} queue the queue of work to be processed by the task
 145  */
 146 Scheduler.prototype.addHandlerTask = function (id, priority, queue) {
 147   this.addTask(id, priority, queue, new HandlerTask(this));
 148 };
 149
 150 /**
 151  * Add a handler task to this scheduler.
 152  * @param {int} id the identity of the task
 153  * @param {int} priority the task's priority
 154  * @param {Packet} queue the queue of work to be processed by the task
 155  */
 156 Scheduler.prototype.addDeviceTask = function (id, priority, queue) {
 157   this.addTask(id, priority, queue, new DeviceTask(this))
 158 };
 159
 160 /**
 161  * Add the specified task and mark it as running.
 162  * @param {int} id the identity of the task
 163  * @param {int} priority the task's priority
 164  * @param {Packet} queue the queue of work to be processed by the task
 165  * @param {Task} task the task to add
 166  */
 167 Scheduler.prototype.addRunningTask = function (id, priority, queue, task) {
 168   this.addTask(id, priority, queue, task);
 169   this.currentTcb.setRunning();
 170 };
 171
 172 /**
 173  * Add the specified task to this scheduler.
 174  * @param {int} id the identity of the task
 175  * @param {int} priority the task's priority
 176  * @param {Packet} queue the queue of work to be processed by the task
 177  * @param {Task} task the task to add
 178  */
 179 Scheduler.prototype.addTask = function (id, priority, queue, task) {
 180   this.currentTcb = new TaskControlBlock(this.list, id, priority, queue, task);
 181   this.list = this.currentTcb;
 182   this.blocks[id] = this.currentTcb;
 183 };
 184
 185 /**
 186  * Execute the tasks managed by this scheduler.
 187  */
 188 Scheduler.prototype.schedule = function () {
 189   this.currentTcb = this.list;
 190   while (this.currentTcb != null) {
 191     if (this.currentTcb.isHeldOrSuspended()) {
 192       this.currentTcb = this.currentTcb.link;
 193     } else {
 194       this.currentId = this.currentTcb.id;
 195       this.currentTcb = this.currentTcb.run();
 196     }
 197   }
 198 };
 199
 200 /**
 201  * Release a task that is currently blocked and return the next block to run.
 202  * @param {int} id the id of the task to suspend
 203  */
 204 Scheduler.prototype.release = function (id) {
 205   var tcb = this.blocks[id];
 206   if (tcb == null) return tcb;
 207   tcb.markAsNotHeld();
 208   if (tcb.priority > this.currentTcb.priority) {
 209     return tcb;
 210   } else {
 211     return this.currentTcb;
 212   }
 213 };
 214
 215 /**
 216  * Block the currently executing task and return the next task control block
 217  * to run.  The blocked task will not be made runnable until it is explicitly
 218  * released, even if new work is added to it.
 219  */
 220 Scheduler.prototype.holdCurrent = function () {
 221   this.holdCount++;
 222   this.currentTcb.markAsHeld();
 223   return this.currentTcb.link;
 224 };
 225
 226 /**
 227  * Suspend the currently executing task and return the next task control block
 228  * to run.  If new work is added to the suspended task it will be made runnable.
 229  */
 230 Scheduler.prototype.suspendCurrent = function () {
 231   this.currentTcb.markAsSuspended();
 232   return this.currentTcb;
 233 };
 234
 235 /**
 236  * Add the specified packet to the end of the worklist used by the task
 237  * associated with the packet and make the task runnable if it is currently
 238  * suspended.
 239  * @param {Packet} packet the packet to add
 240  */
 241 Scheduler.prototype.queue = function (packet) {
 242   var t = this.blocks[packet.id];
 243   if (t == null) return t;
 244   this.queueCount++;
 245   packet.link = null;
 246   packet.id = this.currentId;
 247   return t.checkPriorityAdd(this.currentTcb, packet);
 248 };
 249
 250 /**
 251  * A task control block manages a task and the queue of work packages associated
 252  * with it.
 253  * @param {TaskControlBlock} link the preceding block in the linked block list
 254  * @param {int} id the id of this block
 255  * @param {int} priority the priority of this block
 256  * @param {Packet} queue the queue of packages to be processed by the task
 257  * @param {Task} task the task
 258  * @constructor
 259  */
 260 function TaskControlBlock(link, id, priority, queue, task) {
 261   this.link = link;
 262   this.id = id;
 263   this.priority = priority;
 264   this.queue = queue;
 265   this.task = task;
 266   if (queue == null) {
 267     this.state = STATE_SUSPENDED;
 268   } else {
 269     this.state = STATE_SUSPENDED_RUNNABLE;
 270   }
 271 }
 272
 273 /**
 274  * The task is running and is currently scheduled.
 275  */
 276 var STATE_RUNNING = 0;
 277
 278 /**
 279  * The task has packets left to process.
 280  */
 281 var STATE_RUNNABLE = 1;
 282
 283 /**
 284  * The task is not currently running.  The task is not blocked as such and may
 285 * be started by the scheduler.
 286  */
 287 var STATE_SUSPENDED = 2;
 288
 289 /**
 290  * The task is blocked and cannot be run until it is explicitly released.
 291  */
 292 var STATE_HELD = 4;
 293
 294 var STATE_SUSPENDED_RUNNABLE = STATE_SUSPENDED | STATE_RUNNABLE;
 295 var STATE_NOT_HELD = ~STATE_HELD;
 296
 297 TaskControlBlock.prototype.setRunning = function () {
 298   this.state = STATE_RUNNING;
 299 };
 300
 301 TaskControlBlock.prototype.markAsNotHeld = function () {
 302   this.state = this.state & STATE_NOT_HELD;
 303 };
 304
 305 TaskControlBlock.prototype.markAsHeld = function () {
 306   this.state = this.state | STATE_HELD;
 307 };
 308
 309 TaskControlBlock.prototype.isHeldOrSuspended = function () {
 310   return (this.state & STATE_HELD) != 0 || (this.state == STATE_SUSPENDED);
 311 };
 312
 313 TaskControlBlock.prototype.markAsSuspended = function () {
 314   this.state = this.state | STATE_SUSPENDED;
 315 };
 316
 317 TaskControlBlock.prototype.markAsRunnable = function () {
 318   this.state = this.state | STATE_RUNNABLE;
 319 };
 320
 321 /**
 322  * Runs this task, if it is ready to be run, and returns the next task to run.
 323  */
 324 TaskControlBlock.prototype.run = function () {
 325   var packet;
 326   if (this.state == STATE_SUSPENDED_RUNNABLE) {
 327     packet = this.queue;
 328     this.queue = packet.link;
 329     if (this.queue == null) {
 330       this.state = STATE_RUNNING;
 331     } else {
 332       this.state = STATE_RUNNABLE;
 333     }
 334   } else {
 335     packet = null;
 336   }
 337   return this.task.run(packet);
 338 };
 339
 340 /**
 341  * Adds a packet to the worklist of this block's task, marks this as runnable if
 342  * necessary, and returns the next runnable object to run (the one
 343  * with the highest priority).
 344  */
 345 TaskControlBlock.prototype.checkPriorityAdd = function (task, packet) {
 346   if (this.queue == null) {
 347     this.queue = packet;
 348     this.markAsRunnable();
 349     if (this.priority > task.priority) return this;
 350   } else {
 351     this.queue = packet.addTo(this.queue);
 352   }
 353   return task;
 354 };
 355
 356 TaskControlBlock.prototype.toString = function () {
 357   return "tcb { " + this.task + "@" + this.state + " }";
 358 };
 359
 360 /**
 361  * An idle task doesn't do any work itself but cycles control between the two
 362  * device tasks.
 363  * @param {Scheduler} scheduler the scheduler that manages this task
 364  * @param {int} v1 a seed value that controls how the device tasks are scheduled
 365  * @param {int} count the number of times this task should be scheduled
 366  * @constructor
 367  */
 368 function IdleTask(scheduler, v1, count) {
 369   this.scheduler = scheduler;
 370   this.v1 = v1;
 371   this.count = count;
 372 }
 373
 374 IdleTask.prototype.run = function (packet) {
 375   this.count--;
 376   if (this.count == 0) return this.scheduler.holdCurrent();
 377   if ((this.v1 & 1) == 0) {
 378     this.v1 = this.v1 >> 1;
 379     return this.scheduler.release(ID_DEVICE_A);
 380   } else {
 381     this.v1 = (this.v1 >> 1) ^ 0xD008;
 382     return this.scheduler.release(ID_DEVICE_B);
 383   }
 384 };
 385
 386 IdleTask.prototype.toString = function () {
 387   return "IdleTask"
 388 };
 389
 390 /**
 391  * A task that suspends itself after each time it has been run to simulate
 392  * waiting for data from an external device.
 393  * @param {Scheduler} scheduler the scheduler that manages this task
 394  * @constructor
 395  */
 396 function DeviceTask(scheduler) {
 397   this.scheduler = scheduler;
 398   this.v1 = null;
 399 }
 400
 401 DeviceTask.prototype.run = function (packet) {
 402   if (packet == null) {
 403     if (this.v1 == null) return this.scheduler.suspendCurrent();
 404     var v = this.v1;
 405     this.v1 = null;
 406     return this.scheduler.queue(v);
 407   } else {
 408     this.v1 = packet;
 409     return this.scheduler.holdCurrent();
 410   }
 411 };
 412
 413 DeviceTask.prototype.toString = function () {
 414   return "DeviceTask";
 415 };
 416
 417 /**
 418  * A task that manipulates work packets.
 419  * @param {Scheduler} scheduler the scheduler that manages this task
 420  * @param {int} v1 a seed used to specify how work packets are manipulated
 421  * @param {int} v2 another seed used to specify how work packets are manipulated
 422  * @constructor
 423  */
 424 function WorkerTask(scheduler, v1, v2) {
 425   this.scheduler = scheduler;
 426   this.v1 = v1;
 427   this.v2 = v2;
 428 }
 429
 430 WorkerTask.prototype.run = function (packet) {
 431   if (packet == null) {
 432     return this.scheduler.suspendCurrent();
 433   } else {
 434     if (this.v1 == ID_HANDLER_A) {
 435       this.v1 = ID_HANDLER_B;
 436     } else {
 437       this.v1 = ID_HANDLER_A;
 438     }
 439     packet.id = this.v1;
 440     packet.a1 = 0;
 441     for (var i = 0; i < DATA_SIZE; i++) {
 442       this.v2++;
 443       if (this.v2 > 26) this.v2 = 1;
 444       packet.a2[i] = this.v2;
 445     }
 446     return this.scheduler.queue(packet);
 447   }
 448 };
 449
 450 WorkerTask.prototype.toString = function () {
 451   return "WorkerTask";
 452 };
 453
 454 /**
 455  * A task that manipulates work packets and then suspends itself.
 456  * @param {Scheduler} scheduler the scheduler that manages this task
 457  * @constructor
 458  */
 459 function HandlerTask(scheduler) {
 460   this.scheduler = scheduler;
 461   this.v1 = null;
 462   this.v2 = null;
 463 }
 464
 465 HandlerTask.prototype.run = function (packet) {
 466   if (packet != null) {
 467     if (packet.kind == KIND_WORK) {
 468       this.v1 = packet.addTo(this.v1);
 469     } else {
 470       this.v2 = packet.addTo(this.v2);
 471     }
 472   }
 473   if (this.v1 != null) {
 474     var count = this.v1.a1;
 475     var v;
 476     if (count < DATA_SIZE) {
 477       if (this.v2 != null) {
 478         v = this.v2;
 479         this.v2 = this.v2.link;
 480         v.a1 = this.v1.a2[count];
 481         this.v1.a1 = count + 1;
 482         return this.scheduler.queue(v);
 483       }
 484     } else {
 485       v = this.v1;
 486       this.v1 = this.v1.link;
 487       return this.scheduler.queue(v);
 488     }
 489   }
 490   return this.scheduler.suspendCurrent();
 491 };
 492
 493 HandlerTask.prototype.toString = function () {
 494   return "HandlerTask";
 495 };
 496
 497 /* --- *
 498  * P a c k e t
 499  * --- */
 500
 501 var DATA_SIZE = 4;
 502
 503 /**
 504  * A simple package of data that is manipulated by the tasks.  The exact layout
 505  * of the payload data carried by a packet is not importaint, and neither is the
 506  * nature of the work performed on packets by the tasks.
 507  *
 508  * Besides carrying data, packets form linked lists and are hence used both as
 509  * data and worklists.
 510  * @param {Packet} link the tail of the linked list of packets
 511  * @param {int} id an ID for this packet
 512  * @param {int} kind the type of this packet
 513  * @constructor
 514  */
 515 function Packet(link, id, kind) {
 516   this.link = link;
 517   this.id = id;
 518   this.kind = kind;
 519   this.a1 = 0;
 520   this.a2 = new Array(DATA_SIZE);
 521 }
 522
 523 /**
 524  * Add this packet to the end of a worklist, and return the worklist.
 525  * @param {Packet} queue the worklist to add this packet to
 526  */
 527 Packet.prototype.addTo = function (queue) {
 528   this.link = null;
 529   if (queue == null) return this;
 530   var peek, next = queue;
 531   while ((peek = next.link) != null)
 532     next = peek;
 533   next.link = this;
 534   return queue;
 535 };
 536
 537 Packet.prototype.toString = function () {
 538   return "Packet";
 539 };