Could binning millions of values be faster?

[mbostock]

Currently the bin transform can be slow (several seconds) when binning millions of values. Since rendering is fast (when there are only a few bins), the data transform dwarfs the rendering cost and this might be a good candidate for optimization. For example, if the bin thresholds are uniformly-spaced, and dense, can we use quantization instead of bisection to create the bins?

This is arguably an issue for d3-array (d3.bin) instead of Plot, but there might be other smarts we can do in Plot, so I figured I would start with an issue here.

Related #451.

[Fil]

I've tested quantization in d3-array: it's about 10 lines of code, and almost 2x faster on an array of 30 million values with 1000 bins. See d3/d3-array#220 and d3p at https://observablehq.com/@d3/faster-bins-454

However, if the only reduction we do afterwards is to a length, we've wasted a lot of memory trying to keep track of the bin's contents, pushing each value into its bin. By just incrementing an object {x0, x1, length: 0}, we are 5x faster than the original. See d3l at https://observablehq.com/@d3/faster-bins-454

Of course with d3l we lose any possibility of reducing the binned data beyond returning its length, so integrating this approach seems to require a bit more code, like a specific code path for "binning numbers uniformly and getting a count".

[mbostock]

Nice work @Fil!

[mbostock]

Fixed by d3/d3-array#220.

[mbostock]

There still seem to be plenty of cases where grouping is orders of magnitude faster than binning; we could have a heuristic to switch to grouping under the hood to optimize. For example, with 1.2M observations, this takes ~300 ms:

Plot.plot({
  y: {
    transform: d => d / 1000
  },
  marks: [
    Plot.line(data, Plot.groupX({y: "max"}, {x: d => d3.utcMonth(d.dateTime), y: "value"})),
    Plot.ruleY([0])
  ]
})

but this takes ~15.2 seconds:

Plot.plot({
  y: {
    transform: d => d / 1000
  },
  marks: [
    Plot.line(data, Plot.binX({y: "max"}, {x: "dateTime", y: "value", thresholds: d3.utcMonth})),
    Plot.ruleY([0])
  ]
})

And even this, which should be using the “fast” path of quantization, still takes ~12 seconds:

Plot.plot({
  y: {
    transform: d => d / 1000
  },
  marks: [
    Plot.line(data, Plot.binX({y: "max"}, {
      x: d => d.dateTime.getUTCFullYear() * 12 + d.dateTime.getUTCMonth(),
      y: "value",
      interval: 1
    })),
    Plot.ruleY([0])
  ]
})

So we should investigate and look for further performance improvements when binning.

There also should be some improvements possible if we avoid materializing the binned data; in most cases we only need the reduced aggregates only.

Examples: https://observablehq.com/d/e4668f3ec01c184ca

[mbostock]

Simple test case that takes ~7 seconds to bin:

import * as Plot from "@observablehq/plot";

const dates = new Array(1e6);
const start = +new Date("2020-01-01");
const end = +new Date("2021-01-01");
for (let i = 0; i < dates.length; ++i) dates[i] = new Date(Math.random() * (end - start) + start);

export async function bin1m() {
  return Plot.plot({
    marks: [
      Plot.rectY(dates, Plot.binX())
    ]
  });
}

Looks like most of the work is happening here:

plot/src/transforms/bin.js

Line 337 in a946fd9

return [x0, x1, set.size ? (I) => I.filter(set.has, set) : binempty];

Which is getting called here:

plot/src/transforms/bin.js

Line 168 in a946fd9

const bb = fx(g);

plot/src/transforms/bin.js

Line 171 in a946fd9

const b = fy(bb);

I suspect things are slow because we’re basically precomputing the bins as a Set, and then filtering the index against the bins. I’m guessing we probably just want to avoid d3.bin entirely and apply a different strategy within Plot (since we support two-dimensional, cumulative binning, faceting, etc.).

[mbostock]

#1225 improves the performance from ~15 seconds to ~300 ms, which seems much better!