Closed mourner closed 6 years ago
Not sure why Node benchmarks don't show much difference when doing manual gc()
inside timings, but in Chrome, the difference between master
and this branch (on 1 million uniform case) is quite staggering.
Before:
After:
Also, the memory overhead doesn't seem bad at all — even for int32 coordinates case, it's 15n
vs 18n
, and offset by not having to GC scattered objects constantly. So I think it's definitely worth merging.
I'm a bit late here. I used very similar approach in http://github.com/delfrrr/delaunator-cpp The only difference that I stored struct in a hull (which is a vector) which was keeping indexes to next and prev. instead of pointers; I think it makes no difference for cpp as struct has known size, but @mourner approach must be better for JS. Good change I will try to follow up.
This makes Delaunator faster on cases where the convex hull grows big by avoiding GC churn, which happens because of constant allocation/removal of hull nodes during the algorithm. E.g. degenerate 1 million case went from 720ms to 460ms (and a 10 million degenerate one no longer crashes with out-of-memory error).
The code also becomes easier to port to other languages like Rust because we no longer use object pointers.
As a side effect, instead of using a linked list for the hull, the PR exposes it as a typed array of indices, which is easier to work with, although a breaking change.
A potential drawback might be the need to allocate
Uint32Array(3 * n)
additional memory at the beginning to track the hull, but this should have a negligible effect.@mbostock @fogleman @delfrrr what do you think?