Make JetStream 2
[WebKit-https.git] / PerformanceTests / JetStream2 / worker / async-task.js
1 /*
2  * Copyright (C) 2018 Apple 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
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 var Statistics = new (function () {
27
28     this.min = function (values) {
29         return Math.min.apply(Math, values);
30     }
31
32     this.max = function (values) {
33         return Math.max.apply(Math, values);
34     }
35
36     this.sum = function (values) {
37         return values.length ? values.reduce(function (a, b) { return a + b; }) : 0;
38     }
39
40     this.mean = function (values) {
41         return this.sum(values) / values.length;
42     }
43
44     this.median = function (values) {
45         return values.sort(function (a, b) { return a - b; })[Math.floor(values.length / 2)];
46     }
47
48     this.squareSum = function (values) {
49         return values.length ? values.reduce(function (sum, value) { return sum + value * value;}, 0) : 0;
50     }
51
52     // With sum and sum of squares, we can compute the sample standard deviation in O(1).
53     // See https://rniwa.com/2012-11-10/sample-standard-deviation-in-terms-of-sum-and-square-sum-of-samples/
54     this.sampleStandardDeviation = function (numberOfSamples, sum, squareSum) {
55         if (numberOfSamples < 2)
56             return 0;
57         return Math.sqrt(squareSum / (numberOfSamples - 1) - sum * sum / (numberOfSamples - 1) / numberOfSamples);
58     }
59
60     this.supportedConfidenceIntervalProbabilities = function () {
61         var supportedProbabilities = [];
62         for (var probability in tDistributionByOneSidedProbability)
63             supportedProbabilities.push(oneSidedToTwoSidedProbability(probability).toFixed(2));
64         return supportedProbabilities
65     }
66
67     this.supportedOneSideTTestProbabilities = function () {
68         return Object.keys(tDistributionByOneSidedProbability);
69     }
70
71     // Computes the delta d s.t. (mean - d, mean + d) is the confidence interval with the specified probability in O(1).
72     this.confidenceIntervalDelta = function (probability, numberOfSamples, sum, squareSum) {
73         var oneSidedProbability = twoSidedToOneSidedProbability(probability);
74         if (!(oneSidedProbability in tDistributionByOneSidedProbability)) {
75             throw 'We only support ' + this.supportedConfidenceIntervalProbabilities().map(function (probability)
76             { return probability * 100 + '%'; } ).join(', ') + ' confidence intervals.';
77         }
78         if (numberOfSamples - 2 < 0)
79             return NaN;
80         var deltas = tDistributionByOneSidedProbability[oneSidedProbability];
81         var degreesOfFreedom = numberOfSamples - 1;
82         if (degreesOfFreedom > deltas.length)
83             throw 'We only support up to ' + deltas.length + ' degrees of freedom';
84
85         // d = c * S/sqrt(numberOfSamples) where c ~ t-distribution(degreesOfFreedom) and S is the sample standard deviation.
86         return deltas[degreesOfFreedom - 1] * this.sampleStandardDeviation(numberOfSamples, sum, squareSum) / Math.sqrt(numberOfSamples);
87     }
88
89     this.confidenceInterval = function (values, probability) {
90         var sum = this.sum(values);
91         var mean = sum / values.length;
92         var delta = this.confidenceIntervalDelta(probability || 0.95, values.length, sum, this.squareSum(values));
93         return [mean - delta, mean + delta];
94     }
95
96     // Welch's t-test (http://en.wikipedia.org/wiki/Welch%27s_t_test)
97     this.testWelchsT = function (values1, values2, probability) {
98         return this.computeWelchsT(values1, 0, values1.length, values2, 0, values2.length, probability).significantlyDifferent;
99     }
100
101     this.probabilityRangeForWelchsT = function (values1, values2) {
102         var result = this.computeWelchsT(values1, 0, values1.length, values2, 0, values2.length);
103         if (isNaN(result.t) || isNaN(result.degreesOfFreedom))
104             return {t: NaN, degreesOfFreedom:NaN, range: [null, null]};
105
106         var lowerBound = null;
107         var upperBound = null;
108         for (var probability in tDistributionByOneSidedProbability) {
109             var twoSidedProbability = oneSidedToTwoSidedProbability(probability);
110             if (result.t > tDistributionByOneSidedProbability[probability][Math.round(result.degreesOfFreedom - 1)])
111                 lowerBound = twoSidedProbability;
112             else if (lowerBound) {
113                 upperBound = twoSidedProbability;
114                 break;
115             }
116         }
117         return {t: result.t, degreesOfFreedom: result.degreesOfFreedom, range: [lowerBound, upperBound]};
118     }
119
120     this.computeWelchsT = function (values1, startIndex1, length1, values2, startIndex2, length2, probability) {
121         var stat1 = sampleMeanAndVarianceForValues(values1, startIndex1, length1);
122         var stat2 = sampleMeanAndVarianceForValues(values2, startIndex2, length2);
123         var sumOfSampleVarianceOverSampleSize = stat1.variance / stat1.size + stat2.variance / stat2.size;
124         var t = Math.abs((stat1.mean - stat2.mean) / Math.sqrt(sumOfSampleVarianceOverSampleSize));
125
126         // http://en.wikipedia.org/wiki/Welch–Satterthwaite_equation
127         var degreesOfFreedom = sumOfSampleVarianceOverSampleSize * sumOfSampleVarianceOverSampleSize
128             / (stat1.variance * stat1.variance / stat1.size / stat1.size / stat1.degreesOfFreedom
129                 + stat2.variance * stat2.variance / stat2.size / stat2.size / stat2.degreesOfFreedom);
130         var minT = tDistributionByOneSidedProbability[twoSidedToOneSidedProbability(probability || 0.8)][Math.round(degreesOfFreedom - 1)];
131         return {
132             t: t,
133             degreesOfFreedom: degreesOfFreedom,
134             significantlyDifferent: t > minT,
135         };
136     }
137
138     this.findRangesForChangeDetectionsWithWelchsTTest = function (values, segmentations, oneSidedPossibility=0.99) {
139         if (!values.length)
140             return [];
141
142         const selectedRanges = [];
143         const twoSidedFromOneSidedPossibility = 2 * oneSidedPossibility - 1;
144
145         for (let i = 1; i + 2 < segmentations.length; i += 2) {
146             let found = false;
147             const previousMean = segmentations[i].value;
148             const currentMean = segmentations[i + 1].value;
149             console.assert(currentMean != previousMean);
150             const currentChangePoint = segmentations[i].seriesIndex;
151             const start = segmentations[i - 1].seriesIndex;
152             const end = segmentations[i + 2].seriesIndex;
153
154             for (let leftEdge = currentChangePoint - 2, rightEdge = currentChangePoint + 2; leftEdge >= start && rightEdge <= end; leftEdge--, rightEdge++) {
155                 const result = this.computeWelchsT(values, leftEdge, currentChangePoint - leftEdge, values, currentChangePoint, rightEdge - currentChangePoint, twoSidedFromOneSidedPossibility);
156                 if (result.significantlyDifferent) {
157                     selectedRanges.push({
158                         startIndex: leftEdge,
159                         endIndex: rightEdge - 1,
160                         segmentationStartValue: previousMean,
161                         segmentationEndValue: currentMean
162                     });
163                     found = true;
164                     break;
165                 }
166             }
167             if (!found && Statistics.debuggingTestingRangeNomination)
168                 console.log('Failed to find a testing range at', currentChangePoint, 'changing from', previousMean, 'to', currentMean);
169         }
170
171         return selectedRanges;
172     };
173
174     function sampleMeanAndVarianceForValues(values, startIndex, length) {
175         var sum = 0;
176         for (var i = 0; i < length; i++)
177             sum += values[startIndex + i];
178         var squareSum = 0;
179         for (var i = 0; i < length; i++)
180             squareSum += values[startIndex + i] * values[startIndex + i];
181         var sampleMean = sum / length;
182         // FIXME: Maybe we should be using the biased sample variance.
183         var unbiasedSampleVariance = (squareSum - sum * sum / length) / (length - 1);
184         return {
185             mean: sampleMean,
186             variance: unbiasedSampleVariance,
187             size: length,
188             degreesOfFreedom: length - 1,
189         }
190     }
191
192     this.movingAverage = function (values, backwardWindowSize, forwardWindowSize) {
193         var averages = new Array(values.length);
194         // We use naive O(n^2) algorithm for simplicy as well as to avoid accumulating round-off errors.
195         for (var i = 0; i < values.length; i++) {
196             var sum = 0;
197             var count = 0;
198             for (var j = i - backwardWindowSize; j <= i + forwardWindowSize; j++) {
199                 if (j >= 0 && j < values.length) {
200                     sum += values[j];
201                     count++;
202                 }
203             }
204             averages[i] = sum / count;
205         }
206         return averages;
207     }
208
209     this.cumulativeMovingAverage = function (values) {
210         var averages = new Array(values.length);
211         var sum = 0;
212         for (var i = 0; i < values.length; i++) {
213             sum += values[i];
214             averages[i] = sum / (i + 1);
215         }
216         return averages;
217     }
218
219     this.exponentialMovingAverage = function (values, smoothingFactor) {
220         var averages = new Array(values.length);
221         var movingAverage = values[0];
222         averages[0] = movingAverage;
223         for (var i = 1; i < values.length; i++) {
224             movingAverage = smoothingFactor * values[i] + (1 - smoothingFactor) * movingAverage;
225             averages[i] = movingAverage;
226         }
227         return averages;
228     }
229
230     // The return value is the starting indices of each segment.
231     this.segmentTimeSeriesGreedyWithStudentsTTest = function (values, minLength) {
232         if (values.length < 2)
233             return [0];
234         var segments = new Array;
235         recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent(values, 0, values.length, minLength, segments);
236         segments.push(values.length);
237         return segments;
238     }
239
240     this.debuggingSegmentation = false;
241     this.segmentTimeSeriesByMaximizingSchwarzCriterion = function (values, segmentCountWeight, gridSize) {
242         // Split the time series into grids since splitIntoSegmentsUntilGoodEnough is O(n^2).
243         var gridLength = gridSize || 500;
244         var totalSegmentation = [0];
245         for (var gridCount = 0; gridCount < Math.ceil(values.length / gridLength); gridCount++) {
246             var gridValues = values.slice(gridCount * gridLength, (gridCount + 1) * gridLength);
247             var segmentation = splitIntoSegmentsUntilGoodEnough(gridValues, segmentCountWeight);
248
249             if (Statistics.debuggingSegmentation)
250                 console.log('grid=' + gridCount, segmentation);
251
252             for (var i = 1; i < segmentation.length - 1; i++)
253                 totalSegmentation.push(gridCount * gridLength + segmentation[i]);
254         }
255
256         if (Statistics.debuggingSegmentation)
257             console.log('Final Segmentation', totalSegmentation);
258
259         totalSegmentation.push(values.length);
260
261         return totalSegmentation;
262     }
263
264     function recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent(values, startIndex, length, minLength, segments) {
265         var tMax = 0;
266         var argTMax = null;
267         for (var i = 1; i < length - 1; i++) {
268             var firstLength = i;
269             var secondLength = length - i;
270             if (firstLength < minLength || secondLength < minLength)
271                 continue;
272             var result = Statistics.computeWelchsT(values, startIndex, firstLength, values, startIndex + i, secondLength, 0.9);
273             if (result.significantlyDifferent && result.t > tMax) {
274                 tMax = result.t;
275                 argTMax = i;
276             }
277         }
278         if (!tMax) {
279             segments.push(startIndex);
280             return;
281         }
282         recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent(values, startIndex, argTMax, minLength, segments);
283         recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent(values, startIndex + argTMax, length - argTMax, minLength, segments);
284     }
285
286     var tDistributionByOneSidedProbability = {
287         0.9: [
288             3.077684, 1.885618, 1.637744, 1.533206, 1.475884, 1.439756, 1.414924, 1.396815, 1.383029, 1.372184,
289             1.363430, 1.356217, 1.350171, 1.345030, 1.340606, 1.336757, 1.333379, 1.330391, 1.327728, 1.325341,
290             1.323188, 1.321237, 1.319460, 1.317836, 1.316345, 1.314972, 1.313703, 1.312527, 1.311434, 1.310415,
291             1.309464, 1.308573, 1.307737, 1.306952, 1.306212, 1.305514, 1.304854, 1.304230, 1.303639, 1.303077,
292             1.302543, 1.302035, 1.301552, 1.301090, 1.300649, 1.300228, 1.299825, 1.299439, 1.299069, 1.298714,
293
294             1.298373, 1.298045, 1.297730, 1.297426, 1.297134, 1.296853, 1.296581, 1.296319, 1.296066, 1.295821,
295             1.295585, 1.295356, 1.295134, 1.294920, 1.294712, 1.294511, 1.294315, 1.294126, 1.293942, 1.293763,
296             1.293589, 1.293421, 1.293256, 1.293097, 1.292941, 1.292790, 1.292643, 1.292500, 1.292360, 1.292224,
297             1.292091, 1.291961, 1.291835, 1.291711, 1.291591, 1.291473, 1.291358, 1.291246, 1.291136, 1.291029,
298             1.290924, 1.290821, 1.290721, 1.290623, 1.290527, 1.290432, 1.290340, 1.290250, 1.290161, 1.290075],
299         0.95: [
300             6.313752, 2.919986, 2.353363, 2.131847, 2.015048, 1.943180, 1.894579, 1.859548, 1.833113, 1.812461,
301             1.795885, 1.782288, 1.770933, 1.761310, 1.753050, 1.745884, 1.739607, 1.734064, 1.729133, 1.724718,
302             1.720743, 1.717144, 1.713872, 1.710882, 1.708141, 1.705618, 1.703288, 1.701131, 1.699127, 1.697261,
303             1.695519, 1.693889, 1.692360, 1.690924, 1.689572, 1.688298, 1.687094, 1.685954, 1.684875, 1.683851,
304             1.682878, 1.681952, 1.681071, 1.680230, 1.679427, 1.678660, 1.677927, 1.677224, 1.676551, 1.675905,
305
306             1.675285, 1.674689, 1.674116, 1.673565, 1.673034, 1.672522, 1.672029, 1.671553, 1.671093, 1.670649,
307             1.670219, 1.669804, 1.669402, 1.669013, 1.668636, 1.668271, 1.667916, 1.667572, 1.667239, 1.666914,
308             1.666600, 1.666294, 1.665996, 1.665707, 1.665425, 1.665151, 1.664885, 1.664625, 1.664371, 1.664125,
309             1.663884, 1.663649, 1.663420, 1.663197, 1.662978, 1.662765, 1.662557, 1.662354, 1.662155, 1.661961,
310             1.661771, 1.661585, 1.661404, 1.661226, 1.661052, 1.660881, 1.660715, 1.660551, 1.660391, 1.660234],
311         0.975: [
312             12.706205, 4.302653, 3.182446, 2.776445, 2.570582, 2.446912, 2.364624, 2.306004, 2.262157, 2.228139,
313             2.200985, 2.178813, 2.160369, 2.144787, 2.131450, 2.119905, 2.109816, 2.100922, 2.093024, 2.085963,
314             2.079614, 2.073873, 2.068658, 2.063899, 2.059539, 2.055529, 2.051831, 2.048407, 2.045230, 2.042272,
315             2.039513, 2.036933, 2.034515, 2.032245, 2.030108, 2.028094, 2.026192, 2.024394, 2.022691, 2.021075,
316             2.019541, 2.018082, 2.016692, 2.015368, 2.014103, 2.012896, 2.011741, 2.010635, 2.009575, 2.008559,
317
318             2.007584, 2.006647, 2.005746, 2.004879, 2.004045, 2.003241, 2.002465, 2.001717, 2.000995, 2.000298,
319             1.999624, 1.998972, 1.998341, 1.997730, 1.997138, 1.996564, 1.996008, 1.995469, 1.994945, 1.994437,
320             1.993943, 1.993464, 1.992997, 1.992543, 1.992102, 1.991673, 1.991254, 1.990847, 1.990450, 1.990063,
321             1.989686, 1.989319, 1.988960, 1.988610, 1.988268, 1.987934, 1.987608, 1.987290, 1.986979, 1.986675,
322             1.986377, 1.986086, 1.985802, 1.985523, 1.985251, 1.984984, 1.984723, 1.984467, 1.984217, 1.983972],
323         0.99: [
324             31.820516, 6.964557, 4.540703, 3.746947, 3.364930, 3.142668, 2.997952, 2.896459, 2.821438, 2.763769,
325             2.718079, 2.680998, 2.650309, 2.624494, 2.602480, 2.583487, 2.566934, 2.552380, 2.539483, 2.527977,
326             2.517648, 2.508325, 2.499867, 2.492159, 2.485107, 2.478630, 2.472660, 2.467140, 2.462021, 2.457262,
327             2.452824, 2.448678, 2.444794, 2.441150, 2.437723, 2.434494, 2.431447, 2.428568, 2.425841, 2.423257,
328             2.420803, 2.418470, 2.416250, 2.414134, 2.412116, 2.410188, 2.408345, 2.406581, 2.404892, 2.403272,
329
330             2.401718, 2.400225, 2.398790, 2.397410, 2.396081, 2.394801, 2.393568, 2.392377, 2.391229, 2.390119,
331             2.389047, 2.388011, 2.387008, 2.386037, 2.385097, 2.384186, 2.383302, 2.382446, 2.381615, 2.380807,
332             2.380024, 2.379262, 2.378522, 2.377802, 2.377102, 2.376420, 2.375757, 2.375111, 2.374482, 2.373868,
333             2.373270, 2.372687, 2.372119, 2.371564, 2.371022, 2.370493, 2.369977, 2.369472, 2.368979, 2.368497,
334             2.368026, 2.367566, 2.367115, 2.366674, 2.366243, 2.365821, 2.365407, 2.365002, 2.364606, 2.364217]
335     };
336     function oneSidedToTwoSidedProbability(probability) { return 2 * probability - 1; }
337     function twoSidedToOneSidedProbability(probability) { return (1 - (1 - probability) / 2); }
338
339     function splitIntoSegmentsUntilGoodEnough(values, BirgeAndMassartC) {
340         if (values.length < 2)
341             return [0, values.length];
342
343         var matrix = new SampleVarianceUpperTriangularMatrix(values);
344
345         var SchwarzCriterionBeta = Math.log1p(values.length - 1) / values.length;
346
347         BirgeAndMassartC = BirgeAndMassartC || 2.5; // Suggested by the authors.
348         var BirgeAndMassartPenalization = function (segmentCount) {
349             return segmentCount * (1 + BirgeAndMassartC * Math.log1p(values.length / segmentCount - 1));
350         }
351
352         var segmentation;
353         var minTotalCost = Infinity;
354         var maxK = Math.min(50, values.length);
355
356         for (var k = 1; k < maxK; k++) {
357             var start = Date.now();
358             var result = findOptimalSegmentation(values, matrix, k);
359             var cost = result.cost / values.length;
360             var penalty = SchwarzCriterionBeta * BirgeAndMassartPenalization(k);
361             if (cost + penalty < minTotalCost) {
362                 minTotalCost = cost + penalty;
363                 segmentation = result.segmentation;
364             } else
365                 maxK = Math.min(maxK, k + 3);
366             if (Statistics.debuggingSegmentation)
367                 console.log('splitIntoSegmentsUntilGoodEnough', k, Date.now() - start, cost + penalty);
368         }
369
370         return segmentation;
371     }
372
373     function allocateCostUpperTriangularForSegmentation(values, segmentCount)
374     {
375         // Dynamic programming. cost[i][k] = The cost to segmenting values up to i into k segments.
376         var cost = new Array(values.length);
377         for (var segmentEnd = 0; segmentEnd < values.length; segmentEnd++)
378             cost[segmentEnd] = new Float32Array(segmentCount + 1);
379         return cost;
380     }
381
382     function allocatePreviousNodeForSegmentation(values, segmentCount)
383     {
384         // previousNode[i][k] = The start of the last segment in an optimal segmentation that ends at i with k segments.
385         var previousNode = new Array(values.length);
386         for (var i = 0; i < values.length; i++)
387             previousNode[i] = new Array(segmentCount + 1);
388         return previousNode;
389     }
390
391     function findOptimalSegmentationInternal(cost, previousNode, values, costMatrix, segmentCount)
392     {
393         cost[0] = [0]; // The cost of segmenting single value is always 0.
394         previousNode[0] = [-1];
395         for (var segmentStart = 0; segmentStart < values.length; segmentStart++) {
396             var costOfOptimalSegmentationThatEndAtCurrentStart = cost[segmentStart];
397             for (var k = 0; k < segmentCount; k++) {
398                 var noSegmentationOfLenghtKEndsAtCurrentStart = previousNode[segmentStart][k] === undefined;
399                 if (noSegmentationOfLenghtKEndsAtCurrentStart)
400                     continue;
401                 for (var segmentEnd = segmentStart + 1; segmentEnd < values.length; segmentEnd++) {
402                     var costOfOptimalSegmentationOfLengthK = costOfOptimalSegmentationThatEndAtCurrentStart[k];
403                     var costOfCurrentSegment = costMatrix.costBetween(segmentStart, segmentEnd);
404                     var totalCost = costOfOptimalSegmentationOfLengthK + costOfCurrentSegment;
405                     if (previousNode[segmentEnd][k + 1] === undefined || totalCost < cost[segmentEnd][k + 1]) {
406                         cost[segmentEnd][k + 1] = totalCost;
407                         previousNode[segmentEnd][k + 1] = segmentStart;
408                     }
409                 }
410             }
411         }
412     }
413
414     function findOptimalSegmentation(values, costMatrix, segmentCount) {
415         var cost = allocateCostUpperTriangularForSegmentation(values, segmentCount);
416         var previousNode = allocatePreviousNodeForSegmentation(values, segmentCount);
417
418         findOptimalSegmentationInternal(cost, previousNode, values, costMatrix, segmentCount);
419
420         if (Statistics.debuggingSegmentation) {
421             console.log('findOptimalSegmentation with', segmentCount, 'segments');
422             for (var end = 0; end < values.length; end++) {
423                 for (var k = 0; k <= segmentCount; k++) {
424                     var start = previousNode[end][k];
425                     if (start === undefined)
426                         continue;
427                     console.log(`C(segment=[${start}, ${end + 1}], segmentCount=${k})=${cost[end][k]}`);
428                 }
429             }
430         }
431
432         var segmentEnd = values.length - 1;
433         var segmentation = new Array(segmentCount + 1);
434         segmentation[segmentCount] = values.length;
435         for (var k = segmentCount; k > 0; k--) {
436             segmentEnd = previousNode[segmentEnd][k];
437             segmentation[k - 1] = segmentEnd;
438         }
439         var costOfOptimalSegmentation = cost[values.length - 1][segmentCount];
440
441         if (Statistics.debuggingSegmentation)
442             console.log('Optimal segmentation:', segmentation, 'with cost =', costOfOptimalSegmentation);
443
444         return {segmentation: segmentation, cost: costOfOptimalSegmentation};
445     }
446
447     function SampleVarianceUpperTriangularMatrix(values) {
448         // The cost of segment (i, j].
449         var costMatrix = new Array(values.length - 1);
450         for (var i = 0; i < values.length - 1; i++) {
451             var remainingValueCount = values.length - i - 1;
452             costMatrix[i] = new Float32Array(remainingValueCount);
453             var sum = values[i];
454             var squareSum = sum * sum;
455             costMatrix[i][0] = 0;
456             for (var j = i + 1; j < values.length; j++) {
457                 var currentValue = values[j];
458                 sum += currentValue;
459                 squareSum += currentValue * currentValue;
460                 var sampleSize = j - i + 1;
461                 var stdev = Statistics.sampleStandardDeviation(sampleSize, sum, squareSum);
462                 costMatrix[i][j - i - 1] = stdev > 0 ? sampleSize * Math.log(stdev * stdev) : 0;
463             }
464         }
465         this.costMatrix = costMatrix;
466     }
467
468     SampleVarianceUpperTriangularMatrix.prototype.costBetween = function(from, to) {
469         if (from >= this.costMatrix.length || from == to)
470             return 0; // The cost of the segment that starts at the last data point is 0.
471         return this.costMatrix[from][to - from - 1];
472     }
473
474 })();
475
476 if (typeof module != 'undefined')
477     module.exports = Statistics;
478
479 class AsyncTask {
480
481     constructor(method, args)
482     {
483         this._method = method;
484         this._args = args;
485     }
486
487     execute()
488     {
489         if (!(this._method in Statistics))
490             throw `${this._method} is not a valid method of Statistics`;
491
492         AsyncTask._asyncMessageId++;
493
494         var startTime = Date.now();
495         var method = this._method;
496         var args = this._args;
497         return new Promise(function (resolve, reject) {
498             AsyncTaskWorker.waitForAvailableWorker(function (worker) {
499                 worker.sendTask({id: AsyncTask._asyncMessageId, method: method, args: args}).then(function (data) {
500                     var startLatency = data.workerStartTime - startTime;
501                     var totalTime = Date.now() - startTime;
502                     var callback = data.status == 'resolve' ? resolve : reject;
503                     callback({result: data.result, workerId: worker.id(), startLatency: startLatency, totalTime: totalTime, workerTime: data.workerTime});
504                 });
505             });
506         });
507     }
508
509     static isAvailable()
510     {
511         return typeof Worker !== 'undefined';
512     }
513 }
514
515 AsyncTask._asyncMessageId = 0;
516
517 class AsyncTaskWorker {
518
519     // Takes a callback instead of returning a promise because a worker can become unavailable before the end of the current microtask.
520     static waitForAvailableWorker(callback)
521     {
522         var worker = this._makeWorkerEventuallyAvailable();
523         if (worker)
524             callback(worker);
525         this._queue.push(callback);
526     }
527
528     static _makeWorkerEventuallyAvailable()
529     {
530         var worker = this._findAvailableWorker();
531         if (worker)
532             return worker;
533
534         var canStartMoreWorker = this._workerSet.size < this._maxWorkerCount;
535         if (!canStartMoreWorker)
536             return null;
537
538         if (this._latestStartTime > Date.now() - 50) {
539             setTimeout(function () {
540                 var worker = AsyncTaskWorker._findAvailableWorker();
541                 if (worker)
542                     AsyncTaskWorker._queue.pop()(worker);
543             }, 50);
544             return null;
545         }
546         return new AsyncTaskWorker;
547     }
548
549     static _findAvailableWorker()
550     {
551         for (var worker of this._workerSet) {
552             if (!worker._currentTaskId)
553                 return worker;
554         }
555         return null;
556     }
557
558     constructor()
559     {
560         this._webWorker = new Worker('async-task.js');
561         this._webWorker.onmessage = this._didRecieveMessage.bind(this);
562         this._id = AsyncTaskWorker._workerId;
563         this._startTime = Date.now();
564         this._currentTaskId = null;
565         this._callback = null;
566
567         AsyncTaskWorker._latestStartTime = this._startTime;
568         AsyncTaskWorker._workerId++;
569         AsyncTaskWorker._workerSet.add(this);
570     }
571
572     id() { return this._id; }
573
574     sendTask(task)
575     {
576         console.assert(!this._currentTaskId);
577         console.assert(task.id);
578         var self = this;
579         this._currentTaskId = task.id;
580         return new Promise(function (resolve) {
581             self._webWorker.postMessage(task);
582             self._callback = resolve;
583         });
584     }
585
586     _didRecieveMessage(event)
587     {
588         var callback = this._callback;
589
590         console.assert(this._currentTaskId);
591         this._currentTaskId = null;
592         this._callback = null;
593
594         if (AsyncTaskWorker._queue.length)
595             AsyncTaskWorker._queue.pop()(this);
596         else {
597             var self = this;
598             setTimeout(function () {
599                 if (self._currentTaskId == null)
600                     AsyncTaskWorker._workerSet.delete(self);
601             }, 1000);
602         }
603
604         callback(event.data);
605     }
606
607     static workerDidRecieveMessage(event)
608     {
609         var data = event.data;
610         var id = data.id;
611         var method = Statistics[data.method];
612         var startTime = Date.now();
613         try {
614             var returnValue = method.apply(Statistics, data.args);
615             postMessage({'id': id, 'status': 'resolve', 'result': returnValue, 'workerStartTime': startTime, 'workerTime': Date.now() - startTime});
616         } catch (error) {
617             postMessage({'id': id, 'status': 'reject', 'result': error.toString(), 'workerStartTime': startTime, 'workerTime': Date.now() - startTime});
618             throw error;
619         }
620     }
621 }
622
623 AsyncTaskWorker._maxWorkerCount = 4;
624 AsyncTaskWorker._workerSet = new Set;
625 AsyncTaskWorker._queue = [];
626 AsyncTaskWorker._workerId = 1;
627 AsyncTaskWorker._latestStartTime = 0;
628
629 if (typeof module == 'undefined' && typeof window == 'undefined' && typeof importScripts != 'undefined') { // Inside a worker
630     //importScripts('/shared/statistics.js');
631     onmessage = AsyncTaskWorker.workerDidRecieveMessage.bind(AsyncTaskWorker);
632 }
633
634 if (typeof module != 'undefined')
635     module.exports.AsyncTask = AsyncTask;