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 });