blob: 2010ec2c3190186903a40778306ee746a60ff82a [file] [log] [blame]
guijemont@igalia.com863f0982017-12-21 18:40:14 +00001//@ skip if $memoryLimited
fpizlo@apple.comc1ed3e72017-02-22 00:58:15 +00002//@ 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.
35var performance = performance || {};
36performance.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.
54function 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.
70function 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.
79BenchmarkResult.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.
88function 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.
97BenchmarkSuite.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.
102BenchmarkSuite.version = '9';
103
104// Override the alert function to throw an exception instead.
105alert = 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.
112BenchmarkSuite.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.
133BenchmarkSuite.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.
167BenchmarkSuite.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.
178BenchmarkSuite.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.
188BenchmarkSuite.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.
199BenchmarkSuite.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.
237BenchmarkSuite.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.
256BenchmarkSuite.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.
266BenchmarkSuite.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.
274BenchmarkSuite.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.
297BenchmarkSuite.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.
309BenchmarkSuite.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.
353BenchmarkSuite.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
440var Splay = new BenchmarkSuite('Splay', [81491, 2739514], [
441 new Benchmark("Splay", true, false,
442 SplayRun, SplaySetup, SplayTearDown, SplayLatency)
443]);
444
445
446// Configuration.
447var kSplayTreeSize = 8000;
448var kSplayTreeModifications = 80;
449var kSplayTreePayloadDepth = 5;
450
451var splayTree = null;
452var splaySampleTimeStart = 0.0;
453
454function 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
469function GenerateKey() {
470 // The benchmark framework guarantees that Math.random is
471 // deterministic; see base.js.
472 return Math.random();
473}
474
475var splaySamples = [];
476
477function SplayLatency() {
478 return splaySamples;
479}
480
481function SplayUpdateStats(time) {
482 var pause = time - splaySampleTimeStart;
483 splaySampleTimeStart = time;
484 splaySamples.push(pause);
485}
486
487function 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
499function 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
517function 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
541function 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 */
561function SplayTree() {
562};
563
564
565/**
566 * Pointer to the root node of the tree.
567 *
568 * @type {SplayTree.Node}
569 * @private
570 */
571SplayTree.prototype.root_ = null;
572
573
574/**
575 * @return {boolean} Whether the tree is empty.
576 */
577SplayTree.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 */
590SplayTree.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 */
623SplayTree.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 */
654SplayTree.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 */
666SplayTree.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 */
682SplayTree.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 */
704SplayTree.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 */
723SplayTree.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 */
791SplayTree.Node = function(key, value) {
792 this.key = key;
793 this.value = value;
794};
795
796
797/**
798 * @type {SplayTree.Node}
799 */
800SplayTree.Node.prototype.left = null;
801
802
803/**
804 * @type {SplayTree.Node}
805 */
806SplayTree.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 */
816SplayTree.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};
825function jscSetUp() {
826 SplaySetup();
827}
828
829function jscTearDown() {
830 SplayTearDown();
831}
832
833function jscRun() {
834 SplayRun();
835}
836
837jscSetUp();
838var __before = preciseTime();
839var times = [];
840for (var i = 0; i < 2000; ++i) {
841 var _before = preciseTime();
842 jscRun();
843 var _after = preciseTime();
844 times.push(_after - _before);
845 flashHeapAccess(1);
846}
847var __after = preciseTime();
848jscTearDown();
849
850function averageAbovePercentile(numbers, percentile) {
851 // Don't change the original array.
852 numbers = numbers.slice();
853
854 // Sort in ascending order.
855 numbers.sort(function(a, b) { return a - b; });
856
857 // Now the elements we want are at the end. Keep removing them until the array size shrinks too much.
858 // Examples assuming percentile = 99:
859 //
860 // - numbers.length starts at 100: we will remove just the worst entry and then not remove anymore,
861 // since then numbers.length / originalLength = 0.99.
862 //
863 // - numbers.length starts at 1000: we will remove the ten worst.
864 //
865 // - numbers.length starts at 10: we will remove just the worst.
866 var numbersWeWant = [];
867 var originalLength = numbers.length;
868 while (numbers.length / originalLength > percentile / 100)
869 numbersWeWant.push(numbers.pop());
870
871 var sum = 0;
872 for (var i = 0; i < numbersWeWant.length; ++i)
873 sum += numbersWeWant[i];
874
875 var result = sum / numbersWeWant.length;
876
877 // Do a sanity check.
878 if (numbers.length && result < numbers[numbers.length - 1]) {
879 throw "Sanity check fail: the worst case result is " + result +
880 " but we didn't take into account " + numbers;
881 }
882
883 return result;
884}
885
886print("That took " + (__after - __before) * 1000 + " ms.");
887
888function printPercentile(percentile)
889{
890 print("Above " + percentile + "%: " + averageAbovePercentile(times, percentile) * 1000 + " ms.");
891}
892
893printPercentile(99.9);
894printPercentile(99.5);
895printPercentile(99);
896printPercentile(97.5);
897printPercentile(95);
898printPercentile(90);
899printPercentile(75);
900printPercentile(50);
901printPercentile(0);
902
903gc();