DOM/DOMDivWalk.html result is unreliable
[WebKit-https.git] / PerformanceTests / DOM / resources / 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 // To make the benchmark results predictable, we replace Math.random with a
119 // 100% deterministic alternative.
120 Math.random = (function() {
121     var seed = 49734321;
122     return function() {
123         // Robert Jenkins' 32 bit integer hash function.
124         seed = ((seed + 0x7ed55d16) + (seed << 12))  & 0xffffffff;
125         seed = ((seed ^ 0xc761c23c) ^ (seed >>> 19)) & 0xffffffff;
126         seed = ((seed + 0x165667b1) + (seed << 5))   & 0xffffffff;
127         seed = ((seed + 0xd3a2646c) ^ (seed << 9))   & 0xffffffff;
128         seed = ((seed + 0xfd7046c5) + (seed << 3))   & 0xffffffff;
129         seed = ((seed ^ 0xb55a4f09) ^ (seed >>> 16)) & 0xffffffff;
130         return (seed & 0xfffffff) / 0x10000000;
131     };
132 })();
133
134 function Benchmark(name, run, opt_setup, opt_cleanup, opt_shareSetup) {
135     this.name = name;
136     this.timeToRun = 500; // ms
137     this.run = run;
138     this.setup = opt_setup;
139     this.cleanup = opt_cleanup;
140     this.shareSetup = opt_shareSetup;
141 }
142
143 // BenchmarkSuite
144 // A group of benchmarks that can be run together.
145 function BenchmarkSuite(name, benchmarks) {
146     this.name = name;
147     this.benchmarks = benchmarks;
148     for (var i = 0; i < this.benchmarks.length; i++)
149         this.benchmarks[i].suite = this;
150     this.suiteFile = this.currentSuiteFile;
151 }
152
153 // This computes the amount of overhead is associated with the call to the test
154 // function and getting the date. 
155 BenchmarkSuite.start = new Date();
156
157 BenchmarkSuite.Math = new (function() {
158     // Computes the geometric mean of a set of numbers.
159     // nulls in numbers will be ignored
160     // minNumber is optional (defaults to 0.001) anything smaller than this
161     // will be changed to this value, eliminating infinite results
162     // mapFn is an optional arg that will be used as a map function on numbers
163     this.GeometricMean = function(numbers, minNumber, mapFn) {
164         if (mapFn)
165             numbers = dojo.map(numbers, mapFn);
166         var log = 0;
167         var nNumbers = 0;
168         for (var i = 0, n = numbers.length; i < n; i++) {
169             var number = numbers[i];
170             if (number) {
171                 if (number < minNumber)
172                     number = minNumber;
173                 nNumbers++;
174                 log += Math.log(number);
175             }
176         }
177         return Math.pow(Math.E, log / nNumbers);
178     };
179
180     // Compares two objects using built-in JavaScript operators.
181     this.ascend = function(a, b) {
182         if (a < b)
183           return -1;
184         else if (a > b)
185           return 1;
186         return 0;
187     };
188 });
189
190 // Benchmark results hold the benchmark and the measured time used to run the
191 // benchmark. The benchmark score is computed later once a full benchmark suite
192 // has run to completion.
193 function BenchmarkResult(benchmark, times, error, benchmarkContent) {
194     this.benchmark = benchmark;
195     this.error = error;
196     this.times = times;
197
198     this.countNodes = function(parent) {
199         var nDescendants = 0;
200         for (var child = parent.firstChild; child; child = child.nextSibling)
201             nDescendants += countNodes(child);
202         return nDescendants + 1;
203     };
204
205     if (benchmarkContent) {
206         var nNodes = countNodes(benchmarkContent) - 1;
207         if (nNodes > 0) {
208             this.html = benchmarkContent.innerHTML;
209             this.nNodes = nNodes;
210         }
211     }
212     if (!error) {
213         var data = times.slice();
214         var count = data.length;
215
216         // Sort the data so that all seemingly
217         // insignificant values such as 0.000000003 will
218         // be at the beginning of the array and their
219         // contribution to the mean and variance of the
220         // data will not be lost because of the precision
221         // of the CPU.
222         data.sort(BenchmarkSuite.Math.ascend);
223
224         // Since the data is now sorted, the minimum value
225         // is at the beginning of the array, the median
226         // value is in the middle of the array, and the
227         // maximum value is at the end of the array.
228         this.min = data[0];
229         var middle = Math.floor(data.length / 2);
230         if ((data.length % 2) !== 0)
231             this.median = data[middle];
232         else
233             this.median = (data[middle - 1] + data[middle]) / 2;
234         this.max = data[data.length - 1];
235
236         // Compute the mean and variance using a
237         // numerically stable algorithm.
238         var sqsum = 0;
239         this.mean = data[0];
240         var nZeros = 0;
241         for (var i = 1; i < data.length; ++i) {
242             var x = data[i];
243             var delta = x - this.mean;
244             var sweep = i + 1.0;
245             this.mean += delta / sweep;
246             sqsum += delta * delta * (i / sweep);
247         }
248         this.sum = this.mean * count;
249         this.variance = sqsum / count;
250
251         this.sdev = Math.sqrt(this.variance);
252         this.score = 1000 / this.mean;
253     }
254
255     this.toString = function() {
256         var s =
257           " min: " + this.min + 
258           " max: " + this.max + 
259           " mean: " + this.mean + 
260           " median: " + this.median + 
261           " sdev: " + this.sdev;
262         return s;
263     };
264
265     // Convert results to numbers. Used by the geometric mean computation.
266     this.valueOf = function() { return this.time; };
267 }
268
269 // Runs a single benchmark and computes the average time it takes to run a
270 // single iteration.
271 BenchmarkSuite.prototype.RunSingle = function(benchmark, times) {
272     var elapsed = 0;
273     var start = new Date();
274     var runInterval = new Interval();
275     var setupReturn = null;
276     var runReturn = null;
277     var time;
278     var totalTime = 0;
279     var nZeros = 0;
280     var error = null;
281     var profiler = GetProfiler();
282     for (var n = 0; !error && totalTime < benchmark.timeToRun;  n++) {
283         if (this.benchmarkContent)
284             this.benchmarkContentHolder.removeChild(this.benchmarkContent);
285         this.benchmarkContent = this.benchmarkContentProto.cloneNode();
286         this.benchmarkContentHolder.appendChild(this.benchmarkContent);
287         gc();
288
289         try {
290             if (benchmark.setup) {
291                 if (!setupReturn || !benchmark.shareSetup)
292                     setupReturn = benchmark.setup();
293             }
294
295             profiler.start();
296             runInterval.start();
297             runReturn = benchmark.run(setupReturn);
298             runInterval.stop();
299             profiler.stop();
300             time = runInterval.microseconds() / 1000;
301             if (time > 0) {
302                 times.push(time);
303                 elapsed += time;
304             } else
305                 times.push(0);
306             if (benchmark.cleanup)
307                 benchmark.cleanup(runReturn);
308         } catch (e) {
309             error = e;
310         }
311         totalTime = new Date() - start;
312     }
313
314     var result = new BenchmarkResult(benchmark, times, error, null);
315     if (this.benchmarkContent) {
316         this.benchmarkContentHolder.removeChild(this.benchmarkContent);
317         this.benchmarkContent = null;
318     }
319     return result;
320 };
321
322 BenchmarkSuite.prototype.generateTree = function(parent, width, depth) {
323     var id = parent.id;
324     if (depth !== 0) {
325         var middle = Math.floor(width / 2);
326         for (var i = 0; i < width; i++) {
327             if (i == middle) {
328                 var divNode = document.createElement("div");
329                 // TODO:[dave] this causes us to have potentially very long
330                 // ids. We might want to encode these values into a smaller string
331                 divNode.id = id + ':(' + i + ', 0)';
332                 parent.appendChild(divNode);
333                 this.generateTree(divNode, width, depth - 1);
334             } else {
335                 var p = parent;
336                 for (var j = 0; j < i; j++) {
337                     var divNode = document.createElement("div");
338                     divNode.id = id + ':(' + i + ',' + j + ')';
339                     p.appendChild(divNode);
340                     p = divNode;
341                 }
342                 var span = document.createElement("span");
343                 span.appendChild(document.createTextNode(p.id));
344                 p.appendChild(span);
345             }
346         }
347     }
348 };
349
350 // Generates a DOM tree (doesn't insert it into the document).
351 // The width and depth arguments help shape the "bushiness" of the full tree.
352 // The approach is to recursively generate a set of subtrees. At each root we
353 // generate width trees, of increasing depth, from 1 to width.  Then we recurse
354 // from the middle child of this subtree. We do this up to depth times.  reps
355 // allows us to duplicate a set of trees, without additional recursions. 
356 BenchmarkSuite.prototype.generateDOMTree = function(width, depth, reps) {
357     var top = document.createElement("div");
358
359     top.id = "test";
360     for (var i = 0; i < reps; i++) {
361         var divNode = document.createElement("div");
362         divNode.id = "test" + i;
363         this.generateTree(divNode, width, depth);
364         top.appendChild(divNode);
365     }
366     return top;
367 };
368
369 // Generate a small sized tree.
370 // 92 span leaves, max depth: 23, avg depth: 14
371 BenchmarkSuite.prototype.generateSmallTree = function() {
372     return this.generateDOMTree(14, 12, 10);
373 };
374
375 // Generate a medium sized tree.
376 // 1320 span leaves, max depth: 27, avg depth: 16
377 BenchmarkSuite.prototype.generateMediumTree = function() {
378     return this.generateDOMTree(19, 13, 9);
379 };
380
381 // Generate a large sized tree.
382 // 2600 span leaves, max depth: 55, avg depth: 30
383 BenchmarkSuite.prototype.generateLargeTree = function() {
384     return this.generateDOMTree(26, 26, 4);
385 };
386
387 function runBenchmarkSuite(suite) {
388     startCustom(20, function () {
389         var container = document.getElementById('container');
390         var content = document.getElementById('benchmark_content');
391         suite.benchmarkContentHolder = container;
392         suite.benchmarkContentProto = content;
393         var totalMeanTime = 0;
394         for (var j = 0; j < suite.benchmarks.length; j++) {
395             var result = suite.RunSingle(suite.benchmarks[j], []);
396             if (result.error)
397                 log(result.error);
398             else
399                 totalMeanTime += result.mean;
400         }
401         return totalMeanTime;
402     }, function () {
403         var container = document.getElementById('container');
404         if (container.firstChild)
405             container.removeChild(container.firstChild);
406     });
407 }