search

d3 / d3-contour

Compute contour polygons using marching squares.
https://d3js.org/d3-contour
ISC License
494 stars 63 forks source link

Improve slow computations for large images #44

Closed hoeck closed 4 years ago

hoeck commented 4 years ago

I'm using this library to discretely compute polygons of swept areas for trucks and semi-trailers in the frontend of a web application.

It works really great, but computing the contour polygons of large images (> 1Megapixels) takes lots of time. For my specific case, at around with around 3MP I need ~10seconds and with 7MP I have to wait around 30seconds to compute the contour of a single-threshold area.

Profiling the code showed that the Array.concat at https://github.com/d3/d3-contour/blob/0606516a3291557e79e9ced553a4d0c5c400981e/src/contours.js#L134 and at https://github.com/d3/d3-contour/blob/master/src/contours.js#L149 is causing lots of GC time and slowing things down by a great margin. This concat is constantly copying a large array just to prepend/append a small number of points.

Replacing this with a simple g.ring.push(...f.ring) improves the performance by 2 to 3 times. Using that push and a more fancy tree-building and flattening when the result is returned in the callback does even more to reduce the strain on the GC and speeds up my 7MP computation almost tenfold.

Though I'm not 100% sure if that change is correct or if the concat was required there for some edge case. Anyway, here is the change, are you interested in a PR?:

https://github.com/hoeck/d3-contour/commit/5e50033135e43a51806d939da2d3dee85ed4f4ae

hoeck commented 4 years ago

After looking at it again, its really just using f.ring.push.apply(f, g.ring); instead of f.ring.concat(g.ring); that makes things noticeably faster. Sorry for the noise.

hoeck commented 4 years ago

As @Fil showed here there is actually no noticeable difference in performance between concat and array.push. I tried to check it myself but couldn't reproduce any speed ups.

Closing this as it seems its more a problem with my specific use case and not with the library in general.