Benchmark of Node.js Histogram Libraries

README.md

Benchmark of Node.js Histogram Libraries

This benchmark compares the following libraries:

• metrics@0.1.20 + mikejihbe/metrics#67
• measured-core@1.40.1
• hdr-histogram-js@1.1.4
• native-hdr-histogram@0.5.0

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.

metrics-vs-hdr.js

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}%`);
    }
  }
}