You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ah...@apache.org on 2020/01/14 11:24:28 UTC
[commons-numbers] branch master updated: Add benchmark for sin/cos
computation.
This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-numbers.git
The following commit(s) were added to refs/heads/master by this push:
new 4531ba1 Add benchmark for sin/cos computation.
4531ba1 is described below
commit 4531ba1fecb206f7bd6ecdd7c58ad5ec14a1db95
Author: Alex Herbert <ah...@apache.org>
AuthorDate: Tue Jan 14 11:24:24 2020 +0000
Add benchmark for sin/cos computation.
Computing sin/cos together would improve many of the functions in
Complex. This benchmark investigates the possibility of using the
Commons FastMath implementation instead of java.util.Math.
---
commons-numbers-examples/examples-jmh/pom.xml | 12 +-
.../examples/jmh/complex/SinCosPerformance.java | 261 +++++++++++++++++++++
2 files changed, 272 insertions(+), 1 deletion(-)
diff --git a/commons-numbers-examples/examples-jmh/pom.xml b/commons-numbers-examples/examples-jmh/pom.xml
index 11ce26a..e29bc68 100644
--- a/commons-numbers-examples/examples-jmh/pom.xml
+++ b/commons-numbers-examples/examples-jmh/pom.xml
@@ -34,7 +34,17 @@
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-numbers-complex</artifactId>
- </dependency>
+ </dependency>
+
+ <dependency>
+ <groupId>org.apache.commons</groupId>
+ <artifactId>commons-numbers-core</artifactId>
+ </dependency>
+
+ <dependency>
+ <groupId>org.apache.commons</groupId>
+ <artifactId>commons-math3</artifactId>
+ </dependency>
<dependency>
<groupId>org.openjdk.jmh</groupId>
diff --git a/commons-numbers-examples/examples-jmh/src/main/java/org/apache/commons/numbers/examples/jmh/complex/SinCosPerformance.java b/commons-numbers-examples/examples-jmh/src/main/java/org/apache/commons/numbers/examples/jmh/complex/SinCosPerformance.java
new file mode 100644
index 0000000..778b7cb
--- /dev/null
+++ b/commons-numbers-examples/examples-jmh/src/main/java/org/apache/commons/numbers/examples/jmh/complex/SinCosPerformance.java
@@ -0,0 +1,261 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.commons.numbers.examples.jmh.complex;
+
+import org.apache.commons.math3.util.FastMath;
+import org.apache.commons.numbers.core.Precision;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Param;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Warmup;
+
+import java.util.SplittableRandom;
+import java.util.concurrent.TimeUnit;
+import java.util.function.DoubleSupplier;
+import java.util.function.DoubleUnaryOperator;
+import java.util.function.Supplier;
+import java.util.stream.DoubleStream;
+
+/**
+ * Executes a benchmark to estimate the speed of sin/cos operations.
+ * This compares the Math implementation to FastMath. It would be possible
+ * to adapt FastMath to compute sin/cos together as they both use a common
+ * initial stage to map the value to the domain [0, pi/2).
+ */
+@BenchmarkMode(Mode.AverageTime)
+@OutputTimeUnit(TimeUnit.NANOSECONDS)
+@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
+@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
+@State(Scope.Benchmark)
+@Fork(value = 1, jvmArgs = {"-server", "-Xms512M", "-Xmx512M"})
+public class SinCosPerformance {
+ /**
+ * An array of edge numbers that will produce edge case results from sin/cos functions:
+ * {@code +/-inf, +/-0, nan}.
+ */
+ private static final double[] EDGE_NUMBERS = {
+ Double.POSITIVE_INFINITY, Double.NEGATIVE_INFINITY, 0.0, -0.0, Double.NaN};
+
+ /**
+ * Contains the size of numbers.
+ */
+ @State(Scope.Benchmark)
+ public static class NumberSize {
+ /**
+ * The size of the data.
+ */
+ @Param({"1000"})
+ private int size;
+
+ /**
+ * Gets the size.
+ *
+ * @return the size
+ */
+ public int getSize() {
+ return size;
+ }
+ }
+
+ /**
+ * Contains an array of numbers.
+ */
+ @State(Scope.Benchmark)
+ public static class Numbers extends NumberSize {
+ /** The numbers. */
+ protected double[] numbers;
+
+ /**
+ * The type of the data.
+ */
+ @Param({"pi", "random", "edge"})
+ private String type;
+
+ /**
+ * Gets the numbers.
+ *
+ * @return the numbers
+ */
+ public double[] getNumbers() {
+ return numbers;
+ }
+
+ /**
+ * Create the complex numbers.
+ */
+ @Setup
+ public void setup() {
+ numbers = createNumbers(new SplittableRandom());
+ // Verify functions
+ for (final double x : numbers) {
+ final double sin = Math.sin(x);
+ assertEquals(sin, FastMath.sin(x), 1, () -> "sin " + x);
+ final double cos = Math.cos(x);
+ assertEquals(cos, FastMath.cos(x), 1, () -> "cos " + x);
+ }
+ }
+
+ /**
+ * Creates the numbers.
+ *
+ * @param rng Random number generator.
+ * @return the random number
+ */
+ private double[] createNumbers(SplittableRandom rng) {
+ DoubleSupplier generator;
+ if ("pi".equals(type)) {
+ generator = () -> rng.nextDouble() * 2 * Math.PI - Math.PI;
+ } else if ("random".equals(type)) {
+ generator = () -> createRandomNumber(rng);
+ } else if ("edge".equals(type)) {
+ generator = () -> createEdgeNumber(rng);
+ } else {
+ throw new IllegalStateException("Unknown number type: " + type);
+ }
+ return DoubleStream.generate(generator).limit(getSize()).toArray();
+ }
+
+ /**
+ * Assert the values are equal to the given ulps, else throw an AssertionError.
+ *
+ * @param x the x
+ * @param y the y
+ * @param maxUlps the max ulps for equality
+ * @param msg the message upon failure
+ */
+ private static void assertEquals(double x, double y, int maxUlps, Supplier<String> msg) {
+ if (!Precision.equalsIncludingNaN(x, y, maxUlps)) {
+ throw new AssertionError(msg.get() + ": " + x + " != " + y);
+ }
+ }
+ }
+
+ /**
+ * Creates a random double number with a random sign and mantissa and a large range for
+ * the exponent. The numbers will not be uniform over the range.
+ *
+ * @param rng Random number generator.
+ * @return the random number
+ */
+ private static double createRandomNumber(SplittableRandom rng) {
+ // Create random doubles using random bits in the sign bit and the mantissa.
+ // Then create an exponent in the range -64 to 64.
+ final long mask = ((1L << 52) - 1) | 1L << 63;
+ final long bits = rng.nextLong() & mask;
+ // The exponent must be unsigned so + 1023 to the signed exponent
+ final long exp = rng.nextInt(129) - 64 + 1023;
+ return Double.longBitsToDouble(bits | (exp << 52));
+ }
+
+ /**
+ * Creates a random double number that will be an edge case:
+ * {@code +/-inf, +/-0, nan}.
+ *
+ * @param rng Random number generator.
+ * @return the random number
+ */
+ private static double createEdgeNumber(SplittableRandom rng) {
+ return EDGE_NUMBERS[rng.nextInt(EDGE_NUMBERS.length)];
+ }
+
+ /**
+ * Apply the function to all the numbers.
+ *
+ * @param numbers Numbers.
+ * @param fun Function.
+ * @return the result of the function.
+ */
+ private static double[] apply(double[] numbers, DoubleUnaryOperator fun) {
+ final double[] result = new double[numbers.length];
+ for (int i = 0; i < numbers.length; i++) {
+ result[i] = fun.applyAsDouble(numbers[i]);
+ }
+ return result;
+ }
+
+ /**
+ * Identity function. This can be used to measure overhead of copy array creation.
+ *
+ * @param z Complex number.
+ * @return the number
+ */
+ private static double identity(double z) {
+ return z;
+ }
+
+ // Benchmark methods.
+ //
+ // The methods are partially documented as the names are self-documenting.
+ // CHECKSTYLE: stop JavadocMethod
+ // CHECKSTYLE: stop DesignForExtension
+ //
+ // Benchmarks use function references to perform different operations on the numbers.
+ // Tests show that explicit programming of the same benchmarks run in the same time.
+ // For reference examples are provided for sin(x).
+
+ /**
+ * Explicit benchmark without using a method reference.
+ * This is commented out as it exists for reference purposes.
+ */
+ //@Benchmark
+ public double[] mathSin2(Numbers numbers) {
+ final double[] x = numbers.getNumbers();
+ final double[] result = new double[x.length];
+ for (int i = 0; i < x.length; i++) {
+ result[i] = Math.sin(x[i]);
+ }
+ return result;
+ }
+
+ /**
+ * Baseline the creation of the new array of numbers with the same number (an identity).
+ * This contains the baseline JMH overhead for all the benchmarks that create numbers.
+ * All other methods are expected to be slower than this.
+ */
+ @Benchmark
+ public double[] baselineIdentity(Numbers numbers) {
+ return apply(numbers.getNumbers(), SinCosPerformance::identity);
+ }
+
+ @Benchmark
+ public double[] mathSin(Numbers numbers) {
+ return apply(numbers.getNumbers(), Math::sin);
+ }
+
+ @Benchmark
+ public double[] mathCos(Numbers numbers) {
+ return apply(numbers.getNumbers(), Math::cos);
+ }
+
+ @Benchmark
+ public double[] fastMathSin(Numbers numbers) {
+ return apply(numbers.getNumbers(), FastMath::sin);
+ }
+
+ @Benchmark
+ public double[] fastMathCos(Numbers numbers) {
+ return apply(numbers.getNumbers(), FastMath::cos);
+ }
+}
Re: [commons-numbers] branch master updated: Add benchmark for
sin/cos computation.
Posted by Alex Herbert <al...@gmail.com>.
On 14/01/2020 12:14, Gilles Sadowski wrote:
> Hi.
>
> Le mar. 14 janv. 2020 à 12:24, <ah...@apache.org> a écrit :
>> [...]
>>
>> Add benchmark for sin/cos computation.
>>
>> Computing sin/cos together would improve many of the functions in
>> Complex. This benchmark investigates the possibility of using the
>> Commons FastMath implementation instead of java.util.Math.
> Related issues:
> https://issues.apache.org/jira/browse/MATH-901
> https://issues.apache.org/jira/browse/MATH-1113
> https://issues.apache.org/jira/browse/MATH-740
Thanks for the links.
Most of this discussion is that speed can be improved but it seems to be
at the loss of accuracy. I would err on the side of accuracy rather than
speed. Ideally a sin/cos implementation should be within 1 ULP of the
actual result as per java.util.Math.
>
> But CM does not provide sine and cosine in a single function call.
But it could. Both sin and cos first assign the input number x to a
quadrant in the range -pi to pi. This could be shared by a sin/cos
implementation.
Looking at the code it seems that the assignment to a quadrant may not
be the significant part of the run-time. I am going to investigate this
using a profiler to check.
There are a few scenarios to consider:
edge cases: NaN, Inf, 0
These have a definite result that can be computed for both sin and cos
together.
Domain: 0 - pi/2
This is the domain used to perform the computation.
Domain: >pi/2
The input value x has to be mapped to the computation domain 0 - pi/2.
This can be shared by sin and cos.
When I ran the benchmark on my laptop (MacOS) FastMath was a fair bit
faster for all scenarios. The actual computation is 5x faster when the
value x is not in the correct domain. I was surprised by this so I added
it to the JMH project to try on a few other machines. On an old linux
workstation FastMath is about 3x faster. On a more modern workstation
the difference is in favour of FastMath but only by about 1.2x.
In the event that the input is an edge case (NaN, Inf, or 0) then the
java version is definitely faster everywhere I tested. This indicates
that it may be better to check edge cases in java and then delegate to
Math to do the computation, i.e. a hybrid approach. The edge cases for
sin/cos are the same and so a SinCos implementation should have a speed
gain for edge case numbers. This may not be relevant given that edge
cases are likely to be rare in a real world usage scenario.
Given that Math.sin and Math.cos are native intrinsics in Java 8 they
are running efficient code. Beating them will be hard to do with the
same accuracy.
What requires further investigation is whether the reduction to the
domain 0 - pi/2 done by FastMath is exact for all values of x, and if it
is a significant part of the run-time of the function. If so then a
hybrid sincos would be:
sinCos(double x, double[] result) {
// Check edge cases and return if possible
// Map to domain 0 - pi/2
// Call Math.sin and Math.cos
// map results to correct quadrant -pi to pi
// return result
}
This would be simple to add to the current benchmark.
Alternatively if FastMath is accurate to 1 ULP as per Math then the
entire set of routines could be ported from CM. So I have a bit more
investigating to do on this to determine to determine the ULP range for
FastMath compared to Math and the cost of mapping to the computation domain.
Alex
>
> Regards,
> Gilles
>
>> [...]
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [commons-numbers] branch master updated: Add benchmark for
sin/cos computation.
Posted by Gilles Sadowski <gi...@gmail.com>.
Hi.
Le mar. 14 janv. 2020 à 12:24, <ah...@apache.org> a écrit :
>
> [...]
>
> Add benchmark for sin/cos computation.
>
> Computing sin/cos together would improve many of the functions in
> Complex. This benchmark investigates the possibility of using the
> Commons FastMath implementation instead of java.util.Math.
Related issues:
https://issues.apache.org/jira/browse/MATH-901
https://issues.apache.org/jira/browse/MATH-1113
https://issues.apache.org/jira/browse/MATH-740
But CM does not provide sine and cosine in a single function call.
Regards,
Gilles
> [...]
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org