#851

Committed 16 Dec 2022 12:27PM CUT coverage: 86.568% (+0.2%) from 86.404%

Build # #851

Build Type

push

Committed by StellarBot

Commit Message

Merge #6104

6104: Adding parameters API: measure_iteration r=hkaiser a=hkaiser

- split `get_chunk_size` CP into `measure_iteration` and modified `get_chunk_size`
- introducing a breaking change to `get_chunk_size` and `processing_units_count` customization point, those now expect the time for one iteration

The new APIs are:
```
    template <typename Target, typename F>
    hpx::chrono::steady_duration measure_iteration(
        Target&&, F&&, std::size_t num_tasks);

    template <typename Target>
    std::size_t processing_units_count(
        Target&&, hpx::chrono::steady_duration const&, std::size_t num_tasks);

    template <typename Target>
    std::size_t get_chunk_size(Target&&,
        hpx::chrono::steady_duration const&, std::size_t num_cores,
        std::size_t num_tasks);
```
This also moves all executor parameter objects to `namespace hpx::execution::experimental`. 

Co-authored-by: Hartmut Kaiser <hartmut.kaiser@gmail.com>

Run Details

209 of 209 new or added lines in 34 files covered. (100.0%)

174475 of 201546 relevant lines covered (86.57%)

1888115.1 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

83.33

/libs/core/algorithms/include/hpx/parallel/algorithms/shift_right.hpp

//  Copyright (c) 2007-2017 Hartmut Kaiser
//  Copyright (c) 2021 Akhil J Nair
//
//  SPDX-License-Identifier: BSL-1.0
//  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)

/// \file parallel/algorithms/shift_right.hpp

#pragma once

#if defined(DOXYGEN)
namespace hpx {
    // clang-format off

    ///////////////////////////////////////////////////////////////////////////
    /// Shifts the elements in the range [first, last) by n positions towards
    /// the end of the range. For every integer i in [0, last - first - n),
    /// moves the element originally at position first + i to position first
    /// + n + i.
    ///
    /// \note   Complexity: At most (last - first) - n assignments.
    ///
    /// \tparam FwdIter     The type of the source iterators used (deduced).
    ///                     This iterator type must meet the requirements of a
    ///                     forward iterator.
    /// \tparam Size        The type of the argument specifying the number of
    ///                     positions to shift by.
    ///
    /// \param first        Refers to the beginning of the sequence of elements
    ///                     the algorithm will be applied to.
    /// \param last         Refers to the end of the sequence of elements the
    ///                     algorithm will be applied to.
    /// \param n            Refers to the number of positions to shift.
    ///
    /// The assignment operations in the parallel \a shift_right algorithm
    /// invoked without an execution policy object will execute in sequential
    /// order in the calling thread.
    ///
    /// \note The type of dereferenced \a FwdIter must meet the requirements
    ///       of \a MoveAssignable.
    ///
    /// \returns  The \a shift_right algorithm returns \a FwdIter.
    ///           The \a shift_right algorithm returns an iterator to the
    ///           end of the resulting range.
    ///
    template <typename FwdIter, typename Size>
    FwdIter shift_right(FwdIter first, FwdIter last, Size n);

