georust / geo

Geospatial primitives and algorithms for Rust
https://crates.io/crates/geo
Other
1.48k stars 191 forks source link

small perf improvements to TriangulateSpade #1122

Closed michaelkirk closed 7 months ago

michaelkirk commented 7 months ago

Bench output:

TriangulateSpade (unconstrained)
                        time:   [8.8442 ms 8.8522 ms 8.8619 ms]
                        change: [-2.9583% -2.7775% -2.6122%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 4 outliers among 100 measurements (4.00%)
  1 (1.00%) high mild
  3 (3.00%) high severe

TriangulateSpade (constrained)
                        time:   [8.9126 ms 8.9274 ms 8.9444 ms]
                        change: [-2.4017% -2.1584% -1.9066%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 3 outliers among 100 measurements (3.00%)
  3 (3.00%) high severe

TriangulateEarcut       time:   [6.9632 ms 6.9750 ms 6.9883 ms]
                        change: [-1.0174% -0.7692% -0.5114%] (p = 0.00 < 0.05)
                        Change within noise threshold.
Found 2 outliers among 100 measurements (2.00%)

Note this is an internal API, so we can safely break the API.

michaelkirk commented 7 months ago

Interested to hear how you came up with it, but lgtm.

When the TriangulateSpade feature was merged, I made a non-blocking suggestion to try something like this. It didn't make it into the original PR, but I decided to give it a shot myself before I forgot.