source: trip-planner-front/node_modules/hdr-histogram-js/src/JsHistogram.ts@ 1ad8e64

Last change on this file since 1ad8e64 was 6a3a178, checked in by Ema <ema_spirova@…>, 3 years ago

initial commit

  • Property mode set to 100644
File size: 41.4 KB
Line 
1/*
2 * This is a TypeScript port of the original Java version, which was written by
3 * Gil Tene as described in
4 * https://github.com/HdrHistogram/HdrHistogram
5 * and released to the public domain, as explained at
6 * http://creativecommons.org/publicdomain/zero/1.0/
7 */
8import RecordedValuesIterator from "./RecordedValuesIterator";
9import PercentileIterator from "./PercentileIterator";
10import HistogramIterationValue from "./HistogramIterationValue";
11import { integerFormatter, floatFormatter } from "./formatters";
12import ulp from "./ulp";
13import Histogram, { NO_TAG, toSummary, HistogramSummary } from "./Histogram";
14
15const { pow, floor, ceil, log2, max, min } = Math;
16
17export abstract class JsHistogram implements Histogram {
18 static identityBuilder: number;
19
20 identity: number;
21 autoResize: boolean = false;
22
23 highestTrackableValue: number;
24 lowestDiscernibleValue: number;
25 numberOfSignificantValueDigits: number;
26
27 bucketCount: number;
28 /**
29 * Power-of-two length of linearly scaled array slots in the counts array. Long enough to hold the first sequence of
30 * entries that must be distinguished by a single unit (determined by configured precision).
31 */
32 subBucketCount: number;
33 countsArrayLength: number;
34 wordSizeInBytes: number;
35
36 startTimeStampMsec: number = Number.MAX_SAFE_INTEGER;
37 endTimeStampMsec: number = 0;
38 tag: string = NO_TAG;
39
40 percentileIterator: PercentileIterator;
41 recordedValuesIterator: RecordedValuesIterator;
42
43 // "Hot" accessed fields (used in the the value recording code path) are bunched here, such
44 // that they will have a good chance of ending up in the same cache line as the totalCounts and
45 // counts array reference fields that subclass implementations will typically add.
46
47 /**
48 * Number of leading zeros in the largest value that can fit in bucket 0.
49 */
50 leadingZeroCountBase: number;
51 subBucketHalfCountMagnitude: number;
52 /**
53 * Largest k such that 2^k &lt;= lowestDiscernibleValue
54 */
55 unitMagnitude: number;
56 subBucketHalfCount: number;
57
58 lowestDiscernibleValueRounded: number;
59
60 /**
61 * Biggest value that can fit in bucket 0
62 */
63 subBucketMask: number;
64 /**
65 * Lowest unitMagnitude bits are set
66 */
67 unitMagnitudeMask: number;
68
69 maxValue: number = 0;
70 minNonZeroValue: number = Number.MAX_SAFE_INTEGER;
71
72 _totalCount: number;
73
74 incrementTotalCount() {
75 this._totalCount++;
76 }
77
78 addToTotalCount(value: number) {
79 this._totalCount += value;
80 }
81
82 setTotalCount(value: number) {
83 this._totalCount = value;
84 }
85
86 /**
87 * Get the total count of all recorded values in the histogram
88 * @return the total count of all recorded values in the histogram
89 */
90 get totalCount() {
91 return this._totalCount;
92 }
93
94 //
95 //
96 //
97 // Abstract, counts-type dependent methods to be provided by subclass implementations:
98 //
99 //
100 //
101
102 abstract getCountAtIndex(index: number): number;
103
104 abstract incrementCountAtIndex(index: number): void;
105
106 abstract addToCountAtIndex(index: number, value: number): void;
107
108 abstract setCountAtIndex(index: number, value: number): void;
109
110 abstract clearCounts(): void;
111
112 protected abstract _getEstimatedFootprintInBytes(): number;
113
114 abstract resize(newHighestTrackableValue: number): void;
115
116 private updatedMaxValue(value: number): void {
117 const internalValue: number = value + this.unitMagnitudeMask;
118 this.maxValue = internalValue;
119 }
120
121 private updateMinNonZeroValue(value: number): void {
122 if (value <= this.unitMagnitudeMask) {
123 return;
124 }
125 const internalValue =
126 floor(value / this.lowestDiscernibleValueRounded) *
127 this.lowestDiscernibleValueRounded;
128 this.minNonZeroValue = internalValue;
129 }
130
131 constructor(
132 lowestDiscernibleValue: number,
133 highestTrackableValue: number,
134 numberOfSignificantValueDigits: number
135 ) {
136 this.identity = 0;
137 this.highestTrackableValue = 0;
138 this.lowestDiscernibleValue = 0;
139 this.numberOfSignificantValueDigits = 0;
140 this.bucketCount = 0;
141 this.subBucketCount = 0;
142 this.countsArrayLength = 0;
143 this.wordSizeInBytes = 0;
144 // Verify argument validity
145 if (lowestDiscernibleValue < 1) {
146 throw new Error("lowestDiscernibleValue must be >= 1");
147 }
148 if (highestTrackableValue < 2 * lowestDiscernibleValue) {
149 throw new Error(
150 `highestTrackableValue must be >= 2 * lowestDiscernibleValue ( 2 * ${lowestDiscernibleValue} )`
151 );
152 }
153 if (
154 numberOfSignificantValueDigits < 0 ||
155 numberOfSignificantValueDigits > 5
156 ) {
157 throw new Error("numberOfSignificantValueDigits must be between 0 and 5");
158 }
159 this.identity = JsHistogram.identityBuilder++;
160
161 this.init(
162 lowestDiscernibleValue,
163 highestTrackableValue,
164 numberOfSignificantValueDigits
165 );
166 }
167
168 init(
169 lowestDiscernibleValue: number,
170 highestTrackableValue: number,
171 numberOfSignificantValueDigits: number
172 ) {
173 this.lowestDiscernibleValue = lowestDiscernibleValue;
174 this.highestTrackableValue = highestTrackableValue;
175 this.numberOfSignificantValueDigits = numberOfSignificantValueDigits;
176
177 /*
178 * Given a 3 decimal point accuracy, the expectation is obviously for "+/- 1 unit at 1000". It also means that
179 * it's "ok to be +/- 2 units at 2000". The "tricky" thing is that it is NOT ok to be +/- 2 units at 1999. Only
180 * starting at 2000. So internally, we need to maintain single unit resolution to 2x 10^decimalPoints.
181 */
182 const largestValueWithSingleUnitResolution =
183 2 * floor(pow(10, numberOfSignificantValueDigits));
184
185 this.unitMagnitude = floor(log2(lowestDiscernibleValue));
186
187 this.lowestDiscernibleValueRounded = pow(2, this.unitMagnitude);
188 this.unitMagnitudeMask = this.lowestDiscernibleValueRounded - 1;
189
190 // We need to maintain power-of-two subBucketCount (for clean direct indexing) that is large enough to
191 // provide unit resolution to at least largestValueWithSingleUnitResolution. So figure out
192 // largestValueWithSingleUnitResolution's nearest power-of-two (rounded up), and use that:
193 const subBucketCountMagnitude = ceil(
194 log2(largestValueWithSingleUnitResolution)
195 );
196 this.subBucketHalfCountMagnitude =
197 (subBucketCountMagnitude > 1 ? subBucketCountMagnitude : 1) - 1;
198 this.subBucketCount = pow(2, this.subBucketHalfCountMagnitude + 1);
199 this.subBucketHalfCount = this.subBucketCount / 2;
200 this.subBucketMask =
201 (floor(this.subBucketCount) - 1) * pow(2, this.unitMagnitude);
202
203 this.establishSize(highestTrackableValue);
204
205 this.leadingZeroCountBase =
206 53 - this.unitMagnitude - this.subBucketHalfCountMagnitude - 1;
207 this.percentileIterator = new PercentileIterator(this, 1);
208 this.recordedValuesIterator = new RecordedValuesIterator(this);
209 }
210
211 /**
212 * The buckets (each of which has subBucketCount sub-buckets, here assumed to be 2048 as an example) overlap:
213 *
214 * <pre>
215 * The 0'th bucket covers from 0...2047 in multiples of 1, using all 2048 sub-buckets
216 * The 1'th bucket covers from 2048..4097 in multiples of 2, using only the top 1024 sub-buckets
217 * The 2'th bucket covers from 4096..8191 in multiple of 4, using only the top 1024 sub-buckets
218 * ...
219 * </pre>
220 *
221 * Bucket 0 is "special" here. It is the only one that has 2048 entries. All the rest have 1024 entries (because
222 * their bottom half overlaps with and is already covered by the all of the previous buckets put together). In other
223 * words, the k'th bucket could represent 0 * 2^k to 2048 * 2^k in 2048 buckets with 2^k precision, but the midpoint
224 * of 1024 * 2^k = 2048 * 2^(k-1) = the k-1'th bucket's end, so we would use the previous bucket for those lower
225 * values as it has better precision.
226 */
227 establishSize(newHighestTrackableValue: number): void {
228 // establish counts array length:
229 this.countsArrayLength = this.determineArrayLengthNeeded(
230 newHighestTrackableValue
231 );
232 // establish exponent range needed to support the trackable value with no overflow:
233 this.bucketCount = this.getBucketsNeededToCoverValue(
234 newHighestTrackableValue
235 );
236 // establish the new highest trackable value:
237 this.highestTrackableValue = newHighestTrackableValue;
238 }
239
240 determineArrayLengthNeeded(highestTrackableValue: number): number {
241 if (highestTrackableValue < 2 * this.lowestDiscernibleValue) {
242 throw new Error(
243 "highestTrackableValue (" +
244 highestTrackableValue +
245 ") cannot be < (2 * lowestDiscernibleValue)"
246 );
247 }
248 //determine counts array length needed:
249 const countsArrayLength = this.getLengthForNumberOfBuckets(
250 this.getBucketsNeededToCoverValue(highestTrackableValue)
251 );
252 return countsArrayLength;
253 }
254
255 /**
256 * If we have N such that subBucketCount * 2^N > max value, we need storage for N+1 buckets, each with enough
257 * slots to hold the top half of the subBucketCount (the lower half is covered by previous buckets), and the +1
258 * being used for the lower half of the 0'th bucket. Or, equivalently, we need 1 more bucket to capture the max
259 * value if we consider the sub-bucket length to be halved.
260 */
261 getLengthForNumberOfBuckets(numberOfBuckets: number): number {
262 const lengthNeeded: number =
263 (numberOfBuckets + 1) * (this.subBucketCount / 2);
264 return lengthNeeded;
265 }
266
267 getBucketsNeededToCoverValue(value: number): number {
268 // the k'th bucket can express from 0 * 2^k to subBucketCount * 2^k in units of 2^k
269 let smallestUntrackableValue =
270 this.subBucketCount * pow(2, this.unitMagnitude);
271 // always have at least 1 bucket
272 let bucketsNeeded = 1;
273 while (smallestUntrackableValue <= value) {
274 if (smallestUntrackableValue > Number.MAX_SAFE_INTEGER / 2) {
275 // TODO check array max size in JavaScript
276 // next shift will overflow, meaning that bucket could represent values up to ones greater than
277 // Number.MAX_SAFE_INTEGER, so it's the last bucket
278 return bucketsNeeded + 1;
279 }
280 smallestUntrackableValue = smallestUntrackableValue * 2;
281 bucketsNeeded++;
282 }
283 return bucketsNeeded;
284 }
285
286 /**
287 * Record a value in the histogram
288 *
289 * @param value The value to be recorded
290 * @throws may throw Error if value is exceeds highestTrackableValue
291 */
292 recordValue(value: number) {
293 this.recordSingleValue(value);
294 }
295
296 recordSingleValue(value: number) {
297 const countsIndex = this.countsArrayIndex(value);
298 if (countsIndex >= this.countsArrayLength) {
299 this.handleRecordException(1, value);
300 } else {
301 this.incrementCountAtIndex(countsIndex);
302 }
303 this.updateMinAndMax(value);
304 this.incrementTotalCount();
305 }
306
307 handleRecordException(count: number, value: number) {
308 if (!this.autoResize) {
309 throw new Error(
310 "Value " + value + " is outside of histogram covered range"
311 );
312 }
313 this.resize(value);
314 var countsIndex: number = this.countsArrayIndex(value);
315 this.addToCountAtIndex(countsIndex, count);
316 this.highestTrackableValue = this.highestEquivalentValue(
317 this.valueFromIndex(this.countsArrayLength - 1)
318 );
319 }
320
321 countsArrayIndex(value: number): number {
322 if (value < 0) {
323 throw new Error("Histogram recorded value cannot be negative.");
324 }
325 const bucketIndex = this.getBucketIndex(value);
326 const subBucketIndex = this.getSubBucketIndex(value, bucketIndex);
327 return this.computeCountsArrayIndex(bucketIndex, subBucketIndex);
328 }
329
330 private computeCountsArrayIndex(bucketIndex: number, subBucketIndex: number) {
331 // TODO
332 //assert(subBucketIndex < subBucketCount);
333 //assert(bucketIndex == 0 || (subBucketIndex >= subBucketHalfCount));
334
335 // Calculate the index for the first entry that will be used in the bucket (halfway through subBucketCount).
336 // For bucketIndex 0, all subBucketCount entries may be used, but bucketBaseIndex is still set in the middle.
337 const bucketBaseIndex =
338 (bucketIndex + 1) * pow(2, this.subBucketHalfCountMagnitude);
339 // Calculate the offset in the bucket. This subtraction will result in a positive value in all buckets except
340 // the 0th bucket (since a value in that bucket may be less than half the bucket's 0 to subBucketCount range).
341 // However, this works out since we give bucket 0 twice as much space.
342 const offsetInBucket = subBucketIndex - this.subBucketHalfCount;
343 // The following is the equivalent of ((subBucketIndex - subBucketHalfCount) + bucketBaseIndex;
344 return bucketBaseIndex + offsetInBucket;
345 }
346
347 /**
348 * @return the lowest (and therefore highest precision) bucket index that can represent the value
349 */
350 getBucketIndex(value: number) {
351 // Calculates the number of powers of two by which the value is greater than the biggest value that fits in
352 // bucket 0. This is the bucket index since each successive bucket can hold a value 2x greater.
353 // The mask maps small values to bucket 0.
354
355 // return this.leadingZeroCountBase - Long.numberOfLeadingZeros(value | subBucketMask);
356 return max(
357 floor(log2(value)) -
358 this.subBucketHalfCountMagnitude -
359 this.unitMagnitude,
360 0
361 );
362 }
363
364 getSubBucketIndex(value: number, bucketIndex: number) {
365 // For bucketIndex 0, this is just value, so it may be anywhere in 0 to subBucketCount.
366 // For other bucketIndex, this will always end up in the top half of subBucketCount: assume that for some bucket
367 // k > 0, this calculation will yield a value in the bottom half of 0 to subBucketCount. Then, because of how
368 // buckets overlap, it would have also been in the top half of bucket k-1, and therefore would have
369 // returned k-1 in getBucketIndex(). Since we would then shift it one fewer bits here, it would be twice as big,
370 // and therefore in the top half of subBucketCount.
371 return floor(value / pow(2, bucketIndex + this.unitMagnitude));
372 }
373
374 updateMinAndMax(value: number) {
375 if (value > this.maxValue) {
376 this.updatedMaxValue(value);
377 }
378 if (value < this.minNonZeroValue && value !== 0) {
379 this.updateMinNonZeroValue(value);
380 }
381 }
382
383 /**
384 * Get the value at a given percentile.
385 * When the given percentile is &gt; 0.0, the value returned is the value that the given
386 * percentage of the overall recorded value entries in the histogram are either smaller than
387 * or equivalent to. When the given percentile is 0.0, the value returned is the value that all value
388 * entries in the histogram are either larger than or equivalent to.
389 * <p>
390 * Note that two values are "equivalent" in this statement if
391 * {@link org.HdrHistogram.JsHistogram#valuesAreEquivalent} would return true.
392 *
393 * @param percentile The percentile for which to return the associated value
394 * @return The value that the given percentage of the overall recorded value entries in the
395 * histogram are either smaller than or equivalent to. When the percentile is 0.0, returns the
396 * value that all value entries in the histogram are either larger than or equivalent to.
397 */
398 getValueAtPercentile(percentile: number) {
399 const requestedPercentile = min(percentile, 100); // Truncate down to 100%
400
401 // round count up to nearest integer, to ensure that the largest value that the requested percentile
402 // of overall recorded values is actually included. However, this must be done with care:
403 //
404 // First, Compute fp value for count at the requested percentile. Note that fp result end up
405 // being 1 ulp larger than the correct integer count for this percentile:
406 const fpCountAtPercentile = (requestedPercentile / 100.0) * this.totalCount;
407 // Next, round up, but make sure to prevent <= 1 ulp inaccurancies in the above fp math from
408 // making us skip a count:
409 const countAtPercentile = max(
410 ceil(fpCountAtPercentile - ulp(fpCountAtPercentile)), // round up
411 1 // Make sure we at least reach the first recorded entry
412 );
413
414 let totalToCurrentIndex = 0;
415 for (let i = 0; i < this.countsArrayLength; i++) {
416 totalToCurrentIndex += this.getCountAtIndex(i);
417 if (totalToCurrentIndex >= countAtPercentile) {
418 var valueAtIndex: number = this.valueFromIndex(i);
419 return percentile === 0.0
420 ? this.lowestEquivalentValue(valueAtIndex)
421 : this.highestEquivalentValue(valueAtIndex);
422 }
423 }
424 return 0;
425 }
426
427 valueFromIndexes(bucketIndex: number, subBucketIndex: number) {
428 return subBucketIndex * pow(2, bucketIndex + this.unitMagnitude);
429 }
430
431 valueFromIndex(index: number) {
432 let bucketIndex = floor(index / this.subBucketHalfCount) - 1;
433 let subBucketIndex =
434 (index % this.subBucketHalfCount) + this.subBucketHalfCount;
435 if (bucketIndex < 0) {
436 subBucketIndex -= this.subBucketHalfCount;
437 bucketIndex = 0;
438 }
439 return this.valueFromIndexes(bucketIndex, subBucketIndex);
440 }
441
442 /**
443 * Get the lowest value that is equivalent to the given value within the histogram's resolution.
444 * Where "equivalent" means that value samples recorded for any two
445 * equivalent values are counted in a common total count.
446 *
447 * @param value The given value
448 * @return The lowest value that is equivalent to the given value within the histogram's resolution.
449 */
450 lowestEquivalentValue(value: number) {
451 const bucketIndex = this.getBucketIndex(value);
452 const subBucketIndex = this.getSubBucketIndex(value, bucketIndex);
453 const thisValueBaseLevel = this.valueFromIndexes(
454 bucketIndex,
455 subBucketIndex
456 );
457 return thisValueBaseLevel;
458 }
459
460 /**
461 * Get the highest value that is equivalent to the given value within the histogram's resolution.
462 * Where "equivalent" means that value samples recorded for any two
463 * equivalent values are counted in a common total count.
464 *
465 * @param value The given value
466 * @return The highest value that is equivalent to the given value within the histogram's resolution.
467 */
468 highestEquivalentValue(value: number) {
469 return this.nextNonEquivalentValue(value) - 1;
470 }
471
472 /**
473 * Get the next value that is not equivalent to the given value within the histogram's resolution.
474 * Where "equivalent" means that value samples recorded for any two
475 * equivalent values are counted in a common total count.
476 *
477 * @param value The given value
478 * @return The next value that is not equivalent to the given value within the histogram's resolution.
479 */
480 nextNonEquivalentValue(value: number) {
481 return (
482 this.lowestEquivalentValue(value) + this.sizeOfEquivalentValueRange(value)
483 );
484 }
485
486 /**
487 * Get the size (in value units) of the range of values that are equivalent to the given value within the
488 * histogram's resolution. Where "equivalent" means that value samples recorded for any two
489 * equivalent values are counted in a common total count.
490 *
491 * @param value The given value
492 * @return The size of the range of values equivalent to the given value.
493 */
494 sizeOfEquivalentValueRange(value: number) {
495 const bucketIndex = this.getBucketIndex(value);
496 const subBucketIndex = this.getSubBucketIndex(value, bucketIndex);
497 const distanceToNextValue = pow(
498 2,
499 this.unitMagnitude +
500 (subBucketIndex >= this.subBucketCount ? bucketIndex + 1 : bucketIndex)
501 );
502 return distanceToNextValue;
503 }
504
505 /**
506 * Get a value that lies in the middle (rounded up) of the range of values equivalent the given value.
507 * Where "equivalent" means that value samples recorded for any two
508 * equivalent values are counted in a common total count.
509 *
510 * @param value The given value
511 * @return The value lies in the middle (rounded up) of the range of values equivalent the given value.
512 */
513 medianEquivalentValue(value: number) {
514 return (
515 this.lowestEquivalentValue(value) +
516 floor(this.sizeOfEquivalentValueRange(value) / 2)
517 );
518 }
519
520 /**
521 * Get the computed mean value of all recorded values in the histogram
522 *
523 * @return the mean value (in value units) of the histogram data
524 */
525 get mean() {
526 if (this.totalCount === 0) {
527 return 0;
528 }
529 this.recordedValuesIterator.reset();
530 let totalValue = 0;
531 while (this.recordedValuesIterator.hasNext()) {
532 const iterationValue = this.recordedValuesIterator.next();
533 totalValue +=
534 this.medianEquivalentValue(iterationValue.valueIteratedTo) *
535 iterationValue.countAtValueIteratedTo;
536 }
537 return totalValue / this.totalCount;
538 }
539
540 private getStdDeviation(mean: number = this.mean) {
541 if (this.totalCount === 0) {
542 return 0;
543 }
544 let geometric_deviation_total = 0.0;
545 this.recordedValuesIterator.reset();
546 while (this.recordedValuesIterator.hasNext()) {
547 const iterationValue = this.recordedValuesIterator.next();
548 const deviation =
549 this.medianEquivalentValue(iterationValue.valueIteratedTo) - mean;
550 geometric_deviation_total +=
551 deviation * deviation * iterationValue.countAddedInThisIterationStep;
552 }
553 const std_deviation = Math.sqrt(
554 geometric_deviation_total / this.totalCount
555 );
556 return std_deviation;
557 }
558
559 /**
560 * Get the computed standard deviation of all recorded values in the histogram
561 *
562 * @return the standard deviation (in value units) of the histogram data
563 */
564 get stdDeviation() {
565 if (this.totalCount === 0) {
566 return 0;
567 }
568 const mean = this.mean;
569 let geometric_deviation_total = 0.0;
570 this.recordedValuesIterator.reset();
571 while (this.recordedValuesIterator.hasNext()) {
572 const iterationValue = this.recordedValuesIterator.next();
573 const deviation =
574 this.medianEquivalentValue(iterationValue.valueIteratedTo) - mean;
575 geometric_deviation_total +=
576 deviation * deviation * iterationValue.countAddedInThisIterationStep;
577 }
578 const std_deviation = Math.sqrt(
579 geometric_deviation_total / this.totalCount
580 );
581 return std_deviation;
582 }
583
584 /**
585 * Produce textual representation of the value distribution of histogram data by percentile. The distribution is
586 * output with exponentially increasing resolution, with each exponentially decreasing half-distance containing
587 * <i>dumpTicksPerHalf</i> percentile reporting tick points.
588 *
589 * @param printStream Stream into which the distribution will be output
590 * <p>
591 * @param percentileTicksPerHalfDistance The number of reporting points per exponentially decreasing half-distance
592 * <p>
593 * @param outputValueUnitScalingRatio The scaling factor by which to divide histogram recorded values units in
594 * output
595 * @param useCsvFormat Output in CSV format if true. Otherwise use plain text form.
596 */
597 outputPercentileDistribution(
598 percentileTicksPerHalfDistance = 5,
599 outputValueUnitScalingRatio = 1,
600 useCsvFormat = false
601 ): string {
602 let result = "";
603 if (useCsvFormat) {
604 result += '"Value","Percentile","TotalCount","1/(1-Percentile)"\n';
605 } else {
606 result += " Value Percentile TotalCount 1/(1-Percentile)\n\n";
607 }
608
609 const iterator = this.percentileIterator;
610 iterator.reset(percentileTicksPerHalfDistance);
611
612 let lineFormatter: (iterationValue: HistogramIterationValue) => string;
613 let lastLineFormatter: (iterationValue: HistogramIterationValue) => string;
614
615 if (useCsvFormat) {
616 const valueFormatter = floatFormatter(
617 0,
618 this.numberOfSignificantValueDigits
619 );
620 const percentileFormatter = floatFormatter(0, 12);
621 const lastFormatter = floatFormatter(0, 2);
622
623 lineFormatter = (iterationValue: HistogramIterationValue) =>
624 valueFormatter(
625 iterationValue.valueIteratedTo / outputValueUnitScalingRatio
626 ) +
627 "," +
628 percentileFormatter(iterationValue.percentileLevelIteratedTo / 100) +
629 "," +
630 iterationValue.totalCountToThisValue +
631 "," +
632 lastFormatter(
633 1 / (1 - iterationValue.percentileLevelIteratedTo / 100)
634 ) +
635 "\n";
636 lastLineFormatter = (iterationValue: HistogramIterationValue) =>
637 valueFormatter(
638 iterationValue.valueIteratedTo / outputValueUnitScalingRatio
639 ) +
640 "," +
641 percentileFormatter(iterationValue.percentileLevelIteratedTo / 100) +
642 "," +
643 iterationValue.totalCountToThisValue +
644 ",Infinity\n";
645 } else {
646 const valueFormatter = floatFormatter(
647 12,
648 this.numberOfSignificantValueDigits
649 );
650 const percentileFormatter = floatFormatter(2, 12);
651 const totalCountFormatter = integerFormatter(10);
652 const lastFormatter = floatFormatter(14, 2);
653
654 lineFormatter = (iterationValue: HistogramIterationValue) =>
655 valueFormatter(
656 iterationValue.valueIteratedTo / outputValueUnitScalingRatio
657 ) +
658 " " +
659 percentileFormatter(iterationValue.percentileLevelIteratedTo / 100) +
660 " " +
661 totalCountFormatter(iterationValue.totalCountToThisValue) +
662 " " +
663 lastFormatter(
664 1 / (1 - iterationValue.percentileLevelIteratedTo / 100)
665 ) +
666 "\n";
667
668 lastLineFormatter = (iterationValue: HistogramIterationValue) =>
669 valueFormatter(
670 iterationValue.valueIteratedTo / outputValueUnitScalingRatio
671 ) +
672 " " +
673 percentileFormatter(iterationValue.percentileLevelIteratedTo / 100) +
674 " " +
675 totalCountFormatter(iterationValue.totalCountToThisValue) +
676 "\n";
677 }
678
679 while (iterator.hasNext()) {
680 const iterationValue = iterator.next();
681 if (iterationValue.percentileLevelIteratedTo < 100) {
682 result += lineFormatter(iterationValue);
683 } else {
684 result += lastLineFormatter(iterationValue);
685 }
686 }
687
688 if (!useCsvFormat) {
689 // Calculate and output mean and std. deviation.
690 // Note: mean/std. deviation numbers are very often completely irrelevant when
691 // data is extremely non-normal in distribution (e.g. in cases of strong multi-modal
692 // response time distribution associated with GC pauses). However, reporting these numbers
693 // can be very useful for contrasting with the detailed percentile distribution
694 // reported by outputPercentileDistribution(). It is not at all surprising to find
695 // percentile distributions where results fall many tens or even hundreds of standard
696 // deviations away from the mean - such results simply indicate that the data sampled
697 // exhibits a very non-normal distribution, highlighting situations for which the std.
698 // deviation metric is a useless indicator.
699 //
700 const formatter = floatFormatter(12, this.numberOfSignificantValueDigits);
701 const _mean = this.mean;
702 const mean = formatter(_mean / outputValueUnitScalingRatio);
703 const std_deviation = formatter(
704 this.getStdDeviation(_mean) / outputValueUnitScalingRatio
705 );
706 const max = formatter(this.maxValue / outputValueUnitScalingRatio);
707 const intFormatter = integerFormatter(12);
708 const totalCount = intFormatter(this.totalCount);
709 const bucketCount = intFormatter(this.bucketCount);
710 const subBucketCount = intFormatter(this.subBucketCount);
711
712 result += `#[Mean = ${mean}, StdDeviation = ${std_deviation}]
713#[Max = ${max}, Total count = ${totalCount}]
714#[Buckets = ${bucketCount}, SubBuckets = ${subBucketCount}]
715`;
716 }
717
718 return result;
719 }
720
721 get summary(): HistogramSummary {
722 return toSummary(this);
723 }
724
725 toJSON(): HistogramSummary {
726 return this.summary;
727 }
728
729 inspect() {
730 return this.toString();
731 }
732
733 [Symbol.for("nodejs.util.inspect.custom")]() {
734 return this.toString();
735 }
736
737 /**
738 * Provide a (conservatively high) estimate of the Histogram's total footprint in bytes
739 *
740 * @return a (conservatively high) estimate of the Histogram's total footprint in bytes
741 */
742 get estimatedFootprintInBytes() {
743 return this._getEstimatedFootprintInBytes();
744 }
745
746 recordSingleValueWithExpectedInterval(
747 value: number,
748 expectedIntervalBetweenValueSamples: number
749 ) {
750 this.recordSingleValue(value);
751 if (expectedIntervalBetweenValueSamples <= 0) {
752 return;
753 }
754 for (
755 let missingValue = value - expectedIntervalBetweenValueSamples;
756 missingValue >= expectedIntervalBetweenValueSamples;
757 missingValue -= expectedIntervalBetweenValueSamples
758 ) {
759 this.recordSingleValue(missingValue);
760 }
761 }
762
763 private recordCountAtValue(count: number, value: number) {
764 const countsIndex = this.countsArrayIndex(value);
765 if (countsIndex >= this.countsArrayLength) {
766 this.handleRecordException(count, value);
767 } else {
768 this.addToCountAtIndex(countsIndex, count);
769 }
770 this.updateMinAndMax(value);
771 this.addToTotalCount(count);
772 }
773
774 /**
775 * Record a value in the histogram (adding to the value's current count)
776 *
777 * @param value The value to be recorded
778 * @param count The number of occurrences of this value to record
779 * @throws ArrayIndexOutOfBoundsException (may throw) if value is exceeds highestTrackableValue
780 */
781 recordValueWithCount(value: number, count: number) {
782 this.recordCountAtValue(count, value);
783 }
784
785 /**
786 * Record a value in the histogram.
787 * <p>
788 * To compensate for the loss of sampled values when a recorded value is larger than the expected
789 * interval between value samples, Histogram will auto-generate an additional series of decreasingly-smaller
790 * (down to the expectedIntervalBetweenValueSamples) value records.
791 * <p>
792 * Note: This is a at-recording correction method, as opposed to the post-recording correction method provided
793 * by {@link #copyCorrectedForCoordinatedOmission(long)}.
794 * The two methods are mutually exclusive, and only one of the two should be be used on a given data set to correct
795 * for the same coordinated omission issue.
796 * <p>
797 * See notes in the description of the Histogram calls for an illustration of why this corrective behavior is
798 * important.
799 *
800 * @param value The value to record
801 * @param expectedIntervalBetweenValueSamples If expectedIntervalBetweenValueSamples is larger than 0, add
802 * auto-generated value records as appropriate if value is larger
803 * than expectedIntervalBetweenValueSamples
804 * @throws ArrayIndexOutOfBoundsException (may throw) if value is exceeds highestTrackableValue
805 */
806 recordValueWithExpectedInterval(
807 value: number,
808 expectedIntervalBetweenValueSamples: number
809 ) {
810 this.recordSingleValueWithExpectedInterval(
811 value,
812 expectedIntervalBetweenValueSamples
813 );
814 }
815
816 private recordValueWithCountAndExpectedInterval(
817 value: number,
818 count: number,
819 expectedIntervalBetweenValueSamples: number
820 ) {
821 this.recordCountAtValue(count, value);
822 if (expectedIntervalBetweenValueSamples <= 0) {
823 return;
824 }
825 for (
826 let missingValue = value - expectedIntervalBetweenValueSamples;
827 missingValue >= expectedIntervalBetweenValueSamples;
828 missingValue -= expectedIntervalBetweenValueSamples
829 ) {
830 this.recordCountAtValue(count, missingValue);
831 }
832 }
833
834 /**
835 * Add the contents of another histogram to this one, while correcting the incoming data for coordinated omission.
836 * <p>
837 * To compensate for the loss of sampled values when a recorded value is larger than the expected
838 * interval between value samples, the values added will include an auto-generated additional series of
839 * decreasingly-smaller (down to the expectedIntervalBetweenValueSamples) value records for each count found
840 * in the current histogram that is larger than the expectedIntervalBetweenValueSamples.
841 *
842 * Note: This is a post-recording correction method, as opposed to the at-recording correction method provided
843 * by {@link #recordValueWithExpectedInterval(long, long) recordValueWithExpectedInterval}. The two
844 * methods are mutually exclusive, and only one of the two should be be used on a given data set to correct
845 * for the same coordinated omission issue.
846 * by
847 * <p>
848 * See notes in the description of the Histogram calls for an illustration of why this corrective behavior is
849 * important.
850 *
851 * @param otherHistogram The other histogram. highestTrackableValue and largestValueWithSingleUnitResolution must match.
852 * @param expectedIntervalBetweenValueSamples If expectedIntervalBetweenValueSamples is larger than 0, add
853 * auto-generated value records as appropriate if value is larger
854 * than expectedIntervalBetweenValueSamples
855 * @throws ArrayIndexOutOfBoundsException (may throw) if values exceed highestTrackableValue
856 */
857 addWhileCorrectingForCoordinatedOmission(
858 otherHistogram: JsHistogram,
859 expectedIntervalBetweenValueSamples: number
860 ) {
861 const toHistogram = this;
862
863 const otherValues = new RecordedValuesIterator(otherHistogram);
864
865 while (otherValues.hasNext()) {
866 const v = otherValues.next();
867 toHistogram.recordValueWithCountAndExpectedInterval(
868 v.valueIteratedTo,
869 v.countAtValueIteratedTo,
870 expectedIntervalBetweenValueSamples
871 );
872 }
873 }
874
875 /**
876 * Get a copy of this histogram, corrected for coordinated omission.
877 * <p>
878 * To compensate for the loss of sampled values when a recorded value is larger than the expected
879 * interval between value samples, the new histogram will include an auto-generated additional series of
880 * decreasingly-smaller (down to the expectedIntervalBetweenValueSamples) value records for each count found
881 * in the current histogram that is larger than the expectedIntervalBetweenValueSamples.
882 *
883 * Note: This is a post-correction method, as opposed to the at-recording correction method provided
884 * by {@link #recordValueWithExpectedInterval(long, long) recordValueWithExpectedInterval}. The two
885 * methods are mutually exclusive, and only one of the two should be be used on a given data set to correct
886 * for the same coordinated omission issue.
887 * by
888 * <p>
889 * See notes in the description of the Histogram calls for an illustration of why this corrective behavior is
890 * important.
891 *
892 * @param expectedIntervalBetweenValueSamples If expectedIntervalBetweenValueSamples is larger than 0, add
893 * auto-generated value records as appropriate if value is larger
894 * than expectedIntervalBetweenValueSamples
895 * @return a copy of this histogram, corrected for coordinated omission.
896 */
897 abstract copyCorrectedForCoordinatedOmission(
898 expectedIntervalBetweenValueSamples: number
899 ): JsHistogram;
900
901 /**
902 * Add the contents of another histogram to this one.
903 * <p>
904 * As part of adding the contents, the start/end timestamp range of this histogram will be
905 * extended to include the start/end timestamp range of the other histogram.
906 *
907 * @param otherHistogram The other histogram.
908 * @throws (may throw) if values in fromHistogram's are
909 * higher than highestTrackableValue.
910 */
911 add(otherHistogram: JsHistogram) {
912 if (!(otherHistogram instanceof JsHistogram)) {
913 // should be impossible to be in this situation but actually
914 // TypeScript has some flaws...
915 throw new Error("Cannot add a WASM histogram to a regular JS histogram");
916 }
917 const highestRecordableValue = this.highestEquivalentValue(
918 this.valueFromIndex(this.countsArrayLength - 1)
919 );
920
921 if (highestRecordableValue < otherHistogram.maxValue) {
922 if (!this.autoResize) {
923 throw new Error(
924 "The other histogram includes values that do not fit in this histogram's range."
925 );
926 }
927 this.resize(otherHistogram.maxValue);
928 }
929
930 if (
931 this.bucketCount === otherHistogram.bucketCount &&
932 this.subBucketCount === otherHistogram.subBucketCount &&
933 this.unitMagnitude === otherHistogram.unitMagnitude
934 ) {
935 // Counts arrays are of the same length and meaning, so we can just iterate and add directly:
936 let observedOtherTotalCount = 0;
937 for (let i = 0; i < otherHistogram.countsArrayLength; i++) {
938 const otherCount = otherHistogram.getCountAtIndex(i);
939 if (otherCount > 0) {
940 this.addToCountAtIndex(i, otherCount);
941 observedOtherTotalCount += otherCount;
942 }
943 }
944 this.setTotalCount(this.totalCount + observedOtherTotalCount);
945 this.updatedMaxValue(max(this.maxValue, otherHistogram.maxValue));
946 this.updateMinNonZeroValue(
947 min(this.minNonZeroValue, otherHistogram.minNonZeroValue)
948 );
949 } else {
950 // Arrays are not a direct match (or the other could change on the fly in some valid way),
951 // so we can't just stream through and add them. Instead, go through the array and add each
952 // non-zero value found at it's proper value:
953
954 // Do max value first, to avoid max value updates on each iteration:
955 const otherMaxIndex = otherHistogram.countsArrayIndex(
956 otherHistogram.maxValue
957 );
958 let otherCount = otherHistogram.getCountAtIndex(otherMaxIndex);
959 this.recordCountAtValue(
960 otherCount,
961 otherHistogram.valueFromIndex(otherMaxIndex)
962 );
963
964 // Record the remaining values, up to but not including the max value:
965 for (let i = 0; i < otherMaxIndex; i++) {
966 otherCount = otherHistogram.getCountAtIndex(i);
967 if (otherCount > 0) {
968 this.recordCountAtValue(otherCount, otherHistogram.valueFromIndex(i));
969 }
970 }
971 }
972 this.startTimeStampMsec = min(
973 this.startTimeStampMsec,
974 otherHistogram.startTimeStampMsec
975 );
976 this.endTimeStampMsec = max(
977 this.endTimeStampMsec,
978 otherHistogram.endTimeStampMsec
979 );
980 }
981
982 /**
983 * Get the count of recorded values at a specific value (to within the histogram resolution at the value level).
984 *
985 * @param value The value for which to provide the recorded count
986 * @return The total count of values recorded in the histogram within the value range that is
987 * {@literal >=} lowestEquivalentValue(<i>value</i>) and {@literal <=} highestEquivalentValue(<i>value</i>)
988 */
989 private getCountAtValue(value: number) {
990 const index = min(
991 max(0, this.countsArrayIndex(value)),
992 this.countsArrayLength - 1
993 );
994 return this.getCountAtIndex(index);
995 }
996
997 /**
998 * Subtract the contents of another histogram from this one.
999 * <p>
1000 * The start/end timestamps of this histogram will remain unchanged.
1001 *
1002 * @param otherHistogram The other histogram.
1003 * @throws ArrayIndexOutOfBoundsException (may throw) if values in otherHistogram's are higher than highestTrackableValue.
1004 *
1005 */
1006 subtract(otherHistogram: JsHistogram) {
1007 const highestRecordableValue = this.valueFromIndex(
1008 this.countsArrayLength - 1
1009 );
1010 if (!(otherHistogram instanceof JsHistogram)) {
1011 // should be impossible to be in this situation but actually
1012 // TypeScript has some flaws...
1013 throw new Error(
1014 "Cannot subtract a WASM histogram to a regular JS histogram"
1015 );
1016 }
1017 if (highestRecordableValue < otherHistogram.maxValue) {
1018 if (!this.autoResize) {
1019 throw new Error(
1020 "The other histogram includes values that do not fit in this histogram's range."
1021 );
1022 }
1023 this.resize(otherHistogram.maxValue);
1024 }
1025
1026 if (
1027 this.bucketCount === otherHistogram.bucketCount &&
1028 this.subBucketCount === otherHistogram.subBucketCount &&
1029 this.unitMagnitude === otherHistogram.unitMagnitude
1030 ) {
1031 // optim
1032 // Counts arrays are of the same length and meaning, so we can just iterate and add directly:
1033 let observedOtherTotalCount = 0;
1034 for (let i = 0; i < otherHistogram.countsArrayLength; i++) {
1035 const otherCount = otherHistogram.getCountAtIndex(i);
1036 if (otherCount > 0) {
1037 this.addToCountAtIndex(i, -otherCount);
1038 observedOtherTotalCount += otherCount;
1039 }
1040 }
1041 this.setTotalCount(this.totalCount - observedOtherTotalCount);
1042 } else {
1043 for (let i = 0; i < otherHistogram.countsArrayLength; i++) {
1044 const otherCount = otherHistogram.getCountAtIndex(i);
1045 if (otherCount > 0) {
1046 const otherValue = otherHistogram.valueFromIndex(i);
1047 if (this.getCountAtValue(otherValue) < otherCount) {
1048 throw new Error(
1049 "otherHistogram count (" +
1050 otherCount +
1051 ") at value " +
1052 otherValue +
1053 " is larger than this one's (" +
1054 this.getCountAtValue(otherValue) +
1055 ")"
1056 );
1057 }
1058 this.recordCountAtValue(-otherCount, otherValue);
1059 }
1060 }
1061 }
1062 // With subtraction, the max and minNonZero values could have changed:
1063 if (
1064 this.getCountAtValue(this.maxValue) <= 0 ||
1065 this.getCountAtValue(this.minNonZeroValue) <= 0
1066 ) {
1067 this.establishInternalTackingValues();
1068 }
1069 }
1070
1071 establishInternalTackingValues(lengthToCover = this.countsArrayLength) {
1072 this.maxValue = 0;
1073 this.minNonZeroValue = Number.MAX_VALUE;
1074 let maxIndex = -1;
1075 let minNonZeroIndex = -1;
1076 let observedTotalCount = 0;
1077 for (let index = 0; index < lengthToCover; index++) {
1078 const countAtIndex = this.getCountAtIndex(index);
1079 if (countAtIndex > 0) {
1080 observedTotalCount += countAtIndex;
1081 maxIndex = index;
1082 if (minNonZeroIndex == -1 && index != 0) {
1083 minNonZeroIndex = index;
1084 }
1085 }
1086 }
1087 if (maxIndex >= 0) {
1088 this.updatedMaxValue(
1089 this.highestEquivalentValue(this.valueFromIndex(maxIndex))
1090 );
1091 }
1092 if (minNonZeroIndex >= 0) {
1093 this.updateMinNonZeroValue(this.valueFromIndex(minNonZeroIndex));
1094 }
1095 this.setTotalCount(observedTotalCount);
1096 }
1097
1098 reset() {
1099 this.clearCounts();
1100 this.setTotalCount(0);
1101 this.startTimeStampMsec = 0;
1102 this.endTimeStampMsec = 0;
1103 this.tag = NO_TAG;
1104 this.maxValue = 0;
1105 this.minNonZeroValue = Number.MAX_SAFE_INTEGER;
1106 }
1107
1108 destroy() {
1109 // no op - not needed here
1110 }
1111}
1112
1113export { JsHistogram as default };
Note: See TracBrowser for help on using the repository browser.