Repository navigation
Could binning millions of values be faster? #454
Description
Activity
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".
Reacted by Yuri, Mike Bostock and Toph Tucker- added 2 commits that reference this issue
on Apr 1, 2022 Fixed by d3/d3-array#220.
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.
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:
Line 337 in a946fd9
Which is getting called here:
Line 168 in a946fd9
Line 171 in a946fd9
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.).
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.