uber / uber/h3

Parallelization of computing-intensive functions

Open
#191 9 comments 2 reactions 0 assignees View on GitHub

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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.