JetStream should have a more rational story for jitter-oriented latency tests
[WebKit-https.git] / PerformanceTests / JetStream / Octane2 / splay.js
1 // Copyright 2009 the V8 project authors. All rights reserved.
2 // Copyright (C) 2015 Apple Inc. All rights reserved.
3 // Redistribution and use in source and binary forms, with or without
4 // modification, are permitted provided that the following conditions are
5 // met:
6 //
7 //     * Redistributions of source code must retain the above copyright
8 //       notice, this list of conditions and the following disclaimer.
9 //     * Redistributions in binary form must reproduce the above
10 //       copyright notice, this list of conditions and the following
11 //       disclaimer in the documentation and/or other materials provided
12 //       with the distribution.
13 //     * Neither the name of Google Inc. nor the names of its
14 //       contributors may be used to endorse or promote products derived
15 //       from this software without specific prior written permission.
16 //
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28
29 // This benchmark is based on a JavaScript log processing module used
30 // by the V8 profiler to generate execution time profiles for runs of
31 // JavaScript applications, and it effectively measures how fast the
32 // JavaScript engine is at allocating nodes and reclaiming the memory
33 // used for old nodes. Because of the way splay trees work, the engine
34 // also has to deal with a lot of changes to the large tree object
35 // graph.
36
37 var Splay = new BenchmarkSuite('Splay', [81491, 2739514], [
38   new Benchmark("Splay", true, false, 
39     SplayRun, SplaySetup, SplayTearDown, SplayLatency)
40 ]);
41
42
43 // Configuration.
44 var kSplayTreeSize = 8000;
45 var kSplayTreeModifications = 80;
46 var kSplayTreePayloadDepth = 5;
47
48 var splayTree = null;
49 var splaySampleTimeStart = 0.0;
50
51 function GeneratePayloadTree(depth, tag) {
52   if (depth == 0) {
53     return {
54       array  : [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ],
55       string : 'String for key ' + tag + ' in leaf node'
56     };
57   } else {
58     return {
59       left:  GeneratePayloadTree(depth - 1, tag),
60       right: GeneratePayloadTree(depth - 1, tag)
61     };
62   }
63 }
64
65
66 function GenerateKey() {
67   // The benchmark framework guarantees that Math.random is
68   // deterministic; see base.js.
69   return Math.random();
70 }
71
72 var splaySamples = [];
73
74 function SplayLatency() {
75   return splaySamples;
76 }
77
78 function SplayUpdateStats(time) {
79   var pause = time - splaySampleTimeStart;
80   splaySampleTimeStart = time;
81   splaySamples.push(pause);
82 }
83
84 function InsertNewNode() {
85   // Insert new node with a unique key.
86   var key;
87   do {
88     key = GenerateKey();
89   } while (splayTree.find(key) != null);
90   var payload = GeneratePayloadTree(kSplayTreePayloadDepth, String(key));
91   splayTree.insert(key, payload);
92   return key;
93 }
94
95
96 function SplaySetup() {
97   // Check if the platform has the performance.now high resolution timer.
98   // If not, throw exception and quit.
99   if (!performance.now) {
100     throw "PerformanceNowUnsupported";
101   }
102
103   splayTree = new SplayTree();
104   splaySampleTimeStart = performance.now()
105   for (var i = 0; i < kSplayTreeSize; i++) {
106     InsertNewNode();
107     if ((i+1) % 20 == 19) {
108       SplayUpdateStats(performance.now());
109     }
110   }
111 }
112
113
114 function SplayTearDown() {
115   // Allow the garbage collector to reclaim the memory
116   // used by the splay tree no matter how we exit the
117   // tear down function.
118   var keys = splayTree.exportKeys();
119   splayTree = null;
120
121   splaySamples = [];
122
123   // Verify that the splay tree has the right size.
124   var length = keys.length;
125   if (length != kSplayTreeSize) {
126     throw new Error("Splay tree has wrong size");
127   }
128
129   // Verify that the splay tree has sorted, unique keys.
130   for (var i = 0; i < length - 1; i++) {
131     if (keys[i] >= keys[i + 1]) {
132       throw new Error("Splay tree not sorted");
133     }
134   }
135 }
136
137
138 function SplayRun() {
139   // Replace a few nodes in the splay tree.
140   for (var i = 0; i < kSplayTreeModifications; i++) {
141     var key = InsertNewNode();
142     var greatest = splayTree.findGreatestLessThan(key);
143     if (greatest == null) splayTree.remove(key);
144     else splayTree.remove(greatest.key);
145   }
146   SplayUpdateStats(performance.now());
147 }
148
149
150 /**
151  * Constructs a Splay tree.  A splay tree is a self-balancing binary
152  * search tree with the additional property that recently accessed
153  * elements are quick to access again. It performs basic operations
154  * such as insertion, look-up and removal in O(log(n)) amortized time.
155  *
156  * @constructor
157  */
158 function SplayTree() {
159 };
160
161
162 /**
163  * Pointer to the root node of the tree.
164  *
165  * @type {SplayTree.Node}
166  * @private
167  */
168 SplayTree.prototype.root_ = null;
169
170
171 /**
172  * @return {boolean} Whether the tree is empty.
173  */
174 SplayTree.prototype.isEmpty = function() {
175   return !this.root_;
176 };
177
178
179 /**
180  * Inserts a node into the tree with the specified key and value if
181  * the tree does not already contain a node with the specified key. If
182  * the value is inserted, it becomes the root of the tree.
183  *
184  * @param {number} key Key to insert into the tree.
185  * @param {*} value Value to insert into the tree.
186  */
187 SplayTree.prototype.insert = function(key, value) {
188   if (this.isEmpty()) {
189     this.root_ = new SplayTree.Node(key, value);
190     return;
191   }
192   // Splay on the key to move the last node on the search path for
193   // the key to the root of the tree.
194   this.splay_(key);
195   if (this.root_.key == key) {
196     return;
197   }
198   var node = new SplayTree.Node(key, value);
199   if (key > this.root_.key) {
200     node.left = this.root_;
201     node.right = this.root_.right;
202     this.root_.right = null;
203   } else {
204     node.right = this.root_;
205     node.left = this.root_.left;
206     this.root_.left = null;
207   }
208   this.root_ = node;
209 };
210
211
212 /**
213  * Removes a node with the specified key from the tree if the tree
214  * contains a node with this key. The removed node is returned. If the
215  * key is not found, an exception is thrown.
216  *
217  * @param {number} key Key to find and remove from the tree.
218  * @return {SplayTree.Node} The removed node.
219  */
220 SplayTree.prototype.remove = function(key) {
221   if (this.isEmpty()) {
222     throw Error('Key not found: ' + key);
223   }
224   this.splay_(key);
225   if (this.root_.key != key) {
226     throw Error('Key not found: ' + key);
227   }
228   var removed = this.root_;
229   if (!this.root_.left) {
230     this.root_ = this.root_.right;
231   } else {
232     var right = this.root_.right;
233     this.root_ = this.root_.left;
234     // Splay to make sure that the new root has an empty right child.
235     this.splay_(key);
236     // Insert the original right child as the right child of the new
237     // root.
238     this.root_.right = right;
239   }
240   return removed;
241 };
242
243
244 /**
245  * Returns the node having the specified key or null if the tree doesn't contain
246  * a node with the specified key.
247  *
248  * @param {number} key Key to find in the tree.
249  * @return {SplayTree.Node} Node having the specified key.
250  */
251 SplayTree.prototype.find = function(key) {
252   if (this.isEmpty()) {
253     return null;
254   }
255   this.splay_(key);
256   return this.root_.key == key ? this.root_ : null;
257 };
258
259
260 /**
261  * @return {SplayTree.Node} Node having the maximum key value.
262  */
263 SplayTree.prototype.findMax = function(opt_startNode) {
264   if (this.isEmpty()) {
265     return null;
266   }
267   var current = opt_startNode || this.root_;
268   while (current.right) {
269     current = current.right;
270   }
271   return current;
272 };
273
274
275 /**
276  * @return {SplayTree.Node} Node having the maximum key value that
277  *     is less than the specified key value.
278  */
279 SplayTree.prototype.findGreatestLessThan = function(key) {
280   if (this.isEmpty()) {
281     return null;
282   }
283   // Splay on the key to move the node with the given key or the last
284   // node on the search path to the top of the tree.
285   this.splay_(key);
286   // Now the result is either the root node or the greatest node in
287   // the left subtree.
288   if (this.root_.key < key) {
289     return this.root_;
290   } else if (this.root_.left) {
291     return this.findMax(this.root_.left);
292   } else {
293     return null;
294   }
295 };
296
297
298 /**
299  * @return {Array<*>} An array containing all the keys of tree's nodes.
300  */
301 SplayTree.prototype.exportKeys = function() {
302   var result = [];
303   if (!this.isEmpty()) {
304     this.root_.traverse_(function(node) { result.push(node.key); });
305   }
306   return result;
307 };
308
309
310 /**
311  * Perform the splay operation for the given key. Moves the node with
312  * the given key to the top of the tree.  If no node has the given
313  * key, the last node on the search path is moved to the top of the
314  * tree. This is the simplified top-down splaying algorithm from:
315  * "Self-adjusting Binary Search Trees" by Sleator and Tarjan
316  *
317  * @param {number} key Key to splay the tree on.
318  * @private
319  */
320 SplayTree.prototype.splay_ = function(key) {
321   if (this.isEmpty()) {
322     return;
323   }
324   // Create a dummy node.  The use of the dummy node is a bit
325   // counter-intuitive: The right child of the dummy node will hold
326   // the L tree of the algorithm.  The left child of the dummy node
327   // will hold the R tree of the algorithm.  Using a dummy node, left
328   // and right will always be nodes and we avoid special cases.
329   var dummy, left, right;
330   dummy = left = right = new SplayTree.Node(null, null);
331   var current = this.root_;
332   while (true) {
333     if (key < current.key) {
334       if (!current.left) {
335         break;
336       }
337       if (key < current.left.key) {
338         // Rotate right.
339         var tmp = current.left;
340         current.left = tmp.right;
341         tmp.right = current;
342         current = tmp;
343         if (!current.left) {
344           break;
345         }
346       }
347       // Link right.
348       right.left = current;
349       right = current;
350       current = current.left;
351     } else if (key > current.key) {
352       if (!current.right) {
353         break;
354       }
355       if (key > current.right.key) {
356         // Rotate left.
357         var tmp = current.right;
358         current.right = tmp.left;
359         tmp.left = current;
360         current = tmp;
361         if (!current.right) {
362           break;
363         }
364       }
365       // Link left.
366       left.right = current;
367       left = current;
368       current = current.right;
369     } else {
370       break;
371     }
372   }
373   // Assemble.
374   left.right = current.left;
375   right.left = current.right;
376   current.left = dummy.right;
377   current.right = dummy.left;
378   this.root_ = current;
379 };
380
381
382 /**
383  * Constructs a Splay tree node.
384  *
385  * @param {number} key Key.
386  * @param {*} value Value.
387  */
388 SplayTree.Node = function(key, value) {
389   this.key = key;
390   this.value = value;
391 };
392
393
394 /**
395  * @type {SplayTree.Node}
396  */
397 SplayTree.Node.prototype.left = null;
398
399
400 /**
401  * @type {SplayTree.Node}
402  */
403 SplayTree.Node.prototype.right = null;
404
405
406 /**
407  * Performs an ordered traversal of the subtree starting at
408  * this SplayTree.Node.
409  *
410  * @param {function(SplayTree.Node)} f Visitor function.
411  * @private
412  */
413 SplayTree.Node.prototype.traverse_ = function(f) {
414   var current = this;
415   while (current) {
416     var left = current.left;
417     if (left) left.traverse_(f);
418     f(current);
419     current = current.right;
420   }
421 };