statistics.js - mozsearch

mozilla-central/third_party/webkit/PerformanceTests/MotionMark/resources/statistics.js (file symbol)

Enable keyboard shortcuts

Source code

File a bug in Firefox Build System :: General

Revision control

Copy as Markdown

Other Tools

Pseudo =

    initialRandomSeed: 49734321,

    randomSeed: 49734321,

    resetRandomSeed: function()

        Pseudo.randomSeed = Pseudo.initialRandomSeed;

},

    random: function()

        var randomSeed = Pseudo.randomSeed;

        randomSeed = ((randomSeed + 0x7ed55d16) + (randomSeed << 12))  & 0xffffffff;

        randomSeed = ((randomSeed ^ 0xc761c23c) ^ (randomSeed >>> 19)) & 0xffffffff;

        randomSeed = ((randomSeed + 0x165667b1) + (randomSeed << 5))   & 0xffffffff;

        randomSeed = ((randomSeed + 0xd3a2646c) ^ (randomSeed << 9))   & 0xffffffff;

        randomSeed = ((randomSeed + 0xfd7046c5) + (randomSeed << 3))   & 0xffffffff;

        randomSeed = ((randomSeed ^ 0xb55a4f09) ^ (randomSeed >>> 16)) & 0xffffffff;

        Pseudo.randomSeed = randomSeed;

        return (randomSeed & 0xfffffff) / 0x10000000;

};

Statistics =

    sampleMean: function(numberOfSamples, sum)

        if (numberOfSamples < 1)

            return 0;

        return sum / numberOfSamples;

},

    // With sum and sum of squares, we can compute the sample standard deviation in O(1).

    // See https://rniwa.com/2012-11-10/sample-standard-deviation-in-terms-of-sum-and-square-sum-of-samples/

    unbiasedSampleStandardDeviation: function(numberOfSamples, sum, squareSum)

        if (numberOfSamples < 2)

            return 0;

        return Math.sqrt((squareSum - sum * sum / numberOfSamples) / (numberOfSamples - 1));

},

    geometricMean: function(values)

        if (!values.length)

            return 0;

        var roots = values.map(function(value) { return Math.pow(value, 1 / values.length); })

        return roots.reduce(function(a, b) { return a * b; });

},

    // Cumulative distribution function

    cdf: function(value, mean, standardDeviation)

        return 0.5 * (1 + Statistics.erf((value - mean) / (Math.sqrt(2 * standardDeviation * standardDeviation))));

},

    // Approximation of Gauss error function, Abramowitz and Stegun 7.1.26

    erf: function(value)

          var sign = (value >= 0) ? 1 : -1;

          value = Math.abs(value);

          var a1 = 0.254829592;

          var a2 = -0.284496736;

          var a3 = 1.421413741;

          var a4 = -1.453152027;

          var a5 = 1.061405429;

          var p = 0.3275911;

          var t = 1.0 / (1.0 + p * value);

          var y = 1.0 - (((((a5 * t + a4) * t) + a3) * t + a2) * t + a1) * t * Math.exp(-value * value);

          return sign * y;

},

    largestDeviationPercentage: function(low, mean, high)

        return Math.max(Math.abs(low / mean - 1), (high / mean - 1));

};

Experiment = Utilities.createClass(

    function(includeConcern)

        if (includeConcern)

            this._maxHeap = Heap.createMaxHeap(Experiment.defaults.CONCERN_SIZE);

        this.reset();

    }, {

    reset: function()

        this._sum = 0;

        this._squareSum = 0;

        this._numberOfSamples = 0;

        if (this._maxHeap)

            this._maxHeap.init();

},

    get sampleCount()

        return this._numberOfSamples;

},

    sample: function(value)

        this._sum += value;

        this._squareSum += value * value;

        if (this._maxHeap)

            this._maxHeap.push(value);

        ++this._numberOfSamples;

},

    mean: function()

        return Statistics.sampleMean(this._numberOfSamples, this._sum);

},

    standardDeviation: function()

        return Statistics.unbiasedSampleStandardDeviation(this._numberOfSamples, this._sum, this._squareSum);

},

    cdf: function(value)

        return Statistics.cdf(value, this.mean(), this.standardDeviation());

},

    percentage: function()

        var mean = this.mean();

        return mean ? this.standardDeviation() * 100 / mean : 0;

},

    concern: function(percentage)

        if (!this._maxHeap)

            return this.mean();

        var size = Math.ceil(this._numberOfSamples * percentage / 100);

        var values = this._maxHeap.values(size);

        return values.length ? values.reduce(function(a, b) { return a + b; }) / values.length : 0;

},

    score: function(percentage)

        return Statistics.geometricMean([this.mean(), Math.max(this.concern(percentage), 1)]);

});

