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 }