View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.geometry.examples.jmh.euclidean;
18  
19  import java.util.List;
20  import java.util.concurrent.TimeUnit;
21  
22  import org.apache.commons.geometry.euclidean.twod.LineConvexSubset;
23  import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
24  import org.apache.commons.geometry.euclidean.twod.Vector2D;
25  import org.apache.commons.geometry.euclidean.twod.shape.Circle;
26  import org.apache.commons.numbers.core.Precision;
27  import org.openjdk.jmh.annotations.Benchmark;
28  import org.openjdk.jmh.annotations.BenchmarkMode;
29  import org.openjdk.jmh.annotations.Fork;
30  import org.openjdk.jmh.annotations.Level;
31  import org.openjdk.jmh.annotations.Measurement;
32  import org.openjdk.jmh.annotations.Mode;
33  import org.openjdk.jmh.annotations.OutputTimeUnit;
34  import org.openjdk.jmh.annotations.Param;
35  import org.openjdk.jmh.annotations.Scope;
36  import org.openjdk.jmh.annotations.Setup;
37  import org.openjdk.jmh.annotations.State;
38  import org.openjdk.jmh.annotations.Warmup;
39  
40  /** Benchmarks for the {@link RegionBSPTree2D} class.
41   */
42  @BenchmarkMode(Mode.AverageTime)
43  @OutputTimeUnit(TimeUnit.NANOSECONDS)
44  @Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
45  @Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
46  @Fork(value = 1, jvmArgs = {"-server", "-Xms512M", "-Xmx512M"})
47  public class RegionBSPTree2DPerformance {
48  
49      /** Base class for inputs that use circle approximation boundaries.
50       */
51      @State(Scope.Thread)
52      public static class CircularBoundaryInputBase {
53  
54          /** The input to use for the segments parameter when generating the circle boundaries. */
55          @Param({"10", "20", "50"})
56          private int segments;
57  
58          /** Compute the boundaries for this instance.
59           * @return the boundaries for this instance
60           */
61          protected List<LineConvexSubset> computeBoundaries() {
62              final Circle circle = Circle.from(Vector2D.ZERO, 1, Precision.doubleEquivalenceOfEpsilon(1e-10));
63              return circle.toTree(segments).getBoundaries();
64          }
65      }
66  
67      /** Class providing a list of boundaries for a circle approximation.
68       */
69      @State(Scope.Thread)
70      public static class CircularBoundaryInput extends CircularBoundaryInputBase {
71  
72          /** List containing the convex boundaries of the circle approximation. */
73          private List<LineConvexSubset> boundaries;
74  
75          /** Set up the instance for the benchmark. */
76          @Setup(Level.Iteration)
77          public void setup() {
78              boundaries = computeBoundaries();
79          }
80  
81          /** Get the computed circle boundaries.
82           * @return the computed circle boundaries
83           */
84          public List<LineConvexSubset> getBoundaries() {
85              return boundaries;
86          }
87      }
88  
89      /** Class providing a region approximating a circular boundary. The region is in a worst-case
90       * tree structure, meaning that the tree is completely unbalanced.
91       */
92      @State(Scope.Thread)
93      public static class WorstCaseCircularRegionInput extends CircularBoundaryInputBase {
94  
95          /** Tree containing the circle approximation. */
96          private RegionBSPTree2D tree;
97  
98          /** Set up the instance for the benchmark. */
99          @Setup(Level.Iteration)
100         public void setup() {
101             tree = RegionBSPTree2D.empty();
102             tree.insert(computeBoundaries());
103         }
104 
105         /** Get the computed circle approximation tree.
106          * @return the computed circle approximation tree.
107          */
108         public RegionBSPTree2D getTree() {
109             return tree;
110         }
111     }
112 
113     /** Benchmark testing the performance of tree creation for a convex region. The insertion
114      * behavior is worst-case, meaning that the tree is unbalanced and degenerates into a simple
115      * list of nodes.
116      * @param input benchmark boundary input
117      * @return created BSP tree
118      */
119     @Benchmark
120     public RegionBSPTree2D insertConvexWorstCase(final CircularBoundaryInput input) {
121         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
122 
123         for (final LineConvexSubset boundary : input.getBoundaries()) {
124             tree.insert(boundary);
125         }
126 
127         return tree;
128     }
129 
130     /** Benchmark testing the performance of boundary determination using a tree with a worst-case,
131      * unbalanced structure.
132      * @param input input tree
133      * @return list of tree boundaries
134      */
135     @Benchmark
136     public List<LineConvexSubset> boundaryConvexWorstCase(final WorstCaseCircularRegionInput input) {
137         return input.getTree().getBoundaries();
138     }
139 }