dom-perf.js

   1 /*
   2  * Copyright (C) 2009 Google Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  *     * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *     * Redistributions in binary form must reproduce the above
  11  * copyright notice, this list of conditions and the following disclaimer
  12  * in the documentation and/or other materials provided with the
  13  * distribution.
  14  *     * Neither the name of Google Inc. nor the names of its
  15  * contributors may be used to endorse or promote products derived from
  16  * this software without specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 // A framework for running the benchmark suites and computing a score based
  32 // on timing measurements.
  33 //
  34 // Time measurements are computed by summing individual measurements in a
  35 // test's run() function.  Because Javascript generally has a 1ms timer
  36 // granularity, tests should be careful to take at least 2ms to run.  Tests
  37 // which run in less than 1ms are invalid.  Some older browsers have less
  38 // timer resolution, as low as 15ms.  On these systems tests which take less
  39 // than 15ms to run are invalid.
  40 //
  41 // Scores for a benchmark suite are calculated as the geometric mean across
  42 // all benchmarks which comprise that suite.
  43 //
  44 // Overall score is calculated as the geometric mean across all benchmark
  45 // suites.
  46
  47 // Benchmark Object.
  48 // A benchmark is a test which can be run as part of a BenchmarkSuite.
  49 //
  50 // Each test provides the following properties:
  51 //    name
  52 //      The name of the benchmark.
  53 //    run
  54 //      The work function which is measured
  55 //    opt_setup (optional)
  56 //      A function which is run before each benchmark iteration.
  57 //    opt_cleanup (optional)
  58 //      A function to cleanup any side-effects of a benchmark.
  59 //    opt_shareSetup (optional)
  60 //      A flag indicating whether the setup function should be run once or with
  61 //      each benchmark iteration.  (default is false)
  62 //
  63
  64 // Add each method to Arrays, to allow easy iteration over elements
  65 if(!Array.prototype.forEach) {
  66     // forEach's calling syntax is:
  67     //   [].forEach(func, scope);
  68     // registered callbacks always get 3 args:
  69     //   [].forEach(function(item, index, fullArray){});
  70     Array.prototype.forEach = function(callback, scope) {
  71         callback = hitch(scope, callback);
  72         for (var i = 0, len = this.length; i < len; i++)
  73             callback(this[i], i, this);
  74     };
  75 }
  76
  77 byId = function(id, doc) {
  78     if (typeof id == "string")
  79         return (doc||document).getElementById(id);
  80     return id;
  81 };
  82
  83 // A utility object for measuring time intervals.
  84 function Interval() {
  85   var start_ = 0;
  86   var stop_ = 0;
  87   this.start = function() { start_ = new Date(); };
  88   this.stop = function() { stop_ = new Date(); };
  89   this.microseconds = function() { return (stop_ - start_) * 1000; };
  90 }
  91
  92 // A stub profiler object.
  93 function PseudoProfiler() {}
  94 PseudoProfiler.prototype.start = function() {};
  95 PseudoProfiler.prototype.stop = function() {};
  96
  97 var chromiumProfilerInitOnce = false;   // Chromium profiler initialization.
  98
  99 // Cross-platform function to get the profiler object.
 100 // For chromium, returns a Profiler object which can be used during the run.
 101 // For other browsers, returns a PseudoProfiler object.
 102 function GetProfiler() {
 103     if (window.chromium && window.chromium.Profiler) {
 104         var profiler = new window.chromium.Profiler();
 105         if (!chromiumProfilerInitOnce) {
 106             chromiumProfilerInitOnce = true;
 107             profiler.stop();
 108             if (profiler.clear)
 109                 profiler.clear();
 110             if (profiler.setThreadName)
 111                 profiler.setThreadName("domperf javascript");
 112         }
 113         return profiler;
 114     }
 115     return new PseudoProfiler();
 116 }
 117
 118 function Benchmark(name, run, opt_setup, opt_cleanup, opt_shareSetup) {
 119     this.name = name;
 120     this.timeToRun = 100; // ms.
 121     // Tests like DOM/DOMWalk.html are too fast and need to be ran multiple times.
 122     // 100 ms was chosen since it was long enough to make DOMWalk and other fast tests stable
 123     // but was short enough not to make other slow tests run multiple times.
 124     this.run = run;
 125     this.setup = opt_setup;
 126     this.cleanup = opt_cleanup;
 127     this.shareSetup = opt_shareSetup;
 128 }
 129
 130 // BenchmarkSuite
 131 // A group of benchmarks that can be run together.
 132 function BenchmarkSuite(name, benchmarks) {
 133     this.name = name;
 134     this.benchmarks = benchmarks;
 135     for (var i = 0; i < this.benchmarks.length; i++)
 136         this.benchmarks[i].suite = this;
 137     this.suiteFile = this.currentSuiteFile;
 138 }
 139
 140 // This computes the amount of overhead is associated with the call to the test
 141 // function and getting the date.
 142 BenchmarkSuite.start = new Date();
 143
 144 BenchmarkSuite.Math = new (function() {
 145     // Computes the geometric mean of a set of numbers.
 146     // nulls in numbers will be ignored
 147     // minNumber is optional (defaults to 0.001) anything smaller than this
 148     // will be changed to this value, eliminating infinite results
 149     // mapFn is an optional arg that will be used as a map function on numbers
 150     this.GeometricMean = function(numbers, minNumber, mapFn) {
 151         if (mapFn)
 152             numbers = dojo.map(numbers, mapFn);
 153         var log = 0;
 154         var nNumbers = 0;
 155         for (var i = 0, n = numbers.length; i < n; i++) {
 156             var number = numbers[i];
 157             if (number) {
 158                 if (number < minNumber)
 159                     number = minNumber;
 160                 nNumbers++;
 161                 log += Math.log(number);
 162             }
 163         }
 164         return Math.pow(Math.E, log / nNumbers);
 165     };
 166
 167     // Compares two objects using built-in JavaScript operators.
 168     this.ascend = function(a, b) {
 169         if (a < b)
 170           return -1;
 171         else if (a > b)
 172           return 1;
 173         return 0;
 174     };
 175 });
 176
 177 // Benchmark results hold the benchmark and the measured time used to run the
 178 // benchmark. The benchmark score is computed later once a full benchmark suite
 179 // has run to completion.
 180 function BenchmarkResult(benchmark, times, error, benchmarkContent) {
 181     this.benchmark = benchmark;
 182     this.error = error;
 183     this.times = times;
 184
 185     this.countNodes = function(parent) {
 186         var nDescendants = 0;
 187         for (var child = parent.firstChild; child; child = child.nextSibling)
 188             nDescendants += countNodes(child);
 189         return nDescendants + 1;
 190     };
 191
 192     if (benchmarkContent) {
 193         var nNodes = countNodes(benchmarkContent) - 1;
 194         if (nNodes > 0) {
 195             this.html = benchmarkContent.innerHTML;
 196             this.nNodes = nNodes;
 197         }
 198     }
 199     if (!error) {
 200         var statistics = PerfTestRunner.computeStatistics(times);
 201         this.min = statistics.min;
 202         this.max = statistics.max;
 203         this.median = statistics.median;
 204         this.mean = statistics.mean;
 205         this.sum = statistics.sum;
 206         this.variance = statistics.variance;
 207         this.stdev = statistics.stdev;
 208     }
 209
 210     // Convert results to numbers. Used by the geometric mean computation.
 211     this.valueOf = function() { return this.time; };
 212 }
 213
 214 // Runs a single benchmark and computes the average time it takes to run a
 215 // single iteration.
 216 BenchmarkSuite.prototype.RunSingle = function(benchmark, times) {
 217     var elapsed = 0;
 218     var start = new Date();
 219     var runInterval = new Interval();
 220     var setupReturn = null;
 221     var runReturn = null;
 222     var time;
 223     var totalTime = 0;
 224     var nZeros = 0;
 225     var error = null;
 226     var profiler = GetProfiler();
 227
 228     for (var n = 0; !error && totalTime < benchmark.timeToRun;  n++) {
 229         if (this.benchmarkContent)
 230             this.benchmarkContentHolder.removeChild(this.benchmarkContent);
 231         this.benchmarkContent = this.benchmarkContentProto.cloneNode();
 232         this.benchmarkContentHolder.appendChild(this.benchmarkContent);
 233         PerfTestRunner.gc();
 234
 235         try {
 236             if (benchmark.setup) {
 237                 if (!setupReturn || !benchmark.shareSetup)
 238                     setupReturn = benchmark.setup();
 239             }
 240
 241             profiler.start();
 242             runInterval.start();
 243             runReturn = benchmark.run(setupReturn);
 244             runInterval.stop();
 245             profiler.stop();
 246             time = runInterval.microseconds() / 1000;
 247             if (time > 0) {
 248                 times.push(time);
 249                 elapsed += time;
 250             } else
 251                 times.push(0);
 252             if (benchmark.cleanup)
 253                 benchmark.cleanup(runReturn);
 254         } catch (e) {
 255             error = e;
 256         }
 257         totalTime = new Date() - start;
 258   }
 259
 260     var result = new BenchmarkResult(benchmark, times, error, null);
 261     if (this.benchmarkContent) {
 262         this.benchmarkContentHolder.removeChild(this.benchmarkContent);
 263         this.benchmarkContent = null;
 264     }
 265     return result;
 266 };
 267
 268 BenchmarkSuite.prototype.generateTree = function(parent, width, depth) {
 269     var id = parent.id;
 270     if (depth !== 0) {
 271         var middle = Math.floor(width / 2);
 272         for (var i = 0; i < width; i++) {
 273             if (i == middle) {
 274                 var divNode = document.createElement("div");
 275                 // TODO:[dave] this causes us to have potentially very long
 276                 // ids. We might want to encode these values into a smaller string
 277                 divNode.id = id + ':(' + i + ', 0)';
 278                 parent.appendChild(divNode);
 279                 this.generateTree(divNode, width, depth - 1);
 280             } else {
 281                 var p = parent;
 282                 for (var j = 0; j < i; j++) {
 283                     var divNode = document.createElement("div");
 284                     divNode.id = id + ':(' + i + ',' + j + ')';
 285                     p.appendChild(divNode);
 286                     p = divNode;
 287                 }
 288                 var span = document.createElement("span");
 289                 span.appendChild(document.createTextNode(p.id));
 290                 p.appendChild(span);
 291             }
 292         }
 293     }
 294 };
 295
 296 // Generates a DOM tree (doesn't insert it into the document).
 297 // The width and depth arguments help shape the "bushiness" of the full tree.
 298 // The approach is to recursively generate a set of subtrees. At each root we
 299 // generate width trees, of increasing depth, from 1 to width.  Then we recurse
 300 // from the middle child of this subtree. We do this up to depth times.  reps
 301 // allows us to duplicate a set of trees, without additional recursions.
 302 BenchmarkSuite.prototype.generateDOMTree = function(width, depth, reps) {
 303     var top = document.createElement("div");
 304
 305     top.id = "test";
 306     for (var i = 0; i < reps; i++) {
 307         var divNode = document.createElement("div");
 308         divNode.id = "test" + i;
 309         this.generateTree(divNode, width, depth);
 310         top.appendChild(divNode);
 311     }
 312     return top;
 313 };
 314
 315 // Generate a small sized tree.
 316 // 92 span leaves, max depth: 23, avg depth: 14
 317 BenchmarkSuite.prototype.generateSmallTree = function() {
 318     return this.generateDOMTree(14, 12, 10);
 319 };
 320
 321 // Generate a medium sized tree.
 322 // 1320 span leaves, max depth: 27, avg depth: 16
 323 BenchmarkSuite.prototype.generateMediumTree = function() {
 324     return this.generateDOMTree(19, 13, 9);
 325 };
 326
 327 // Generate a large sized tree.
 328 // 2600 span leaves, max depth: 55, avg depth: 30
 329 BenchmarkSuite.prototype.generateLargeTree = function() {
 330     return this.generateDOMTree(26, 26, 4);
 331 };
 332
 333 function runBenchmarkSuite(suite, runCount) {
 334     PerfTestRunner.run(function () {
 335         var container = document.getElementById('container');
 336         var content = document.getElementById('benchmark_content');
 337         suite.benchmarkContentHolder = container;
 338         suite.benchmarkContentProto = content;
 339         var totalMeanTime = 0;
 340         for (var j = 0; j < suite.benchmarks.length; j++) {
 341             var result = suite.RunSingle(suite.benchmarks[j], []);
 342             if (result.error)
 343                 log(result.error);
 344             else
 345                 totalMeanTime += result.mean;
 346         }
 347         return totalMeanTime;
 348     }, 1, runCount || 20, function () {
 349         var container = document.getElementById('container');
 350         if (container.firstChild)
 351             container.removeChild(container.firstChild);
 352     });
 353 }