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