Instantly share code, notes, and snippets.

@shuhei /README.md
Last active Dec 29, 2018

Embed
What would you like to do?
Benchmark of Node.js Histogram Libraries

Benchmark of Node.js Histogram Libraries

This benchmark compares the following libraries:

of:

  • adding values to the histogram
  • extracting percentiles from the histogram

Result

On my Macbook Air Early 2015, 2,2 GHz Intel Core i7:

$ node -v
v10.14.2
$ node metrics-vs-hdr.js
metrics add x 173 ops/sec ±2.00% (80 runs sampled)
measured add x 421 ops/sec ±1.19% (90 runs sampled)
hdr add x 1,769 ops/sec ±1.84% (92 runs sampled)
native hdr add x 1,516 ops/sec ±0.82% (92 runs sampled)
metrics percentiles x 1,721 ops/sec ±1.93% (92 runs sampled)
measured percentiles x 3,709 ops/sec ±0.78% (93 runs sampled)
measured weighted percentiles x 2,383 ops/sec ±1.30% (90 runs sampled)
hdr percentiles x 3,509 ops/sec ±0.61% (93 runs sampled)
native hdr percentiles x 2,760 ops/sec ±0.76% (93 runs sampled)
metrics
  p1: expected 32.78451876557936, actual 34.32360857117004, diff +4.694562749557829%
  p5: expected 113.90993657780048, actual 154.41298708426586, diff +35.55708283517637%
  p10: expected 242.85610202982733, actual 298.3053114422007, diff +22.832125258093445%
  p25: expected 722.1497061761282, actual 828.6797102043815, diff +14.751789430524427%
  p50: expected 1913.49019820661, actual 2040.5304152241363, diff +6.639188282050919%
  p75: expected 3852.203208877553, actual 3905.4413978810426, diff +1.382019226836215%
  p90: expected 5830.608344799762, actual 5662.430472651247, diff +2.884396656457123%
measured
  p0.1: expected 21.218494204025724, actual 20.27356218358636, diff +4.453341558328321%
  p1: expected 32.78451876557936, actual 29.82512303951269, diff +9.026808498326206%
  p5: expected 113.90993657780048, actual 92.92786178859731, diff +18.419881021417662%
  p10: expected 242.85610202982733, actual 203.45593783044987, diff +16.22366655400669%
  p25: expected 722.1497061761282, actual 565.8805327719571, diff +21.639442911586258%
  p50: expected 1913.49019820661, actual 1829.6051828705563, diff +4.383874838484868%
  p75: expected 3852.203208877553, actual 3738.844210310594, diff +2.9427055744546107%
  p90: expected 5830.608344799762, actual 5672.390172207577, diff +2.713579153936779%
  p95: expected 7053.6497348847715, actual 6838.165767996919, diff +3.0549286537740494%
  p98: expected 8118.946801196526, actual 8020.978761400429, diff +1.2066594620580517%
  p99: expected 8705.182961136283, actual 8452.757208313868, diff +2.899717949058089%
measured weighted
  p0.1: expected 21.218494204025724, actual 23.45278614539394, diff +10.529926958456413%
  p1: expected 32.78451876557936, actual 39.99264716813243, diff +21.986378552919085%
  p5: expected 113.90993657780048, actual 348.03758579263103, diff +205.53751169453193%
  p10: expected 242.85610202982733, actual 406.971425557188, diff +67.5771875426067%
  p25: expected 722.1497061761282, actual 3801.7963411950545, diff +426.45543004178944%
  p50: expected 1913.49019820661, actual 4515.103377664744, diff +135.96166742303964%
  p75: expected 3852.203208877553, actual 4515.103377664744, diff +17.208338523251086%
  p90: expected 5830.608344799762, actual 4515.103377664744, diff +22.56205338004393%
  p95: expected 7053.6497348847715, actual 4516.832774174043, diff +35.96460068274385%
  p98: expected 8118.946801196526, actual 5474.484696523862, diff +32.57149196103783%
  p99: expected 8705.182961136283, actual 6578.167964548056, diff +24.43389192489285%
  p99.9: expected 9555.493013254609, actual 8995.441611545473, diff +5.861041402387897%
hdr
  p0.1: expected 21.218494204025724, actual 21, diff +1.0297347301123272%
  p1: expected 32.78451876557936, actual 32, diff +2.3929549528816847%
native hdr
  p0.1: expected 21.218494204025724, actual 21, diff +1.0297347301123272%
  p1: expected 32.78451876557936, actual 32, diff +2.3929549528816847%
done

Accuracy

  • hdr-histogram-js and native-hdr-histogram were most accurate. All percentiles errors of less than 1% except small percentiles. Small percentiles had ~2% of errors because the HDR histograms store only integer while the values used in the benchmark were floating point numbers.
  • measured's weighted percentiles were least accurate.

