Add JetStream to PerformanceTests
[WebKit-https.git] / PerformanceTests / JetStream / Octane2 / richards.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 var Richards = new BenchmarkSuite('Richards', [35302], [
39   new Benchmark("Richards", true, false, 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     throw new Error(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 };