    ///////////////////////////////////////////////////////////////////////////
    /// Shifts the elements in the range [first, last) by n positions towards
    /// the end of the range. For every integer i in [0, last - first - n),
    /// moves the element originally at position first + i to position first
    /// + n + i. Executed according to the policy.
    ///
    /// \note   Complexity: At most (last - first) - n assignments.
    ///
    /// \tparam ExPolicy    The type of the execution policy to use (deduced).
    ///                     It describes the manner in which the execution
    ///                     of the algorithm may be parallelized and the manner
    ///                     in which it executes the assignments.
    /// \tparam FwdIter     The type of the source iterators used (deduced).
    ///                     This iterator type must meet the requirements of a
    ///                     forward iterator.
    /// \tparam Size        The type of the argument specifying the number of
    ///                     positions to shift by.
    ///
    /// \param policy       The execution policy to use for the scheduling of
    ///                     the iterations.
    /// \param first        Refers to the beginning of the sequence of elements
    ///                     the algorithm will be applied to.
    /// \param last         Refers to the end of the sequence of elements the
    ///                     algorithm will be applied to.
    /// \param n            Refers to the number of positions to shift.
    ///
    /// The assignment operations in the parallel \a shift_right algorithm
    /// invoked with an execution policy object of type \a sequenced_policy
    /// execute in sequential order in the calling thread.
    ///
    /// The assignment operations in the parallel \a shift_right algorithm
    /// invoked with an execution policy object of type \a parallel_policy
    /// or \a parallel_task_policy are permitted to execute in an unordered
    /// fashion in unspecified threads, and indeterminately sequenced
    /// within each thread.
    ///
    /// \note The type of dereferenced \a FwdIter must meet the requirements
    ///       of \a MoveAssignable.
    ///
    /// \returns  The \a shift_right algorithm returns a
    ///           \a hpx::future<FwdIter> if
    ///           the execution policy is of type
    ///           \a sequenced_task_policy or
    ///           \a parallel_task_policy and
    ///           returns \a FwdIter otherwise.
    ///           The \a shift_right algorithm returns an iterator to the
    ///           end of the resulting range.
    ///
    template <typename ExPolicy, typename FwdIter, typename Size>
    typename hpx::parallel::util::detail::algorithm_result<ExPolicy, FwdIter>
    shift_right(ExPolicy&& policy, FwdIter first, FwdIter last, Size n);

    // clang-format on
}    // namespace hpx

#else    // DOXYGEN

#include <hpx/config.hpp>
#include <hpx/async_local/dataflow.hpp>
#include <hpx/concepts/concepts.hpp>
#include <hpx/iterator_support/traits/is_iterator.hpp>
#include <hpx/modules/execution.hpp>
#include <hpx/pack_traversal/unwrap.hpp>

#include <hpx/executors/execution_policy.hpp>
#include <hpx/parallel/algorithms/copy.hpp>
#include <hpx/parallel/algorithms/detail/dispatch.hpp>
#include <hpx/parallel/algorithms/reverse.hpp>
#include <hpx/parallel/util/detail/algorithm_result.hpp>
#include <hpx/parallel/util/result_types.hpp>
#include <hpx/parallel/util/transfer.hpp>

#include <algorithm>
#include <cstddef>
#include <iterator>
#include <type_traits>
#include <utility>

namespace hpx { namespace parallel { inline namespace v1 {
    ///////////////////////////////////////////////////////////////////////////
    // shift_right
    namespace detail {
        template <typename ExPolicy, typename FwdIter, typename Sent>
        hpx::future<FwdIter> shift_right_helper(
            ExPolicy policy, FwdIter first, Sent last, FwdIter new_first)
        {
            using non_seq = std::false_type;

            auto p = hpx::execution::parallel_task_policy()
                         .on(policy.executor())
                         .with(policy.parameters());

            detail::reverse<FwdIter> r;
            return dataflow(
                [=](hpx::future<FwdIter>&& f1) mutable -> hpx::future<FwdIter> {
                    f1.get();

                    hpx::future<FwdIter> f = r.call2(p, non_seq(), first, last);
                    return f.then(
                        [=](hpx::future<FwdIter>&& f) mutable -> FwdIter {
                            f.get();
                            return new_first;
                        });
                },
                r.call2(p, non_seq(), first, new_first));
        }

        /* Sequential shift_right implementation borrowed
        from https://github.com/danra/shift_proposal */

        template <class I>
        using difference_type_t =
            typename std::iterator_traits<I>::difference_type;

        template <class I>
        using iterator_category_t =
            typename std::iterator_traits<I>::iterator_category;

        template <class I, class Tag, class = void>
        constexpr bool is_category = false;
        template <class I, class Tag>
        constexpr bool is_category<I, Tag,
            std::enable_if_t<
                std::is_convertible_v<iterator_category_t<I>, Tag>>> = true;

