search

d3 / d3-delaunay

Compute the Voronoi diagram of a set of two-dimensional points.
https://d3js.org/d3-delaunay
ISC License
611 stars 57 forks source link

Severe performance regression with delaunay.find since v4.1.0 #76

Closed mourner closed 5 years ago

mourner commented 5 years ago

@mbostock I just tried upgrading https://observablehq.com/@mbostock/voronoi-stippling to newer versions of d3-delaunay and discovered that it gets really slow since v4.1.0 (but is fast with v4.0.2) — apparently https://github.com/d3/d3-delaunay/commit/abb0fd830bc99f75ce2699be44d576cb8e5673b2 caused a severe regression of delaunay.find performance (profiling shows it taking most of the worker time). I wonder what's going on here. Could the way we use a generator cause this? cc @Fil

mourner commented 5 years ago

Damn, if I change neighbors to be a regular function that returns an array (rather than a generator), it gets much faster, so it is indeed caused by using a generator unfortunately. I've added a bench script to explore this in https://github.com/d3/d3-delaunay/commit/02dfd85373496d576fd2206858b549717ced9904

Results (10 iterations, total time):

Since find is a building block of many algorithms and is often on a hot path, I would suggest rewriting _step to inline iteration over neighbors (avoiding both a generator and allocating neighbor arrays), even if this means duplicating code.

But generally, I think we might want to get rid of generators in the library and release a new major version — performance concerns overweight generator convenience in algorithmic libraries like this IMO. As a side benefit, this would make it ES5-compatible.

Fil commented 5 years ago

tbh I don't see a speed difference in any browser (tested with Safari, FF and Chrome on MacOS): https://observablehq.com/d/a14108eadf908ea4

my mistake — indeed there is a 4x difference.

mourner commented 5 years ago

I tested it out on the stippling notebook — works fast now with v5.1.1 https://observablehq.com/d/16e9be3e70ccefe5