Adapting iterator requirements for parallel algorithms #2733

hkaiser · 2017-07-01T13:50:37Z

This makes the iterator requirements of the parallel algorithms conforming to C++17. It mainly strengthens those requirements by not allowing pure input or output iterators.

This fixes #2699.

This also applies some flyby changes:

consistently using hpx::util::invoke to call predicates
all lambda function now have explicit return types specified

…oop`

…detection

- flyby: simplified destroy

…thms/is_heap.hpp - flyby: add return types to lambdas

sithhell · 2017-07-03T13:24:32Z

CMakeLists.txt

@@ -912,6 +912,14 @@ if(HPX_WITH_INCLUSIVE_SCAN_COMPATIBILITY)
  hpx_add_config_define(HPX_HAVE_INCLUSIVE_SCAN_COMPATIBILITY)
 endif()

+# HPX_WITH_ALGORITHM_INPUT_ITERATOR_SUPPORT: introduced in V1.1.0
+hpx_option(HPX_WITH_ALGORITHM_INPUT_ITERATOR_SUPPORT BOOL
+    "Enable old overloads for inclkusive_scan (default: OFF)"


There is a typo here. should read inclusive_scan

That's already fixed on master.

This PR will bring the typo back though, no?

I think you are referring to a different option.

Yah, you are right, this was a copy & paste problem to begin with. Should be fixed now.

taeguk · 2017-07-04T01:46:35Z

hpx/parallel/algorithms/copy.hpp

    >::type
-    copy(ExPolicy && policy, InIter first, InIter last, OutIter dest)
+    copy(ExPolicy && policy, FwdIter first, FwdIter last, OutIter dest)


Why didn't you change OutIter? As I think, dest is forward iterator, too.
This comment is applied on other many codes, too.

I just left the type-name as OutIter, the requirements are updated to 'forward iterator'.

Is there any specific reason to left the type-name as OutIter?
As I think, FwdIter seems better because FwdIter can imply 'forward iterator'.

No specific reason, no. I guess I wanted to keep it clear that this parameter is used as a destination iterator...

@hkaiser I understand your intention. But, using OutIter seems not clear because it can't imply forward iterator. As I think, an user can know that it is used as a destination iterator through parameter name.
This naming issue may be tiny thing, but I want to clarify because the naming will be used from all PRs in future.

In cppreference.com, FwdIter is used for destination iterator.
And in c++ standard document, you search keyword 'copy_backward', then you can find that such naming way is used.
(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3797.pdf)

taeguk · 2017-07-04T01:49:08Z

hpx/parallel/algorithms/copy.hpp

    /// \tparam OutIter     The type of the iterator representing the
    ///                     destination range (deduced).
    ///                     This iterator type must meet the requirements of an
-    ///                     output iterator.
+    ///                     forward iterator.


Why is naming inconsistent to documentation?
The parameter type is OutIter. But, it is illustrated to forward iterator in documentation.

I just left the type-name as OutIter, the requirements are updated to 'forward iterator'.

taeguk · 2017-07-04T01:53:51Z

hpx/parallel/algorithms/fill.hpp

            HPX_HOST_DEVICE
            static hpx::util::unused_type
-            sequential(ExPolicy, InIter first, InIter last,
+            sequential(ExPolicy, FwdIter first, FwdIter last,


Apart from adapting the parallel algorithm interface to the standard, this sequential function requires just InputIterator. So I think that InIter is correct in this position. How do you think?
This comment is applied to many spots in this PR, too.

Yes, this could be left as InIter, but it will never be called with an input iterator... Not sure how to proceed.

Right, it will never be called with an input iterator. But, regardless of execution flow, as one independent function, clarifying iterator requirements seems better. If anyone refer this function for another implementation, he(she) may misunderstand that this function only works with forward iterator.

hkaiser · 2017-07-08T21:38:22Z

@taeguk Ok, I'm done with the renaming, please review.

taeguk · 2017-07-09T05:40:37Z

hpx/parallel/algorithms/adjacent_difference.hpp

            static typename util::detail::algorithm_result<
                ExPolicy, Iter
            >::type
-            parallel(ExPolicy && policy, FwdIter first, FwdIter last,
+            parallel(ExPolicy && policy, FwdIter1 first, FwdIter1 last,


There is tiny inconsistent thing.
When there is only one forward iterator type in parameters,
FwdIter is used in some places, but FwdIter1 is used in others.

As I think,
when there is only one forward iterator type in parameters,
changing naming from FwdIter1 to FwdIter is better.

taeguk · 2017-07-09T05:41:11Z

hpx/parallel/algorithms/all_any_none.hpp

    inline typename std::enable_if<
        execution::is_execution_policy<ExPolicy>::value,
        typename util::detail::algorithm_result<ExPolicy, bool>::type
    >::type
-    none_of(ExPolicy && policy, InIter first, InIter last, F && f)
+    none_of(ExPolicy && policy, FwdIter first, FwdIter last, F && f)


There is tiny inconsistent thing.
When there is only one forward iterator type in parameters,
FwdIter is used in some places, but FwdIter1 is used in others.

This one is actually correct, I believe.

taeguk · 2017-07-09T05:52:12Z

hpx/parallel/algorithms/detail/transfer.hpp

        >::type
-        transfer_(ExPolicy && policy, InIter first, InIter last, OutIter dest,
+        transfer_(ExPolicy && policy, FwdIter first, FwdIter last, OutIter dest,


Still, there is OutIter in here. Maybe this is your mistake.

taeguk · 2017-07-09T05:53:29Z

hpx/parallel/algorithms/detail/transfer.hpp

        >::type
-        transfer(ExPolicy && policy, InIter first, InIter last, OutIter dest)
+        transfer(ExPolicy && policy, FwdIter first, FwdIter last, OutIter dest)


Still, there is OutIter in here. Maybe this is your mistake.

taeguk · 2017-07-09T05:53:51Z

hpx/parallel/algorithms/detail/transfer.hpp

        >::type
-        transfer_(ExPolicy && policy, InIter first, InIter last, OutIter dest,
+        transfer_(ExPolicy && policy, FwdIter first, FwdIter last, OutIter dest,


Still, there is OutIter in here. Maybe this is your mistake.

taeguk · 2017-07-09T06:40:46Z

hpx/parallel/algorithms/set_difference.hpp

-               !hpx::traits::is_random_access_iterator<OutIter>::value
+               !hpx::traits::is_random_access_iterator<FwdIter1>::value ||
+               !hpx::traits::is_random_access_iterator<FwdIter2>::value ||
+               !hpx::traits::is_random_access_iterator<FwdIter3>::value


Why is hpx::traits::is_random_access_iterator used instead of hpx::traits::is_forward_iterator?
And, this typedef of is_seq should be inside conditional macro above as I think.
This is applied to other places like set algorithms.

taeguk · 2017-07-09T06:46:46Z

hpx/parallel/algorithms/swap_ranges.hpp

@@ -84,7 +85,7 @@ namespace hpx { namespace parallel { inline namespace v1
    ///                     It describes the manner in which the execution
    ///                     of the algorithm may be parallelized and the manner
    ///                     in which it executes the swap operations.
-    /// \tparam ForwardIter1 The type of the first range of iterators to swap
+    /// \tparam FwdIter1 The type of the first range of iterators to swap


More spaces are needed for beauty.

taeguk · 2017-07-09T06:51:54Z

hpx/parallel/algorithms/transform.hpp

-    ///                     input iterator.
-    /// \tparam OutIter     The type of the iterator representing the
+    ///                     forward iterator.
+    /// \tparam FwdIter3   se The type of the iterator representing the


what is it? :)

taeguk · 2017-07-09T06:54:37Z

hpx/parallel/algorithms/transform_exclusive_scan.hpp

            sequential(ExPolicy, InIter first, InIter last,
-                OutIter dest, Conv && conv, T && init, Op && op)
+                FwdIter2 dest, Conv && conv, T && init, Op && op)


Maybe FwdIter2 should be changed to OutIter.

taeguk · 2017-07-09T07:07:14Z

hpx/parallel/segmented_algorithms/detail/transfer.hpp

        >::type
-        transfer_(ExPolicy&& policy, InIter first, InIter last, OutIter dest,
+        transfer_(ExPolicy&& policy, FwdIter first, FwdIter last, OutIter dest,


Is it okay to use OutIter as naming in here?
This review is applied in other places in this file.

…UP#2733).

taeguk · 2017-07-11T17:51:17Z

hpx/parallel/algorithms/reverse.hpp

    ///           if the execution policy is of type
    ///           \a sequenced_task_policy or
    ///           \a parallel_task_policy and
-    ///           returns \a tagged_pair<tag::in(BidirIter), tag::out(OutIter)>
+    ///           returns \a tagged_pair<tag::in(BidirIter), tag::out(FwdIter)>
    ///           otherwise.
    ///           The \a copy algorithm returns the pair of the input iterator


Tiny typo
\a copy -> \a reverse_copy

But it is so tiny. So, I'll approve this PR.

taeguk

Thank you for your efforts to fix the issue which I suggested.

hkaiser added 17 commits June 23, 2017 19:46

Restricting iterator categories usable with for_each[_n] and `for_l…

