We can see a significant speedup on the already-impressive performance if we just change the way we represent the underlying coordinates.
Instead of having a single array that we've flattened our points into, we have two parallel arrays that each store x & y coordinates. The algorithm is otherwise unchanged.
Combining all the categories in the benchmark, this nearly doubles the speed of the library - an average of %98.5 faster
This eliminates all of the operations involved with calculating the proper index - (2 * e), (2 * e + 1) sort of thing. now, x and y coordinates will always be at the same index in both arrays. This should be both easier to work with and faster.
I discovered this optimization in the process of trying to port delaunator to C# / Unity - I wanted to modify the implementation in JS first to make it easier to translate. My port doesn't work right yet, but it doesn't seem too far off.
All tests were run on a 2018 Razer Blade with an intel i7-8750H cpu, using node.js v10.15.0.
"before" results were tested on current master branch of delaunator, "after" on this branch.
Performance Comparison
uniform:
20000 average: before 11.8ms, after 5.318ms - 122% faster
1000000 average: before 938.27ms, after 466.973ms - %100 faster
gaussian:
20000: before 10.405ms, after 4.787ms - %117 faster
1000000: before 899.979ms, after 459.642ms - %96 faster
grid:
20000 average: before 9.665ms, after 5.528ms - 75% faster
1000000 average: before 835.14ms, after 499.08ms - 67% faster
degenerate:
20000 average: before 4.638ms, after 3.05ms- 52% faster
1000000 average: before 323.286ms, after 124.749ms - %159 faster
per-run benchmark results can be seen at this Gist
We can see a significant speedup on the already-impressive performance if we just change the way we represent the underlying coordinates.
Instead of having a single array that we've flattened our points into, we have two parallel arrays that each store x & y coordinates. The algorithm is otherwise unchanged.
Combining all the categories in the benchmark, this nearly doubles the speed of the library - an average of %98.5 faster
This eliminates all of the operations involved with calculating the proper index -
(2 * e), (2 * e + 1)sort of thing. now, x and y coordinates will always be at the same index in both arrays. This should be both easier to work with and faster.I discovered this optimization in the process of trying to port
delaunatorto C# / Unity - I wanted to modify the implementation in JS first to make it easier to translate. My port doesn't work right yet, but it doesn't seem too far off.All tests were run on a 2018 Razer Blade with an intel i7-8750H cpu, using node.js
v10.15.0."before" results were tested on current master branch of delaunator, "after" on this branch.
Performance Comparison
uniform:
20000 average: before 11.8ms, after 5.318ms - 122% faster
1000000 average: before 938.27ms, after 466.973ms - %100 faster
gaussian:
20000: before 10.405ms, after 4.787ms - %117 faster
1000000: before 899.979ms, after 459.642ms - %96 faster
grid:
20000 average: before 9.665ms, after 5.528ms - 75% faster
1000000 average: before 835.14ms, after 499.08ms - 67% faster
degenerate:
20000 average: before 4.638ms, after 3.05ms- 52% faster
1000000 average: before 323.286ms, after 124.749ms - %159 faster
per-run benchmark results can be seen at this Gist