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

Support forward and bidirectional iterators in parallel::merge. #2826

Open
taeguk opened this Issue Aug 12, 2017 · 10 comments

Comments

Projects
None yet
3 participants
@taeguk
Member

taeguk commented Aug 12, 2017

I'm implementing parallel::merge. And parallel::merge for random access iterator was already implemented.
But, the problem is supporting forward and bidirectional iterator.
It is very hard to support forward and bidirectional iterator.

I tried to support those, and I implemented in two ways.
First one is utilizing random access's thing with generic iterator function like std::next and std::distance. (https://github.com/taeguk/hpx/blob/tg_merge_all_iter_support/hpx/parallel/algorithms/merge.hpp#L229-L231)
Second one is creating vector of iterator. And then utilizing random access's thing with double dereferencing. (https://github.com/taeguk/hpx/blob/tg_merge_all_iter_support_ver2/hpx/parallel/algorithms/merge.hpp#L347-L372)

Resultingly, two ways are both very slow and using sequential thing is more much better.
And I can't search other implementations of forward and bidirectional iterator in parallel merge.

So, I want to get the ideas to implement forward and bidirectional iterator versions of parallel::merge if you have good ideas.

But, I think it is too hard. So, I want to support only random access iterator for now.
If we determine to just leave this issue for now, we have to determine the policy for handling forward and bidirectional iterators. There are two candidates.
First policy is just restricting iterator tag to random access. fallback to sequential execution is only performed when only HPX_WITH_ALGORITHM_INPUT_ITERATOR_SUPPORT is ON.
Second policy is fallback to sequential execution when forward or bidirectional iterator is given even if HPX_WITH_ALGORITHM_INPUT_ITERATOR_SUPPORT is OFF.

I want to hear your thoughts.

Added by after)
For now, we selected the first policy.
We should rethink and resolve this issue in the future.

@taeguk

This comment has been minimized.

Show comment
Hide comment
@taeguk

taeguk Aug 12, 2017

Member

@biddisco @hkaiser Excuse me, could you give me your thoughts about this issue?

Member

taeguk commented Aug 12, 2017

@biddisco @hkaiser Excuse me, could you give me your thoughts about this issue?

@taeguk

This comment has been minimized.

Show comment
Hide comment
@taeguk

taeguk Aug 12, 2017

Member

And where can I see the requirements of iterator tag in the standard?
Every documents don't mention the requirements of iterator tag of parallel algorithms except only cppreference.com (http://en.cppreference.com/w/cpp/algorithm/merge).

Member

taeguk commented Aug 12, 2017

And where can I see the requirements of iterator tag in the standard?
Every documents don't mention the requirements of iterator tag of parallel algorithms except only cppreference.com (http://en.cppreference.com/w/cpp/algorithm/merge).

@hkaiser

This comment has been minimized.

Show comment
Hide comment
@hkaiser

hkaiser Aug 12, 2017

Member

@taeguk: a couple of thoughts:

  • using std::next and std::distance with random access iterators shouldn't be slow as in this case those functions turn into simple arithmetic (pointer) operations.
  • calling merge with anything but random access iterators will be slow by definition as any operation on iterators will result in a sequential loop
  • the only thing I could think of would be to implement two versions of merge, one for random access iterators (using operator+= and operator-) and one for non-random access iterators (possibly based on the double dereferencing technique you mention)
Member

hkaiser commented Aug 12, 2017

@taeguk: a couple of thoughts:

  • using std::next and std::distance with random access iterators shouldn't be slow as in this case those functions turn into simple arithmetic (pointer) operations.
  • calling merge with anything but random access iterators will be slow by definition as any operation on iterators will result in a sequential loop
  • the only thing I could think of would be to implement two versions of merge, one for random access iterators (using operator+= and operator-) and one for non-random access iterators (possibly based on the double dereferencing technique you mention)
@hkaiser

This comment has been minimized.

Show comment
Hide comment
@hkaiser

hkaiser Aug 12, 2017

Member

And where can I see the requirements of iterator tag in the standard?

If not otherwise stated all algorithms taking an execution policy should work for at least forward iterators. The committee explicitly ditched support for input iterators for those overloads. In the end cppreference is a perfect source of information for this.

Member

hkaiser commented Aug 12, 2017

And where can I see the requirements of iterator tag in the standard?

If not otherwise stated all algorithms taking an execution policy should work for at least forward iterators. The committee explicitly ditched support for input iterators for those overloads. In the end cppreference is a perfect source of information for this.

@hkaiser

This comment has been minimized.

Show comment
Hide comment
@hkaiser

hkaiser Aug 12, 2017

Member

And where can I see the requirements of iterator tag in the standard?

If not otherwise stated all algorithms taking an execution policy should work for at least forward iterators. The committee explicitly ditched support for input iterators for those overloads. In the end cppreference is a perfect source of information for this.

Let me rephrase this: all algorithms taking an execution policy should work for at least forward iterators except if there are stronger iterator requirements defined for the corresponding sequential algorithm (the one not taking an execution policy). In this case the stronger requirements apply.

Member

hkaiser commented Aug 12, 2017

And where can I see the requirements of iterator tag in the standard?

