[
https://issues.apache.org/jira/browse/GEOMETRY-96?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17100846#comment-17100846
]
Matt Juntunen commented on GEOMETRY-96:
---------------------------------------
Here are some before and after benchmarks for worst-case BSP tree boundary
computations.
*Before*
{noformat}
Benchmark (segments) Mode Cnt
Score Error Units
RegionBSPTree2DPerformance.boundaryConvexWorstCase 10 avgt 5
1933.759 ± 161.911 ns/op
RegionBSPTree2DPerformance.boundaryConvexWorstCase 20 avgt 5
3951.823 ± 194.480 ns/op
RegionBSPTree2DPerformance.boundaryConvexWorstCase 50 avgt 5
9716.751 ± 627.596 ns/op
Benchmark (stacksSlices) Mode Cnt
Score Error Units
RegionBSPTree3DPerformance.boundaryConvexWorstCase 5 avgt 5
28785.297 ± 668.225 ns/op
RegionBSPTree3DPerformance.boundaryConvexWorstCase 10 avgt 5
125600.771 ± 5485.010 ns/op
RegionBSPTree3DPerformance.boundaryConvexWorstCase 15 avgt 5
296061.749 ± 7491.620 ns/op
{noformat}
*After*
{noformat}
Benchmark (segments) Mode Cnt
Score Error Units
RegionBSPTree2DPerformance.boundaryConvexWorstCase 10 avgt 5
362.341 ± 2.360 ns/op
RegionBSPTree2DPerformance.boundaryConvexWorstCase 20 avgt 5
710.649 ± 22.730 ns/op
RegionBSPTree2DPerformance.boundaryConvexWorstCase 50 avgt 5
1690.960 ± 51.393 ns/op
Benchmark (stacksSlices) Mode Cnt
Score Error Units
RegionBSPTree3DPerformance.boundaryConvexWorstCase 5 avgt 5
1198.648 ± 198.546 ns/op
RegionBSPTree3DPerformance.boundaryConvexWorstCase 10 avgt 5
4559.114 ± 470.226 ns/op
RegionBSPTree3DPerformance.boundaryConvexWorstCase 15 avgt 5
10954.021 ± 1504.797 ns/op
{noformat}
> Optimize HyperplaneSubset.Builder Implementations
> -------------------------------------------------
>
> Key: GEOMETRY-96
> URL: https://issues.apache.org/jira/browse/GEOMETRY-96
> Project: Apache Commons Geometry
> Issue Type: Improvement
> Reporter: Matt Juntunen
> Priority: Major
> Labels: beta1
>
> The current implementations of {{HyperplaneSubset.Builder}} always use a BSP
> tree in order to build hyperplane subsets. However, in many cases (such as
> when building region BSP tree boundaries), these builders only have a single,
> immutable convex subset added to them. In these cases, the creation of the
> BSP tree is unnecessary and simply adds more overhead to the computation.
> Therefore, we should optimize the builder implementations to only create BSP
> trees when needed, and to simply return the immutable convex subset directly
> if that was the only thing added. This applies to Euclidean 2D and 3D and
> Spherical 2D.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
