ee0757dc39ecd2b046d1f173ed0dbd1049debd88
[WebKit-https.git] / JSTests / stress / splay-flash-access.js
1 //@skip if $memoryLimited
2 //@ runNoisyTestDefault
3 //@ runNoisyTestNoCJIT
4
5 // Copyright 2013 the V8 project authors. All rights reserved.
6 // Copyright (C) 2015 Apple Inc. All rights reserved.
7 // Redistribution and use in source and binary forms, with or without
8 // modification, are permitted provided that the following conditions are
9 // met:
10 //
11 //     * Redistributions of source code must retain the above copyright
12 //       notice, this list of conditions and the following disclaimer.
13 //     * Redistributions in binary form must reproduce the above
14 //       copyright notice, this list of conditions and the following
15 //       disclaimer in the documentation and/or other materials provided
16 //       with the distribution.
17 //     * Neither the name of Google Inc. nor the names of its
18 //       contributors may be used to endorse or promote products derived
19 //       from this software without specific prior written permission.
20 //
21 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32
33
34 // Performance.now is used in latency benchmarks, the fallback is Date.now.
35 var performance = performance || {};
36 performance.now = (function() {
37   return performance.now       ||
38          performance.mozNow    ||
39          performance.msNow     ||
40          performance.oNow      ||
41          performance.webkitNow ||
42          Date.now;
43 })();
44
45 // Simple framework for running the benchmark suites and
46 // computing a score based on the timing measurements.
47
48
49 // A benchmark has a name (string) and a function that will be run to
50 // do the performance measurement. The optional setup and tearDown
51 // arguments are functions that will be invoked before and after
52 // running the benchmark, but the running time of these functions will
53 // not be accounted for in the benchmark score.
54 function Benchmark(name, doWarmup, doDeterministic, run, setup, tearDown, latencyResult, minIterations) {
55   this.name = name;
56   this.doWarmup = doWarmup;
57   this.doDeterministic = doDeterministic;
58   this.run = run;
59   this.Setup = setup ? setup : function() { };
60   this.TearDown = tearDown ? tearDown : function() { };
61   this.latencyResult = latencyResult ? latencyResult : null; 
62   this.minIterations = minIterations ? minIterations : 32;
63 }
64
65
66 // Benchmark results hold the benchmark and the measured time used to
67 // run the benchmark. The benchmark score is computed later once a
68 // full benchmark suite has run to completion. If latency is set to 0
69 // then there is no latency score for this benchmark.
70 function BenchmarkResult(benchmark, time, latency) {
71   this.benchmark = benchmark;
72   this.time = time;
73   this.latency = latency;
74 }
75
76
77 // Automatically convert results to numbers. Used by the geometric
78 // mean computation.
79 BenchmarkResult.prototype.valueOf = function() {
80   return this.time;
81 }
82
83
84 // Suites of benchmarks consist of a name and the set of benchmarks in
85 // addition to the reference timing that the final score will be based
86 // on. This way, all scores are relative to a reference run and higher
87 // scores implies better performance.
88 function BenchmarkSuite(name, reference, benchmarks) {
89   this.name = name;
90   this.reference = reference;
91   this.benchmarks = benchmarks;
92   BenchmarkSuite.suites.push(this);
93 }
94
95
96 // Keep track of all declared benchmark suites.
97 BenchmarkSuite.suites = [];
98
99 // Scores are not comparable across versions. Bump the version if
100 // you're making changes that will affect that scores, e.g. if you add
101 // a new benchmark or change an existing one.
102 BenchmarkSuite.version = '9';
103
104 // Override the alert function to throw an exception instead.
105 alert = function(s) {
106   throw "Alert called with argument: " + s;
107 };
108
109
110 // To make the benchmark results predictable, we replace Math.random
111 // with a 100% deterministic alternative.
112 BenchmarkSuite.ResetRNG = function() {
113   Math.random = (function() {
114     var seed = 49734321;
115     return function() {
116       // Robert Jenkins' 32 bit integer hash function.
117       seed = ((seed + 0x7ed55d16) + (seed << 12))  & 0xffffffff;
118       seed = ((seed ^ 0xc761c23c) ^ (seed >>> 19)) & 0xffffffff;
119       seed = ((seed + 0x165667b1) + (seed << 5))   & 0xffffffff;
120       seed = ((seed + 0xd3a2646c) ^ (seed << 9))   & 0xffffffff;
121       seed = ((seed + 0xfd7046c5) + (seed << 3))   & 0xffffffff;
122       seed = ((seed ^ 0xb55a4f09) ^ (seed >>> 16)) & 0xffffffff;
123       return (seed & 0xfffffff) / 0x10000000;
124     };
125   })();
126 }
127
128
129 // Runs all registered benchmark suites and optionally yields between
130 // each individual benchmark to avoid running for too long in the
131 // context of browsers. Once done, the final score is reported to the
132 // runner.
133 BenchmarkSuite.RunSuites = function(runner) {
134   var continuation = null;
135   var suites = BenchmarkSuite.suites;
136   var length = suites.length;
137   BenchmarkSuite.scores = [];
138   var index = 0;
139   function RunStep() {
140     while (continuation || index < length) {
141       if (continuation) {
142         continuation = continuation();
143       } else {
144         var suite = suites[index++];
145         if (runner.NotifyStart) runner.NotifyStart(suite.name);
146         continuation = suite.RunStep(runner);
147       }
148       if (continuation && typeof window != 'undefined' && window.setTimeout) {
149         window.setTimeout(RunStep, 25);
150         return;
151       }
152     }
153
154     // show final result
155     if (runner.NotifyScore) {
156       var score = BenchmarkSuite.GeometricMean(BenchmarkSuite.scores);
157       var formatted = BenchmarkSuite.FormatScore(100 * score);
158       runner.NotifyScore(formatted);
159     }
160   }
161   RunStep();
162 }
163
164
165 // Counts the total number of registered benchmarks. Useful for
166 // showing progress as a percentage.
167 BenchmarkSuite.CountBenchmarks = function() {
168   var result = 0;
169   var suites = BenchmarkSuite.suites;
170   for (var i = 0; i < suites.length; i++) {
171     result += suites[i].benchmarks.length;
172   }
173   return result;
174 }
175
176
177 // Computes the geometric mean of a set of numbers.
178 BenchmarkSuite.GeometricMean = function(numbers) {
179   var log = 0;
180   for (var i = 0; i < numbers.length; i++) {
181     log += Math.log(numbers[i]);
182   }
183   return Math.pow(Math.E, log / numbers.length);
184 }
185
186
187 // Computes the geometric mean of a set of throughput time measurements.
188 BenchmarkSuite.GeometricMeanTime = function(measurements) {
189   var log = 0;
190   for (var i = 0; i < measurements.length; i++) {
191     log += Math.log(measurements[i].time);
192   }
193   return Math.pow(Math.E, log / measurements.length);
194 }
195
196
197 // Computes the average of the worst samples. For example, if percentile is 99, this will report the
198 // average of the worst 1% of the samples.
199 BenchmarkSuite.AverageAbovePercentile = function(numbers, percentile) {
200   // Don't change the original array.
201   numbers = numbers.slice();
202   
203   // Sort in ascending order.
204   numbers.sort(function(a, b) { return a - b; });
205   
206   // Now the elements we want are at the end. Keep removing them until the array size shrinks too much.
207   // Examples assuming percentile = 99:
208   //
209   // - numbers.length starts at 100: we will remove just the worst entry and then not remove anymore,
210   //   since then numbers.length / originalLength = 0.99.
211   //
212   // - numbers.length starts at 1000: we will remove the ten worst.
213   //
214   // - numbers.length starts at 10: we will remove just the worst.
215   var numbersWeWant = [];
216   var originalLength = numbers.length;
217   while (numbers.length / originalLength > percentile / 100)
218     numbersWeWant.push(numbers.pop());
219   
220   var sum = 0;
221   for (var i = 0; i < numbersWeWant.length; ++i)
222     sum += numbersWeWant[i];
223   
224   var result = sum / numbersWeWant.length;
225   
226   // Do a sanity check.
227   if (numbers.length && result < numbers[numbers.length - 1]) {
228     throw "Sanity check fail: the worst case result is " + result +
229       " but we didn't take into account " + numbers;
230   }
231   
232   return result;
233 }
234
235
236 // Computes the geometric mean of a set of latency measurements.
237 BenchmarkSuite.GeometricMeanLatency = function(measurements) {
238   var log = 0;
239   var hasLatencyResult = false;
240   for (var i = 0; i < measurements.length; i++) {
241     if (measurements[i].latency != 0) {
242       log += Math.log(measurements[i].latency);
243       hasLatencyResult = true;
244     }
245   }
246   if (hasLatencyResult) {
247     return Math.pow(Math.E, log / measurements.length);
248   } else {
249     return 0;
250   }
251 }
252
253
254 // Converts a score value to a string with at least three significant
255 // digits.
256 BenchmarkSuite.FormatScore = function(value) {
257   if (value > 100) {
258     return value.toFixed(0);
259   } else {
260     return value.toPrecision(3);
261   }
262 }
263
264 // Notifies the runner that we're done running a single benchmark in
265 // the benchmark suite. This can be useful to report progress.
266 BenchmarkSuite.prototype.NotifyStep = function(result) {
267   this.results.push(result);
268   if (this.runner.NotifyStep) this.runner.NotifyStep(result.benchmark.name);
269 }
270
271
272 // Notifies the runner that we're done with running a suite and that
273 // we have a result which can be reported to the user if needed.
274 BenchmarkSuite.prototype.NotifyResult = function() {
275   var mean = BenchmarkSuite.GeometricMeanTime(this.results);
276   var score = this.reference[0] / mean;
277   BenchmarkSuite.scores.push(score);
278   if (this.runner.NotifyResult) {
279     var formatted = BenchmarkSuite.FormatScore(100 * score);
280     this.runner.NotifyResult(this.name, formatted);
281   }
282   if (this.reference.length == 2) {
283     var meanLatency = BenchmarkSuite.GeometricMeanLatency(this.results);
284     if (meanLatency != 0) {
285       var scoreLatency = this.reference[1] / meanLatency;
286       BenchmarkSuite.scores.push(scoreLatency);
287       if (this.runner.NotifyResult) {
288         var formattedLatency = BenchmarkSuite.FormatScore(100 * scoreLatency)
289         this.runner.NotifyResult(this.name + "Latency", formattedLatency);
290       }
291     }
292   }
293 }
294
295
296 // Notifies the runner that running a benchmark resulted in an error.
297 BenchmarkSuite.prototype.NotifyError = function(error) {
298   if (this.runner.NotifyError) {
299     this.runner.NotifyError(this.name, error);
300   }
301   if (this.runner.NotifyStep) {
302     this.runner.NotifyStep(this.name);
303   }
304 }
305
306
307 // Runs a single benchmark for at least a second and computes the
308 // average time it takes to run a single iteration.
309 BenchmarkSuite.prototype.RunSingleBenchmark = function(benchmark, data) {
310   function Measure(data) {
311     var elapsed = 0;
312     var start = new Date();
313   
314   // Run either for 1 second or for the number of iterations specified
315   // by minIterations, depending on the config flag doDeterministic.
316     for (var i = 0; (benchmark.doDeterministic ? 
317       i<benchmark.minIterations : elapsed < 1000); i++) {
318       benchmark.run();
319       elapsed = new Date() - start;
320     }
321     if (data != null) {
322       data.runs += i;
323       data.elapsed += elapsed;
324     }
325   }
326
327   // Sets up data in order to skip or not the warmup phase.
328   if (!benchmark.doWarmup && data == null) {
329     data = { runs: 0, elapsed: 0 };
330   }
331
332   if (data == null) {
333     Measure(null);
334     return { runs: 0, elapsed: 0 };
335   } else {
336     Measure(data);
337     // If we've run too few iterations, we continue for another second.
338     if (data.runs < benchmark.minIterations) return data;
339     var usec = (data.elapsed * 1000) / data.runs;
340     var latencySamples = (benchmark.latencyResult != null) ? benchmark.latencyResult() : [0];
341     var percentile = 99.5;
342     var latency = BenchmarkSuite.AverageAbovePercentile(latencySamples, percentile) * 1000;
343     this.NotifyStep(new BenchmarkResult(benchmark, usec, latency));
344     return null;
345   }
346 }
347
348
349 // This function starts running a suite, but stops between each
350 // individual benchmark in the suite and returns a continuation
351 // function which can be invoked to run the next benchmark. Once the
352 // last benchmark has been executed, null is returned.
353 BenchmarkSuite.prototype.RunStep = function(runner) {
354   BenchmarkSuite.ResetRNG();
355   this.results = [];
356   this.runner = runner;
357   var length = this.benchmarks.length;
358   var index = 0;
359   var suite = this;
360   var data;
361
362   // Run the setup, the actual benchmark, and the tear down in three
363   // separate steps to allow the framework to yield between any of the
364   // steps.
365
366   function RunNextSetup() {
367     if (index < length) {
368       try {
369         suite.benchmarks[index].Setup();
370       } catch (e) {
371         suite.NotifyError(e);
372         return null;
373       }
374       return RunNextBenchmark;
375     }
376     suite.NotifyResult();
377     return null;
378   }
379
380   function RunNextBenchmark() {
381     try {
382       data = suite.RunSingleBenchmark(suite.benchmarks[index], data);
383     } catch (e) {
384       suite.NotifyError(e);
385       return null;
386     }
387     // If data is null, we're done with this benchmark.
388     return (data == null) ? RunNextTearDown : RunNextBenchmark();
389   }
390
391   function RunNextTearDown() {
392     try {
393       suite.benchmarks[index++].TearDown();
394     } catch (e) {
395       suite.NotifyError(e);
396       return null;
397     }
398     return RunNextSetup;
399   }
400
401   // Start out running the setup.
402   return RunNextSetup();
403 }
404 // Copyright 2009 the V8 project authors. All rights reserved.
405 // Copyright (C) 2015 Apple Inc. All rights reserved.
406 // Redistribution and use in source and binary forms, with or without
407 // modification, are permitted provided that the following conditions are
408 // met:
409 //
410 //     * Redistributions of source code must retain the above copyright
411 //       notice, this list of conditions and the following disclaimer.
412 //     * Redistributions in binary form must reproduce the above
413 //       copyright notice, this list of conditions and the following
414 //       disclaimer in the documentation and/or other materials provided
415 //       with the distribution.
416 //     * Neither the name of Google Inc. nor the names of its
417 //       contributors may be used to endorse or promote products derived
418 //       from this software without specific prior written permission.
419 //
420 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
421 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
422 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
423 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
424 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
425 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
426 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
427 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
428 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
429 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
430 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
431
432 // This benchmark is based on a JavaScript log processing module used
433 // by the V8 profiler to generate execution time profiles for runs of
434 // JavaScript applications, and it effectively measures how fast the
435 // JavaScript engine is at allocating nodes and reclaiming the memory
436 // used for old nodes. Because of the way splay trees work, the engine
437 // also has to deal with a lot of changes to the large tree object
438 // graph.
439
440 var Splay = new BenchmarkSuite('Splay', [81491, 2739514], [
441   new Benchmark("Splay", true, false, 
442     SplayRun, SplaySetup, SplayTearDown, SplayLatency)
443 ]);
444
445
446 // Configuration.
447 var kSplayTreeSize = 8000;
448 var kSplayTreeModifications = 80;
449 var kSplayTreePayloadDepth = 5;
450
451 var splayTree = null;
452 var splaySampleTimeStart = 0.0;
453
454 function GeneratePayloadTree(depth, tag) {
455   if (depth == 0) {
456     return {
457       array  : [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ],
458       string : 'String for key ' + tag + ' in leaf node'
459     };
460   } else {
461     return {
462       left:  GeneratePayloadTree(depth - 1, tag),
463       right: GeneratePayloadTree(depth - 1, tag)
464     };
465   }
466 }
467
468
469 function GenerateKey() {
470   // The benchmark framework guarantees that Math.random is
471   // deterministic; see base.js.
472   return Math.random();
473 }
474
475 var splaySamples = [];
476
477 function SplayLatency() {
478   return splaySamples;
479 }
480
481 function SplayUpdateStats(time) {
482   var pause = time - splaySampleTimeStart;
483   splaySampleTimeStart = time;
484   splaySamples.push(pause);
485 }
486
487 function InsertNewNode() {
488   // Insert new node with a unique key.
489   var key;
490   do {
491     key = GenerateKey();
492   } while (splayTree.find(key) != null);
493   var payload = GeneratePayloadTree(kSplayTreePayloadDepth, String(key));
494   splayTree.insert(key, payload);
495   return key;
496 }
497
498
499 function SplaySetup() {
500   // Check if the platform has the performance.now high resolution timer.
501   // If not, throw exception and quit.
502   if (!performance.now) {
503     throw "PerformanceNowUnsupported";
504   }
505
506   splayTree = new SplayTree();
507   splaySampleTimeStart = performance.now()
508   for (var i = 0; i < kSplayTreeSize; i++) {
509     InsertNewNode();
510     if ((i+1) % 20 == 19) {
511       SplayUpdateStats(performance.now());
512     }
513   }
514 }
515
516
517 function SplayTearDown() {
518   // Allow the garbage collector to reclaim the memory
519   // used by the splay tree no matter how we exit the
520   // tear down function.
521   var keys = splayTree.exportKeys();
522   splayTree = null;
523
524   splaySamples = [];
525
526   // Verify that the splay tree has the right size.
527   var length = keys.length;
528   if (length != kSplayTreeSize) {
529     throw new Error("Splay tree has wrong size");
530   }
531
532   // Verify that the splay tree has sorted, unique keys.
533   for (var i = 0; i < length - 1; i++) {
534     if (keys[i] >= keys[i + 1]) {
535       throw new Error("Splay tree not sorted");
536     }
537   }
538 }
539
540
541 function SplayRun() {
542   // Replace a few nodes in the splay tree.
543   for (var i = 0; i < kSplayTreeModifications; i++) {
544     var key = InsertNewNode();
545     var greatest = splayTree.findGreatestLessThan(key);
546     if (greatest == null) splayTree.remove(key);
547     else splayTree.remove(greatest.key);
548   }
549   SplayUpdateStats(performance.now());
550 }
551
552
553 /**
554  * Constructs a Splay tree.  A splay tree is a self-balancing binary
555  * search tree with the additional property that recently accessed
556  * elements are quick to access again. It performs basic operations
557  * such as insertion, look-up and removal in O(log(n)) amortized time.
558  *
559  * @constructor
560  */
561 function SplayTree() {
562 };
563
564
565 /**
566  * Pointer to the root node of the tree.
567  *
568  * @type {SplayTree.Node}
569  * @private
570  */
571 SplayTree.prototype.root_ = null;
572
573
574 /**
575  * @return {boolean} Whether the tree is empty.
576  */
577 SplayTree.prototype.isEmpty = function() {
578   return !this.root_;
579 };
580
581
582 /**
583  * Inserts a node into the tree with the specified key and value if
584  * the tree does not already contain a node with the specified key. If
585  * the value is inserted, it becomes the root of the tree.
586  *
587  * @param {number} key Key to insert into the tree.
588  * @param {*} value Value to insert into the tree.
589  */
590 SplayTree.prototype.insert = function(key, value) {
591   if (this.isEmpty()) {
592     this.root_ = new SplayTree.Node(key, value);
593     return;
594   }
595   // Splay on the key to move the last node on the search path for
596   // the key to the root of the tree.
597   this.splay_(key);
598   if (this.root_.key == key) {
599     return;
600   }
601   var node = new SplayTree.Node(key, value);
602   if (key > this.root_.key) {
603     node.left = this.root_;
604     node.right = this.root_.right;
605     this.root_.right = null;
606   } else {
607     node.right = this.root_;
608     node.left = this.root_.left;
609     this.root_.left = null;
610   }
611   this.root_ = node;
612 };
613
614
615 /**
616  * Removes a node with the specified key from the tree if the tree
617  * contains a node with this key. The removed node is returned. If the
618  * key is not found, an exception is thrown.
619  *
620  * @param {number} key Key to find and remove from the tree.
621  * @return {SplayTree.Node} The removed node.
622  */
623 SplayTree.prototype.remove = function(key) {
624   if (this.isEmpty()) {
625     throw Error('Key not found: ' + key);
626   }
627   this.splay_(key);
628   if (this.root_.key != key) {
629     throw Error('Key not found: ' + key);
630   }
631   var removed = this.root_;
632   if (!this.root_.left) {
633     this.root_ = this.root_.right;
634   } else {
635     var right = this.root_.right;
636     this.root_ = this.root_.left;
637     // Splay to make sure that the new root has an empty right child.
638     this.splay_(key);
639     // Insert the original right child as the right child of the new
640     // root.
641     this.root_.right = right;
642   }
643   return removed;
644 };
645
646
647 /**
648  * Returns the node having the specified key or null if the tree doesn't contain
649  * a node with the specified key.
650  *
651  * @param {number} key Key to find in the tree.
652  * @return {SplayTree.Node} Node having the specified key.
653  */
654 SplayTree.prototype.find = function(key) {
655   if (this.isEmpty()) {
656     return null;
657   }
658   this.splay_(key);
659   return this.root_.key == key ? this.root_ : null;
660 };
661
662
663 /**
664  * @return {SplayTree.Node} Node having the maximum key value.
665  */
666 SplayTree.prototype.findMax = function(opt_startNode) {
667   if (this.isEmpty()) {
668     return null;
669   }
670   var current = opt_startNode || this.root_;
671   while (current.right) {
672     current = current.right;
673   }
674   return current;
675 };
676
677
678 /**
679  * @return {SplayTree.Node} Node having the maximum key value that
680  *     is less than the specified key value.
681  */
682 SplayTree.prototype.findGreatestLessThan = function(key) {
683   if (this.isEmpty()) {
684     return null;
685   }
686   // Splay on the key to move the node with the given key or the last
687   // node on the search path to the top of the tree.
688   this.splay_(key);
689   // Now the result is either the root node or the greatest node in
690   // the left subtree.
691   if (this.root_.key < key) {
692     return this.root_;
693   } else if (this.root_.left) {
694     return this.findMax(this.root_.left);
695   } else {
696     return null;
697   }
698 };
699
700
701 /**
702  * @return {Array<*>} An array containing all the keys of tree's nodes.
703  */
704 SplayTree.prototype.exportKeys = function() {
705   var result = [];
706   if (!this.isEmpty()) {
707     this.root_.traverse_(function(node) { result.push(node.key); });
708   }
709   return result;
710 };
711
712
713 /**
714  * Perform the splay operation for the given key. Moves the node with
715  * the given key to the top of the tree.  If no node has the given
716  * key, the last node on the search path is moved to the top of the
717  * tree. This is the simplified top-down splaying algorithm from:
718  * "Self-adjusting Binary Search Trees" by Sleator and Tarjan
719  *
720  * @param {number} key Key to splay the tree on.
721  * @private
722  */
723 SplayTree.prototype.splay_ = function(key) {
724   if (this.isEmpty()) {
725     return;
726   }
727   // Create a dummy node.  The use of the dummy node is a bit
728   // counter-intuitive: The right child of the dummy node will hold
729   // the L tree of the algorithm.  The left child of the dummy node
730   // will hold the R tree of the algorithm.  Using a dummy node, left
731   // and right will always be nodes and we avoid special cases.
732   var dummy, left, right;
733   dummy = left = right = new SplayTree.Node(null, null);
734   var current = this.root_;
735   while (true) {
736     if (key < current.key) {
737       if (!current.left) {
738         break;
739       }
740       if (key < current.left.key) {
741         // Rotate right.
742         var tmp = current.left;
743         current.left = tmp.right;
744         tmp.right = current;
745         current = tmp;
746         if (!current.left) {
747           break;
748         }
749       }
750       // Link right.
751       right.left = current;
752       right = current;
753       current = current.left;
754     } else if (key > current.key) {
755       if (!current.right) {
756         break;
757       }
758       if (key > current.right.key) {
759         // Rotate left.
760         var tmp = current.right;
761         current.right = tmp.left;
762         tmp.left = current;
763         current = tmp;
764         if (!current.right) {
765           break;
766         }
767       }
768       // Link left.
769       left.right = current;
770       left = current;
771       current = current.right;
772     } else {
773       break;
774     }
775   }
776   // Assemble.
777   left.right = current.left;
778   right.left = current.right;
779   current.left = dummy.right;
780   current.right = dummy.left;
781   this.root_ = current;
782 };
783
784
785 /**
786  * Constructs a Splay tree node.
787  *
788  * @param {number} key Key.
789  * @param {*} value Value.
790  */
791 SplayTree.Node = function(key, value) {
792   this.key = key;
793   this.value = value;
794 };
795
796
797 /**
798  * @type {SplayTree.Node}
799  */
800 SplayTree.Node.prototype.left = null;
801
802
803 /**
804  * @type {SplayTree.Node}
805  */
806 SplayTree.Node.prototype.right = null;
807
808
809 /**
810  * Performs an ordered traversal of the subtree starting at
811  * this SplayTree.Node.
812  *
813  * @param {function(SplayTree.Node)} f Visitor function.
814  * @private
815  */
816 SplayTree.Node.prototype.traverse_ = function(f) {
817   var current = this;
818   while (current) {
819     var left = current.left;
820     if (left) left.traverse_(f);
821     f(current);
822     current = current.right;
823   }
824 };
825 function jscSetUp() {
826     SplaySetup();
827 }
828
829 function jscTearDown() {
830     SplayTearDown();
831 }
832
833 function jscRun() {
834     SplayRun();
835 }
836
837 jscSetUp();
838 var __before = preciseTime();
839 var times = [];
840 for (var i = 0; i < 10000; ++i) {
841 //for (var i = 0; i < 1000000; ++i) {
842     var _before = preciseTime();
843     jscRun();
844     var _after = preciseTime();
845     times.push(_after - _before);
846     flashHeapAccess();
847 }
848 var __after = preciseTime();
849 jscTearDown();
850
851 function averageAbovePercentile(numbers, percentile) {
852     // Don't change the original array.
853     numbers = numbers.slice();
854     
855     // Sort in ascending order.
856     numbers.sort(function(a, b) { return a - b; });
857     
858     // Now the elements we want are at the end. Keep removing them until the array size shrinks too much.
859     // Examples assuming percentile = 99:
860     //
861     // - numbers.length starts at 100: we will remove just the worst entry and then not remove anymore,
862     //   since then numbers.length / originalLength = 0.99.
863     //
864     // - numbers.length starts at 1000: we will remove the ten worst.
865     //
866     // - numbers.length starts at 10: we will remove just the worst.
867     var numbersWeWant = [];
868     var originalLength = numbers.length;
869     while (numbers.length / originalLength > percentile / 100)
870         numbersWeWant.push(numbers.pop());
871     
872     var sum = 0;
873     for (var i = 0; i < numbersWeWant.length; ++i)
874         sum += numbersWeWant[i];
875     
876     var result = sum / numbersWeWant.length;
877     
878     // Do a sanity check.
879     if (numbers.length && result < numbers[numbers.length - 1]) {
880         throw "Sanity check fail: the worst case result is " + result +
881             " but we didn't take into account " + numbers;
882     }
883     
884     return result;
885 }
886
887 print("That took " + (__after - __before) * 1000 + " ms.");
888
889 function printPercentile(percentile)
890 {
891     print("Above " + percentile + "%: " + averageAbovePercentile(times, percentile) * 1000 + " ms.");
892 }
893
894 printPercentile(99.9);
895 printPercentile(99.5);
896 printPercentile(99);
897 printPercentile(97.5);
898 printPercentile(95);
899 printPercentile(90);
900 printPercentile(75);
901 printPercentile(50);
902 printPercentile(0);
903
904 gc();