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.ArrayList;
    20  import java.util.List;
    21  import java.util.concurrent.TimeUnit;
    22  import java.util.function.DoubleSupplier;
    23  import java.util.function.Function;
    24  import java.util.function.ToDoubleFunction;
    25  import java.util.function.UnaryOperator;
    26
    27  import org.apache.commons.geometry.core.Vector;
    28  import org.apache.commons.geometry.euclidean.oned.Vector1D;
    29  import org.apache.commons.geometry.euclidean.threed.Vector3D;
    30  import org.apache.commons.geometry.euclidean.twod.Vector2D;
    31  import org.apache.commons.rng.UniformRandomProvider;
    32  import org.apache.commons.rng.sampling.distribution.ZigguratNormalizedGaussianSampler;
    33  import org.apache.commons.rng.simple.RandomSource;
    34  import org.openjdk.jmh.annotations.Benchmark;
    35  import org.openjdk.jmh.annotations.BenchmarkMode;
    36  import org.openjdk.jmh.annotations.Fork;
    37  import org.openjdk.jmh.annotations.Level;
    38  import org.openjdk.jmh.annotations.Measurement;
    39  import org.openjdk.jmh.annotations.Mode;
    40  import org.openjdk.jmh.annotations.OutputTimeUnit;
    41  import org.openjdk.jmh.annotations.Param;
    42  import org.openjdk.jmh.annotations.Scope;
    43  import org.openjdk.jmh.annotations.Setup;
    44  import org.openjdk.jmh.annotations.State;
    45  import org.openjdk.jmh.annotations.Warmup;
    46  import org.openjdk.jmh.infra.Blackhole;
    47
    48  /**
    49   * Benchmarks for the Euclidean vector classes.
    50   */
    51  @BenchmarkMode(Mode.AverageTime)
    52  @OutputTimeUnit(TimeUnit.NANOSECONDS)
    53  @Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
    54  @Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
    55  @Fork(value = 1, jvmArgs = {"-server", "-Xms512M", "-Xmx512M"})
    56  public class VectorPerformance {
    57
    58      /**
    59       * An array of edge numbers that will produce edge case results from functions:
    60       * {@code +/-inf, +/-max, +/-min, +/-0, nan}.
    61       */
    62      private static final double[] EDGE_NUMBERS = {
    63          Double.POSITIVE_INFINITY, Double.NEGATIVE_INFINITY, Double.MAX_VALUE,
    64          -Double.MAX_VALUE, Double.MIN_VALUE, -Double.MIN_VALUE, 0.0, -0.0, Double.NaN
    65      };
    66
    67      /** String constant used to request random double values, excluding NaN and infinity. */
    68      private static final String RANDOM = "random";
    69
    70      /** String constant used to request a set of double values capable of vector normalization. These
    71       * values are similar to those in the {@link #RANDOM} type but specifically exclude 0.
    72       */
    73      private static final String NORMALIZABLE = "normalizable";
    74
    75      /** String constant used to request edge-case double values, which includes NaN, infinity, zero,
    76       * and the double min and max values.
    77       */
    78      private static final String EDGE = "edge";
    79
    80      /** Base class for vector inputs.
    81       * @param <V> Vector implementation type
    82       */
    83      @State(Scope.Thread)
    84      public abstract static class VectorInputBase<V extends Vector<V>> {
    85
    86          /** The dimension of the vector. */
    87          private final int dimension;
    88
    89          /** Factory function used to create vectors from arrays of doubles. */
    90          private final Function<double[], V> vectorFactory;
    91
    92          /** The number of vectors in the input list. */
    93          @Param({"100", "10000"})
    94          private int size;
    95
    96          /** The vector for the instance. */
    97          private List<V> vectors;
    98
    99          /** Create a new instance with the vector dimension.
    100          * @param dimension vector dimension
    101          * @param vectorFactory function for creating vectors from double arrays
    102          */
    103         VectorInputBase(final int dimension, final Function<double[], V> vectorFactory) {
    104             this.dimension = dimension;
    105             this.vectorFactory = vectorFactory;
    106         }
    107
    108         /** Set up the instance for the benchmark.
    109          */
    110         @Setup(Level.Iteration)
    111         public void setup() {
    112             vectors = new ArrayList<>(size);
    113
    114             final double[] values = new double[dimension];
    115             final DoubleSupplier doubleSupplier = createDoubleSupplier(getType(),
    116                     RandomSource.create(RandomSource.XO_RO_SHI_RO_128_PP));
    117
    118             for (int i = 0; i < size; ++i) {
    119                 for (int j = 0; j < dimension; ++j) {
    120                     values[j] = doubleSupplier.getAsDouble();
    121                 }
    122
    123                 vectors.add(vectorFactory.apply(values));
    124             }
    125         }
    126
    127         /** Get the input vectors for the instance.
    128          * @return the input vectors for the instance
    129          */
    130         public List<V> getVectors() {
    131             return vectors;
    132         }
    133
    134         /** Get the type of double values to use in the creation of input vectors.
    135          * @return the type of double values to use in the creation of input vectors
    136          */
    137         public abstract String getType();
    138
    139         /** Create a supplier that produces doubles of the given type.
    140          * @param type type of doubles to produce
    141          * @param rng random provider
    142          * @return a supplier that produces doubles of the given type
    143          */
    144         private DoubleSupplier createDoubleSupplier(final String type, final UniformRandomProvider rng) {
    145             switch (type) {
    146             case RANDOM:
    147                 return () -> createRandomDouble(rng);
    148             case NORMALIZABLE:
    149                 final ZigguratNormalizedGaussianSampler sampler = ZigguratNormalizedGaussianSampler.of(rng);
    150                 return () -> {
    151                     double n = sampler.sample();
    152                     return n == 0 ? 0.1 : n; // do not return exactly zero
    153                 };
    154             case EDGE:
    155                 return () -> EDGE_NUMBERS[rng.nextInt(EDGE_NUMBERS.length)];
    156             default:
    157                 throw new IllegalStateException("Invalid input type: " + type);
    158             }
    159         }
    160     }
    161
    162     /** Vector input class producing {@link Vector1D} instances with random
    163      * double values.
    164      */
    165     @State(Scope.Thread)
    166     public static class VectorInput1D extends VectorInputBase<Vector1D> {
    167
    168         /** The type of values to use in the vector. */
    169         @Param({RANDOM, EDGE})
    170         private String type;
    171
    172         /** Default constructor. */
    173         public VectorInput1D() {
    174             super(1, arr -> Vector1D.of(arr[0]));
    175         }
    176
    177         /** {@inheritDoc} */
    178         @Override
    179         public String getType() {
    180             return type;
    181         }
    182     }
    183
    184     /** Vector input class producing {@link Vector1D} instances capable of being normalized.
    185      */
    186     @State(Scope.Thread)
    187     public static class NormalizableVectorInput1D extends VectorInputBase<Vector1D> {
    188
    189         /** Default constructor. */
    190         public NormalizableVectorInput1D() {
    191             super(1, arr -> Vector1D.of(arr[0]));
    192         }
    193
    194         /** {@inheritDoc} */
    195         @Override
    196         public String getType() {
    197             return NORMALIZABLE;
    198         }
    199     }
    200
    201     /** Vector input class producing {@link Vector2D} instances with random
    202      * double values.
    203      */
    204     @State(Scope.Thread)
    205     public static class VectorInput2D extends VectorInputBase<Vector2D> {
    206
    207         /** The type of values to use in the vector. */
    208         @Param({RANDOM, EDGE})
    209         private String type;
    210
    211         /** Default constructor. */
    212         public VectorInput2D() {
    213             super(2, Vector2D::of);
    214         }
    215
    216         /** {@inheritDoc} */
    217         @Override
    218         public String getType() {
    219             return type;
    220         }
    221     }
    222
    223     /** Vector input class producing {@link Vector2D} instances capable of being normalized.
    224      */
    225     @State(Scope.Thread)
    226     public static class NormalizableVectorInput2D extends VectorInputBase<Vector2D> {
    227
    228         /** Default constructor. */
    229         public NormalizableVectorInput2D() {
    230             super(2, Vector2D::of);
    231         }
    232
    233         /** {@inheritDoc} */
    234         @Override
    235         public String getType() {
    236             return NORMALIZABLE;
    237         }
    238     }
    239
    240     /** Vector input class producing {@link Vector2D} instances with random
    241      * double values.
    242      */
    243     @State(Scope.Thread)
    244     public static class VectorInput3D extends VectorInputBase<Vector3D> {
    245
    246         /** The type of values to use in the vector. */
    247         @Param({RANDOM, EDGE})
    248         private String type;
    249
    250         /** Default constructor. */
    251         public VectorInput3D() {
    252             super(3, Vector3D::of);
    253         }
    254
    255         /** {@inheritDoc} */
    256         @Override
    257         public String getType() {
    258             return type;
    259         }
    260     }
    261
    262     /** Vector input class producing {@link Vector3D} instances capable of being normalized.
    263      */
    264     @State(Scope.Thread)
    265     public static class NormalizableVectorInput3D extends VectorInputBase<Vector3D> {
    266
    267         /** Default constructor. */
    268         public NormalizableVectorInput3D() {
    269             super(3, Vector3D::of);
    270         }
    271
    272         /** {@inheritDoc} */
    273         @Override
    274         public String getType() {
    275             return NORMALIZABLE;
    276         }
    277     }
    278
    279     /** Creates a random double number with a random sign and mantissa and a large range for
    280      * the exponent. The numbers will not be uniform over the range.
    281      * @param rng random number generator
    282      * @return the random number
    283      */
    284     private static double createRandomDouble(final UniformRandomProvider rng) {
    285         // Create random doubles using random bits in the sign bit and the mantissa.
    286         // Then create an exponent in the range -64 to 64. Thus the sum product
    287         // of 4 max or min values will not over or underflow.
    288         final long mask = ((1L << 52) - 1) | 1L << 63;
    289         final long bits = rng.nextLong() & mask;
    290         // The exponent must be unsigned so + 1023 to the signed exponent
    291         final long exp = rng.nextInt(129) - 64 + 1023;
    292         return Double.longBitsToDouble(bits | (exp << 52));
    293     }
    294
    295     /** Run a benchmark test on a function that produces a double.
    296      * @param <V> Vector implementation type
    297      * @param input vector input
    298      * @param bh jmh blackhole for consuming output
    299      * @param fn function to call
    300      */
    301     private static <V extends Vector<V>> void testToDouble(final VectorInputBase<V> input, final Blackhole bh,
    302             final ToDoubleFunction<V> fn) {
    303         for (final V vec : input.getVectors()) {
    304             bh.consume(fn.applyAsDouble(vec));
    305         }
    306     }
    307
    308     /** Run a benchmark test on a function that produces a vector.
    309      * @param <V> Vector implementation type
    310      * @param input vector input
    311      * @param bh jmh blackhole for consuming output
    312      * @param fn function to call
    313      */
    314     private static <V extends Vector<V>> void testUnary(final VectorInputBase<V> input, final Blackhole bh,
    315             final UnaryOperator<V> fn) {
    316         for (final V vec : input.getVectors()) {
    317             bh.consume(fn.apply(vec));
    318         }
    319     }
    320
    321     /** Benchmark testing just the overhead of the benchmark harness.
    322      * @param input benchmark state input
    323      * @param bh jmh blackhole for consuming output
    324      */
    325     @Benchmark
    326     public void baseline(final VectorInput1D input, final Blackhole bh) {
    327         testUnary(input, bh, UnaryOperator.identity());
    328     }
    329
    330     /** Benchmark testing the performance of the {@link Vector1D#norm()} method.
    331      * @param input benchmark state input
    332      * @param bh jmh blackhole for consuming output
    333      */
    334     @Benchmark
    335     public void norm1D(final VectorInput1D input, final Blackhole bh) {
    336         testToDouble(input, bh, Vector1D::norm);
    337     }
    338
    339     /** Benchmark testing the performance of the {@link Vector2D#norm()} method.
    340      * @param input benchmark state input
    341      * @param bh jmh blackhole for consuming output
    342      */
    343     @Benchmark
    344     public void norm2D(final VectorInput2D input, final Blackhole bh) {
    345         testToDouble(input, bh, Vector2D::norm);
    346     }
    347
    348     /** Benchmark testing the performance of the {@link Vector3D#norm()} method.
    349      * @param input benchmark state input
    350      * @param bh jmh blackhole for consuming output
    351      */
    352     @Benchmark
    353     public void norm3D(final VectorInput3D input, final Blackhole bh) {
    354         testToDouble(input, bh, Vector3D::norm);
    355     }
    356
    357     /** Benchmark testing the performance of the {@link Vector1D#normalize()} method.
    358      * @param input benchmark state input
    359      * @param bh jmh blackhole for consuming output
    360      */
    361     @Benchmark
    362     public void normalize1D(final NormalizableVectorInput1D input, final Blackhole bh) {
    363         testUnary(input, bh, Vector1D::normalize);
    364     }
    365
    366     /** Benchmark testing the performance of the {@link Vector2D#normalize()}
    367      * method.
    368      * @param input benchmark state input
    369      * @param bh jmh blackhole for consuming output
    370      */
    371     @Benchmark
    372     public void normalize2D(final NormalizableVectorInput2D input, final Blackhole bh) {
    373         testUnary(input, bh, Vector2D::normalize);
    374     }
    375
    376     /** Benchmark testing the performance of the {@link Vector3D#normalize()}
    377      * method.
    378      * @param input benchmark state input
    379      * @param bh jmh blackhole for consuming output
    380      */
    381     @Benchmark
    382     public void normalize3D(final NormalizableVectorInput3D input, final Blackhole bh) {
    383         testUnary(input, bh, Vector3D::normalize);
    384     }
    385 }