8000 Optimize the face locating logic by wewei · Pull Request #63 · uber/h3 · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Optimize the face locating logic #63

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 5 commits into from
Jun 1, 2018
Merged

Optimize the face locating logic #63

merged 5 commits into from
Jun 1, 2018

Conversation

wewei
Copy link
Contributor
@wewei wewei commented May 30, 2018

Hi, our was investigating the geo-indexing libraries recently. While comparing H3 and S2, we found the index calculation method (geoToH3) is a lot slower than that for S2. The icosahedron projection and the hexagon cells does require more calculation, but it shouldn't like that.

After reading the code, I found the triangle functions are heavily used in H3, while S2 uses 3D points to do the spherical calculation, which can largely reduce the amount of sin/cos calls.

Just logic deciding which face the point is projected to, it make 120 triangle function calls. (For each face, make 3 cos, 2 sin, 1 acos calls to get the great circle distance). Indeed, at most 5 triangle function calls is necessary.

  1. The 3D coordinate of the face centers can be pre-calculated.
  2. The center of the face the point projected to has the smallest great circle distance(a), thus it has the smallest square distance (S). Because S = (2 * sin(a/2))^2 = 4 * sin^2(a/2) = 2 * (1 - cos(a)), as cos(a) is monotonic decreasing on [0, PI], S is monotonic increasing according to a on [0, PI]. That means, instead of comparing the great circle distance, we can compare the square distance of the 3D points.

With the optimization proposal, we only need to calculate the cos/sin of the lat/lon of the given GeoCoord to translate it into (x, y, z), and calculate acos once to get the great cycle distance for later calculation of the IJK.

I tested the performance with a simple routine,

#include <h3/h3api.h>

int main() {
    for (int lat = -90; lat <= 90; ++lat) {
        for (int lon = 0; lon < 360; ++ lon) {
            GeoCoord coord = {
                .lat = degsToRads(lat),
                .lon = degsToRads(lon),
            };
            for (int res = 0; res < 16; ++ res) {
                geoToH3(&coord, res);
            }
        }
    }
    return 0;
}

And here's the result

# Baseline
real    0m4.402s
user    0m4.400s
sys     0m0.000s

# Optimized
real    0m2.121s
user    0m2.119s
sys     0m0.000s

@CLAassistant
Copy link
CLAassistant commented May 30, 2018 •
edited
Loading

CLA assistant check
All committers have signed the CLA.

@coveralls
Copy link
coveralls commented May 30, 2018 •
edited
Loading

Coverage Status

Coverage remained the same at 100.0% when pulling 08d42b4 on wewei:improve-perf into f666632 on uber:master.

isaacbrodsky
isaacbrodsky reviewed May 30, 2018
View reviewed changes
Copy link
Collaborator
@isaacbrodsky isaacbrodsky left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Hi, thanks for your contribution! I have a few comments, but the overall optimization looks good to me. Please remember to sign the CLA so we can merge your changes.

src/h3lib/include/h3api.h Outdated
@@ -67,6 +67,15 @@ typedef struct {
double lon; ///< longitude in radians
} GeoCoord;

/** @struct Point
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Since this structure is not used by the public facing API. could you move it to geoCoord.h or faceIjk.h?

src/h3lib/include/geoCoord.h Outdated
@@ -47,4 +47,9 @@ double _geoDistKm(const GeoCoord* p1, const GeoCoord* p2);
double _geoAzimuthRads(const GeoCoord* p1, const GeoCoord* p2);
void _geoAzDistanceRads(const GeoCoord* p1, double az, double distance,
GeoCoord* p2);

void _geoToPoint(const GeoCoord* geo, Point* point);
void _pointToGeo(const Point* point, GeoCoord* geo);
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Please delete the unused _pointToGeo declaration.

src/h3lib/lib/faceijk.c Outdated
@@ -56,6 +56,29 @@ static const GeoCoord faceCenterGeo[NUM_ICOSA_FACES] = {
{-1.054751253523952054, 1.794075294689396615}, // face 19
};

static const Point faceCenterPoint[NUM_ICOSA_FACES] = {
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Maybe add /** @brief icosahedron face centers in x/y/z on the unit sphere */

@sahrk
Copy link
Collaborator
sahrk commented May 30, 2018

Since all of the coordinate systems describe a point, usingPoint in these names seems like too generic a term for the 3D coordinates. Maybe substitute with xyz, pt3D, or ECEF (for earth-centered, earth fixed)?

@isaacbrodsky
Copy link
Collaborator

Since all of the coordinate systems describe a point, usingPoint in these names seems like too generic a term for the 3D coordinates. Maybe substitute with xyz, pt3D, or ECEF (for earth-centered, earth fixed)?

Maybe Vec3d to parallel Vec2d?

@jogly jogly self-requested a review May 30, 2018 17:41
@sahrk
Copy link
Collaborator
sahrk commented May 30, 2018

I agree with Vec3D. Originally I discarded that idea because there is no Vec3D structure (as there is for Vec2D), but upon further reflection I don't think that is a real issue.

@nrabinowitz
Copy link
Collaborator

Agree with @isaacbrodsky's comments, but this looks great to me otherwise. Thanks for submitting!

@nrabinowitz
Copy link
Collaborator

FWIW the perf benefit here is reflected in the existing benchmark script as well:

master:

Built target benchmarkH3Api
	-- geoToH3: 0.002700 milliseconds per iteration (10000 iterations)

PR:

Built target benchmarkH3Api
	-- geoToH3: 0.001200 milliseconds per iteration (10000 iterations)

@wewei
Copy link
Contributor Author
wewei commented May 31, 2018

Thanks for the quick response. I just updated the change accordingly.

For the new Vec3d structure, I put it into geoCoord.h. However, it sounds better to have a vec3d.h in parallel with vec2d.h, or merge them into something like vec.h? I'll leave the necessary refactoring to you owners, as I don't have confidence to fill the legal terms correctly for a new file.

isaacbrodsky
isaacbrodsky approved these changes May 31, 2018
View reviewed changes
Copy link
Collaborator
@isaacbrodsky isaacbrodsky left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I am ok with leaving moving Vec3d to a future PR.

src/h3lib/lib/faceijk.c Outdated
@@ -359,18 +383,27 @@ void _geoToFaceIjk(const GeoCoord* g, int res, FaceIJK* h) {
* @param face The icosahedral face containing the spherical coordinates.
* @param v The 2D hex coordinates of the cell containing the point.
*/

Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

nit: there is an unneeded extra line

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yeah, removed it.

@nrabinowitz nrabinowitz merged commit 2cc1782 into uber:master Jun 1, 2018
@isaacbrodsky isaacbrodsky mentioned this pull request Jun 1, 2018
Merged
mrdvt92 pushed a commit to mrdvt92/h3 that referenced this pull request Jun 19, 2022
@nrabinowitz
Merge pull request uber#63 from wewei/improve-perf
93c38e8 
Optimize the face locating logic
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@nrabinowitz nrabinowitz nrabinowitz approved these changes

@isaacbrodsky isaacbrodsky isaacbrodsky approved these changes

@jogly jogly Awaiting requested review from jogly

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
6 participants
@wewei @CLAassistant @coveralls @sahrk @isaacbrodsky @nrabinowitz
0