        template <typename FwdIter>
        FwdIter sequential_shift_right(FwdIter first, FwdIter last,
            difference_type_t<FwdIter> n, std::size_t dist)
        {
            if constexpr (is_category<FwdIter, std::bidirectional_iterator_tag>)
            {
                auto mid = std::next(first, dist - n);
                return std::move_backward(
                    HPX_MOVE(first), HPX_MOVE(mid), HPX_MOVE(last));
            }
            else
            {
                auto result = std::next(first, n);
                auto lead = result;
                auto trail = first;

                for (; trail != result; ++lead, void(++trail))
                {
                    if (lead == last)
                    {
                        std::move(HPX_MOVE(first), HPX_MOVE(trail), result);
                        return result;
                    }
                }

                for (;;)
                {
                    for (auto mid = first; mid != result;
                         ++lead, void(++trail), ++mid)
                    {
                        if (lead == last)
                        {
                            trail = std::move(mid, result, HPX_MOVE(trail));
                            std::move(HPX_MOVE(first), HPX_MOVE(mid),
                                HPX_MOVE(trail));
                            return result;
                        }
                        std::iter_swap(mid, trail);
                    }
                }
            }
        }

        template <typename FwdIter2>
        struct shift_right
          : public detail::algorithm<shift_right<FwdIter2>, FwdIter2>
        {
            shift_right()
              : shift_right::algorithm("shift_right")
            {
            }

            template <typename ExPolicy, typename FwdIter, typename Sent,
                typename Size>
            static FwdIter sequential(
                ExPolicy, FwdIter first, Sent last, Size n)
            {
                auto dist =
                    static_cast<std::size_t>(detail::distance(first, last));
                if (n <= 0 || static_cast<std::size_t>(n) >= dist)
                {
                    return first;
                }

                auto last_iter = detail::advance_to_sentinel(first, last);
                return detail::sequential_shift_right(
                    first, last_iter, difference_type_t<FwdIter>(n), dist);
            }

            template <typename ExPolicy, typename Sent, typename Size>
            static typename util::detail::algorithm_result<ExPolicy,
                FwdIter2>::type
            parallel(ExPolicy&& policy, FwdIter2 first, Sent last, Size n)
            {
                auto dist =
                    static_cast<std::size_t>(detail::distance(first, last));
                if (n <= 0 || static_cast<std::size_t>(n) >= dist)
                {
                    return parallel::util::detail::algorithm_result<ExPolicy,
                        FwdIter2>::get(HPX_MOVE(first));
                }

                auto new_first = std::next(first, dist - n);
                return util::detail::algorithm_result<ExPolicy, FwdIter2>::get(
                    shift_right_helper(policy, first, last, new_first));
            }
        };
        /// \endcond
    }    // namespace detail
}}}      // namespace hpx::parallel::v1

namespace hpx {

    ///////////////////////////////////////////////////////////////////////////
    // CPO for hpx::shift_right
    inline constexpr struct shift_right_t final
      : hpx::functional::detail::tag_fallback<shift_right_t>
    {
    private:
        // clang-format off
        template <typename FwdIter, typename Size,
            HPX_CONCEPT_REQUIRES_(
                hpx::traits::is_iterator<FwdIter>::value)>
        // clang-format on
        friend FwdIter tag_fallback_invoke(
            shift_right_t, FwdIter first, FwdIter last, Size n)
        {
            static_assert(hpx::traits::is_forward_iterator<FwdIter>::value,
                "Requires at least forward iterator.");

            return hpx::parallel::v1::detail::shift_right<FwdIter>().call(
                hpx::execution::seq, first, last, n);
        }

        // clang-format off
        template <typename ExPolicy, typename FwdIter, typename Size,
            HPX_CONCEPT_REQUIRES_(
                hpx::is_execution_policy<ExPolicy>::value &&
                hpx::traits::is_iterator<FwdIter>::value)>
        // clang-format on
        friend typename hpx::parallel::util::detail::algorithm_result<ExPolicy,
            FwdIter>::type
        tag_fallback_invoke(shift_right_t, ExPolicy&& policy, FwdIter first,
            FwdIter last, Size n)
        {
            static_assert(hpx::traits::is_forward_iterator<FwdIter>::value,
                "Requires at least forward iterator.");

            return hpx::parallel::v1::detail::shift_right<FwdIter>().call(
                HPX_FORWARD(ExPolicy, policy), first, last, n);
        }
    } shift_right{};
}    // namespace hpx

#endif    // DOXYGEN

