Skip to content

Commit

Permalink
Restricting iterator categories usable with for_each[_n] and `for_l…
Browse files Browse the repository at this point in the history 
…oop`
  • Loading branch information
@hkaiser
hkaiser committed Jun 22, 2017
1 parent e853e98 commit 1713a6e
Show file tree
Hide file tree
Showing 21 changed files with 163 additions and 70 deletions.
8 changes: 8 additions & 0 deletions CMakeLists.txt
View file
Expand Up @@ -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)"
OFF ADVANCED)
if(HPX_WITH_ALGORITHM_INPUT_ITERATOR_SUPPORT)
hpx_add_config_define(HPX_HAVE_ALGORITHM_INPUT_ITERATOR_SUPPORT)
endif()

################################################################################
# Set basic search paths for HPX
################################################################################
Expand Down
8 changes: 8 additions & 0 deletions docs/whats_new.qbk
View file
Expand Up @@ -38,6 +38,14 @@ particular order):
* Removed the (broken) component type `hpx::lcos::queue<T>`. The old type is
still available at configure time by passing
`-DHPX_WITH_QUEUE_COMPATIBILITY=On` to __cmake__.
* The parallel algorithms adopted for C++17 restrict the iterator categories
usable with those to at least forward iterators. Our implementation of the
parallel algorithms was supporting input iterators (and output iterators)
as well by simply falling back to sequential execution. We have now made
our implementations conforming by requiring at least forward iterators. In
order to enable the old behavior use the the compatibility option
`-DHPX_WITH_ALGORITHM_INPUT_ITERATOR_SUPPORT=On` on the __cmake__ command
line.

[heading Breaking Changes]