0ec9f95

…oop`

Fixing adjacent_difference

24c347e

Additionally use boost iterator traversal tags for iterator category …

b4e7938

…detection

Fixing all_of, any_of, and none_of

9b4008a

Fixing copy, copy_if, and move

2ba2ad7

Fixed count, count_if, and equal algorithms

d809c2b

- flyby: simplified destroy

Fixing inspect problems

3b104df

Fixing inclusive_scan and exclusive_scan

7ca6f0c

Fixing fill* and find* algorithms

b1da234

Fixing generate, includes, and transform_reduce

5cd77b0

Fixing all uninitialized* algorithms

83a63e8

Fixing is_partitioned, minmax_element, lexicographical_compare algori…

064178e

…thms/is_heap.hpp - flyby: add return types to lambdas

Fixing mismatch and reduce algorithms

1616e86

Fixing set* algorithms

6f4c238

Fixed remove*, replace, reverse, search, and transform algorithms

dce77a9

Fixing transform_*_scan, and transform_reduce algorithms

6485c8c

Fixing range tests

889f962

hkaiser added category: algorithms type: compatibility issue labels Jul 1, 2017

hkaiser added this to the 1.1.0 milestone Jul 1, 2017

hkaiser changed the title ~~Adapting iterator rquirements for parallel algorithms~~ Adapting iterator requirements for parallel algorithms Jul 1, 2017

sithhell reviewed Jul 3, 2017

View reviewed changes

Fix option description in cmake

7df83a4

taeguk reviewed Jul 4, 2017

View reviewed changes

Merge branch 'master' into fixing_2699

5f794c2

taeguk mentioned this pull request Jul 8, 2017

Implement parallel::partition_copy. #2716

Merged

10 tasks

Renamed FwdIter to InIter for sequential functions

4c8cdde

hkaiser force-pushed the fixing_2699 branch from e80436e to 4c8cdde Compare July 8, 2017 20:09

Renamed OutIter --> FwdIter (except for sequential code)

736cb48

taeguk reviewed Jul 9, 2017

View reviewed changes

taeguk added a commit to taeguk/hpx that referenced this pull request Jul 9, 2017

Adapt parallel::partition_copy for iterator requirements (STEllAR-GRO…

bcf5b45

…UP#2733).

taeguk added a commit to taeguk/hpx that referenced this pull request Jul 9, 2017

Adapt parallel::partition_copy for iterator requirements (STEllAR-GRO…

bceca35

…UP#2733).

Remaining naming changes

078c0f7

taeguk reviewed Jul 11, 2017

View reviewed changes

taeguk approved these changes Jul 11, 2017

View reviewed changes

hkaiser merged commit c3d8bdf into master Jul 11, 2017

hkaiser deleted the fixing_2699 branch July 11, 2017 18:09

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Adapting iterator requirements for parallel algorithms #2733

Adapting iterator requirements for parallel algorithms #2733

hkaiser commented Jul 1, 2017

sithhell Jul 3, 2017

hkaiser Jul 3, 2017

sithhell Jul 3, 2017

sithhell Jul 3, 2017

hkaiser Jul 3, 2017

taeguk Jul 4, 2017 •

edited

Loading

hkaiser Jul 4, 2017

taeguk Jul 4, 2017

hkaiser Jul 4, 2017

taeguk Jul 6, 2017

taeguk Jul 6, 2017

taeguk Jul 4, 2017

hkaiser Jul 4, 2017

taeguk Jul 4, 2017 •

edited

Loading

hkaiser Jul 4, 2017

taeguk Jul 6, 2017

hkaiser commented Jul 8, 2017

taeguk Jul 9, 2017

taeguk Jul 9, 2017

hkaiser Jul 10, 2017

taeguk Jul 9, 2017

hkaiser Jul 10, 2017

taeguk Jul 9, 2017

taeguk Jul 9, 2017

taeguk Jul 9, 2017

taeguk Jul 9, 2017

taeguk Jul 9, 2017

taeguk Jul 9, 2017

taeguk Jul 9, 2017

taeguk Jul 9, 2017

taeguk Jul 11, 2017

taeguk Jul 11, 2017

taeguk left a comment

Adapting iterator requirements for parallel algorithms #2733

Adapting iterator requirements for parallel algorithms #2733

Conversation

hkaiser commented Jul 1, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

taeguk Jul 4, 2017 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

taeguk Jul 4, 2017 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

hkaiser commented Jul 8, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

taeguk left a comment

Choose a reason for hiding this comment

taeguk Jul 4, 2017 •

edited

Loading

taeguk Jul 4, 2017 •

edited

Loading