perf_hooks: implement qrde analysis support in Histogram · nodejs/node@6b3e6f9 · GitHub
Skip to content

Commit 6b3e6f9

Browse files
jasnelladuh95
authored andcommitted
perf_hooks: implement qrde analysis support in Histogram
Implements quantile-respectful density estimate calcuation on Histogram. Helps with tail-focused latency analysis without retaining raw samples. Baking this directly into Node.js, based on a 1 million sample, 1k bin workload, this impl is roughly 150-325x faster than performing the equivalent in Rscript. Signed-off-by: James M Snell <jasnell@gmail.com> Assisted-by: Opencode PR-URL: #65806 Reviewed-By: Matteo Collina <matteo.collina@gmail.com>
1 parent 047d7c5 commit 6b3e6f9

10 files changed

Lines changed: 1480 additions & 41 deletions

File tree

Lines changed: 37 additions & 0 deletions

‎doc/api/perf_hooks.md‎

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2427,6 +2427,82 @@ Returns the values at the specified percentiles, computed in a single
24272427
efficient pass over the histogram data. More efficient than calling
24282428
`histogram.percentile()` multiple times.
24292429

2430+
### `histogram.qrde([options])`
2431+
2432+
<!-- YAML
2433+
added: REPLACEME
2434+
-->
2435+
2436+
* `options` {Object}
2437+
* `bins` {number} The number of equal-probability density bins to return.
2438+
Must be between 1 and 1000. Cannot be used with `probabilities`.
2439+
**Default:** `100`.
2440+
* `probabilities` {number\[]} Custom probability boundaries. The array must
2441+
contain between 2 and 1001 strictly increasing values, start with `0`, and
2442+
end with `1`. Cannot be used with `bins`.
2443+
* `dequantize` {string} Controls whether repeated bucket values are spread
2444+
deterministically over their equivalent-value ranges. May be `'none'`,
2445+
`'hdr'`, or `'all'`. **Default:** `'hdr'`.
2446+
* `cache` {boolean} When `true`, retains the expanded histogram snapshot for
2447+
reuse by subsequent calls with `cache: true`. The snapshot is invalidated
2448+
when the histogram is modified. **Default:** `false`.
2449+
* Returns: {Promise} Fulfills with an {Object} containing:
2450+
* `probabilities` {Float64Array} The probability boundaries used by the
2451+
estimate.
2452+
* `quantiles` {Float64Array} The quantiles at the probability boundaries.
2453+
* `densities` {Float64Array} The density within each quantile interval.
2454+
* `count` {bigint} The number of values in the histogram snapshot.
2455+
* `bucketCount` {number} The number of occupied HDR buckets.
2456+
* `corrections` {number} The number of non-monotonic floating-point results
2457+
that were clamped to the preceding quantile.
2458+
* `dequantize` {string} The selected dequantization mode.
2459+
2460+
Returns a quantile-respectful density estimate based on the Harrell-Davis
2461+
quantile estimator. By default, `bins` generates equal probability boundaries.
2462+
The `probabilities` option can instead focus the estimate on regions such as
2463+
p90, p99, p99.9, and p99.99. The density for interval `i` contains probability
2464+
mass `probabilities[i + 1] - probabilities[i]`. The histogram is snapshotted
2465+
when the method is called. Snapshot expansion and the estimate are calculated
2466+
in the libuv thread pool. Highly concentrated beta weights use a second-order
2467+
asymptotic approximation to avoid numerical convergence loss at large sample
2468+
counts.
2469+
2470+
Setting `cache` to `true` avoids repeating snapshot capture and expansion when
2471+
several estimates are requested from an unchanged histogram. The retained
2472+
snapshot uses memory proportional to the number of occupied HDR buckets and is
2473+
released when the histogram is next modified.
2474+
2475+
QRDE temporarily uses approximately one additional HDR count array plus 32
2476+
bytes per occupied bucket. With `cache: true`, the expanded 32-byte-per-bucket
2477+
snapshot remains allocated. The following estimates use `lowest: 1` and
2478+
`highest: Number.MAX_SAFE_INTEGER` and exclude allocator and JavaScript object
2479+
overhead:
2480+
2481+
| `figures` | Histogram | Maximum expanded snapshot | Peak cache-miss QRDE |
2482+
| --------- | --------: | ------------------------: | -------------------: |
2483+
| 1 | 6.3 KiB | 25 KiB | 31 KiB |
2484+
| 2 | 47 KiB | 188 KiB | 235 KiB |
2485+
| 3 | 352 KiB | 1.4 MiB | 1.7 MiB |
2486+
| 4 | 5.0 MiB | 20 MiB | 25 MiB |
2487+
| 5 | 37 MiB | 148 MiB | 185 MiB |
2488+
2489+
The maximum snapshot column assumes every representable bucket is occupied.
2490+
Lower `highest` values reduce histogram and temporary copy sizes. Concurrent
2491+
calls that miss the cache each require their own temporary copy and expanded
2492+
snapshot.
2493+
2494+
HDR histograms aggregate observations into equivalent-value buckets. The
2495+
`'hdr'` dequantization mode models repeated values in buckets wider than one
2496+
unit as a continuous uniform distribution over the bucket resolution. This
2497+
reduces density artifacts introduced by HDR quantization while preserving
2498+
repeated unit-resolution values as point masses. The `'all'` mode also
2499+
dequantizes repeated unit-resolution values. Use `'none'` to calculate the
2500+
grouped Harrell-Davis estimator using bucket midpoints directly.
2501+
2502+
An empty histogram returns the requested `probabilities` but produces empty
2503+
`quantiles` and `densities` arrays. A non-dequantized interval whose quantile
2504+
boundaries are equal has an infinite density.
2505+
24302506
### `histogram.reset()`
24312507