1	// Copyright (c) 2007-2017 Hartmut Kaiser
2	// Copyright (c) 2021 Akhil J Nair
3	//
4	// SPDX-License-Identifier: BSL-1.0
5	// Distributed under the Boost Software License, Version 1.0. (See accompanying
6	// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7
8	/// \file parallel/algorithms/shift_right.hpp
9
10	#pragma once
11
12	#if defined(DOXYGEN)
13	namespace hpx {
14	// clang-format off
15
16	///////////////////////////////////////////////////////////////////////////
17	/// Shifts the elements in the range [first, last) by n positions towards
18	/// the end of the range. For every integer i in [0, last - first - n),
19	/// moves the element originally at position first + i to position first
20	/// + n + i.
21	///
22	/// \note Complexity: At most (last - first) - n assignments.
23	///
24	/// \tparam FwdIter The type of the source iterators used (deduced).
25	/// This iterator type must meet the requirements of a
26	/// forward iterator.
27	/// \tparam Size The type of the argument specifying the number of
28	/// positions to shift by.
29	///
30	/// \param first Refers to the beginning of the sequence of elements
31	/// the algorithm will be applied to.
32	/// \param last Refers to the end of the sequence of elements the
33	/// algorithm will be applied to.
34	/// \param n Refers to the number of positions to shift.
35	///
36	/// The assignment operations in the parallel \a shift_right algorithm
37	/// invoked without an execution policy object will execute in sequential
38	/// order in the calling thread.
39	///
40	/// \note The type of dereferenced \a FwdIter must meet the requirements
41	/// of \a MoveAssignable.
42	///
43	/// \returns The \a shift_right algorithm returns \a FwdIter.
44	/// The \a shift_right algorithm returns an iterator to the
45	/// end of the resulting range.
46	///
47	template <typename FwdIter, typename Size>
48	FwdIter shift_right(FwdIter first, FwdIter last, Size n);
49
50	///////////////////////////////////////////////////////////////////////////
51	/// Shifts the elements in the range [first, last) by n positions towards
52	/// the end of the range. For every integer i in [0, last - first - n),
53	/// moves the element originally at position first + i to position first
54	/// + n + i. Executed according to the policy.
55	///
56	/// \note Complexity: At most (last - first) - n assignments.
57	///
58	/// \tparam ExPolicy The type of the execution policy to use (deduced).
59	/// It describes the manner in which the execution
60	/// of the algorithm may be parallelized and the manner
61	/// in which it executes the assignments.
62	/// \tparam FwdIter The type of the source iterators used (deduced).
63	/// This iterator type must meet the requirements of a
64	/// forward iterator.
65	/// \tparam Size The type of the argument specifying the number of
66	/// positions to shift by.
67	///
68	/// \param policy The execution policy to use for the scheduling of
69	/// the iterations.
70	/// \param first Refers to the beginning of the sequence of elements
71	/// the algorithm will be applied to.
72	/// \param last Refers to the end of the sequence of elements the
73	/// algorithm will be applied to.
74	/// \param n Refers to the number of positions to shift.
75	///
76	/// The assignment operations in the parallel \a shift_right algorithm
77	/// invoked with an execution policy object of type \a sequenced_policy
78	/// execute in sequential order in the calling thread.
79	///
80	/// The assignment operations in the parallel \a shift_right algorithm
81	/// invoked with an execution policy object of type \a parallel_policy
82	/// or \a parallel_task_policy are permitted to execute in an unordered
83	/// fashion in unspecified threads, and indeterminately sequenced
84	/// within each thread.
85	///
86	/// \note The type of dereferenced \a FwdIter must meet the requirements
87	/// of \a MoveAssignable.
88	///
89	/// \returns The \a shift_right algorithm returns a
90	/// \a hpx::future<FwdIter> if
91	/// the execution policy is of type
92	/// \a sequenced_task_policy or
93	/// \a parallel_task_policy and
94	/// returns \a FwdIter otherwise.
95	/// The \a shift_right algorithm returns an iterator to the
96	/// end of the resulting range.
97	///
98	template <typename ExPolicy, typename FwdIter, typename Size>
99	typename hpx::parallel::util::detail::algorithm_result<ExPolicy, FwdIter>
100	shift_right(ExPolicy&& policy, FwdIter first, FwdIter last, Size n);
101
102	// clang-format on
103	} // namespace hpx
104
105	#else // DOXYGEN
106
107	#include <hpx/config.hpp>
108	#include <hpx/async_local/dataflow.hpp>
109	#include <hpx/concepts/concepts.hpp>
110	#include <hpx/iterator_support/traits/is_iterator.hpp>
111	#include <hpx/modules/execution.hpp>
112	#include <hpx/pack_traversal/unwrap.hpp>
113
114	#include <hpx/executors/execution_policy.hpp>
115	#include <hpx/parallel/algorithms/copy.hpp>
116	#include <hpx/parallel/algorithms/detail/dispatch.hpp>
117	#include <hpx/parallel/algorithms/reverse.hpp>
118	#include <hpx/parallel/util/detail/algorithm_result.hpp>
119	#include <hpx/parallel/util/result_types.hpp>
120	#include <hpx/parallel/util/transfer.hpp>
121
122	#include <algorithm>
123	#include <cstddef>
124	#include <iterator>
125	#include <type_traits>
126	#include <utility>
127
128	namespace hpx { namespace parallel { inline namespace v1 {
129	///////////////////////////////////////////////////////////////////////////
130	// shift_right
131	namespace detail {
132	template <typename ExPolicy, typename FwdIter, typename Sent>
133	hpx::future<FwdIter> shift_right_helper(	16✔
134	ExPolicy policy, FwdIter first, Sent last, FwdIter new_first)
135	{
136	using non_seq = std::false_type;
137
138	auto p = hpx::execution::parallel_task_policy()	32✔
139	.on(policy.executor())	16✔
140	.with(policy.parameters());	16✔
141
142	detail::reverse<FwdIter> r;	16✔
143	return dataflow(	16✔
144	[=](hpx::future<FwdIter>&& f1) mutable -> hpx::future<FwdIter> {	32✔
145	f1.get();	16✔
146
147	hpx::future<FwdIter> f = r.call2(p, non_seq(), first, last);	16✔
148	return f.then(	16✔
149	[=](hpx::future<FwdIter>&& f) mutable -> FwdIter {	32✔
150	f.get();	16✔
151	return new_first;	16✔
152	});
153	},	16✔
154	r.call2(p, non_seq(), first, new_first));	16✔
155	}	×
156
157	/* Sequential shift_right implementation borrowed
158	from https://github.com/danra/shift_proposal */
159
160	template <class I>
161	using difference_type_t =
162	typename std::iterator_traits<I>::difference_type;
163
164	template <class I>
165	using iterator_category_t =
166	typename std::iterator_traits<I>::iterator_category;
167
168	template <class I, class Tag, class = void>
169	constexpr bool is_category = false;
170	template <class I, class Tag>
171	constexpr bool is_category<I, Tag,
172	std::enable_if_t<
173	std::is_convertible_v<iterator_category_t<I>, Tag>>> = true;
174
175	template <typename FwdIter>
176	FwdIter sequential_shift_right(FwdIter first, FwdIter last,	18✔
177	difference_type_t<FwdIter> n, std::size_t dist)
178	{
179	if constexpr (is_category<FwdIter, std::bidirectional_iterator_tag>)
180	{
181	auto mid = std::next(first, dist - n);	16✔
182	return std::move_backward(	16✔
183	HPX_MOVE(first), HPX_MOVE(mid), HPX_MOVE(last));	16✔
184	}
185	else
186	{
187	auto result = std::next(first, n);	2✔
188	auto lead = result;	2✔
189	auto trail = first;	2✔
190
191	for (; trail != result; ++lead, void(++trail))	60,845✔
192	{
193	if (lead == last)	60,845✔
194	{
195	std::move(HPX_MOVE(first), HPX_MOVE(trail), result);	2✔
196	return result;	2✔
197	}
198	}	60,843✔
199
200	for (;;)	×
201	{
202	for (auto mid = first; mid != result;	×
203	++lead, void(++trail), ++mid)	×
204	{
205	if (lead == last)	×
206	{
207	trail = std::move(mid, result, HPX_MOVE(trail));	×
208	std::move(HPX_MOVE(first), HPX_MOVE(mid),	×
209	HPX_MOVE(trail));	×
210	return result;	×
211	}
212	std::iter_swap(mid, trail);	×
213	}	×
214	}
215	}
216	}	2✔
217
218	template <typename FwdIter2>
219	struct shift_right
220	: public detail::algorithm<shift_right<FwdIter2>, FwdIter2>
221	{
222	shift_right()	136✔
223	: shift_right::algorithm("shift_right")	136✔
224	{	136✔
225	}	136✔
226
227	template <typename ExPolicy, typename FwdIter, typename Sent,
228	typename Size>
229	static FwdIter sequential(	72✔
230	ExPolicy, FwdIter first, Sent last, Size n)
231	{
232	auto dist =	72✔
233	static_cast<std::size_t>(detail::distance(first, last));	72✔
234	if (n <= 0 \|\| static_cast<std::size_t>(n) >= dist)	72✔
235	{
236	return first;	54✔
237	}
238
239	auto last_iter = detail::advance_to_sentinel(first, last);	18✔
240	return detail::sequential_shift_right(	18✔
241	first, last_iter, difference_type_t<FwdIter>(n), dist);	18✔
242	}	72✔
243
244	template <typename ExPolicy, typename Sent, typename Size>
245	static typename util::detail::algorithm_result<ExPolicy,
246	FwdIter2>::type
247	parallel(ExPolicy&& policy, FwdIter2 first, Sent last, Size n)	64✔
248	{
249	auto dist =	64✔
250	static_cast<std::size_t>(detail::distance(first, last));	64✔
251	if (n <= 0 \|\| static_cast<std::size_t>(n) >= dist)	64✔
252	{
253	return parallel::util::detail::algorithm_result<ExPolicy,	48✔
254	FwdIter2>::get(HPX_MOVE(first));
255	}
256
257	auto new_first = std::next(first, dist - n);	16✔
258	return util::detail::algorithm_result<ExPolicy, FwdIter2>::get(	16✔
259	shift_right_helper(policy, first, last, new_first));	16✔
260	}	64✔
261	};
262	/// \endcond
263	} // namespace detail
264	}}} // namespace hpx::parallel::v1
265
266	namespace hpx {
267
268	///////////////////////////////////////////////////////////////////////////
269	// CPO for hpx::shift_right
270	inline constexpr struct shift_right_t final
271	: hpx::functional::detail::tag_fallback<shift_right_t>
272	{
273	private:
274	// clang-format off
275	template <typename FwdIter, typename Size,
276	HPX_CONCEPT_REQUIRES_(
277	hpx::traits::is_iterator<FwdIter>::value)>
278	// clang-format on
279	friend FwdIter tag_fallback_invoke(	16✔
280	shift_right_t, FwdIter first, FwdIter last, Size n)
281	{
282	static_assert(hpx::traits::is_forward_iterator<FwdIter>::value,
283	"Requires at least forward iterator.");
284
285	return hpx::parallel::v1::detail::shift_right<FwdIter>().call(	16✔
286	hpx::execution::seq, first, last, n);
287	}
288
289	// clang-format off
290	template <typename ExPolicy, typename FwdIter, typename Size,
291	HPX_CONCEPT_REQUIRES_(
292	hpx::is_execution_policy<ExPolicy>::value &&
293	hpx::traits::is_iterator<FwdIter>::value)>
294	// clang-format on
295	friend typename hpx::parallel::util::detail::algorithm_result<ExPolicy,
296	FwdIter>::type
297	tag_fallback_invoke(shift_right_t, ExPolicy&& policy, FwdIter first,	40✔
298	FwdIter last, Size n)
299	{
300	static_assert(hpx::traits::is_forward_iterator<FwdIter>::value,
301	"Requires at least forward iterator.");
302
303	return hpx::parallel::v1::detail::shift_right<FwdIter>().call(	80✔
304	HPX_FORWARD(ExPolicy, policy), first, last, n);	40✔
305	}
306	} shift_right{};
307	} // namespace hpx
308
309	#endif // DOXYGEN

STEllAR-GROUP / hpx / #851

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous