libstdc++
parallel/numeric
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007, 2008, 2009, 2010 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>
47 #include <parallel/partial_sum.h>
48 
49 namespace std _GLIBCXX_VISIBILITY(default)
50 {
51 namespace __parallel
52 {
53  // Sequential fallback.
54  template<typename _IIter, typename _Tp>
55  inline _Tp
56  accumulate(_IIter __begin, _IIter __end, _Tp __init,
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,
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,
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,
88  __gnu_parallel::_Parallelism __parallelism_tag
90  {
92  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
93  >= __gnu_parallel::_Settings::get().accumulate_minimal_n
94  && __gnu_parallel::__is_parallel(__parallelism_tag)))
95  {
96  _Tp __res = __init;
98  __my_selector;
102  __my_selector,
103  __gnu_parallel::
104  __accumulate_binop_reduct
105  <_BinaryOperation>(__binary_op),
106  __res, __res, -1);
107  return __res;
108  }
109  else
110  return accumulate(__begin, __end, __init, __binary_op,
112  }
113 
114  // Public interface.
115  template<typename _IIter, typename _Tp>
116  inline _Tp
117  accumulate(_IIter __begin, _IIter __end, _Tp __init,
118  __gnu_parallel::_Parallelism __parallelism_tag)
119  {
120  typedef std::iterator_traits<_IIter> _IteratorTraits;
121  typedef typename _IteratorTraits::value_type _ValueType;
122  typedef typename _IteratorTraits::iterator_category _IteratorCategory;
123 
124  return __accumulate_switch(__begin, __end, __init,
126  _IteratorCategory(), __parallelism_tag);
127  }
128 
129  template<typename _IIter, typename _Tp>
130  inline _Tp
131  accumulate(_IIter __begin, _IIter __end, _Tp __init)
132  {
133  typedef std::iterator_traits<_IIter> _IteratorTraits;
134  typedef typename _IteratorTraits::value_type _ValueType;
135  typedef typename _IteratorTraits::iterator_category _IteratorCategory;
136 
137  return __accumulate_switch(__begin, __end, __init,
139  _IteratorCategory());
140  }
141 
142  template<typename _IIter, typename _Tp, typename _BinaryOperation>
143  inline _Tp
144  accumulate(_IIter __begin, _IIter __end, _Tp __init,
145  _BinaryOperation __binary_op,
146  __gnu_parallel::_Parallelism __parallelism_tag)
147  {
148  typedef iterator_traits<_IIter> _IteratorTraits;
149  typedef typename _IteratorTraits::iterator_category _IteratorCategory;
150  return __accumulate_switch(__begin, __end, __init, __binary_op,
151  _IteratorCategory(), __parallelism_tag);
152  }
153 
154  template<typename _IIter, typename _Tp, typename _BinaryOperation>
155  inline _Tp
156  accumulate(_IIter __begin, _IIter __end, _Tp __init,
157  _BinaryOperation __binary_op)
158  {
159  typedef iterator_traits<_IIter> _IteratorTraits;
160  typedef typename _IteratorTraits::iterator_category _IteratorCategory;
161  return __accumulate_switch(__begin, __end, __init, __binary_op,
162  _IteratorCategory());
163  }
164 
165 
166  // Sequential fallback.
167  template<typename _IIter1, typename _IIter2, typename _Tp>
168  inline _Tp
169  inner_product(_IIter1 __first1, _IIter1 __last1,
170  _IIter2 __first2, _Tp __init,
172  { return _GLIBCXX_STD_A::inner_product(
173  __first1, __last1, __first2, __init); }
174 
175  template<typename _IIter1, typename _IIter2, typename _Tp,
176  typename _BinaryFunction1, typename _BinaryFunction2>
177  inline _Tp
178  inner_product(_IIter1 __first1, _IIter1 __last1,
179  _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
180  _BinaryFunction2 __binary_op2,
182  { return _GLIBCXX_STD_A::inner_product(__first1, __last1, __first2, __init,
183  __binary_op1, __binary_op2); }
184 
185  // Parallel algorithm for random access iterators.
186  template<typename _RAIter1, typename _RAIter2,
187  typename _Tp, typename _BinaryFunction1, typename _BinaryFunction2>
188  _Tp
189  __inner_product_switch(_RAIter1 __first1,
190  _RAIter1 __last1,
191  _RAIter2 __first2, _Tp __init,
192  _BinaryFunction1 __binary_op1,
193  _BinaryFunction2 __binary_op2,
196  __gnu_parallel::_Parallelism __parallelism_tag
198  {
199  if (_GLIBCXX_PARALLEL_CONDITION((__last1 - __first1)
201  accumulate_minimal_n
202  && __gnu_parallel::
203  __is_parallel(__parallelism_tag)))
204  {
205  _Tp __res = __init;
208  _RAIter2, _Tp> __my_selector(__first1, __first2);
211  __first1, __last1, __binary_op2, __my_selector, __binary_op1,
212  __res, __res, -1);
213  return __res;
214  }
215  else
216  return inner_product(__first1, __last1, __first2, __init,
218  }
219 
220  // No parallelism for input iterators.
221  template<typename _IIter1, typename _IIter2, typename _Tp,
222  typename _BinaryFunction1, typename _BinaryFunction2,
223  typename _IteratorTag1, typename _IteratorTag2>
224  inline _Tp
225  __inner_product_switch(_IIter1 __first1, _IIter1 __last1,
226  _IIter2 __first2, _Tp __init,
227  _BinaryFunction1 __binary_op1,
228  _BinaryFunction2 __binary_op2,
229  _IteratorTag1, _IteratorTag2)
230  { return inner_product(__first1, __last1, __first2, __init, __binary_op1,
231  __binary_op2, __gnu_parallel::sequential_tag()); }
232 
233  template<typename _IIter1, typename _IIter2, typename _Tp,
234  typename _BinaryFunction1, typename _BinaryFunction2>
235  inline _Tp
236  inner_product(_IIter1 __first1, _IIter1 __last1,
237  _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
238  _BinaryFunction2 __binary_op2,
239  __gnu_parallel::_Parallelism __parallelism_tag)
240  {
241  typedef iterator_traits<_IIter1> _TraitsType1;
242  typedef typename _TraitsType1::iterator_category _IteratorCategory1;
243 
244  typedef iterator_traits<_IIter2> _TraitsType2;
245  typedef typename _TraitsType2::iterator_category _IteratorCategory2;
246 
247  return __inner_product_switch(__first1, __last1, __first2, __init,
248  __binary_op1, __binary_op2,
249  _IteratorCategory1(), _IteratorCategory2(),
250  __parallelism_tag);
251  }
252 
253  template<typename _IIter1, typename _IIter2, typename _Tp,
254  typename _BinaryFunction1, typename _BinaryFunction2>
255  inline _Tp
256  inner_product(_IIter1 __first1, _IIter1 __last1,
257  _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
258  _BinaryFunction2 __binary_op2)
259  {
260  typedef iterator_traits<_IIter1> _TraitsType1;
261  typedef typename _TraitsType1::iterator_category _IteratorCategory1;
262 
263  typedef iterator_traits<_IIter2> _TraitsType2;
264  typedef typename _TraitsType2::iterator_category _IteratorCategory2;
265 
266  return __inner_product_switch(__first1, __last1, __first2, __init,
267  __binary_op1, __binary_op2,
268  _IteratorCategory1(),
269  _IteratorCategory2());
270  }
271 
272  template<typename _IIter1, typename _IIter2, typename _Tp>
273  inline _Tp
274  inner_product(_IIter1 __first1, _IIter1 __last1,
275  _IIter2 __first2, _Tp __init,
276  __gnu_parallel::_Parallelism __parallelism_tag)
277  {
278  typedef iterator_traits<_IIter1> _TraitsType1;
279  typedef typename _TraitsType1::value_type _ValueType1;
280  typedef iterator_traits<_IIter2> _TraitsType2;
281  typedef typename _TraitsType2::value_type _ValueType2;
282 
283  typedef typename
285  _MultipliesResultType;
286  return __gnu_parallel::inner_product(__first1, __last1, __first2, __init,
288  __gnu_parallel::
289  _Multiplies<_ValueType1, _ValueType2>(),
290  __parallelism_tag);
291  }
292 
293  template<typename _IIter1, typename _IIter2, typename _Tp>
294  inline _Tp
295  inner_product(_IIter1 __first1, _IIter1 __last1,
296  _IIter2 __first2, _Tp __init)
297  {
298  typedef iterator_traits<_IIter1> _TraitsType1;
299  typedef typename _TraitsType1::value_type _ValueType1;
300  typedef iterator_traits<_IIter2> _TraitsType2;
301  typedef typename _TraitsType2::value_type _ValueType2;
302 
303  typedef typename
305  _MultipliesResultType;
306  return __gnu_parallel::inner_product(__first1, __last1, __first2, __init,
308  __gnu_parallel::
309  _Multiplies<_ValueType1, _ValueType2>());
310  }
311 
312  // Sequential fallback.
313  template<typename _IIter, typename _OutputIterator>
314  inline _OutputIterator
315  partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
317  { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result); }
318 
319  // Sequential fallback.
320  template<typename _IIter, typename _OutputIterator,
321  typename _BinaryOperation>
322  inline _OutputIterator
323  partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
324  _BinaryOperation __bin_op, __gnu_parallel::sequential_tag)
325  { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); }
326 
327  // Sequential fallback for input iterator case.
328  template<typename _IIter, typename _OutputIterator,
329  typename _BinaryOperation, typename _IteratorTag1,
330  typename _IteratorTag2>
331  inline _OutputIterator
332  __partial_sum_switch(_IIter __begin, _IIter __end,
333  _OutputIterator __result, _BinaryOperation __bin_op,
334  _IteratorTag1, _IteratorTag2)
335  { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); }
336 
337  // Parallel algorithm for random access iterators.
338  template<typename _IIter, typename _OutputIterator,
339  typename _BinaryOperation>
340  _OutputIterator
341  __partial_sum_switch(_IIter __begin, _IIter __end,
342  _OutputIterator __result, _BinaryOperation __bin_op,
345  {
347  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
348  >= __gnu_parallel::_Settings::get().partial_sum_minimal_n))
349  return __gnu_parallel::__parallel_partial_sum(__begin, __end,
350  __result, __bin_op);
351  else
352  return partial_sum(__begin, __end, __result, __bin_op,
354  }
355 
356  // Public interface.
357  template<typename _IIter, typename _OutputIterator>
358  inline _OutputIterator
359  partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result)
360  {
361  typedef typename iterator_traits<_IIter>::value_type _ValueType;
362  return __gnu_parallel::partial_sum(__begin, __end,
363  __result, std::plus<_ValueType>());
364  }
365 
366  // Public interface
367  template<typename _IIter, typename _OutputIterator,
368  typename _BinaryOperation>
369  inline _OutputIterator
370  partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
371  _BinaryOperation __binary_op)
372  {
373  typedef iterator_traits<_IIter> _ITraitsType;
374  typedef typename _ITraitsType::iterator_category _IIteratorCategory;
375 
376  typedef iterator_traits<_OutputIterator> _OTraitsType;
377  typedef typename _OTraitsType::iterator_category _OIterCategory;
378 
379  return __partial_sum_switch(__begin, __end, __result, __binary_op,
380  _IIteratorCategory(), _OIterCategory());
381  }
382 
383  // Sequential fallback.
384  template<typename _IIter, typename _OutputIterator>
385  inline _OutputIterator
386  adjacent_difference(_IIter __begin, _IIter __end, _OutputIterator __result,
388  { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end, __result); }
389 
390  // Sequential fallback.
391  template<typename _IIter, typename _OutputIterator,
392  typename _BinaryOperation>
393  inline _OutputIterator
394  adjacent_difference(_IIter __begin, _IIter __end,
395  _OutputIterator __result, _BinaryOperation __bin_op,
397  { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end,
398  __result, __bin_op); }
399 
400  // Sequential fallback for input iterator case.
401  template<typename _IIter, typename _OutputIterator,
402  typename _BinaryOperation, typename _IteratorTag1,
403  typename _IteratorTag2>
404  inline _OutputIterator
405  __adjacent_difference_switch(_IIter __begin, _IIter __end,
406  _OutputIterator __result,
407  _BinaryOperation __bin_op, _IteratorTag1,
408  _IteratorTag2)
409  { return adjacent_difference(__begin, __end, __result, __bin_op,
411 
412  // Parallel algorithm for random access iterators.
413  template<typename _IIter, typename _OutputIterator,
414  typename _BinaryOperation>
415  _OutputIterator
416  __adjacent_difference_switch(_IIter __begin, _IIter __end,
417  _OutputIterator __result,
418  _BinaryOperation __bin_op,
422  __parallelism_tag
424  {
426  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
427  >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n
428  && __gnu_parallel::__is_parallel(__parallelism_tag)))
429  {
430  bool __dummy = true;
431  typedef __gnu_parallel::_IteratorPair<_IIter, _OutputIterator,
433  *__result = *__begin;
434  _ItTrip __begin_pair(__begin + 1, __result + 1),
435  __end_pair(__end, __result + (__end - __begin));
437  __functionality;
440  __begin_pair, __end_pair, __bin_op, __functionality,
441  __gnu_parallel::_DummyReduct(), __dummy, __dummy, -1);
442  return __functionality._M_finish_iterator;
443  }
444  else
445  return adjacent_difference(__begin, __end, __result, __bin_op,
447  }
448 
449  // Public interface.
450  template<typename _IIter, typename _OutputIterator>
451  inline _OutputIterator
452  adjacent_difference(_IIter __begin, _IIter __end,
453  _OutputIterator __result,
454  __gnu_parallel::_Parallelism __parallelism_tag)
455  {
456  typedef iterator_traits<_IIter> _TraitsType;
457  typedef typename _TraitsType::value_type _ValueType;
458  return adjacent_difference(__begin, __end, __result,
460  __parallelism_tag);
461  }
462 
463  template<typename _IIter, typename _OutputIterator>
464  inline _OutputIterator
465  adjacent_difference(_IIter __begin, _IIter __end,
466  _OutputIterator __result)
467  {
468  typedef iterator_traits<_IIter> _TraitsType;
469  typedef typename _TraitsType::value_type _ValueType;
470  return adjacent_difference(__begin, __end, __result,
472  }
473 
474  template<typename _IIter, typename _OutputIterator,
475  typename _BinaryOperation>
476  inline _OutputIterator
477  adjacent_difference(_IIter __begin, _IIter __end,
478  _OutputIterator __result, _BinaryOperation __binary_op,
479  __gnu_parallel::_Parallelism __parallelism_tag)
480  {
481  typedef iterator_traits<_IIter> _ITraitsType;
482  typedef typename _ITraitsType::iterator_category _IIteratorCategory;
483 
484  typedef iterator_traits<_OutputIterator> _OTraitsType;
485  typedef typename _OTraitsType::iterator_category _OIterCategory;
486 
487  return __adjacent_difference_switch(__begin, __end, __result,
488  __binary_op,
489  _IIteratorCategory(),
490  _OIterCategory(),
491  __parallelism_tag);
492  }
493 
494  template<typename _IIter, typename _OutputIterator,
495  typename _BinaryOperation>
496  inline _OutputIterator
497  adjacent_difference(_IIter __begin, _IIter __end,
498  _OutputIterator __result, _BinaryOperation __binary_op)
499  {
500  typedef iterator_traits<_IIter> _ITraitsType;
501  typedef typename _ITraitsType::iterator_category _IIteratorCategory;
502 
503  typedef iterator_traits<_OutputIterator> _OTraitsType;
504  typedef typename _OTraitsType::iterator_category _OIterCategory;
505 
506  return __adjacent_difference_switch(__begin, __end, __result,
507  __binary_op,
508  _IIteratorCategory(),
509  _OIterCategory());
510  }
511 } // end namespace
512 } // end namespace
513 
514 #endif /* _GLIBCXX_NUMERIC_H */
_Parallelism
Run-time equivalents for the compile-time tags.
Definition: types.h:44
static const _Settings & get()
Get the global settings.
Reduction function doing nothing.
Selector that returns the difference between two adjacent __elements.
_OutputIterator __parallel_partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result, _BinaryOperation __bin_op)
Parallel partial sum front-__end.
Definition: partial_sum.h:206
Similar to std::plus, but allows two different types.
Forces sequential execution at compile time.
Definition: tags.h:42
One of the math functors.
Definition: stl_function.h:141
Functors representing different tasks to be plugged into the generic parallelization methods for emba...
A pair of iterators. The usual iterator operations are applied to both child iterators.
Definition: iterator.h:45
Helper iterator classes for the std::transform() functions. This file is a GNU parallel extension to ...
std::inner_product() selector.
_It _M_finish_iterator
_Iterator on last element processed; needed for some algorithms (e. g. std::transform()).
#define _GLIBCXX_PARALLEL_CONDITION(__c)
Determine at compile(?)-time if the parallel variant of an algorithm should be called.
Definition: settings.h:95
_Result result_type
result_type is the return type
Definition: stl_function.h:124
One of the math functors.
Definition: stl_function.h:150
Main interface for embarrassingly parallel functions.
Parallel STL function calls corresponding to stl_numeric.h. The functions defined here mainly do case...
Parallel unbalanced (equal-sized chunks).
Definition: types.h:50
Parallel balanced (work-stealing).
Definition: types.h:53
Random-access iterators support a superset of bidirectional iterator operations.
Parallel implementation of std::partial_sum(), i.e. prefix sums. This file is a GNU parallel extensio...
Functor doing nothing.
_Op __for_each_template_random_access_ed(_RAIter __begin, _RAIter __end, _Op __o, _Fu &__f, _Red __r, _Result __base, _Result &__output, typename std::iterator_traits< _RAIter >::difference_type __bound)
Embarrassingly parallel algorithm for random access iterators, using hand-crafted parallelization by ...
Definition: par_loop.h:67