new fast isValidCell by ajfriend · Pull Request #968 · uber/h3

ajfriend · 2025-02-17T17:58:39Z

Taking over from #496.

New isValidCell should be faster in all cases. Relies on bit manipulation instead of loops.

In the last correctness check, we use compiler intrinsics, so we'll want to verify that that approach works on all platforms. We can always fall back to a loop, and that would still be faster (see the benchmarks plot below). However, we need to ensure that we have the right test to evaluate which approaches are available on each platform. I'm not currently sure how to do that in an exhaustive way.

coveralls · 2025-02-17T18:04:00Z

coverage: 98.786% (+0.002%) from 98.784%
when pulling 52c7146 on ajfriend:new_isValidCell
into 42450ce on uber:master.

ajfriend · 2025-02-18T04:22:05Z

OK, current approach breaks some rules:

/home/runner/work/h3/h3/src/h3lib/lib/h3Index.c: In function ‘_isValidCell_const’:
/home/runner/work/h3/h3/src/h3lib/lib/h3Index.c:297:14: error: dereferencing type-punned pointer will break strict-aliasing rules [-Werror=strict-aliasing]

ajfriend · 2025-02-20T06:22:37Z

Speedup results on my M3 mac are promising. This is for 8_14_null_100.

old is the original algorithm
final is the final algorithm using intrinsics
fallback is the final algorithm, but will the fallback for when intrinsics are not availab.e

Speedups, comparing the fastest run for each name and algo:

┌───────────────┬─────────┬─────────┬─────────┐
│     name      │  algo1  │  algo2  │ speedup │
│    varchar    │ varchar │ varchar │ double  │
├───────────────┼─────────┼─────────┼─────────┤
│ 2_8           │ old     │ final   │     6.4 │
│ 8_14          │ old     │ final   │     9.1 │
│ 8_14_null_10  │ old     │ final   │     7.8 │
│ 8_14_null_100 │ old     │ final   │     8.8 │
│ 8_14_null_2   │ old     │ final   │     5.0 │
└───────────────┴─────────┴─────────┴─────────┘

ajfriend · 2025-02-22T19:35:57Z

Latest benchmarks of final algo:

┌───────────────┬──────────────┬───────┐
│     name      │ microseconds │ runs  │
│    varchar    │    double    │ int64 │
├───────────────┼──────────────┼───────┤
│ 2_8           │      145.976 │   500 │
│ 8_14          │      145.646 │   500 │
│ 8_14_null_10  │      157.995 │   500 │
│ 8_14_null_100 │      149.786 │   500 │
│ 8_14_null_2   │      145.231 │   500 │
└───────────────┴──────────────┴───────┘

ajfriend · 2025-02-22T21:16:38Z

TODO: We test 32 bit windows in CI. Should we do the same for mac and linux?

isaacbrodsky · 2025-02-23T18:18:44Z

TODO: We test 32 bit windows in CI. Should we do the same for mac and linux?

I don't think there is an equivalent Mac 32-bit.
Linux we can test a x86 or ARM 32-bit configuration

isaacbrodsky · 2025-02-23T23:40:58Z

