From ae1de549006c1f15bade4969ba25932e3509f17a Mon Sep 17 00:00:00 2001 From: filipe oliveira Date: Thu, 24 Nov 2022 16:09:56 +0000 Subject: GEOSEARCH BYBOX: Reduce wastefull computation on geohashGetDistanceIfInRectangle and geohashGetDistance (#11535) Optimize geohashGetDistanceIfInRectangle when there are many misses. It calls 3x geohashGetDistance. The first 2 times we call them to produce intermediate results. This PR focus on optimizing for those 2 intermediate results. 1 Reduce expensive computation on intermediate geohashGetDistance with same long 2 Avoid expensive lon_distance calculation if lat_distance fails beforehand Co-authored-by: Oran Agra --- src/geohash_helper.c | 17 +++++++++++++---- 1 file changed, 13 insertions(+), 4 deletions(-) diff --git a/src/geohash_helper.c b/src/geohash_helper.c index a9224a1dd..a089c97c2 100644 --- a/src/geohash_helper.c +++ b/src/geohash_helper.c @@ -225,8 +225,12 @@ double geohashGetDistance(double lon1d, double lat1d, double lon2d, double lat2d lon2r = deg_rad(lon2d); u = sin((lat2r - lat1r) / 2); v = sin((lon2r - lon1r) / 2); - return 2.0 * EARTH_RADIUS_IN_METERS * - asin(sqrt(u * u + cos(lat1r) * cos(lat2r) * v * v)); + double a = u * u; + /* if v == 0 we can avoid doing expensive math */ + if (v != 0.0){ + a += cos(lat1r) * cos(lat2r) * v * v; + } + return 2.0 * EARTH_RADIUS_IN_METERS * asin(sqrt(a)); } int geohashGetDistanceIfInRadius(double x1, double y1, @@ -253,9 +257,14 @@ int geohashGetDistanceIfInRadiusWGS84(double x1, double y1, double x2, */ int geohashGetDistanceIfInRectangle(double width_m, double height_m, double x1, double y1, double x2, double y2, double *distance) { - double lon_distance = geohashGetDistance(x2, y2, x1, y2); + /* latitude distance is less expensive to compute than longitude distance + * so we check first for the latitude condition */ double lat_distance = geohashGetDistance(x2, y2, x2, y1); - if (lon_distance > width_m/2 || lat_distance > height_m/2) { + if (lat_distance > height_m/2) { + return 0; + } + double lon_distance = geohashGetDistance(x2, y2, x1, y2); + if (lon_distance > width_m/2) { return 0; } *distance = geohashGetDistance(x1, y1, x2, y2); -- cgit v1.2.1