24322508
<!-- YAML

‎lib/internal/histogram.js‎

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -33,9 +33,11 @@ const {
3333

3434
const {
3535
validateArray,
36+
validateBoolean,
3637
validateInteger,
3738
validateNumber,
3839
validateObject,
40+
validateOneOf,
3941
} = require('internal/validators');
4042

4143
const {
@@ -45,6 +47,7 @@ const {
4547
const kDestroy = Symbol('kDestroy');
4648
const kHandle = Symbol('kHandle');
4749
const kRecordable = Symbol('kRecordable');
50+
const kQrdeDequantizationModes = ['none', 'hdr', 'all'];
4851

4952
const {
5053
kClone,
@@ -594,6 +597,73 @@ class Histogram {
594597
return map;
595598
}
596599

600+
/**
601+
* Builds a quantile-respectful density estimate using Harrell-Davis
602+
* quantiles. Values can be spread deterministically within their HDR
603+
* equivalent-value ranges to reduce quantization artifacts.
604+
* @param {{ bins?: number, probabilities?: number[],
605+
* dequantize?: 'none'|'hdr'|'all', cache?: boolean }} [options]
606+
* @returns {Promise<{
607+
* probabilities: Float64Array,
608+
* quantiles: Float64Array,
609+
* densities: Float64Array,
610+
* count: bigint,
611+
* bucketCount: number,
612+
* corrections: number,
613+
* dequantize: 'none'|'hdr'|'all',
614+
* }>}
615+
*/
616+
qrde(options = kEmptyObject) {
617+
if (!isHistogram(this))
618+
throw new ERR_INVALID_THIS('Histogram');
619+
validateObject(options, 'options');
620+
const { bins, probabilities, dequantize = 'hdr', cache = false } = options;
621+
if (bins !== undefined && probabilities !== undefined) {
622+
throw new ERR_INVALID_ARG_VALUE(
623+
'options', options, '"bins" and "probabilities" are mutually exclusive');
624+
}
625+
626+
let boundaries;
627+
if (probabilities === undefined) {
628+
const binCount = bins ?? 100;
629+
validateInteger(binCount, 'options.bins', 1, 1000);
630+
boundaries = new Float64Array(binCount + 1);
631+
for (let i = 0; i <= binCount; i++) boundaries[i] = i / binCount;
632+
} else {
633+
validateArray(probabilities, 'options.probabilities', 2);
634+
const length = probabilities.length;
635+
if (length > 1001) {
636+
throw new ERR_OUT_OF_RANGE(
637+
'options.probabilities.length', '>= 2 && <= 1001', length);
638+
}
639+
640+
boundaries = new Float64Array(length);
641+
let previous = -1;
642+
for (let i = 0; i < length; i++) {
643+
const probability = probabilities[i];
644+
validateNumber(probability, `options.probabilities[${i}]`, 0, 1);
645+
if (probability <= previous) {
646+
throw new ERR_INVALID_ARG_VALUE(
647+
'options.probabilities', probabilities, 'must be strictly increasing');
648+
}
649+
boundaries[i] = probability;
650+
previous = probability;
651+
}
652+
if (boundaries[0] !== 0 || boundaries[length - 1] !== 1) {
653+
throw new ERR_INVALID_ARG_VALUE(
654+
'options.probabilities', probabilities, 'must start with 0 and end with 1');
655+
}
656+
}
657+
658+
validateOneOf(dequantize,
659+
'options.dequantize', kQrdeDequantizationModes);
660+
validateBoolean(cache, 'options.cache');
661+
let mode = 0;
662+
if (dequantize === 'hdr') mode = 1;
663+
else if (dequantize === 'all') mode = 2;
664+
return this[kHandle]?.qrde(boundaries, mode, cache);
665+
}
666+
597667
/**
598668
* @returns {void}
599669
*/

‎src/histogram-inl.h‎

Lines changed: 19 additions & 5 deletions

0 commit comments

Comments
 (0)