+        [4] = 1,  [14] = 1, [24] = 1, [38] = 1, [49] = 1,  [58] = 1,
+        [63] = 1, [72] = 1, [83] = 1, [97] = 1, [107] = 1, [117] = 1};
+
+    if (isBaseCellPentagonArr[base_cell]) {


Is there a reason not to use (perhaps an inlined version of) _isBaseCellPentagon?

Good point. I'll run some benchmarks and see if there's any difference.

Definitely slower with the naive use of _isBaseCellPentagon. Test setup in the latest commit:

I'll figure out the right extern and inline incantation and try that next.

Another alternative might be to just expose the BaseCellData directly.

More generally for the H3 lib as a whole, I'm not sure if there's a benefit to using a struct of arrays vs an array of structs.

I think doing this will be a little involved, so I'm proposing doing it later :)

#984

ajfriend · 2025-02-25T01:07:30Z

TODO: We test 32 bit windows in CI. Should we do the same for mac and linux?

I don't think there is an equivalent Mac 32-bit. Linux we can test a x86 or ARM 32-bit configuration

Think that's a blocker for this PR, or can I create a separate task/PR to add that to CI? @isaacbrodsky

isaacbrodsky · 2025-02-25T01:24:22Z

TODO: We test 32 bit windows in CI. Should we do the same for mac and linux?

I don't think there is an equivalent Mac 32-bit. Linux we can test a x86 or ARM 32-bit configuration

Think that's a blocker for this PR, or can I create a separate task/PR to add that to CI? @isaacbrodsky

I don't think it's a blocker, but we could certainly merge it in first.

My sense is Linux x86/i*86 is much less common today and probably not an architecture we need to be too concerned with testing.

I'll open a PR to include Linux arm64. I don't think Github provides Linux arm32 runners, at least as standard: https://docs.github.com/en/actions/using-github-hosted-runners/using-github-hosted-runners/about-github-hosted-runners#standard-github-hosted-runners-for-public-repositories

edit: #974

ajfriend · 2025-03-06T20:25:55Z

Issues trying to inline:

dfellis · 2025-03-06T21:02:35Z

I'm not super familiar with inline functions in C, but going by this StackOverflow answer you need inline int ... in the header, and extern int ... in the implementation.

ajfriend · 2025-03-07T17:51:24Z

I'm not super familiar with inline functions in C, but going by this StackOverflow answer you need inline int ... in the header, and extern int ... in the implementation.

Nice. That works for me locally, but with some errors. Let's see now it does in CI.

ajfriend · 2025-03-09T20:30:41Z

Note the follow-up: #984

ajfriend marked this pull request as draft February 18, 2025 04:06

ajfriend marked this pull request as ready for review February 22, 2025 20:47

ajfriend requested review from dfellis, isaacbrodsky and nrabinowitz February 22, 2025 20:47

ajfriend mentioned this pull request Feb 22, 2025

[WIP] Fast isValidCell #496

Closed

ajfriend changed the title ~~[wip] new fast isValidCell~~ new fast isValidCell Feb 22, 2025

isaacbrodsky approved these changes Feb 23, 2025

View reviewed changes

isaacbrodsky reviewed Feb 23, 2025

View reviewed changes

ajfriend mentioned this pull request Mar 9, 2025

Inline _isBaseCellPentagon #984

Open

ajfriend added 9 commits March 9, 2025 13:28

first real change

22421f0

just for me

7139767

oooof clang format version thing?

82baf7d

fixed clang format

565cfb2

port over old new solution

1157c42

try old

4fdd5ed

check that _isValidCell_const fails on draft PRs

398ed76

try old again

a08cdca

ok, see if this passes

792f8be

ajfriend added 25 commits March 9, 2025 13:28

try defined(_M_X64)

3924806

define some helper functions

37326d8

more helpers

0b62a0a

boop

6ec2a70

notes

7dbd879

function names

dd5d373

move functions around

87886e1

formatting

8bfaffa

benchmarks

5910825

remove dev files

af42fd0

snake to camel

2b982df

drop pos

08c77c7

drop some conditionals

6279096

intention more clear

5ef58d4

organize

8718650

little nicer

f6535a3

remove justfile and remove fail fast

5882f65

comment

a4546cd

bench for is base cell test

252bdb7

maybe working with extern

ce10b14

back to isBaseCellPentagonArr

1d55886

TODO: uber#984

c75debe

changelog

b79169e

remove files

05f7399

remove more files

52c7146

ajfriend force-pushed the new_isValidCell branch from f331d1a to 52c7146 Compare March 9, 2025 20:28

dfellis approved these changes Mar 9, 2025

View reviewed changes

ajfriend merged commit 306a7cb into uber:master Mar 10, 2025

ajfriend deleted the new_isValidCell branch March 10, 2025 01:03

Conversation

ajfriend commented Feb 17, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

coveralls commented Feb 17, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ajfriend commented Feb 18, 2025

Uh oh!

ajfriend commented Feb 20, 2025

Uh oh!

ajfriend commented Feb 22, 2025

Uh oh!

ajfriend commented Feb 22, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

isaacbrodsky commented Feb 23, 2025

Uh oh!

isaacbrodsky Feb 23, 2025

Choose a reason for hiding this comment

Uh oh!

ajfriend Feb 25, 2025

Choose a reason for hiding this comment

Uh oh!

ajfriend Feb 26, 2025

Choose a reason for hiding this comment

Uh oh!

ajfriend Mar 9, 2025

Choose a reason for hiding this comment

Uh oh!

ajfriend commented Feb 25, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

isaacbrodsky commented Feb 25, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ajfriend commented Mar 6, 2025

Uh oh!

dfellis commented Mar 6, 2025

Uh oh!

ajfriend commented Mar 7, 2025

Uh oh!

ajfriend commented Mar 9, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

ajfriend commented Feb 17, 2025 •

edited

Loading

coveralls commented Feb 17, 2025 •

edited

Loading

ajfriend commented Feb 22, 2025 •

edited

Loading

ajfriend commented Feb 25, 2025 •

edited

Loading

isaacbrodsky commented Feb 25, 2025 •

edited

Loading