Performance

  • For adding values, hdr-histogram-js performed best.
  • For extracting percentiles, measured performed best and hdr-histogram-js performed 2nd best. hdr-histogram-js performed better with smaller number of percentiles because its percentile calculation is done per percentile while EDS-based histogram sorts the samples once for all percentiles.

Conclusion

  • hdr-histogram-js is accurate and performs good.
  • I don't see a point to use native-hdr-histogram because hdr-histogram-js performs better.
const assert = require("assert");
const Benchmark = require("benchmark");
const hdr = require("hdr-histogram-js");
const nativeHdr = require("native-hdr-histogram");
const metrics = require("metrics");
const BinaryHeap = require("metrics/lib/binary_heap");
const measured = require("measured-core");
// https://github.com/mikejihbe/metrics/pull/67
BinaryHeap.prototype.clone = function() {
var heap = new BinaryHeap(this.scoreFunction);
heap.content = this.content.slice();
return heap;
};
// The percentiles that are used by "metrics" library by default.
const PERCENTILES = [
0.001,
0.01,
0.05,
0.1,
0.25,
0.5,
0.75,
0.9,
0.95,
0.98,
0.99,
0.999
];
// Prepare a stable set of values for the benchmark.
const values = [];
for (let i = 0; i < 10000; i++) {
values.push(20 + Math.random() * Math.random() * 10000);
}
const sortedValues = values.slice().sort((a, b) => (a - b));
const realPercentiles = {};
for (let i = 0; i < PERCENTILES.length; i++) {
const percentile = PERCENTILES[i];
const pos = percentile * sortedValues.length;
assert.equal(Math.floor(pos), pos);
assert(pos > 0);
assert(pos < sortedValues.length);
realPercentiles[percentile] = sortedValues[pos - 1];
}
// Prepare histograms.
const metricsHistogram = new metrics.Histogram();
const measuredHistogram = new measured.Histogram();
const hdrHistogram = hdr.build();
const nativeHdrHistogram = new nativeHdr(1, 20000);
let a;
let b;
let c;
let d;
let e;
const suite = new Benchmark.Suite();
suite
.add("metrics add", () => {
metricsHistogram.clear();
for (let i = 0; i < values.length; i++) {
metricsHistogram.update(values[i]);
}
})
.add("measured add", () => {
measuredHistogram.reset();
for (let i = 0; i < values.length; i++) {
measuredHistogram.update(values[i]);
}
})
.add("hdr add", () => {
hdrHistogram.reset();
for (let i = 0; i < values.length; i++) {
hdrHistogram.recordValue(values[i]);
}
})
.add("native hdr add", () => {
nativeHdrHistogram.reset();
for (let i = 0; i < values.length; i++) {
nativeHdrHistogram.record(values[i]);
}
})
.add("metrics percentiles", () => {
a = metricsHistogram.percentiles(PERCENTILES);
})
.add("measured percentiles", () => {
d = measuredHistogram._percentiles(PERCENTILES);
})
.add("measured weighted percentiles", () => {
e = measuredHistogram.weightedPercentiles(PERCENTILES);
})
.add("hdr percentiles", () => {
// Create the same result object as "metrics"
const result = {};
for (let i = 0; i < PERCENTILES.length; i++) {
const percentile = PERCENTILES[i];
result[percentile] = hdrHistogram.getValueAtPercentile(percentile * 100);
}
b = result;
})
.add("native hdr percentiles", () => {
const result = {};
for (let i = 0; i < PERCENTILES.length; i++) {
const percentile = PERCENTILES[i];
result[percentile] = nativeHdrHistogram.percentile(percentile * 100);
}
c = result;
})
.on("cycle", function(event) {
console.log(String(event.target));
})
.on("complete", function() {
checkPercentiles("metrics", a);
checkPercentiles("measured", d);
checkPercentiles("measured weighted", e);
checkPercentiles("hdr", b);
checkPercentiles("native hdr", c);
console.log("done");
})
.run();
function checkPercentiles(name, percentiles) {
console.log(name);
for (let i = 0; i < PERCENTILES.length; i++) {
const percentile = PERCENTILES[i];
const actual = percentiles[percentile];
const expected = realPercentiles[percentile];
const diff = Math.abs(percentiles[percentile] - realPercentiles[percentile]) * 100 / realPercentiles[percentile];
// Show the diff if the diff is more than 1%.
if (Math.abs(diff) > 1) {
const withSymbol = diff > 0 ? `+${diff}` : `${diff}`;
console.log(` p${percentile * 100}: expected ${expected}, actual ${actual}, diff ${withSymbol}%`);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment