guijemont@igalia.com | 863f098 | 2017-12-21 18:40:14 +0000 | [diff] [blame] | 1 | //@ skip if $memoryLimited |
fpizlo@apple.com | c1ed3e7 | 2017-02-22 00:58:15 +0000 | [diff] [blame] | 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 < 2000; ++i) { |
| 841 | var _before = preciseTime(); |
| 842 | jscRun(); |
| 843 | var _after = preciseTime(); |
| 844 | times.push(_after - _before); |
| 845 | flashHeapAccess(1); |
| 846 | } |
| 847 | var __after = preciseTime(); |
| 848 | jscTearDown(); |
| 849 | |
| 850 | function 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 | |
| 886 | print("That took " + (__after - __before) * 1000 + " ms."); |
| 887 | |
| 888 | function printPercentile(percentile) |
| 889 | { |
| 890 | print("Above " + percentile + "%: " + averageAbovePercentile(times, percentile) * 1000 + " ms."); |
| 891 | } |
| 892 | |
| 893 | printPercentile(99.9); |
| 894 | printPercentile(99.5); |
| 895 | printPercentile(99); |
| 896 | printPercentile(97.5); |
| 897 | printPercentile(95); |
| 898 | printPercentile(90); |
| 899 | printPercentile(75); |
| 900 | printPercentile(50); |
| 901 | printPercentile(0); |
| 902 | |
| 903 | gc(); |