A faster h3IsValid
slaperche-zenly opened this issue · 3 comments
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:
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 🙂).
I am glad when this library is helpful to you 👍
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.
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 🙂