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