Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement parallel::merge. #2833

Merged
merged 12 commits into from Aug 31, 2017
Merged

Implement parallel::merge. #2833

merged 12 commits into from Aug 31, 2017

Conversation

taeguk
Copy link
Member

@taeguk taeguk commented Aug 15, 2017

Check Box

  • Implementation of parallel::merge only for random access iterator.
  • Unit tests.
  • Benchmark codes.
  • Adapt to Ranges TS.

Issues

  1. How to support forward and bidirectional iterator. (Support forward and bidirectional iterators in parallel::merge. #2826)
    -> For now, restrict the requirements of parallel::merge to only random access iterator.

Note for future

  1. parallel::merge is a little faster than sequential thing. (If can, we should find and implement better algorithms.)
  2. Utilizing 2 cores or 4 cores is the limitation of the algorithm. In other words, can't utilize all cores. I assume performance bottleneck is due to memory bandwidth.

@hkaiser hkaiser added this to the 1.1.0 milestone Aug 15, 2017
@hkaiser hkaiser added this to Work in progress in Standard Algorithms Aug 15, 2017
@hkaiser hkaiser mentioned this pull request Aug 15, 2017
47 tasks
@taeguk
Copy link
Member Author

taeguk commented Aug 23, 2017

@hkaiser When will this PR merged??

@hkaiser
Copy link
Member

hkaiser commented Aug 23, 2017

@taeguk slowly catching up on things...

@taeguk
Copy link
Member Author

taeguk commented Aug 23, 2017

@hkaiser Okay good :) I just worried that you forgot this PR.

Copy link
Member

@hkaiser hkaiser left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM, thanks!

@hkaiser hkaiser merged commit c4e1087 into STEllAR-GROUP:master Aug 31, 2017
@hkaiser hkaiser moved this from Work in progress to Merged to master in Standard Algorithms Aug 31, 2017
@taeguk
Copy link
Member Author

taeguk commented Oct 28, 2017

@hkaiser Were there some improvements in runtime system of HPX since after PR was merged?
Today, I re-benchmarked parallel::merge, and I got better result rather than past result which was measured 2 months ago.
Now, parallel::merge seems 2 times or more faster than sequential thing in 2 or 4 cores. (More cores can't improve performance still.)

@hkaiser
Copy link
Member

hkaiser commented Oct 28, 2017

@taeguk Everything is possible ;-) I wouldn't know from the top of my head however what was changed that may enable the performance improvements you are seeing.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Standard Algorithms
  
Merged to master
Development

Successfully merging this pull request may close these issues.

None yet

2 participants