Experiment.defaults =

    CONCERN: 5,

    CONCERN_SIZE: 100,

};

Regression = Utilities.createClass(

    function(samples, getComplexity, getFrameLength, startIndex, endIndex, options)

        var desiredFrameLength = options.desiredFrameLength || 1000/60;

        var bestProfile;

        if (!options.preferredProfile || options.preferredProfile == Strings.json.profiles.slope) {

            var slope = this._calculateRegression(samples, getComplexity, getFrameLength, startIndex, endIndex, {

                shouldClip: true,

                s1: desiredFrameLength,

                t1: 0

});

            if (!bestProfile || slope.error < bestProfile.error) {

                bestProfile = slope;

                this.profile = Strings.json.profiles.slope;

        if (!options.preferredProfile || options.preferredProfile == Strings.json.profiles.flat) {

            var flat = this._calculateRegression(samples, getComplexity, getFrameLength, startIndex, endIndex, {

                shouldClip: true,

                s1: desiredFrameLength,

                t1: 0,

                t2: 0

});

            if (!bestProfile || flat.error < bestProfile.error) {

                bestProfile = flat;

                this.profile = Strings.json.profiles.flat;

        this.startIndex = Math.min(startIndex, endIndex);

        this.endIndex = Math.max(startIndex, endIndex);

        this.complexity = bestProfile.complexity;

        this.s1 = bestProfile.s1;

        this.t1 = bestProfile.t1;

        this.s2 = bestProfile.s2;

        this.t2 = bestProfile.t2;

        this.stdev1 = bestProfile.stdev1;

        this.stdev2 = bestProfile.stdev2;

        this.n1 = bestProfile.n1;

        this.n2 = bestProfile.n2;

        this.error = bestProfile.error;

    }, {

    valueAt: function(complexity)

        if (this.n1 == 1 || complexity > this.complexity)

            return this.s2 + this.t2 * complexity;

        return this.s1 + this.t1 * complexity;

},

    // A generic two-segment piecewise regression calculator. Based on Kundu/Ubhaya

//

    // Minimize sum of (y - y')^2

    // where                        y = s1 + t1*x

    //                              y = s2 + t2*x

    //                y' = s1 + t1*x' = s2 + t2*x'   if x_0 <= x' <= x_n

//

    // Allows for fixing s1, t1, s2, t2

//

    // x is assumed to be complexity, y is frame length. Can be used for pure complexity-FPS

    // analysis or for ramp controllers since complexity monotonically decreases with time.

    _calculateRegression: function(samples, getComplexity, getFrameLength, startIndex, endIndex, options)

        if (startIndex == endIndex) {

            // Only one sample point; we can't calculate any regression.

            var x = getComplexity(samples, startIndex);

            return {

                complexity: x,

                s1: x,

                t1: 0,

                s2: x,

                t2: 0,

                error1: 0,

                error2: 0

};

        // x is expected to increase in complexity

        var iterationDirection = endIndex > startIndex ? 1 : -1;

        var lowComplexity = getComplexity(samples, startIndex);

        var highComplexity = getComplexity(samples, endIndex);

        var a1 = 0, b1 = 0, c1 = 0, d1 = 0, h1 = 0, k1 = 0;

        var a2 = 0, b2 = 0, c2 = 0, d2 = 0, h2 = 0, k2 = 0;

        // Iterate from low to high complexity

        for (var i = startIndex; iterationDirection * (endIndex - i) > -1; i += iterationDirection) {

            var x = getComplexity(samples, i);

            var y = getFrameLength(samples, i);

            a2 += 1;

            b2 += x;

            c2 += x * x;

            d2 += y;

            h2 += y * x;

            k2 += y * y;

        var s1_best, t1_best, s2_best, t2_best, n1_best, n2_best, error1_best, error2_best, x_best, x_prime;

        function setBest(s1, t1, error1, s2, t2, error2, splitIndex, x_prime, x)

            s1_best = s1;

            t1_best = t1;

            error1_best = error1;

            s2_best = s2;

            t2_best = t2;

            error2_best = error2;

            // Number of samples included in the first segment, inclusive of splitIndex

            n1_best = iterationDirection * (splitIndex - startIndex) + 1;

            // Number of samples included in the second segment

            n2_best = iterationDirection * (endIndex - splitIndex);

            if (!options.shouldClip || (x_prime >= lowComplexity && x_prime <= highComplexity))

                x_best = x_prime;

            else {

                // Discontinuous piecewise regression

                x_best = x;

        // Iterate from startIndex to endIndex - 1, inclusive

        for (var i = startIndex; iterationDirection * (endIndex - i) > 0; i += iterationDirection) {

            var x = getComplexity(samples, i);

            var y = getFrameLength(samples, i);

            var xx = x * x;

            var yx = y * x;

            var yy = y * y;

            // a1, b1, etc. is sum from startIndex to i, inclusive

            a1 += 1;

            b1 += x;

            c1 += xx;

            d1 += y;

            h1 += yx;

            k1 += yy;

            // a2, b2, etc. is sum from i+1 to endIndex, inclusive

            a2 -= 1;

            b2 -= x;

            c2 -= xx;

            d2 -= y;

            h2 -= yx;

            k2 -= yy;

            var A = c1*d1 - b1*h1;

            var B = a1*h1 - b1*d1;

            var C = a1*c1 - b1*b1;

            var D = c2*d2 - b2*h2;

            var E = a2*h2 - b2*d2;

            var F = a2*c2 - b2*b2;

            var s1 = options.s1 !== undefined ? options.s1 : (A / C);

            var t1 = options.t1 !== undefined ? options.t1 : (B / C);

            var s2 = options.s2 !== undefined ? options.s2 : (D / F);

            var t2 = options.t2 !== undefined ? options.t2 : (E / F);

            // Assumes that the two segments meet

            var x_prime = (s1 - s2) / (t2 - t1);

            var error1 = (k1 + a1*s1*s1 + c1*t1*t1 - 2*d1*s1 - 2*h1*t1 + 2*b1*s1*t1) || Number.MAX_VALUE;

            var error2 = (k2 + a2*s2*s2 + c2*t2*t2 - 2*d2*s2 - 2*h2*t2 + 2*b2*s2*t2) || Number.MAX_VALUE;

            if (i == startIndex) {

                setBest(s1, t1, error1, s2, t2, error2, i, x_prime, x);

                continue;

            if (C == 0 || F == 0)

                continue;

            // Projected point is not between this and the next sample

            if (x_prime > getComplexity(samples, i + iterationDirection) || x_prime < x) {

                // Calculate lambda, which divides the weight of this sample between the two lines

                // These values remove the influence of this sample

                var I = c1 - 2*b1*x + a1*xx;

                var H = C - I;

                var G = A + B*x - C*y;

                var J = D + E*x - F*y;

                var K = c2 - 2*b2*x + a2*xx;

                var lambda = (G*F + G*K - H*J) / (I*J + G*K);

                if (lambda > 0 && lambda < 1) {

                    var lambda1 = 1 - lambda;

                    s1 = options.s1 !== undefined ? options.s1 : ((A - lambda1*(-h1*x + d1*xx + c1*y - b1*yx)) / (C - lambda1*I));

                    t1 = options.t1 !== undefined ? options.t1 : ((B - lambda1*(h1 - d1*x - b1*y + a1*yx)) / (C - lambda1*I));

                    s2 = options.s2 !== undefined ? options.s2 : ((D + lambda1*(-h2*x + d2*xx + c2*y - b2*yx)) / (F + lambda1*K));

                    t2 = options.t2 !== undefined ? options.t2 : ((E + lambda1*(h2 - d2*x - b2*y + a2*yx)) / (F + lambda1*K));

                    x_prime = (s1 - s2) / (t2 - t1);

                    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;

                    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;

                } else if (t1 != t2)

                    continue;

            if (error1 + error2 < error1_best + error2_best)

                setBest(s1, t1, error1, s2, t2, error2, i, x_prime, x);

        return {

            complexity: x_best,

            s1: s1_best,

            t1: t1_best,

            stdev1: Math.sqrt(error1_best / n1_best),

            s2: s2_best,

            t2: t2_best,

            stdev2: Math.sqrt(error2_best / n2_best),

            error: error1_best + error2_best,

            n1: n1_best,

            n2: n2_best

};

});

Utilities.extendObject(Regression, {

    bootstrap: function(samples, iterationCount, processResample, confidencePercentage)

        var sampleLength = samples.length;

        var resample = new Array(sampleLength);

        var bootstrapEstimator = new Experiment;

        var bootstrapData = new Array(iterationCount);

        Pseudo.resetRandomSeed();

        for (var i = 0; i < iterationCount; ++i) {

            for (var j = 0; j < sampleLength; ++j)

                resample[j] = samples[Math.floor(Pseudo.random() * sampleLength)];

            var resampleResult = processResample(resample);

            bootstrapEstimator.sample(resampleResult);

            bootstrapData[i] = resampleResult;

        bootstrapData.sort(function(a, b) { return a - b; });

        return {

            confidenceLow: bootstrapData[Math.round((iterationCount - 1) * (1 - confidencePercentage) / 2)],

            confidenceHigh: bootstrapData[Math.round((iterationCount - 1) * (1 + confidencePercentage) / 2)],

            median: bootstrapData[Math.round(iterationCount / 2)],

            mean: bootstrapEstimator.mean(),

            data: bootstrapData,

            confidencePercentage: confidencePercentage

};

});