A faster h3IsValid

[slaperche-zenly]

First and foremost: thanks for this great crate 🙏 Been using for a few days, and the high level API is really enjoyable 👍

I've been working with H3 these last few months, and one thing leading to another I've found that the current implementation of h3IsValid seems suboptimal (contains for-loops that could be avoided). Given that I have to validate set of cells that can be quite large in some case, I gave it a shot at optimizing it.

After a few attempts, I arrrived to a solution that seems to be isofunctional while being x3 to x4 faster than the original implementation:

• Criterion output for hexagons
• Criterion output for pentagons

Code is not necessarily more complex (I would even say it's simpler but I'm not objective here 😀), though there are one or two tricks that do deserve detailed explanations.

The two biggests improvements are:

• replacing the loop checking for invalid digits using an adaptation of an old nul-byte detection algorithm (technology from the past come to save the future 😛)
• replacing the loop checking for invalid pentagons

You can find the code here (with some unit tests). The benchmarks I used is here.

I've also run a check again a few billions of value (~30% valid/70% invalid) with my implementation against the official ones to ensure that the results were identical. Interestingly enough, I can observe the same x3 speedup in this case (on my machine ~8s vs ~24s)

Dunno if it's of interest to you, but I'm sharing it just in case 🙂

Would probably be better to implement this upstream, but I don't have the time nor the motivation to start a pull request in C 😅 (that being said, they do have a PR in progress about this, and I did left a comment over there as well 🙂).

[nmandery]

I am glad when this library is helpful to you :+1:

Great work on the optimization of h3IsValid - the speedup achieved by this is really remarkable. This is definitely very interesting, thank you for sharing.

I saw that there is already some work done to look how to integrate this into h3 itself. This would certainly the best way to integrate this patch. I would propose to see how that works out. In case there are issues with porting this code to portable C while supporting all platforms H3 compiles to, we really should integrate your code into h3ron.

[slaperche-zenly]

I would propose to see how that works out. In case there are issues with porting this code to portable C while supporting all platforms H3 compiles to, we really should integrate your code into h3ron.

Sounds good to me, let's wait and see 🙂

[nmandery]

I suppose we can close this issue as this is certainly implemented now in h3o