Expand Down
127 changes: 73 additions & 54 deletions hpx/parallel/algorithms/for_each.hpp
View file
@@ -1,4 +1,4 @@
// Copyright (c) 2007-2016 Hartmut Kaiser
// Copyright (c) 2007-2017 Hartmut Kaiser
//
// Distributed under the Boost Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
Expand Down Expand Up @@ -120,7 +120,8 @@ namespace hpx { namespace parallel { inline namespace v1
{}
#endif

for_each_iteration& operator=(for_each_iteration const&) = delete;
for_each_iteration& operator=(for_each_iteration const&) = default;
for_each_iteration& operator=(for_each_iteration &&) = default;

template <typename Iter>
HPX_HOST_DEVICE HPX_FORCEINLINE
Expand All @@ -142,23 +143,23 @@ namespace hpx { namespace parallel { inline namespace v1
: for_each_n::algorithm("for_each_n")
{}

template <typename ExPolicy, typename InIter, typename F,
template <typename ExPolicy, typename FwdIter, typename F,
typename Proj = util::projection_identity>
HPX_HOST_DEVICE
static Iter
sequential(ExPolicy && policy, InIter first, std::size_t count,
sequential(ExPolicy && policy, FwdIter first, std::size_t count,
F && f, Proj && proj/* = Proj()*/)
{
return util::loop_n<ExPolicy>(first, count,
invoke_projected<F, Proj>{f, proj});
}

template <typename ExPolicy, typename InIter, typename F,
template <typename ExPolicy, typename FwdIter, typename F,
typename Proj = util::projection_identity>
static typename util::detail::algorithm_result<
ExPolicy, InIter
ExPolicy, FwdIter
>::type
parallel(ExPolicy && policy, InIter first, std::size_t count,
parallel(ExPolicy && policy, FwdIter first, std::size_t count,
F && f, Proj && proj/* = Proj()*/)
{
if (count != 0)
Expand All @@ -171,7 +172,7 @@ namespace hpx { namespace parallel { inline namespace v1
std::move(f1), util::projection_identity());
}

return util::detail::algorithm_result<ExPolicy, InIter>::get(
return util::detail::algorithm_result<ExPolicy, FwdIter>::get(
std::move(first));
}
};
Expand Down Expand Up @@ -199,9 +200,9 @@ 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 applies user-provided function objects.
/// \tparam InIter The type of the source iterators used (deduced).
/// \tparam FwdIter The type of the source iterators used (deduced).
/// This iterator type must meet the requirements of an
/// input iterator.
/// forward iterator.
/// \tparam Size The type of the argument specifying the number of
/// elements to apply \a f to.
/// \tparam F The type of the function/function object to use
Expand All @@ -227,7 +228,7 @@ namespace hpx { namespace parallel { inline namespace v1
/// \endcode \n
/// The signature does not need to have const&. The
/// type \a Type must be such that an object of
/// type \a InIter can be dereferenced and then
/// type \a FwdIter can be dereferenced and then
/// implicitly converted to Type.
/// \param proj Specifies the function (or function object) which
/// will be invoked for each of the elements as a
Expand All @@ -246,44 +247,52 @@ namespace hpx { namespace parallel { inline namespace v1
/// threads, and indeterminately sequenced within each thread.
///
/// \returns The \a for_each_n algorithm returns a
/// \a hpx::future<InIter> if the execution policy is of
/// \a hpx::future<FwdIter> if the execution policy is of
/// type
/// \a sequenced_task_policy or
/// \a parallel_task_policy and returns \a InIter
/// \a parallel_task_policy and returns \a FwdIter
/// otherwise.
/// It returns \a first + \a count for non-negative values of
/// \a count and \a first for negative values.
///
template <typename ExPolicy, typename InIter, typename Size, typename F,
template <typename ExPolicy, typename FwdIter, typename Size, typename F,
typename Proj = util::projection_identity,
HPX_CONCEPT_REQUIRES_(
execution::is_execution_policy<ExPolicy>::value &&
hpx::traits::is_iterator<InIter>::value &&
parallel::traits::is_projected<Proj, InIter>::value &&
hpx::traits::is_iterator<FwdIter>::value &&
parallel::traits::is_projected<Proj, FwdIter>::value &&
parallel::traits::is_indirect_callable<
ExPolicy, F, traits::projected<Proj, InIter>
ExPolicy, F, traits::projected<Proj, FwdIter>
>::value)>
typename util::detail::algorithm_result<ExPolicy, InIter>::type
for_each_n(ExPolicy && policy, InIter first, Size count, F && f,
typename util::detail::algorithm_result<ExPolicy, FwdIter>::type
for_each_n(ExPolicy && policy, FwdIter first, Size count, F && f,
Proj && proj = Proj())
{
#if defined(HPX_HAVE_ALGORITHM_INPUT_ITERATOR_SUPPORT)
static_assert(
(hpx::traits::is_input_iterator<InIter>::value),
(hpx::traits::is_input_iterator<FwdIter>::value),
"Requires at least input iterator.");

typedef std::integral_constant<bool,
execution::is_sequenced_execution_policy<ExPolicy>::value ||
!hpx::traits::is_forward_iterator<FwdIter>::value
> is_seq;
#else
static_assert(
(hpx::traits::is_forward_iterator<FwdIter>::value),
"Requires at least forward iterator.");

typedef execution::is_sequenced_execution_policy<ExPolicy> is_seq;
#endif

// if count is representing a negative value, we do nothing
if (detail::is_negative(count))
{
return util::detail::algorithm_result<ExPolicy, InIter>::get(
return util::detail::algorithm_result<ExPolicy, FwdIter>::get(
std::move(first));
}

typedef std::integral_constant<bool,
execution::is_sequenced_execution_policy<ExPolicy>::value ||
!hpx::traits::is_forward_iterator<InIter>::value
> is_seq;

return detail::for_each_n<InIter>().call(
return detail::for_each_n<FwdIter>().call(
std::forward<ExPolicy>(policy), is_seq(),
first, std::size_t(count), std::forward<F>(f),
std::forward<Proj>(proj));
Expand All @@ -301,22 +310,22 @@ namespace hpx { namespace parallel { inline namespace v1
: for_each::algorithm("for_each")
{}

template <typename ExPolicy, typename InIter, typename F,
template <typename ExPolicy, typename FwdIter, typename F,
typename Proj>
static InIter
sequential(ExPolicy && policy, InIter first, InIter last, F && f,
static FwdIter
sequential(ExPolicy && policy, FwdIter first, FwdIter last, F && f,
Proj && proj)
{
return util::loop(std::forward<ExPolicy>(policy), first, last,
invoke_projected<F, Proj>{f, proj});
}

template <typename ExPolicy, typename InIter, typename F,
template <typename ExPolicy, typename FwdIter, typename F,
typename Proj>
static typename util::detail::algorithm_result<
ExPolicy, InIter
ExPolicy, FwdIter
>::type
parallel(ExPolicy && policy, InIter first, InIter last, F && f,
parallel(ExPolicy && policy, FwdIter first, FwdIter last, F && f,
Proj && proj)
{
if (first != last)
Expand All @@ -330,33 +339,37 @@ namespace hpx { namespace parallel { inline namespace v1
std::move(f1), util::projection_identity());
}

return util::detail::algorithm_result<ExPolicy, InIter>::get(
return util::detail::algorithm_result<ExPolicy, FwdIter>::get(
std::move(first));
}
};

///////////////////////////////////////////////////////////////////////
// non-segmented implementation
template <typename ExPolicy, typename InIter, typename F,
template <typename ExPolicy, typename FwdIter, typename F,
typename Proj>
inline typename util::detail::algorithm_result<ExPolicy, InIter>::type
for_each_(ExPolicy && policy, InIter first, InIter last, F && f,
inline typename util::detail::algorithm_result<ExPolicy, FwdIter>::type
for_each_(ExPolicy && policy, FwdIter first, FwdIter last, F && f,
Proj && proj, std::false_type)
{
#if defined(HPX_HAVE_ALGORITHM_INPUT_ITERATOR_SUPPORT)
typedef std::integral_constant<bool,
parallel::execution::is_sequenced_execution_policy<
ExPolicy
>::value ||
!hpx::traits::is_forward_iterator<InIter>::value
!hpx::traits::is_forward_iterator<FwdIter>::value
> is_seq;

#else
typedef parallel::execution::is_sequenced_execution_policy<ExPolicy>
is_seq;
#endif
if (first == last)
{
typedef util::detail::algorithm_result<ExPolicy, InIter> result;
typedef util::detail::algorithm_result<ExPolicy, FwdIter> result;
return result::get(std::move(last));
}

return for_each<InIter>().call(
return for_each<FwdIter>().call(
std::forward<ExPolicy>(policy), is_seq(),
first, last, std::forward<F>(f), std::forward<Proj>(proj));
}
Expand Down Expand Up @@ -391,9 +404,9 @@ 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 applies user-provided function objects.
/// \tparam InIter The type of the source iterators used (deduced).
/// \tparam FwdIter The type of the source iterators used (deduced).
/// This iterator type must meet the requirements of an
/// input iterator.
/// forward iterator.
/// \tparam F The type of the function/function object to use
/// (deduced). Unlike its sequential form, the parallel
/// overload of \a for_each requires \a F to meet the
Expand All @@ -417,7 +430,7 @@ namespace hpx { namespace parallel { inline namespace v1
/// \endcode \n
/// The signature does not need to have const&. The
/// type \a Type must be such that an object of
/// type \a InIter can be dereferenced and then
/// type \a FwdIter can be dereferenced and then
/// implicitly converted to Type.
/// \param proj Specifies the function (or function object) which
/// will be invoked for each of the elements as a
Expand All @@ -436,10 +449,10 @@ namespace hpx { namespace parallel { inline namespace v1
/// threads, and indeterminately sequenced within each thread.
///
/// \returns The \a for_each algorithm returns a
/// \a hpx::future<InIter> if the execution policy is of
/// \a hpx::future<FwdIter> if the execution policy is of
/// type
/// \a sequenced_task_policy or
/// \a parallel_task_policy and returns \a InIter
/// \a parallel_task_policy and returns \a FwdIter
/// otherwise.
/// It returns \a last.
///
Expand All @@ -448,28 +461,34 @@ namespace hpx { namespace parallel { inline namespace v1
// FIXME : is_indirect_callable does not work properly when compiling
// Cuda host code

template <typename ExPolicy, typename InIter, typename F,
template <typename ExPolicy, typename FwdIter, typename F,
typename Proj = util::projection_identity,
HPX_CONCEPT_REQUIRES_(
execution::is_execution_policy<ExPolicy>::value &&
hpx::traits::is_iterator<InIter>::value &&
parallel::traits::is_projected<Proj, InIter>::value)
hpx::traits::is_iterator<FwdIter>::value &&
parallel::traits::is_projected<Proj, FwdIter>::value)
#if (!defined(__NVCC__) && !defined(__CUDACC__)) || defined(__CUDA_ARCH__)
, HPX_CONCEPT_REQUIRES_(
parallel::traits::is_indirect_callable<
ExPolicy, F, traits::projected<Proj, InIter>
ExPolicy, F, traits::projected<Proj, FwdIter>
>::value)
#endif
>
typename util::detail::algorithm_result<ExPolicy, InIter>::type
for_each(ExPolicy && policy, InIter first, InIter last, F && f,
typename util::detail::algorithm_result<ExPolicy, FwdIter>::type
for_each(ExPolicy && policy, FwdIter first, FwdIter last, F && f,
Proj && proj = Proj())
{
#if defined(HPX_HAVE_ALGORITHM_INPUT_ITERATOR_SUPPORT)
static_assert(
(hpx::traits::is_input_iterator<InIter>::value),
(hpx::traits::is_input_iterator<FwdIter>::value),
"Requires at least input iterator.");
#else
static_assert(
(hpx::traits::is_forward_iterator<FwdIter>::value),
"Requires at least forward iterator.");
#endif

typedef hpx::traits::is_segmented_iterator<InIter> is_segmented;
typedef hpx::traits::is_segmented_iterator<FwdIter> is_segmented;

return detail::for_each_(
std::forward<ExPolicy>(policy), first, last,
Expand Down

0 comments on commit 1713a6e

Please sign in to comment.