Parallelization of computing-intensive functions
Nobody has claimed this yet.
- Dominant language
- C
- Stars
- 6.5k
- Forks
- 627
- Avg merge
- 3d 21h
- Merged PRs (30d)
- 6
Description
I do not know if this an issue there is any interest in, but I noticed the library can potentially benefit from parallelizing parts of computing-intensive functions.
I experimented a bit and used OpenMP to simply parallelize the check if a hexagon is contained in a polygon in the polyfill function: https://github.com/nmandery/h3/commit/65afcb16579e833083feba713a89d7423611212a
Results without openmp:
$ ./bin/benchmarkPolyfill
-- polyfillSF: 5830.508514 microseconds per iteration (500 iterations)
-- polyfillAlameda: 7501.964168 microseconds per iteration (500 iterations)
-- polyfillSouthernExpansion: 325676.916500 microseconds per iteration (10 iterations)
$ ./bin/benchmarkPolyfill
-- polyfillSF: 5241.980240 microseconds per iteration (500 iterations)
-- polyfillAlameda: 7528.802096 microseconds per iteration (500 iterations)
-- polyfillSouthernExpansion: 326040.845100 microseconds per iteration (10 iterations)
Results with openmp:
$ ./bin/benchmarkPolyfill
-- polyfillSF: 2136.395920 microseconds per iteration (500 iterations)
-- polyfillAlameda: 2469.901036 microseconds per iteration (500 iterations)
-- polyfillSouthernExpansion: 98592.296500 microseconds per iteration (10 iterations)
$ ./bin/benchmarkPolyfill
-- polyfillSF: 2006.864104 microseconds per iteration (500 iterations)
-- polyfillAlameda: 2428.976026 microseconds per iteration (500 iterations)
-- polyfillSouthernExpansion: 97370.778000 microseconds per iteration (10 iterations)
These are the specs of the machine I used:
$ grep 'model name' /proc/cpuinfo
model name : Intel(R) Xeon(R) CPU E5-2670 0 @ 2.60GHz
model name : Intel(R) Xeon(R) CPU E5-2670 0 @ 2.60GHz
model name : Intel(R) Xeon(R) CPU E5-2670 0 @ 2.60GHz
model name : Intel(R) Xeon(R) CPU E5-2670 0 @ 2.60GHz
I guess the usage of OpenMP should be optional, as I do not know how this would affect the emscripten based Javascript port of h3.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with the polyfill function and the check for whether a hexagon is contained in a polygon, then review bin/benchmarkPolyfill and the OpenMP experiment linked in the issue. Compare the benchmark results and consider the impact on the emscripten-based JavaScript port. Done means an agreed, optional parallelization approach with validated performance and compatibility.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c
- Domain
- performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 25/100