You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ja...@apache.org on 2025/05/07 00:11:37 UTC
(lucene) 01/03: Move sloppySin into SloppyMath from GeoUtils (#14516)
This is an automated email from the ASF dual-hosted git repository.
jainankitk pushed a commit to branch branch_10x
in repository https://gitbox.apache.org/repos/asf/lucene.git
commit a5e5e9af1d7207efd1707259a6622feca27df9c1
Author: Ankit Jain <ja...@gmail.com>
AuthorDate: Tue May 6 16:31:47 2025 -0700
Move sloppySin into SloppyMath from GeoUtils (#14516)
---
lucene/CHANGES.txt | 3 +
.../lucene/benchmark/jmh/RectangleBenchmark.java | 122 +++++++++++++++++++++
.../lucene/benchmark/jmh/SloppySinBenchmark.java | 47 ++++++++
.../src/java/org/apache/lucene/geo/GeoUtils.java | 25 -----
.../src/java/org/apache/lucene/geo/Rectangle.java | 4 +-
.../java/org/apache/lucene/util/SloppyMath.java | 26 +++++
.../org/apache/lucene/util/TestSloppyMath.java | 33 +++++-
7 files changed, 231 insertions(+), 29 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index f947047b439..e6ce6fa80ea 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -54,6 +54,9 @@ Other
* GITHUB#7145: Adding basic unit tests for SpanWithinQuery. (Jakub Slowinski)
+* GITHUB#14516: Move sloppySin into SloppyMath from GeoUtils (Ankit Jain)
+
+
======================= Lucene 10.2.1 =======================
Bug Fixes
diff --git a/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/RectangleBenchmark.java b/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/RectangleBenchmark.java
new file mode 100644
index 00000000000..801d706b7d9
--- /dev/null
+++ b/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/RectangleBenchmark.java
@@ -0,0 +1,122 @@
+/*
+ * 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.lucene.benchmark.jmh;
+
+import static java.lang.Math.PI;
+import static java.lang.Math.max;
+import static java.lang.Math.min;
+import static org.apache.lucene.geo.GeoUtils.EARTH_MEAN_RADIUS_METERS;
+import static org.apache.lucene.geo.GeoUtils.MAX_LAT_RADIANS;
+import static org.apache.lucene.geo.GeoUtils.MAX_LON_RADIANS;
+import static org.apache.lucene.geo.GeoUtils.MIN_LAT_RADIANS;
+import static org.apache.lucene.geo.GeoUtils.MIN_LON_RADIANS;
+import static org.apache.lucene.geo.GeoUtils.checkLatitude;
+import static org.apache.lucene.geo.GeoUtils.checkLongitude;
+import static org.apache.lucene.util.SloppyMath.asin;
+import static org.apache.lucene.util.SloppyMath.cos;
+
+import java.util.concurrent.TimeUnit;
+import org.apache.lucene.geo.Rectangle;
+import org.openjdk.jmh.annotations.*;
+
+@State(Scope.Thread)
+@BenchmarkMode(Mode.Throughput)
+@OutputTimeUnit(TimeUnit.MILLISECONDS)
+@Fork(value = 1, warmups = 1)
+@Warmup(iterations = 1, time = 1)
+@Measurement(iterations = 3, time = 2)
+public class RectangleBenchmark {
+
+ @State(Scope.Benchmark)
+ public static class ExecutionPlan {
+ // Test cases representing different geographical scenarios
+ @Param({
+ "0.0", // Equator
+ "45.0", // Mid-latitude
+ "89.0", // Near pole
+ "-45.0", // Southern hemisphere
+ "-89.0" // Near south pole
+ })
+ private double latitude;
+
+ @Param({
+ "0.0", // Prime meridian
+ "179.0", // Near dateline
+ "-179.0", // Near dateline other side
+ "90.0", // Mid-longitude
+ "-90.0" // Mid-longitude west
+ })
+ private double longitude;
+
+ @Param({
+ "100", // Small radius (100m)
+ "1000", // 1km
+ "10000", // 10km
+ "100000", // 100km
+ "1000000" // 1000km
+ })
+ private double radiusMeters;
+ }
+
+ @Benchmark
+ public Rectangle benchmarkFromPointDistanceSloppySin(ExecutionPlan plan) {
+ return Rectangle.fromPointDistance(plan.latitude, plan.longitude, plan.radiusMeters);
+ }
+
+ @Benchmark
+ public Rectangle benchmarkFromPointDistanceStandardSin(ExecutionPlan plan) {
+ return fromPointDistanceStandardSin(plan.latitude, plan.longitude, plan.radiusMeters);
+ }
+
+ private static Rectangle fromPointDistanceStandardSin(
+ final double centerLat, final double centerLon, final double radiusMeters) {
+ checkLatitude(centerLat);
+ checkLongitude(centerLon);
+ final double radLat = Math.toRadians(centerLat);
+ final double radLon = Math.toRadians(centerLon);
+ // LUCENE-7143
+ double radDistance = (radiusMeters + 7E-2) / EARTH_MEAN_RADIUS_METERS;
+ double minLat = radLat - radDistance;
+ double maxLat = radLat + radDistance;
+ double minLon;
+ double maxLon;
+
+ if (minLat > MIN_LAT_RADIANS && maxLat < MAX_LAT_RADIANS) {
+ double deltaLon = asin(Math.sin(radDistance) / cos(radLat));
+ minLon = radLon - deltaLon;
+ if (minLon < MIN_LON_RADIANS) {
+ minLon += 2d * PI;
+ }
+ maxLon = radLon + deltaLon;
+ if (maxLon > MAX_LON_RADIANS) {
+ maxLon -= 2d * PI;
+ }
+ } else {
+ // a pole is within the distance
+ minLat = max(minLat, MIN_LAT_RADIANS);
+ maxLat = min(maxLat, MAX_LAT_RADIANS);
+ minLon = MIN_LON_RADIANS;
+ maxLon = MAX_LON_RADIANS;
+ }
+
+ return new Rectangle(
+ Math.toDegrees(minLat),
+ Math.toDegrees(maxLat),
+ Math.toDegrees(minLon),
+ Math.toDegrees(maxLon));
+ }
+}
diff --git a/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/SloppySinBenchmark.java b/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/SloppySinBenchmark.java
new file mode 100644
index 00000000000..337b60bd6a6
--- /dev/null
+++ b/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/SloppySinBenchmark.java
@@ -0,0 +1,47 @@
+/*
+ * 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.lucene.benchmark.jmh;
+
+import java.util.concurrent.TimeUnit;
+import org.apache.lucene.util.SloppyMath;
+import org.openjdk.jmh.annotations.*;
+
+@State(Scope.Thread)
+@BenchmarkMode(Mode.Throughput)
+@OutputTimeUnit(TimeUnit.MILLISECONDS)
+@Fork(value = 1, warmups = 1)
+@Warmup(iterations = 1, time = 1)
+@Measurement(iterations = 3, time = 2)
+public class SloppySinBenchmark {
+ @Benchmark
+ public double standardSin(ExecutionPlan plan) {
+ return Math.sin(plan.value);
+ }
+
+ @Benchmark
+ public double sloppySin(ExecutionPlan plan) {
+ return SloppyMath.sin(plan.value);
+ }
+
+ @State(Scope.Benchmark)
+ public static class ExecutionPlan {
+
+ // Test with different input ranges
+ @Param({"0.1", "0.5", "1.0", "2.0", "3.14"})
+ public double value;
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java b/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
index 825961ffa1b..7f7278d066c 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
@@ -16,7 +16,6 @@
*/
package org.apache.lucene.geo;
-import static org.apache.lucene.util.SloppyMath.cos;
import static org.apache.lucene.util.SloppyMath.haversinMeters;
import org.apache.lucene.index.PointValues;
@@ -87,30 +86,6 @@ public final class GeoUtils {
}
}
- // some sloppyish stuff, do we really need this to be done in a sloppy way?
- // unless it is performance sensitive, we should try to remove.
- private static final double PIO2 = Math.PI / 2D;
-
- /**
- * Returns the trigonometric sine of an angle converted as a cos operation.
- *
- * <p>Note that this is not quite right... e.g. sin(0) != 0
- *
- * <p>Special cases:
- *
- * <ul>
- * <li>If the argument is {@code NaN} or an infinity, then the result is {@code NaN}.
- * </ul>
- *
- * @param a an angle, in radians.
- * @return the sine of the argument.
- * @see Math#sin(double)
- */
- // TODO: deprecate/remove this? at least its no longer public.
- public static double sloppySin(double a) {
- return cos(a - PIO2);
- }
-
/**
* binary search to find the exact sortKey needed to match the specified radius any sort key lte
* this is a query match.
diff --git a/lucene/core/src/java/org/apache/lucene/geo/Rectangle.java b/lucene/core/src/java/org/apache/lucene/geo/Rectangle.java
index e5406b5d3db..6435d745243 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Rectangle.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Rectangle.java
@@ -28,9 +28,9 @@ import static org.apache.lucene.geo.GeoUtils.MIN_LAT_RADIANS;
import static org.apache.lucene.geo.GeoUtils.MIN_LON_RADIANS;
import static org.apache.lucene.geo.GeoUtils.checkLatitude;
import static org.apache.lucene.geo.GeoUtils.checkLongitude;
-import static org.apache.lucene.geo.GeoUtils.sloppySin;
import static org.apache.lucene.util.SloppyMath.asin;
import static org.apache.lucene.util.SloppyMath.cos;
+import static org.apache.lucene.util.SloppyMath.sin;
/** Represents a lat/lon rectangle. */
public class Rectangle extends LatLonGeometry {
@@ -121,7 +121,7 @@ public class Rectangle extends LatLonGeometry {
double maxLon;
if (minLat > MIN_LAT_RADIANS && maxLat < MAX_LAT_RADIANS) {
- double deltaLon = asin(sloppySin(radDistance) / cos(radLat));
+ double deltaLon = asin(sin(radDistance) / cos(radLat));
minLon = radLon - deltaLon;
if (minLon < MIN_LON_RADIANS) {
minLon += 2d * PI;
diff --git a/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java b/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java
index cb8c6cc0273..b992355751b 100644
--- a/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java
+++ b/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java
@@ -178,6 +178,32 @@ public class SloppyMath {
}
}
+ // some sloppyish stuff, do we really need this to be done in a sloppy way?
+ // unless it is performance sensitive, we should try to remove.
+ // This is performance sensitive, check SloppySinBenchmark and RectangleBenchmark
+ private static final double PIO2 = Math.PI / 2D;
+
+ /**
+ * Returns the trigonometric sine of an angle converted as a cos operation.
+ *
+ * <p>Error is around 1E-12.
+ *
+ * <p>Note that this is not quite right... e.g. sin(0) != 0
+ *
+ * <p>Special cases:
+ *
+ * <ul>
+ * <li>If the argument is {@code NaN} or an infinity, then the result is {@code NaN}.
+ * </ul>
+ *
+ * @param a an angle, in radians.
+ * @return the sine of the argument.
+ * @see Math#sin(double)
+ */
+ public static double sin(double a) {
+ return cos(a - PIO2);
+ }
+
// Earth's mean radius, in meters and kilometers; see
// http://earth-info.nga.mil/GandG/publications/tr8350.2/wgs84fin.pdf
private static final double TO_METERS = 6_371_008.7714D; // equatorial radius
diff --git a/lucene/core/src/test/org/apache/lucene/util/TestSloppyMath.java b/lucene/core/src/test/org/apache/lucene/util/TestSloppyMath.java
index cd70093514e..7b96a3e8896 100644
--- a/lucene/core/src/test/org/apache/lucene/util/TestSloppyMath.java
+++ b/lucene/core/src/test/org/apache/lucene/util/TestSloppyMath.java
@@ -20,6 +20,7 @@ import static org.apache.lucene.util.SloppyMath.asin;
import static org.apache.lucene.util.SloppyMath.cos;
import static org.apache.lucene.util.SloppyMath.haversinMeters;
import static org.apache.lucene.util.SloppyMath.haversinSortKey;
+import static org.apache.lucene.util.SloppyMath.sin;
import java.util.Random;
import org.apache.lucene.tests.geo.GeoTestUtil;
@@ -28,6 +29,8 @@ import org.apache.lucene.tests.util.LuceneTestCase;
public class TestSloppyMath extends LuceneTestCase {
// accuracy for cos()
private static final double COS_DELTA = 1E-15;
+ // accuracy for sin()
+ private static final double SIN_DELTA = 1E-12;
// accuracy for asin()
private static final double ASIN_DELTA = 1E-7;
// accuracy for haversinMeters()
@@ -50,8 +53,8 @@ public class TestSloppyMath extends LuceneTestCase {
assertEquals(StrictMath.cos(Math.PI / 6), cos(Math.PI / 6), COS_DELTA);
assertEquals(StrictMath.cos(-Math.PI / 6), cos(-Math.PI / 6), COS_DELTA);
- // testing purely random longs is inefficent, as for stupid parameters we just
- // pass thru to Math.cos() instead of doing some huperduper arg reduction
+ // testing purely random longs is inefficient, as for stupid parameters we just
+ // pass through to Math.cos() instead of doing some superduper arg reduction
for (int i = 0; i < 10000; i++) {
double d = random().nextDouble() * SloppyMath.SIN_COS_MAX_VALUE_FOR_INT_MODULO;
if (random().nextBoolean()) {
@@ -61,6 +64,32 @@ public class TestSloppyMath extends LuceneTestCase {
}
}
+ public void testSin() {
+ assertTrue(Double.isNaN(sin(Double.NaN)));
+ assertTrue(Double.isNaN(sin(Double.NEGATIVE_INFINITY)));
+ assertTrue(Double.isNaN(sin(Double.POSITIVE_INFINITY)));
+ assertEquals(StrictMath.sin(1), sin(1), SIN_DELTA);
+ assertEquals(StrictMath.sin(0), sin(0), SIN_DELTA);
+ assertEquals(StrictMath.sin(Math.PI / 2), sin(Math.PI / 2), SIN_DELTA);
+ assertEquals(StrictMath.sin(-Math.PI / 2), sin(-Math.PI / 2), SIN_DELTA);
+ assertEquals(StrictMath.sin(Math.PI / 4), sin(Math.PI / 4), SIN_DELTA);
+ assertEquals(StrictMath.sin(-Math.PI / 4), sin(-Math.PI / 4), SIN_DELTA);
+ assertEquals(StrictMath.sin(Math.PI * 2 / 3), sin(Math.PI * 2 / 3), SIN_DELTA);
+ assertEquals(StrictMath.sin(-Math.PI * 2 / 3), sin(-Math.PI * 2 / 3), SIN_DELTA);
+ assertEquals(StrictMath.sin(Math.PI / 6), sin(Math.PI / 6), SIN_DELTA);
+ assertEquals(StrictMath.sin(-Math.PI / 6), sin(-Math.PI / 6), SIN_DELTA);
+
+ // testing purely random longs is inefficient, as for stupid parameters we just
+ // pass through to Math.sin() instead of doing some superduper arg reduction
+ for (int i = 0; i < 10000; i++) {
+ double d = random().nextDouble() * SloppyMath.SIN_COS_MAX_VALUE_FOR_INT_MODULO;
+ if (random().nextBoolean()) {
+ d = -d;
+ }
+ assertEquals(StrictMath.sin(d), sin(d), SIN_DELTA);
+ }
+ }
+
public void testAsin() {
assertTrue(Double.isNaN(asin(Double.NaN)));
assertTrue(Double.isNaN(asin(2)));