Add Websites/browserbench.org
[WebKit-https.git] / Websites / browserbench.org / MotionMark / resources / statistics.js
1 Pseudo =
2 {
3     initialRandomSeed: 49734321,
4     randomSeed: 49734321,
5
6     resetRandomSeed: function()
7     {
8         Pseudo.randomSeed = Pseudo.initialRandomSeed;
9     },
10
11     random: function()
12     {
13         var randomSeed = Pseudo.randomSeed;
14         randomSeed = ((randomSeed + 0x7ed55d16) + (randomSeed << 12))  & 0xffffffff;
15         randomSeed = ((randomSeed ^ 0xc761c23c) ^ (randomSeed >>> 19)) & 0xffffffff;
16         randomSeed = ((randomSeed + 0x165667b1) + (randomSeed << 5))   & 0xffffffff;
17         randomSeed = ((randomSeed + 0xd3a2646c) ^ (randomSeed << 9))   & 0xffffffff;
18         randomSeed = ((randomSeed + 0xfd7046c5) + (randomSeed << 3))   & 0xffffffff;
19         randomSeed = ((randomSeed ^ 0xb55a4f09) ^ (randomSeed >>> 16)) & 0xffffffff;
20         Pseudo.randomSeed = randomSeed;
21         return (randomSeed & 0xfffffff) / 0x10000000;
22     }
23 };
24
25 Statistics =
26 {
27     sampleMean: function(numberOfSamples, sum)
28     {
29         if (numberOfSamples < 1)
30             return 0;
31         return sum / numberOfSamples;
32     },
33
34     // With sum and sum of squares, we can compute the sample standard deviation in O(1).
35     // See https://rniwa.com/2012-11-10/sample-standard-deviation-in-terms-of-sum-and-square-sum-of-samples/
36     unbiasedSampleStandardDeviation: function(numberOfSamples, sum, squareSum)
37     {
38         if (numberOfSamples < 2)
39             return 0;
40         return Math.sqrt((squareSum - sum * sum / numberOfSamples) / (numberOfSamples - 1));
41     },
42
43     geometricMean: function(values)
44     {
45         if (!values.length)
46             return 0;
47         var roots = values.map(function(value) { return Math.pow(value, 1 / values.length); })
48         return roots.reduce(function(a, b) { return a * b; });
49     },
50
51     // Cumulative distribution function
52     cdf: function(value, mean, standardDeviation)
53     {
54         return 0.5 * (1 + Statistics.erf((value - mean) / (Math.sqrt(2 * standardDeviation * standardDeviation))));
55     },
56
57     // Approximation of Gauss error function, Abramowitz and Stegun 7.1.26
58     erf: function(value)
59     {
60           var sign = (value >= 0) ? 1 : -1;
61           value = Math.abs(value);
62
63           var a1 = 0.254829592;
64           var a2 = -0.284496736;
65           var a3 = 1.421413741;
66           var a4 = -1.453152027;
67           var a5 = 1.061405429;
68           var p = 0.3275911;
69
70           var t = 1.0 / (1.0 + p * value);
71           var y = 1.0 - (((((a5 * t + a4) * t) + a3) * t + a2) * t + a1) * t * Math.exp(-value * value);
72           return sign * y;
73     },
74
75     largestDeviationPercentage: function(low, mean, high)
76     {
77         return Math.max(Math.abs(low / mean - 1), (high / mean - 1));
78     }
79 };
80
81 Experiment = Utilities.createClass(
82     function(includeConcern)
83     {
84         if (includeConcern)
85             this._maxHeap = Heap.createMaxHeap(Experiment.defaults.CONCERN_SIZE);
86         this.reset();
87     }, {
88
89     reset: function()
90     {
91         this._sum = 0;
92         this._squareSum = 0;
93         this._numberOfSamples = 0;
94         if (this._maxHeap)
95             this._maxHeap.init();
96     },
97
98     get sampleCount()
99     {
100         return this._numberOfSamples;
101     },
102
103     sample: function(value)
104     {
105         this._sum += value;
106         this._squareSum += value * value;
107         if (this._maxHeap)
108             this._maxHeap.push(value);
109         ++this._numberOfSamples;
110     },
111
112     mean: function()
113     {
114         return Statistics.sampleMean(this._numberOfSamples, this._sum);
115     },
116
117     standardDeviation: function()
118     {
119         return Statistics.unbiasedSampleStandardDeviation(this._numberOfSamples, this._sum, this._squareSum);
120     },
121
122     cdf: function(value)
123     {
124         return Statistics.cdf(value, this.mean(), this.standardDeviation());
125     },
126
127     percentage: function()
128     {
129         var mean = this.mean();
130         return mean ? this.standardDeviation() * 100 / mean : 0;
131     },
132
133     concern: function(percentage)
134     {
135         if (!this._maxHeap)
136             return this.mean();
137
138         var size = Math.ceil(this._numberOfSamples * percentage / 100);
139         var values = this._maxHeap.values(size);
140         return values.length ? values.reduce(function(a, b) { return a + b; }) / values.length : 0;
141     },
142
143     score: function(percentage)
144     {
145         return Statistics.geometricMean([this.mean(), Math.max(this.concern(percentage), 1)]);
146     }
147 });
148
149 Experiment.defaults =
150 {
151     CONCERN: 5,
152     CONCERN_SIZE: 100,
153 };
154
155 Regression = Utilities.createClass(
156     function(samples, getComplexity, getFrameLength, startIndex, endIndex, options)
157     {
158         var desiredFrameLength = options.desiredFrameLength || 1000/60;
159         var bestProfile;
160
161         if (!options.preferredProfile || options.preferredProfile == Strings.json.profiles.slope) {
162             var slope = this._calculateRegression(samples, getComplexity, getFrameLength, startIndex, endIndex, {
163                 shouldClip: true,
164                 s1: desiredFrameLength,
165                 t1: 0
166             });
167             if (!bestProfile || slope.error < bestProfile.error) {
168                 bestProfile = slope;
169                 this.profile = Strings.json.profiles.slope;
170             }
171         }
172         if (!options.preferredProfile || options.preferredProfile == Strings.json.profiles.flat) {
173             var flat = this._calculateRegression(samples, getComplexity, getFrameLength, startIndex, endIndex, {
174                 shouldClip: true,
175                 s1: desiredFrameLength,
176                 t1: 0,
177                 t2: 0
178             });
179
180             if (!bestProfile || flat.error < bestProfile.error) {
181                 bestProfile = flat;
182                 this.profile = Strings.json.profiles.flat;
183             }
184         }
185
186         this.startIndex = Math.min(startIndex, endIndex);
187         this.endIndex = Math.max(startIndex, endIndex);
188
189         this.complexity = bestProfile.complexity;
190         this.s1 = bestProfile.s1;
191         this.t1 = bestProfile.t1;
192         this.s2 = bestProfile.s2;
193         this.t2 = bestProfile.t2;
194         this.stdev1 = bestProfile.stdev1;
195         this.stdev2 = bestProfile.stdev2;
196         this.n1 = bestProfile.n1;
197         this.n2 = bestProfile.n2;
198         this.error = bestProfile.error;
199     }, {
200
201     valueAt: function(complexity)
202     {
203         if (this.n1 == 1 || complexity > this.complexity)
204             return this.s2 + this.t2 * complexity;
205         return this.s1 + this.t1 * complexity;
206     },
207
208     // A generic two-segment piecewise regression calculator. Based on Kundu/Ubhaya
209     //
210     // Minimize sum of (y - y')^2
211     // where                        y = s1 + t1*x
212     //                              y = s2 + t2*x
213     //                y' = s1 + t1*x' = s2 + t2*x'   if x_0 <= x' <= x_n
214     //
215     // Allows for fixing s1, t1, s2, t2
216     //
217     // x is assumed to be complexity, y is frame length. Can be used for pure complexity-FPS
218     // analysis or for ramp controllers since complexity monotonically decreases with time.
219     _calculateRegression: function(samples, getComplexity, getFrameLength, startIndex, endIndex, options)
220     {
221         if (startIndex == endIndex) {
222             // Only one sample point; we can't calculate any regression.
223             var x = getComplexity(samples, startIndex);
224             return {
225                 complexity: x,
226                 s1: x,
227                 t1: 0,
228                 s2: x,
229                 t2: 0,
230                 error1: 0,
231                 error2: 0
232             };
233         }
234
235         // x is expected to increase in complexity
236         var iterationDirection = endIndex > startIndex ? 1 : -1;
237         var lowComplexity = getComplexity(samples, startIndex);
238         var highComplexity = getComplexity(samples, endIndex);
239         var a1 = 0, b1 = 0, c1 = 0, d1 = 0, h1 = 0, k1 = 0;
240         var a2 = 0, b2 = 0, c2 = 0, d2 = 0, h2 = 0, k2 = 0;
241
242         // Iterate from low to high complexity
243         for (var i = startIndex; iterationDirection * (endIndex - i) > -1; i += iterationDirection) {
244             var x = getComplexity(samples, i);
245             var y = getFrameLength(samples, i);
246             a2 += 1;
247             b2 += x;
248             c2 += x * x;
249             d2 += y;
250             h2 += y * x;
251             k2 += y * y;
252         }
253
254         var s1_best, t1_best, s2_best, t2_best, n1_best, n2_best, error1_best, error2_best, x_best, x_prime;
255
256         function setBest(s1, t1, error1, s2, t2, error2, splitIndex, x_prime, x)
257         {
258             s1_best = s1;
259             t1_best = t1;
260             error1_best = error1;
261             s2_best = s2;
262             t2_best = t2;
263             error2_best = error2;
264             // Number of samples included in the first segment, inclusive of splitIndex
265             n1_best = iterationDirection * (splitIndex - startIndex) + 1;
266             // Number of samples included in the second segment
267             n2_best = iterationDirection * (endIndex - splitIndex);
268             if (!options.shouldClip || (x_prime >= lowComplexity && x_prime <= highComplexity))
269                 x_best = x_prime;
270             else {
271                 // Discontinuous piecewise regression
272                 x_best = x;
273             }
274         }
275
276         // Iterate from startIndex to endIndex - 1, inclusive
277         for (var i = startIndex; iterationDirection * (endIndex - i) > 0; i += iterationDirection) {
278             var x = getComplexity(samples, i);
279             var y = getFrameLength(samples, i);
280             var xx = x * x;
281             var yx = y * x;
282             var yy = y * y;
283             // a1, b1, etc. is sum from startIndex to i, inclusive
284             a1 += 1;
285             b1 += x;
286             c1 += xx;
287             d1 += y;
288             h1 += yx;
289             k1 += yy;
290             // a2, b2, etc. is sum from i+1 to endIndex, inclusive
291             a2 -= 1;
292             b2 -= x;
293             c2 -= xx;
294             d2 -= y;
295             h2 -= yx;
296             k2 -= yy;
297
298             var A = c1*d1 - b1*h1;
299             var B = a1*h1 - b1*d1;
300             var C = a1*c1 - b1*b1;
301             var D = c2*d2 - b2*h2;
302             var E = a2*h2 - b2*d2;
303             var F = a2*c2 - b2*b2;
304             var s1 = options.s1 !== undefined ? options.s1 : (A / C);
305             var t1 = options.t1 !== undefined ? options.t1 : (B / C);
306             var s2 = options.s2 !== undefined ? options.s2 : (D / F);
307             var t2 = options.t2 !== undefined ? options.t2 : (E / F);
308             // Assumes that the two segments meet
309             var x_prime = (s1 - s2) / (t2 - t1);
310
311             var error1 = (k1 + a1*s1*s1 + c1*t1*t1 - 2*d1*s1 - 2*h1*t1 + 2*b1*s1*t1) || Number.MAX_VALUE;
312             var error2 = (k2 + a2*s2*s2 + c2*t2*t2 - 2*d2*s2 - 2*h2*t2 + 2*b2*s2*t2) || Number.MAX_VALUE;
313
314             if (i == startIndex) {
315                 setBest(s1, t1, error1, s2, t2, error2, i, x_prime, x);
316                 continue;
317             }
318
319             if (C == 0 || F == 0)
320                 continue;
321
322             // Projected point is not between this and the next sample
323             if (x_prime > getComplexity(samples, i + iterationDirection) || x_prime < x) {
324                 // Calculate lambda, which divides the weight of this sample between the two lines
325
326                 // These values remove the influence of this sample
327                 var I = c1 - 2*b1*x + a1*xx;
328                 var H = C - I;
329                 var G = A + B*x - C*y;
330
331                 var J = D + E*x - F*y;
332                 var K = c2 - 2*b2*x + a2*xx;
333
334                 var lambda = (G*F + G*K - H*J) / (I*J + G*K);
335                 if (lambda > 0 && lambda < 1) {
336                     var lambda1 = 1 - lambda;
337                     s1 = options.s1 !== undefined ? options.s1 : ((A - lambda1*(-h1*x + d1*xx + c1*y - b1*yx)) / (C - lambda1*I));
338                     t1 = options.t1 !== undefined ? options.t1 : ((B - lambda1*(h1 - d1*x - b1*y + a1*yx)) / (C - lambda1*I));
339                     s2 = options.s2 !== undefined ? options.s2 : ((D + lambda1*(-h2*x + d2*xx + c2*y - b2*yx)) / (F + lambda1*K));
340                     t2 = options.t2 !== undefined ? options.t2 : ((E + lambda1*(h2 - d2*x - b2*y + a2*yx)) / (F + lambda1*K));
341                     x_prime = (s1 - s2) / (t2 - t1);
342
343                     error1 = ((k1 + a1*s1*s1 + c1*t1*t1 - 2*d1*s1 - 2*h1*t1 + 2*b1*s1*t1) - lambda1 * Math.pow(y - (s1 + t1*x), 2)) || Number.MAX_VALUE;
344                     error2 = ((k2 + a2*s2*s2 + c2*t2*t2 - 2*d2*s2 - 2*h2*t2 + 2*b2*s2*t2) + lambda1 * Math.pow(y - (s2 + t2*x), 2)) || Number.MAX_VALUE;
345                 } else if (t1 != t2)
346                     continue;
347             }
348
349             if (error1 + error2 < error1_best + error2_best)
350                 setBest(s1, t1, error1, s2, t2, error2, i, x_prime, x);
351         }
352
353         return {
354             complexity: x_best,
355             s1: s1_best,
356             t1: t1_best,
357             stdev1: Math.sqrt(error1_best / n1_best),
358             s2: s2_best,
359             t2: t2_best,
360             stdev2: Math.sqrt(error2_best / n2_best),
361             error: error1_best + error2_best,
362             n1: n1_best,
363             n2: n2_best
364         };
365     }
366 });
367
368 Utilities.extendObject(Regression, {
369     bootstrap: function(samples, iterationCount, processResample, confidencePercentage)
370     {
371         var sampleLength = samples.length;
372         var resample = new Array(sampleLength);
373
374         var bootstrapEstimator = new Experiment;
375         var bootstrapData = new Array(iterationCount);
376
377         Pseudo.resetRandomSeed();
378         for (var i = 0; i < iterationCount; ++i) {
379             for (var j = 0; j < sampleLength; ++j)
380                 resample[j] = samples[Math.floor(Pseudo.random() * sampleLength)];
381
382             var resampleResult = processResample(resample);
383             bootstrapEstimator.sample(resampleResult);
384             bootstrapData[i] = resampleResult;
385         }
386
387         bootstrapData.sort(function(a, b) { return a - b; });
388         return {
389             confidenceLow: bootstrapData[Math.round((iterationCount - 1) * (1 - confidencePercentage) / 2)],
390             confidenceHigh: bootstrapData[Math.round((iterationCount - 1) * (1 + confidencePercentage) / 2)],
391             median: bootstrapData[Math.round(iterationCount / 2)],
392             mean: bootstrapEstimator.mean(),
393             data: bootstrapData,
394             confidencePercentage: confidencePercentage
395         };
396     }
397 });