libstdc++
parallel/numeric
Go to the documentation of this file.
1// -*- C++ -*-
2
3// Copyright (C) 2007-2022 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the terms
7// of the GNU General Public License as published by the Free Software
8// Foundation; either version 3, or (at your option) any later
9// version.
10
11// This library is distributed in the hope that it will be useful, but
12// WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14// General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/**
26 * @file parallel/numeric
27*
28 * @brief Parallel STL function calls corresponding to stl_numeric.h.
29 * The functions defined here mainly do case switches and
30 * call the actual parallelized versions in other files.
31 * Inlining policy: Functions that basically only contain one function call,
32 * are declared inline.
33 * This file is a GNU parallel extension to the Standard C++ Library.
34 */
35
36// Written by Johannes Singler and Felix Putze.
37
38#ifndef _GLIBCXX_PARALLEL_NUMERIC_H
39#define _GLIBCXX_PARALLEL_NUMERIC_H 1
40
41#include <numeric>
42#include <bits/stl_function.h>
43#include <parallel/numericfwd.h>
44#include <parallel/iterator.h>
45#include <parallel/for_each.h>
46#include <parallel/for_each_selectors.h>
47#include <parallel/partial_sum.h>
48
49namespace std _GLIBCXX_VISIBILITY(default)
50{
51namespace __parallel
52{
53 // Sequential fallback.
54 template<typename _IIter, typename _Tp>
55 inline _Tp
56 accumulate(_IIter __begin, _IIter __end, _Tp __init,
57 __gnu_parallel::sequential_tag)
58 { return _GLIBCXX_STD_A::accumulate(__begin, __end, __init); }
59
60 template<typename _IIter, typename _Tp, typename _BinaryOperation>
61 inline _Tp
62 accumulate(_IIter __begin, _IIter __end, _Tp __init,
63 _BinaryOperation __binary_op, __gnu_parallel::sequential_tag)
64 { return _GLIBCXX_STD_A::accumulate(__begin, __end, __init, __binary_op); }
65
66 // Sequential fallback for input iterator case.
67 template<typename _IIter, typename _Tp, typename _IteratorTag>
68 inline _Tp
69 __accumulate_switch(_IIter __begin, _IIter __end,
70 _Tp __init, _IteratorTag)
71 { return accumulate(__begin, __end, __init,
72 __gnu_parallel::sequential_tag()); }
73
74 template<typename _IIter, typename _Tp, typename _BinaryOperation,
75 typename _IteratorTag>
76 inline _Tp
77 __accumulate_switch(_IIter __begin, _IIter __end, _Tp __init,
78 _BinaryOperation __binary_op, _IteratorTag)
79 { return accumulate(__begin, __end, __init, __binary_op,
80 __gnu_parallel::sequential_tag()); }
81
82 // Parallel algorithm for random access iterators.
83 template<typename __RAIter, typename _Tp, typename _BinaryOperation>
84 _Tp
85 __accumulate_switch(__RAIter __begin, __RAIter __end,
86 _Tp __init, _BinaryOperation __binary_op,
87 random_access_iterator_tag,
88 __gnu_parallel::_Parallelism __parallelism_tag)
89 {
90 if (_GLIBCXX_PARALLEL_CONDITION(
91 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
92 >= __gnu_parallel::_Settings::get().accumulate_minimal_n
93 && __gnu_parallel::__is_parallel(__parallelism_tag)))
94 {
95 _Tp __res = __init;
96 __gnu_parallel::__accumulate_selector<__RAIter>
97 __my_selector;
98 __gnu_parallel::
99 __for_each_template_random_access_ed(__begin, __end,
100 __gnu_parallel::_Nothing(),
101 __my_selector,
102 __gnu_parallel::
103 __accumulate_binop_reduct
104 <_BinaryOperation>(__binary_op),
105 __res, __res, -1);
106 return __res;
107 }
108 else
109 return accumulate(__begin, __end, __init, __binary_op,
110 __gnu_parallel::sequential_tag());
111 }
112
113 // Public interface.
114 template<typename _IIter, typename _Tp>
115 inline _Tp
116 accumulate(_IIter __begin, _IIter __end, _Tp __init,
117 __gnu_parallel::_Parallelism __parallelism_tag)
118 {
119 typedef std::iterator_traits<_IIter> _IteratorTraits;
120 typedef typename _IteratorTraits::value_type _ValueType;
121 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
122
123 return __accumulate_switch(__begin, __end, __init,
124 __gnu_parallel::_Plus<_Tp, _ValueType>(),
125 _IteratorCategory(), __parallelism_tag);
126 }
127
128 template<typename _IIter, typename _Tp>
129 inline _Tp
130 accumulate(_IIter __begin, _IIter __end, _Tp __init)
131 {
132 typedef std::iterator_traits<_IIter> _IteratorTraits;
133 typedef typename _IteratorTraits::value_type _ValueType;
134 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
135
136 return __accumulate_switch(__begin, __end, __init,
137 __gnu_parallel::_Plus<_Tp, _ValueType>(),
138 _IteratorCategory());
139 }
140
141 template<typename _IIter, typename _Tp, typename _BinaryOperation>
142 inline _Tp
143 accumulate(_IIter __begin, _IIter __end, _Tp __init,
144 _BinaryOperation __binary_op,
145 __gnu_parallel::_Parallelism __parallelism_tag)
146 {
147 typedef iterator_traits<_IIter> _IteratorTraits;
148 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
149 return __accumulate_switch(__begin, __end, __init, __binary_op,
150 _IteratorCategory(), __parallelism_tag);
151 }
152
153 template<typename _IIter, typename _Tp, typename _BinaryOperation>
154 inline _Tp
155 accumulate(_IIter __begin, _IIter __end, _Tp __init,
156 _BinaryOperation __binary_op)
157 {
158 typedef iterator_traits<_IIter> _IteratorTraits;
159 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
160 return __accumulate_switch(__begin, __end, __init, __binary_op,
161 _IteratorCategory());
162 }
163
164
165 // Sequential fallback.
166 template<typename _IIter1, typename _IIter2, typename _Tp>
167 inline _Tp
168 inner_product(_IIter1 __first1, _IIter1 __last1,
169 _IIter2 __first2, _Tp __init,
170 __gnu_parallel::sequential_tag)
171 { return _GLIBCXX_STD_A::inner_product(
172 __first1, __last1, __first2, __init); }
173
174 template<typename _IIter1, typename _IIter2, typename _Tp,
175 typename _BinaryFunction1, typename _BinaryFunction2>
176 inline _Tp
177 inner_product(_IIter1 __first1, _IIter1 __last1,
178 _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
179 _BinaryFunction2 __binary_op2,
180 __gnu_parallel::sequential_tag)
181 { return _GLIBCXX_STD_A::inner_product(__first1, __last1, __first2, __init,
182 __binary_op1, __binary_op2); }
183
184 // Parallel algorithm for random access iterators.
185 template<typename _RAIter1, typename _RAIter2,
186 typename _Tp, typename _BinaryFunction1, typename _BinaryFunction2>
187 _Tp
188 __inner_product_switch(_RAIter1 __first1,
189 _RAIter1 __last1,
190 _RAIter2 __first2, _Tp __init,
191 _BinaryFunction1 __binary_op1,
192 _BinaryFunction2 __binary_op2,
193 random_access_iterator_tag,
194 random_access_iterator_tag,
195 __gnu_parallel::_Parallelism __parallelism_tag)
196 {
197 if (_GLIBCXX_PARALLEL_CONDITION((__last1 - __first1)
198 >= __gnu_parallel::_Settings::get().
199 accumulate_minimal_n
200 && __gnu_parallel::
201 __is_parallel(__parallelism_tag)))
202 {
203 _Tp __res = __init;
204 __gnu_parallel::
205 __inner_product_selector<_RAIter1,
206 _RAIter2, _Tp> __my_selector(__first1, __first2);
207 __gnu_parallel::
208 __for_each_template_random_access_ed(
209 __first1, __last1, __binary_op2, __my_selector, __binary_op1,
210 __res, __res, -1);
211 return __res;
212 }
213 else
214 return inner_product(__first1, __last1, __first2, __init,
215 __gnu_parallel::sequential_tag());
216 }
217
218 // No parallelism for input iterators.
219 template<typename _IIter1, typename _IIter2, typename _Tp,
220 typename _BinaryFunction1, typename _BinaryFunction2,
221 typename _IteratorTag1, typename _IteratorTag2>
222 inline _Tp
223 __inner_product_switch(_IIter1 __first1, _IIter1 __last1,
224 _IIter2 __first2, _Tp __init,
225 _BinaryFunction1 __binary_op1,
226 _BinaryFunction2 __binary_op2,
227 _IteratorTag1, _IteratorTag2)
228 { return inner_product(__first1, __last1, __first2, __init, __binary_op1,
229 __binary_op2, __gnu_parallel::sequential_tag()); }
230
231 template<typename _IIter1, typename _IIter2, typename _Tp,
232 typename _BinaryFunction1, typename _BinaryFunction2>
233 inline _Tp
234 inner_product(_IIter1 __first1, _IIter1 __last1,
235 _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
236 _BinaryFunction2 __binary_op2,
237 __gnu_parallel::_Parallelism __parallelism_tag)
238 {
239 typedef iterator_traits<_IIter1> _TraitsType1;
240 typedef typename _TraitsType1::iterator_category _IteratorCategory1;
241
242 typedef iterator_traits<_IIter2> _TraitsType2;
243 typedef typename _TraitsType2::iterator_category _IteratorCategory2;
244
245 return __inner_product_switch(__first1, __last1, __first2, __init,
246 __binary_op1, __binary_op2,
247 _IteratorCategory1(), _IteratorCategory2(),
248 __parallelism_tag);
249 }
250
251 template<typename _IIter1, typename _IIter2, typename _Tp,
252 typename _BinaryFunction1, typename _BinaryFunction2>
253 inline _Tp
254 inner_product(_IIter1 __first1, _IIter1 __last1,
255 _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
256 _BinaryFunction2 __binary_op2)
257 {
258 typedef iterator_traits<_IIter1> _TraitsType1;
259 typedef typename _TraitsType1::iterator_category _IteratorCategory1;
260
261 typedef iterator_traits<_IIter2> _TraitsType2;
262 typedef typename _TraitsType2::iterator_category _IteratorCategory2;
263
264 return __inner_product_switch(__first1, __last1, __first2, __init,
265 __binary_op1, __binary_op2,
266 _IteratorCategory1(),
267 _IteratorCategory2());
268 }
269
270 template<typename _IIter1, typename _IIter2, typename _Tp>
271 inline _Tp
272 inner_product(_IIter1 __first1, _IIter1 __last1,
273 _IIter2 __first2, _Tp __init,
274 __gnu_parallel::_Parallelism __parallelism_tag)
275 {
276 typedef iterator_traits<_IIter1> _TraitsType1;
277 typedef typename _TraitsType1::value_type _ValueType1;
278 typedef iterator_traits<_IIter2> _TraitsType2;
279 typedef typename _TraitsType2::value_type _ValueType2;
280
281 typedef typename
282 __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type
283 _MultipliesResultType;
284 return __gnu_parallel::inner_product(__first1, __last1, __first2, __init,
285 __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),
286 __gnu_parallel::
287 _Multiplies<_ValueType1, _ValueType2>(),
288 __parallelism_tag);
289 }
290
291 template<typename _IIter1, typename _IIter2, typename _Tp>
292 inline _Tp
293 inner_product(_IIter1 __first1, _IIter1 __last1,
294 _IIter2 __first2, _Tp __init)
295 {
296 typedef iterator_traits<_IIter1> _TraitsType1;
297 typedef typename _TraitsType1::value_type _ValueType1;
298 typedef iterator_traits<_IIter2> _TraitsType2;
299 typedef typename _TraitsType2::value_type _ValueType2;
300
301 typedef typename
302 __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type
303 _MultipliesResultType;
304 return __gnu_parallel::inner_product(__first1, __last1, __first2, __init,
305 __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),
306 __gnu_parallel::
307 _Multiplies<_ValueType1, _ValueType2>());
308 }
309
310 // Sequential fallback.
311 template<typename _IIter, typename _OutputIterator>
312 inline _OutputIterator
313 partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
314 __gnu_parallel::sequential_tag)
315 { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result); }
316
317 // Sequential fallback.
318 template<typename _IIter, typename _OutputIterator,
319 typename _BinaryOperation>
320 inline _OutputIterator
321 partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
322 _BinaryOperation __bin_op, __gnu_parallel::sequential_tag)
323 { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); }
324
325 // Sequential fallback for input iterator case.
326 template<typename _IIter, typename _OutputIterator,
327 typename _BinaryOperation, typename _IteratorTag1,
328 typename _IteratorTag2>
329 inline _OutputIterator
330 __partial_sum_switch(_IIter __begin, _IIter __end,
331 _OutputIterator __result, _BinaryOperation __bin_op,
332 _IteratorTag1, _IteratorTag2)
333 { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); }
334
335 // Parallel algorithm for random access iterators.
336 template<typename _IIter, typename _OutputIterator,
337 typename _BinaryOperation>
338 _OutputIterator
339 __partial_sum_switch(_IIter __begin, _IIter __end,
340 _OutputIterator __result, _BinaryOperation __bin_op,
341 random_access_iterator_tag,
342 random_access_iterator_tag)
343 {
344 if (_GLIBCXX_PARALLEL_CONDITION(
345 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
346 >= __gnu_parallel::_Settings::get().partial_sum_minimal_n))
347 return __gnu_parallel::__parallel_partial_sum(__begin, __end,
348 __result, __bin_op);
349 else
350 return partial_sum(__begin, __end, __result, __bin_op,
351 __gnu_parallel::sequential_tag());
352 }
353
354 // Public interface.
355 template<typename _IIter, typename _OutputIterator>
356 inline _OutputIterator
357 partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result)
358 {
359 typedef typename iterator_traits<_IIter>::value_type _ValueType;
360 return __gnu_parallel::partial_sum(__begin, __end,
361 __result, std::plus<_ValueType>());
362 }
363
364 // Public interface
365 template<typename _IIter, typename _OutputIterator,
366 typename _BinaryOperation>
367 inline _OutputIterator
368 partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
369 _BinaryOperation __binary_op)
370 {
371 typedef iterator_traits<_IIter> _ITraitsType;
372 typedef typename _ITraitsType::iterator_category _IIteratorCategory;
373
374 typedef iterator_traits<_OutputIterator> _OTraitsType;
375 typedef typename _OTraitsType::iterator_category _OIterCategory;
376
377 return __partial_sum_switch(__begin, __end, __result, __binary_op,
378 _IIteratorCategory(), _OIterCategory());
379 }
380
381 // Sequential fallback.
382 template<typename _IIter, typename _OutputIterator>
383 inline _OutputIterator
384 adjacent_difference(_IIter __begin, _IIter __end, _OutputIterator __result,
385 __gnu_parallel::sequential_tag)
386 { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end, __result); }
387
388 // Sequential fallback.
389 template<typename _IIter, typename _OutputIterator,
390 typename _BinaryOperation>
391 inline _OutputIterator
392 adjacent_difference(_IIter __begin, _IIter __end,
393 _OutputIterator __result, _BinaryOperation __bin_op,
394 __gnu_parallel::sequential_tag)
395 { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end,
396 __result, __bin_op); }
397
398 // Sequential fallback for input iterator case.
399 template<typename _IIter, typename _OutputIterator,
400 typename _BinaryOperation, typename _IteratorTag1,
401 typename _IteratorTag2>
402 inline _OutputIterator
403 __adjacent_difference_switch(_IIter __begin, _IIter __end,
404 _OutputIterator __result,
405 _BinaryOperation __bin_op, _IteratorTag1,
406 _IteratorTag2)
407 { return adjacent_difference(__begin, __end, __result, __bin_op,
408 __gnu_parallel::sequential_tag()); }
409
410 // Parallel algorithm for random access iterators.
411 template<typename _IIter, typename _OutputIterator,
412 typename _BinaryOperation>
413 _OutputIterator
414 __adjacent_difference_switch(_IIter __begin, _IIter __end,
415 _OutputIterator __result,
416 _BinaryOperation __bin_op,
417 random_access_iterator_tag,
418 random_access_iterator_tag,
419 __gnu_parallel::_Parallelism
420 __parallelism_tag)
421 {
422 if (_GLIBCXX_PARALLEL_CONDITION(
423 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
424 >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n
425 && __gnu_parallel::__is_parallel(__parallelism_tag)))
426 {
427 bool __dummy = true;
428 typedef __gnu_parallel::_IteratorPair<_IIter, _OutputIterator,
429 random_access_iterator_tag> _ItTrip;
430 *__result = *__begin;
431 _ItTrip __begin_pair(__begin + 1, __result + 1),
432 __end_pair(__end, __result + (__end - __begin));
433 __gnu_parallel::__adjacent_difference_selector<_ItTrip>
434 __functionality;
435 __gnu_parallel::
436 __for_each_template_random_access_ed(
437 __begin_pair, __end_pair, __bin_op, __functionality,
438 __gnu_parallel::_DummyReduct(), __dummy, __dummy, -1);
439 return __functionality._M_finish_iterator;
440 }
441 else
442 return adjacent_difference(__begin, __end, __result, __bin_op,
443 __gnu_parallel::sequential_tag());
444 }
445
446 // Public interface.
447 template<typename _IIter, typename _OutputIterator>
448 inline _OutputIterator
449 adjacent_difference(_IIter __begin, _IIter __end,
450 _OutputIterator __result,
451 __gnu_parallel::_Parallelism __parallelism_tag)
452 {
453 typedef iterator_traits<_IIter> _TraitsType;
454 typedef typename _TraitsType::value_type _ValueType;
455 return adjacent_difference(__begin, __end, __result,
456 std::minus<_ValueType>(),
457 __parallelism_tag);
458 }
459
460 template<typename _IIter, typename _OutputIterator>
461 inline _OutputIterator
462 adjacent_difference(_IIter __begin, _IIter __end,
463 _OutputIterator __result)
464 {
465 typedef iterator_traits<_IIter> _TraitsType;
466 typedef typename _TraitsType::value_type _ValueType;
467 return adjacent_difference(__begin, __end, __result,
468 std::minus<_ValueType>());
469 }
470
471 template<typename _IIter, typename _OutputIterator,
472 typename _BinaryOperation>
473 inline _OutputIterator
474 adjacent_difference(_IIter __begin, _IIter __end,
475 _OutputIterator __result, _BinaryOperation __binary_op,
476 __gnu_parallel::_Parallelism __parallelism_tag)
477 {
478 typedef iterator_traits<_IIter> _ITraitsType;
479 typedef typename _ITraitsType::iterator_category _IIteratorCategory;
480
481 typedef iterator_traits<_OutputIterator> _OTraitsType;
482 typedef typename _OTraitsType::iterator_category _OIterCategory;
483
484 return __adjacent_difference_switch(__begin, __end, __result,
485 __binary_op,
486 _IIteratorCategory(),
487 _OIterCategory(),
488 __parallelism_tag);
489 }
490
491 template<typename _IIter, typename _OutputIterator,
492 typename _BinaryOperation>
493 inline _OutputIterator
494 adjacent_difference(_IIter __begin, _IIter __end,
495 _OutputIterator __result, _BinaryOperation __binary_op)
496 {
497 typedef iterator_traits<_IIter> _ITraitsType;
498 typedef typename _ITraitsType::iterator_category _IIteratorCategory;
499
500 typedef iterator_traits<_OutputIterator> _OTraitsType;
501 typedef typename _OTraitsType::iterator_category _OIterCategory;
502
503 return __adjacent_difference_switch(__begin, __end, __result,
504 __binary_op,
505 _IIteratorCategory(),
506 _OIterCategory());
507 }
508} // end namespace
509} // end namespace
510
511#endif /* _GLIBCXX_NUMERIC_H */