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

Iterator requirements are different from standard in parallel copy_if. #2699

Closed
taeguk opened this Issue Jun 17, 2017 · 11 comments

Comments

Projects
None yet
4 participants
@taeguk
Member

taeguk commented Jun 17, 2017

In HPX, parallel copy_if has a contract about iterator traits.
As below, at least, input iterator must be InputIterator and output iterator must be OutputIterator.
(

static_assert(
(hpx::traits::is_input_iterator<InIter>::value),
"Required at least input iterator.");
static_assert(
(hpx::traits::is_output_iterator<OutIter>::value ||
hpx::traits::is_forward_iterator<OutIter>::value),
"Requires at least output iterator.");
)

But, as I saw in the cppreference website, it has more stronger a contract.
It requires ForwardIterator.
(http://en.cppreference.com/w/cpp/algorithm/copy)

Of course, in case of sequential execution policy, there is no need for ForwardIterator. Just InputIterator or OutputIterator is sufficient. But, it may be more important to correspond to standard. (In fact,
I don't know exactly how it is stated in the standard. But, I thought it could be because there is a difference between cppreference.com and HPX.)

@hkaiser

This comment has been minimized.

Show comment
Hide comment
@hkaiser

hkaiser Jun 17, 2017

Member

@taeguk: yes, our algorithms (almost all of them) put less restrictions on the iterators than the C++17 standard does. The committee has adopted the stricter requirements only last minute.

I think that this does not violate the standard as it is as we provide a wider contract. Our algorithms simply fall back to sequential execution whenever the given iterators don't allow for parallelizing the execution. We've had a heated discussion in the committee about this and in the end the more conservative approach got the majority of votes to 'leave the door open for better solutions in the future'. I personally would like to keep the current contract in place (i.e. allow for using weak iterators and falling back to sequential execution), but I'm open to discussing this.

Member

hkaiser commented Jun 17, 2017

@taeguk: yes, our algorithms (almost all of them) put less restrictions on the iterators than the C++17 standard does. The committee has adopted the stricter requirements only last minute.

I think that this does not violate the standard as it is as we provide a wider contract. Our algorithms simply fall back to sequential execution whenever the given iterators don't allow for parallelizing the execution. We've had a heated discussion in the committee about this and in the end the more conservative approach got the majority of votes to 'leave the door open for better solutions in the future'. I personally would like to keep the current contract in place (i.e. allow for using weak iterators and falling back to sequential execution), but I'm open to discussing this.

@taeguk

This comment has been minimized.

Show comment
Hide comment
@taeguk

taeguk Jun 17, 2017

Member

@hkaiser But, I'm afraid of users' misunderstandings. The users may misthink that the algorithm executed parallelly although it is executed sequentially because of unsatisfied contracts to parallel execution. Falling back to sequential execution may be confusing to the users.

Member

taeguk commented Jun 17, 2017

@hkaiser But, I'm afraid of users' misunderstandings. The users may misthink that the algorithm executed parallelly although it is executed sequentially because of unsatisfied contracts to parallel execution. Falling back to sequential execution may be confusing to the users.

@hkaiser

This comment has been minimized.

Show comment
Hide comment
@hkaiser

hkaiser Jun 17, 2017

Member

@taeguk: yes this is true. Here I'd like to hear opinions from others as well.

Member

hkaiser commented Jun 17, 2017

@taeguk: yes this is true. Here I'd like to hear opinions from others as well.

@mcopik

This comment has been minimized.

Show comment
Hide comment
@mcopik

mcopik Jun 21, 2017

Contributor

@hkaiser it's rather a rare case. if the InputIterator is not custom then can it be something else then I/O in the form of istream_iterator? I don't remember other examples of standard input iterators.
However, a quite fallback to serial execution creates very subtle bugs. We should at least inform the user about that. Maybe by a warning message? I've seen a logger facility in HPX but it seemed to be designed for other purposes.

Contributor

mcopik commented Jun 21, 2017

@hkaiser it's rather a rare case. if the InputIterator is not custom then can it be something else then I/O in the form of istream_iterator? I don't remember other examples of standard input iterators.
However, a quite fallback to serial execution creates very subtle bugs. We should at least inform the user about that. Maybe by a warning message? I've seen a logger facility in HPX but it seemed to be designed for other purposes.

@hkaiser

This comment has been minimized.

Show comment
Hide comment
@hkaiser

hkaiser Jun 21, 2017

Member

@mcopik I was thinking more towards supporting writing generic facilities which use the parallel algorithms in their implementation. Limiting iterator categories for such facilities might be too restricting and not allowing the parallel algorithms to be used with input iterators may make the implementation of those facilities more cumbersome.

But in the end I don't insist in leaving things as we have them. If the majority of people think to make our implementation more conforming by adhering to the stricter iterator requirements, fine by me. If we do that however we should touch on all algorithms and not only copy_if as mentioned in the original comment above.

Member

hkaiser commented Jun 21, 2017

@mcopik I was thinking more towards supporting writing generic facilities which use the parallel algorithms in their implementation. Limiting iterator categories for such facilities might be too restricting and not allowing the parallel algorithms to be used with input iterators may make the implementation of those facilities more cumbersome.

But in the end I don't insist in leaving things as we have them. If the majority of people think to make our implementation more conforming by adhering to the stricter iterator requirements, fine by me. If we do that however we should touch on all algorithms and not only copy_if as mentioned in the original comment above.

@hkaiser

This comment has been minimized.

Show comment
Hide comment
@hkaiser

hkaiser Jun 22, 2017

Member

If this gets addressed, should we phase out our support for input_iterators using backwards compatibility options or simply break compatibility and drop support for those?

Member

hkaiser commented Jun 22, 2017

If this gets addressed, should we phase out our support for input_iterators using backwards compatibility options or simply break compatibility and drop support for those?

@sithhell

This comment has been minimized.

Show comment
Hide comment
@sithhell

sithhell Jun 23, 2017

Member

We provided backwards compatibilty for almost all of thos cases so far. I think this is one case where we should deliberately break users code. As @mcopik mentioned, it could be a subtle bug. In the end, what i'd like to see is support for those generic algorithms to select the execution policy based on the iterators passed.

Member

sithhell commented Jun 23, 2017

We provided backwards compatibilty for almost all of thos cases so far. I think this is one case where we should deliberately break users code. As @mcopik mentioned, it could be a subtle bug. In the end, what i'd like to see is support for those generic algorithms to select the execution policy based on the iterators passed.

@hkaiser

This comment has been minimized.

Show comment
Hide comment
@hkaiser

hkaiser Jun 23, 2017

Member

In the end, what i'd like to see is support for those generic algorithms to select the execution policy based on the iterators passed.

That's exactly what's happening now, isn't it? I'm confused.

Member

hkaiser commented Jun 23, 2017

In the end, what i'd like to see is support for those generic algorithms to select the execution policy based on the iterators passed.

That's exactly what's happening now, isn't it? I'm confused.

@mcopik

This comment has been minimized.

Show comment
Hide comment
@mcopik

mcopik Jun 23, 2017

Contributor
Contributor

mcopik commented Jun 23, 2017

@sithhell

This comment has been minimized.

Show comment
Hide comment
@sithhell

sithhell Jun 23, 2017

Member
Member

sithhell commented Jun 23, 2017

@hkaiser

This comment has been minimized.

Show comment
Hide comment
@hkaiser
Member

hkaiser commented Jun 25, 2017

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