source: trip-planner-front/node_modules/hdr-histogram-js/assembly/Histogram.ts@ ceaed42

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

initial commit

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