If not otherwise stated all algorithms taking an execution policy should work for at least forward iterators. The committee explicitly ditched support for input iterators for those overloads. In the end cppreference is a perfect source of information for this.

Let me rephrase this: all algorithms taking an execution policy should work for at least forward iterators except if there are stronger iterator requirements defined for the corresponding sequential algorithm (the one not taking an execution policy). In this case the stronger requirements apply.

@taeguk

This comment has been minimized.

Show comment
Hide comment
@taeguk

taeguk Aug 12, 2017

Member

the only thing I could think of would be to implement two versions of merge, one for random access iterators (using operator+= and operator-) and one for non-random access iterators (possibly based on the double dereferencing technique you mention)

@hkaiser I already implemented one for non-random access iterators based on the double dereferencing technique. But, the performance is so terrible. Preparation for utilizing the way using double dereferencing takes very very much time... (https://github.com/taeguk/hpx/blob/tg_merge_all_iter_support_ver2/hpx/parallel/algorithms/merge.hpp#L347-L358)
I had a try to parallelize the preparation progress. But, there is no improvement because of maybe memory bandwidth. (https://github.com/taeguk/hpx/blob/tg_merge_all_iter_support_ver2_par_init/hpx/parallel/algorithms/merge.hpp#L348-L395)

Member

taeguk commented Aug 12, 2017

the only thing I could think of would be to implement two versions of merge, one for random access iterators (using operator+= and operator-) and one for non-random access iterators (possibly based on the double dereferencing technique you mention)

@hkaiser I already implemented one for non-random access iterators based on the double dereferencing technique. But, the performance is so terrible. Preparation for utilizing the way using double dereferencing takes very very much time... (https://github.com/taeguk/hpx/blob/tg_merge_all_iter_support_ver2/hpx/parallel/algorithms/merge.hpp#L347-L358)
I had a try to parallelize the preparation progress. But, there is no improvement because of maybe memory bandwidth. (https://github.com/taeguk/hpx/blob/tg_merge_all_iter_support_ver2_par_init/hpx/parallel/algorithms/merge.hpp#L348-L395)

@taeguk

This comment has been minimized.

Show comment
Hide comment
@taeguk

taeguk Aug 14, 2017

Member

@hkaiser Anyway, I think that it is hard to implement parallel merge for forward and bidirectional iterator faster than sequential thing. So, for now, I want to submit PR including what I did until now.

But, I think it is too hard. So, I want to support only random access iterator for now.
If we determine to just leave this issue for now, we have to determine the policy for handling forward and bidirectional iterators. There are two candidates.
First policy is just restricting iterator tag to random access. fallback to sequential execution is only performed when only HPX_WITH_ALGORITHM_INPUT_ITERATOR_SUPPORT is ON.
Second policy is fallback to sequential execution when forward or bidirectional iterator is given even if HPX_WITH_ALGORITHM_INPUT_ITERATOR_SUPPORT is OFF.

So, we need to determine policy about forward and bidirectional iterator for now.
Between two policies, which one is better do you think?

Member

taeguk commented Aug 14, 2017

@hkaiser Anyway, I think that it is hard to implement parallel merge for forward and bidirectional iterator faster than sequential thing. So, for now, I want to submit PR including what I did until now.

But, I think it is too hard. So, I want to support only random access iterator for now.
If we determine to just leave this issue for now, we have to determine the policy for handling forward and bidirectional iterators. There are two candidates.
First policy is just restricting iterator tag to random access. fallback to sequential execution is only performed when only HPX_WITH_ALGORITHM_INPUT_ITERATOR_SUPPORT is ON.
Second policy is fallback to sequential execution when forward or bidirectional iterator is given even if HPX_WITH_ALGORITHM_INPUT_ITERATOR_SUPPORT is OFF.

So, we need to determine policy about forward and bidirectional iterator for now.
Between two policies, which one is better do you think?

@taeguk taeguk referenced this issue Aug 15, 2017

Merged

Implement parallel::merge. #2833

4 of 4 tasks complete
@taeguk

This comment has been minimized.

Show comment
Hide comment
@taeguk

taeguk Aug 15, 2017

Member

For now, I restricted the requirements of parallel::merge to only random access iterator. (In other words, I selected first policy which I said above).

Member

taeguk commented Aug 15, 2017

For now, I restricted the requirements of parallel::merge to only random access iterator. (In other words, I selected first policy which I said above).

@hkaiser

This comment has been minimized.

Show comment
Hide comment
@hkaiser

hkaiser Aug 15, 2017

Member

Ok. Please create a ticket reminding us that we need to get back to this.

Member

hkaiser commented Aug 15, 2017

Ok. Please create a ticket reminding us that we need to get back to this.

@taeguk

This comment has been minimized.

Show comment
Hide comment
@taeguk

taeguk Aug 15, 2017

Member

@hkaiser Should I create new issue? I think that this issue is the ticket itself.

Member

taeguk commented Aug 15, 2017

@hkaiser Should I create new issue? I think that this issue is the ticket itself.

@taeguk taeguk referenced this issue Oct 28, 2017

Merged

Implement parallel::inplace_merge. #2978

4 of 4 tasks complete

@msimberg msimberg removed this from the 1.1.0 milestone Dec 5, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment