#865

Committed 13 Jan 2023 11:46PM UTC coverage: 86.431% (+0.08%) from 86.354%

Build # #865

Build Type

push

Committed by StellarBot

Commit Message

Merge #6132

6132: Fixing to_non_par() for parallel simd policies r=hkaiser a=hkaiser



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

Run Details

64 of 64 new or added lines in 3 files covered. (100.0%)

174506 of 201901 relevant lines covered (86.43%)

1999640.87 hits per line

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

0.0

/libs/full/segmented_algorithms/include/hpx/parallel/segmented_algorithms/reduce.hpp

//  Copyright (c) 2017 Ajai V George
//  Copyright (c) 2022 Hartmut Kaiser
//
//  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)

#pragma once

#include <hpx/config.hpp>
#include <hpx/algorithms/traits/segmented_iterator_traits.hpp>
#include <hpx/functional/invoke.hpp>

#include <hpx/executors/execution_policy.hpp>
#include <hpx/parallel/algorithms/detail/accumulate.hpp>
#include <hpx/parallel/algorithms/detail/dispatch.hpp>
#include <hpx/parallel/algorithms/detail/distance.hpp>
#include <hpx/parallel/algorithms/reduce.hpp>
#include <hpx/parallel/segmented_algorithms/detail/dispatch.hpp>
#include <hpx/parallel/segmented_algorithms/detail/reduce.hpp>
#include <hpx/parallel/util/detail/algorithm_result.hpp>
#include <hpx/parallel/util/detail/handle_remote_exceptions.hpp>

#include <algorithm>
#include <exception>
#include <iterator>
#include <list>
#include <numeric>
#include <type_traits>
#include <utility>
#include <vector>

namespace hpx { namespace parallel { inline namespace v1 {
    ///////////////////////////////////////////////////////////////////////////
    // segmented_reduce
    namespace detail {
        ///////////////////////////////////////////////////////////////////////
        /// \cond NOINTERNAL

        // sequential remote implementation
        template <typename Algo, typename ExPolicy, typename SegIterB,
            typename SegIterE, typename T, typename Reduce>
        static typename util::detail::algorithm_result<ExPolicy, T>::type
        segmented_reduce(Algo&& algo, ExPolicy const& policy, SegIterB first,
            SegIterE last, T&& init, Reduce&& red_op, std::true_type)
        {
            typedef hpx::traits::segmented_iterator_traits<SegIterB> traits;
            typedef typename traits::segment_iterator segment_iterator;
            typedef typename traits::local_iterator local_iterator_type;
            typedef util::detail::algorithm_result<ExPolicy, T> result;

            segment_iterator sit = traits::segment(first);
            segment_iterator send = traits::segment(last);

            T overall_result = init;

            if (sit == send)
            {
                // all elements are on the same partition
                local_iterator_type beg = traits::local(first);
                local_iterator_type end = traits::local(last);
                if (beg != end)
                {
                    overall_result = HPX_INVOKE(red_op, overall_result,
                        dispatch(traits::get_id(sit), algo, policy,
                            std::true_type(), beg, end, red_op));
                }
            }
            else
            {
                // handle the remaining part of the first partition
                local_iterator_type beg = traits::local(first);
                local_iterator_type end = traits::end(sit);
                if (beg != end)
                {
                    overall_result = HPX_INVOKE(red_op, overall_result,
                        dispatch(traits::get_id(sit), algo, policy,
                            std::true_type(), beg, end, red_op));
                }

                // handle all of the full partitions
                for (++sit; sit != send; ++sit)
                {
                    beg = traits::begin(sit);
                    end = traits::end(sit);
                    if (beg != end)
                    {
                        overall_result = HPX_INVOKE(red_op, overall_result,
                            dispatch(traits::get_id(sit), algo, policy,
                                std::true_type(), beg, end, red_op));
                    }
                }

                // handle the beginning of the last partition
                beg = traits::begin(sit);
                end = traits::local(last);
                if (beg != end)
                {
                    overall_result = HPX_INVOKE(red_op, overall_result,
                        dispatch(traits::get_id(sit), algo, policy,
                            std::true_type(), beg, end, red_op));
                }
            }

            return result::get(HPX_MOVE(overall_result));
        }

        // parallel remote implementation
        template <typename Algo, typename ExPolicy, typename SegIterB,
            typename SegIterE, typename T, typename Reduce>
        static typename util::detail::algorithm_result<ExPolicy, T>::type
        segmented_reduce(Algo&& algo, ExPolicy const& policy, SegIterB first,
            SegIterE last, T&& init, Reduce&& red_op, std::false_type)
        {
            typedef hpx::traits::segmented_iterator_traits<SegIterB> traits;
            typedef typename traits::segment_iterator segment_iterator;
            typedef typename traits::local_iterator local_iterator_type;
            typedef util::detail::algorithm_result<ExPolicy, T> result;

            typedef std::integral_constant<bool,
                !hpx::traits::is_forward_iterator<SegIterB>::value>
                forced_seq;

            segment_iterator sit = traits::segment(first);
            segment_iterator send = traits::segment(last);

            std::vector<shared_future<T>> segments;
            segments.reserve(detail::distance(sit, send));

            if (sit == send)
            {
                // all elements are on the same partition
                local_iterator_type beg = traits::local(first);
                local_iterator_type end = traits::local(last);
                if (beg != end)
                {
                    segments.push_back(dispatch_async(traits::get_id(sit), algo,
                        policy, forced_seq(), beg, end, red_op));
                }
            }
            else
            {
                // handle the remaining part of the first partition
                local_iterator_type beg = traits::local(first);
                local_iterator_type end = traits::end(sit);
                if (beg != end)
                {
                    segments.push_back(dispatch_async(traits::get_id(sit), algo,
                        policy, forced_seq(), beg, end, red_op));
                }

                // handle all of the full partitions
                for (++sit; sit != send; ++sit)
                {
                    beg = traits::begin(sit);
                    end = traits::end(sit);
                    if (beg != end)
                    {
                        segments.push_back(dispatch_async(traits::get_id(sit),
                            algo, policy, forced_seq(), beg, end, red_op));
                    }
                }

                // handle the beginning of the last partition
                beg = traits::begin(sit);
                end = traits::local(last);
                if (beg != end)
                {
                    segments.push_back(dispatch_async(traits::get_id(sit), algo,
                        policy, forced_seq(), beg, end, red_op));
                }
            }

            return result::get(dataflow(
                [=](std::vector<shared_future<T>>&& r) mutable -> T {
                    // handle any remote exceptions, will throw on error
                    std::list<std::exception_ptr> errors;
                    parallel::util::detail::handle_remote_exceptions<
                        ExPolicy>::call(r, errors);

                    // VS2015RC bails out if red_op is capture by ref
                    return detail::accumulate(r.begin(), r.end(), init,
                        [=](T val, shared_future<T>& curr) mutable {
                            return HPX_INVOKE(
                                red_op, HPX_MOVE(val), curr.get());
                        });
                },
                HPX_MOVE(segments)));
        }
        /// \endcond
    }    // namespace detail
}}}      // namespace hpx::parallel::v1

// The segmented iterators we support all live in namespace hpx::segmented
namespace hpx { namespace segmented {

    // clang-format off
    template <typename InIterB, typename InIterE,
        typename T, typename F,
        HPX_CONCEPT_REQUIRES_(
            hpx::traits::is_iterator<InIterB>::value &&
            hpx::traits::is_segmented_iterator<InIterB>::value &&
            hpx::traits::is_iterator<InIterE>::value &&
            hpx::traits::is_segmented_iterator<InIterE>::value
        )>
    // clang-format on
    T tag_invoke(hpx::reduce_t, InIterB first, InIterE last, T init, F&& f)
    {
        static_assert(hpx::traits::is_input_iterator<InIterB>::value,
            "Requires at least input iterator.");

        static_assert(hpx::traits::is_input_iterator<InIterE>::value,
            "Requires at least input iterator.");

        if (first == last)
        {
            return init;
        }

        return hpx::parallel::v1::detail::segmented_reduce(
            hpx::parallel::v1::detail::seg_reduce<T>(), hpx::execution::seq,
            first, last, HPX_FORWARD(T, init), HPX_FORWARD(F, f),
            std::true_type{});
    }

    // clang-format off
    template <typename ExPolicy, typename InIterB, typename InIterE,
        typename T, typename F,
        HPX_CONCEPT_REQUIRES_(
            hpx::is_execution_policy<ExPolicy>::value &&
            hpx::traits::is_iterator<InIterB>::value &&
            hpx::traits::is_segmented_iterator<InIterB>::value &&
            hpx::traits::is_iterator<InIterE>::value &&
            hpx::traits::is_segmented_iterator<InIterE>::value
        )>
    // clang-format on
    typename parallel::util::detail::algorithm_result<ExPolicy, T>::type
    tag_invoke(hpx::reduce_t, ExPolicy&& policy, InIterB first, InIterE last,
        T init, F&& f)
    {
        static_assert(hpx::traits::is_input_iterator<InIterB>::value,
            "Requires at least input iterator.");

        static_assert(hpx::traits::is_input_iterator<InIterE>::value,
            "Requires at least input iterator.");

        if (first == last)
        {
            return parallel::util::detail::algorithm_result<ExPolicy, T>::get(
                HPX_FORWARD(T, init));
        }

        using is_seq = hpx::is_sequenced_execution_policy<ExPolicy>;

        return hpx::parallel::v1::detail::segmented_reduce(
            hpx::parallel::v1::detail::seg_reduce<T>(),
            HPX_FORWARD(ExPolicy, policy), first, last, HPX_FORWARD(T, init),
            HPX_FORWARD(F, f), is_seq());
    }
}}    // namespace hpx::segmented

1	// Copyright (c) 2017 Ajai V George
2	// Copyright (c) 2022 Hartmut Kaiser
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	#pragma once
9
10	#include <hpx/config.hpp>
11	#include <hpx/algorithms/traits/segmented_iterator_traits.hpp>
12	#include <hpx/functional/invoke.hpp>
13
14	#include <hpx/executors/execution_policy.hpp>
15	#include <hpx/parallel/algorithms/detail/accumulate.hpp>
16	#include <hpx/parallel/algorithms/detail/dispatch.hpp>
17	#include <hpx/parallel/algorithms/detail/distance.hpp>
18	#include <hpx/parallel/algorithms/reduce.hpp>
19	#include <hpx/parallel/segmented_algorithms/detail/dispatch.hpp>
20	#include <hpx/parallel/segmented_algorithms/detail/reduce.hpp>
21	#include <hpx/parallel/util/detail/algorithm_result.hpp>
22	#include <hpx/parallel/util/detail/handle_remote_exceptions.hpp>
23
24	#include <algorithm>
25	#include <exception>
26	#include <iterator>
27	#include <list>
28	#include <numeric>
29	#include <type_traits>
30	#include <utility>
31	#include <vector>
32
33	namespace hpx { namespace parallel { inline namespace v1 {
34	///////////////////////////////////////////////////////////////////////////
35	// segmented_reduce
36	namespace detail {
37	///////////////////////////////////////////////////////////////////////
38	/// \cond NOINTERNAL
39
40	// sequential remote implementation
41	template <typename Algo, typename ExPolicy, typename SegIterB,
42	typename SegIterE, typename T, typename Reduce>
43	static typename util::detail::algorithm_result<ExPolicy, T>::type
44	segmented_reduce(Algo&& algo, ExPolicy const& policy, SegIterB first,	×
45	SegIterE last, T&& init, Reduce&& red_op, std::true_type)
46	{
47	typedef hpx::traits::segmented_iterator_traits<SegIterB> traits;
48	typedef typename traits::segment_iterator segment_iterator;
49	typedef typename traits::local_iterator local_iterator_type;
50	typedef util::detail::algorithm_result<ExPolicy, T> result;
51
52	segment_iterator sit = traits::segment(first);	×
53	segment_iterator send = traits::segment(last);	×
54
55	T overall_result = init;	×
56
57	if (sit == send)	×
58	{
59	// all elements are on the same partition
60	local_iterator_type beg = traits::local(first);	×
61	local_iterator_type end = traits::local(last);	×
62	if (beg != end)	×
63	{
64	overall_result = HPX_INVOKE(red_op, overall_result,	×
65	dispatch(traits::get_id(sit), algo, policy,
66	std::true_type(), beg, end, red_op));
67	}	×
68	}	×
69	else
70	{
71	// handle the remaining part of the first partition
72	local_iterator_type beg = traits::local(first);	×
73	local_iterator_type end = traits::end(sit);	×
74	if (beg != end)	×
75	{
76	overall_result = HPX_INVOKE(red_op, overall_result,	×
77	dispatch(traits::get_id(sit), algo, policy,
78	std::true_type(), beg, end, red_op));
79	}	×
80
81	// handle all of the full partitions
82	for (++sit; sit != send; ++sit)	×
83	{
84	beg = traits::begin(sit);	×
85	end = traits::end(sit);	×
86	if (beg != end)	×
87	{
88	overall_result = HPX_INVOKE(red_op, overall_result,	×
89	dispatch(traits::get_id(sit), algo, policy,
90	std::true_type(), beg, end, red_op));
91	}	×
92	}	×
93
94	// handle the beginning of the last partition
95	beg = traits::begin(sit);	×
96	end = traits::local(last);	×
97	if (beg != end)	×
98	{
99	overall_result = HPX_INVOKE(red_op, overall_result,	×
100	dispatch(traits::get_id(sit), algo, policy,
101	std::true_type(), beg, end, red_op));
102	}	×
103	}	×
104
105	return result::get(HPX_MOVE(overall_result));	×
106	}	×
107
108	// parallel remote implementation
109	template <typename Algo, typename ExPolicy, typename SegIterB,
110	typename SegIterE, typename T, typename Reduce>
111	static typename util::detail::algorithm_result<ExPolicy, T>::type
112	segmented_reduce(Algo&& algo, ExPolicy const& policy, SegIterB first,	×
113	SegIterE last, T&& init, Reduce&& red_op, std::false_type)
114	{
115	typedef hpx::traits::segmented_iterator_traits<SegIterB> traits;
116	typedef typename traits::segment_iterator segment_iterator;
117	typedef typename traits::local_iterator local_iterator_type;
118	typedef util::detail::algorithm_result<ExPolicy, T> result;
119
120	typedef std::integral_constant<bool,
121	!hpx::traits::is_forward_iterator<SegIterB>::value>
122	forced_seq;
123
124	segment_iterator sit = traits::segment(first);	×
125	segment_iterator send = traits::segment(last);	×
126
127	std::vector<shared_future<T>> segments;	×
128	segments.reserve(detail::distance(sit, send));	×
129
130	if (sit == send)	×
131	{
132	// all elements are on the same partition
133	local_iterator_type beg = traits::local(first);	×
134	local_iterator_type end = traits::local(last);	×
135	if (beg != end)	×
136	{
137	segments.push_back(dispatch_async(traits::get_id(sit), algo,	×
138	policy, forced_seq(), beg, end, red_op));	×
139	}	×
140	}	×
141	else
142	{
143	// handle the remaining part of the first partition
144	local_iterator_type beg = traits::local(first);	×
145	local_iterator_type end = traits::end(sit);	×
146	if (beg != end)	×
147	{
148	segments.push_back(dispatch_async(traits::get_id(sit), algo,	×
149	policy, forced_seq(), beg, end, red_op));	×
150	}	×
151
152	// handle all of the full partitions
153	for (++sit; sit != send; ++sit)	×
154	{
155	beg = traits::begin(sit);	×
156	end = traits::end(sit);	×
157	if (beg != end)	×
158	{
159	segments.push_back(dispatch_async(traits::get_id(sit),	×
160	algo, policy, forced_seq(), beg, end, red_op));	×
161	}	×
162	}	×
163
164	// handle the beginning of the last partition
165	beg = traits::begin(sit);	×
166	end = traits::local(last);	×
167	if (beg != end)	×
168	{
169	segments.push_back(dispatch_async(traits::get_id(sit), algo,	×
170	policy, forced_seq(), beg, end, red_op));	×
171	}	×
172	}	×
173
174	return result::get(dataflow(	×
175	[=](std::vector<shared_future<T>>&& r) mutable -> T {	×
176	// handle any remote exceptions, will throw on error
177	std::list<std::exception_ptr> errors;	×
178	parallel::util::detail::handle_remote_exceptions<	×
179	ExPolicy>::call(r, errors);	×
180
181	// VS2015RC bails out if red_op is capture by ref
182	return detail::accumulate(r.begin(), r.end(), init,	×
183	[=](T val, shared_future<T>& curr) mutable {	×
184	return HPX_INVOKE(	×
185	red_op, HPX_MOVE(val), curr.get());
186	});
187	},	×
188	HPX_MOVE(segments)));
189	}	×
190	/// \endcond
191	} // namespace detail
192	}}} // namespace hpx::parallel::v1
193
194	// The segmented iterators we support all live in namespace hpx::segmented
195	namespace hpx { namespace segmented {
196
197	// clang-format off
198	template <typename InIterB, typename InIterE,
199	typename T, typename F,
200	HPX_CONCEPT_REQUIRES_(
201	hpx::traits::is_iterator<InIterB>::value &&
202	hpx::traits::is_segmented_iterator<InIterB>::value &&
203	hpx::traits::is_iterator<InIterE>::value &&
204	hpx::traits::is_segmented_iterator<InIterE>::value
205	)>
206	// clang-format on
207	T tag_invoke(hpx::reduce_t, InIterB first, InIterE last, T init, F&& f)
208	{
209	static_assert(hpx::traits::is_input_iterator<InIterB>::value,
210	"Requires at least input iterator.");
211
212	static_assert(hpx::traits::is_input_iterator<InIterE>::value,
213	"Requires at least input iterator.");
214
215	if (first == last)
216	{
217	return init;
218	}
219
220	return hpx::parallel::v1::detail::segmented_reduce(
221	hpx::parallel::v1::detail::seg_reduce<T>(), hpx::execution::seq,
222	first, last, HPX_FORWARD(T, init), HPX_FORWARD(F, f),
223	std::true_type{});
224	}
225
226	// clang-format off
227	template <typename ExPolicy, typename InIterB, typename InIterE,
228	typename T, typename F,
229	HPX_CONCEPT_REQUIRES_(
230	hpx::is_execution_policy<ExPolicy>::value &&
231	hpx::traits::is_iterator<InIterB>::value &&
232	hpx::traits::is_segmented_iterator<InIterB>::value &&
233	hpx::traits::is_iterator<InIterE>::value &&
234	hpx::traits::is_segmented_iterator<InIterE>::value
235	)>
236	// clang-format on
237	typename parallel::util::detail::algorithm_result<ExPolicy, T>::type
238	tag_invoke(hpx::reduce_t, ExPolicy&& policy, InIterB first, InIterE last,	×
239	T init, F&& f)
240	{
241	static_assert(hpx::traits::is_input_iterator<InIterB>::value,
242	"Requires at least input iterator.");
243
244	static_assert(hpx::traits::is_input_iterator<InIterE>::value,
245	"Requires at least input iterator.");
246
247	if (first == last)	×
248	{
249	return parallel::util::detail::algorithm_result<ExPolicy, T>::get(	×
250	HPX_FORWARD(T, init));
251	}
252
253	using is_seq = hpx::is_sequenced_execution_policy<ExPolicy>;
254
255	return hpx::parallel::v1::detail::segmented_reduce(	×
256	hpx::parallel::v1::detail::seg_reduce<T>(),	×
257	HPX_FORWARD(ExPolicy, policy), first, last, HPX_FORWARD(T, init),	×
258	HPX_FORWARD(F, f), is_seq());	×
259	}	×
260	}} // namespace hpx::segmented

STEllAR-GROUP / hpx / #865

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