libstdc++
parallel/numeric
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007, 2008, 2009 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 <functional>
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
50 {
51 namespace __parallel
52 {
53  // Sequential fallback.
54  template<typename InputIterator, typename T>
55  inline T
56  accumulate(InputIterator begin, InputIterator end, T init,
58  { return _GLIBCXX_STD_P::accumulate(begin, end, init); }
59 
60  template<typename InputIterator, typename T, typename BinaryOperation>
61  inline T
62  accumulate(InputIterator begin, InputIterator end, T init,
63  BinaryOperation binary_op, __gnu_parallel::sequential_tag)
64  { return _GLIBCXX_STD_P::accumulate(begin, end, init, binary_op); }
65 
66  // Sequential fallback for input iterator case.
67  template<typename InputIterator, typename T, typename IteratorTag>
68  inline T
69  accumulate_switch(InputIterator begin, InputIterator end,
70  T init, IteratorTag)
71  { return accumulate(begin, end, init, __gnu_parallel::sequential_tag()); }
72 
73  template<typename InputIterator, typename T, typename BinaryOperation,
74  typename IteratorTag>
75  inline T
76  accumulate_switch(InputIterator begin, InputIterator end, T init,
77  BinaryOperation binary_op, IteratorTag)
78  { return accumulate(begin, end, init, binary_op,
80 
81  // Parallel algorithm for random access iterators.
82  template<typename _RandomAccessIterator, typename T,
83  typename BinaryOperation>
84  T
85  accumulate_switch(_RandomAccessIterator begin, _RandomAccessIterator end,
86  T init, BinaryOperation binary_op,
88  __gnu_parallel::_Parallelism parallelism_tag
90  {
92  static_cast<__gnu_parallel::sequence_index_t>(end - begin)
93  >= __gnu_parallel::_Settings::get().accumulate_minimal_n
94  && __gnu_parallel::is_parallel(parallelism_tag)))
95  {
96  T 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 InputIterator, typename T>
116  inline T
117  accumulate(InputIterator begin, InputIterator end, T init,
118  __gnu_parallel::_Parallelism parallelism_tag)
119  {
121  typedef typename iterator_traits::value_type value_type;
122  typedef typename iterator_traits::iterator_category iterator_category;
123 
124  return accumulate_switch(begin, end, init,
126  iterator_category(), parallelism_tag);
127  }
128 
129  template<typename InputIterator, typename T>
130  inline T
131  accumulate(InputIterator begin, InputIterator end, T init)
132  {
134  typedef typename iterator_traits::value_type value_type;
135  typedef typename iterator_traits::iterator_category iterator_category;
136 
137  return accumulate_switch(begin, end, init,
139  iterator_category());
140  }
141 
142  template<typename InputIterator, typename T, typename BinaryOperation>
143  inline T
144  accumulate(InputIterator begin, InputIterator end, T init,
145  BinaryOperation binary_op,
146  __gnu_parallel::_Parallelism parallelism_tag)
147  {
149  typedef typename iterator_traits::iterator_category iterator_category;
150  return accumulate_switch(begin, end, init, binary_op,
151  iterator_category(), parallelism_tag);
152  }
153 
154  template<typename InputIterator, typename T, typename BinaryOperation>
155  inline T
156  accumulate(InputIterator begin, InputIterator end, T init,
157  BinaryOperation binary_op)
158  {
160  typedef typename iterator_traits::iterator_category iterator_category;
161  return accumulate_switch(begin, end, init, binary_op,
162  iterator_category());
163  }
164 
165 
166  // Sequential fallback.
167  template<typename InputIterator1, typename InputIterator2, typename T>
168  inline T
169  inner_product(InputIterator1 first1, InputIterator1 last1,
170  InputIterator2 first2, T init,
172  { return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init); }
173 
174  template<typename InputIterator1, typename InputIterator2, typename T,
175  typename BinaryFunction1, typename BinaryFunction2>
176  inline T
177  inner_product(InputIterator1 first1, InputIterator1 last1,
178  InputIterator2 first2, T init, BinaryFunction1 binary_op1,
179  BinaryFunction2 binary_op2, __gnu_parallel::sequential_tag)
180  { return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init,
181  binary_op1, binary_op2); }
182 
183  // Parallel algorithm for random access iterators.
184  template<typename RandomAccessIterator1, typename RandomAccessIterator2,
185  typename T, typename BinaryFunction1, typename BinaryFunction2>
186  T
187  inner_product_switch(RandomAccessIterator1 first1,
188  RandomAccessIterator1 last1,
189  RandomAccessIterator2 first2, T init,
190  BinaryFunction1 binary_op1,
191  BinaryFunction2 binary_op2,
194  __gnu_parallel::_Parallelism parallelism_tag
196  {
197  if (_GLIBCXX_PARALLEL_CONDITION((last1 - first1)
199  accumulate_minimal_n
200  && __gnu_parallel::
201  is_parallel(parallelism_tag)))
202  {
203  T res = init;
205  inner_product_selector<RandomAccessIterator1,
206  RandomAccessIterator2, T> my_selector(first1, first2);
208  for_each_template_random_access_ed(first1, last1, binary_op2,
209  my_selector, binary_op1,
210  res, res, -1);
211  return res;
212  }
213  else
214  return inner_product(first1, last1, first2, init,
216  }
217 
218  // No parallelism for input iterators.
219  template<typename InputIterator1, typename InputIterator2, typename T,
220  typename BinaryFunction1, typename BinaryFunction2,
221  typename IteratorTag1, typename IteratorTag2>
222  inline T
223  inner_product_switch(InputIterator1 first1, InputIterator1 last1,
224  InputIterator2 first2, T init,
225  BinaryFunction1 binary_op1,
226  BinaryFunction2 binary_op2,
227  IteratorTag1, IteratorTag2)
228  { return inner_product(first1, last1, first2, init,
229  binary_op1, binary_op2,
231 
232  template<typename InputIterator1, typename InputIterator2, typename T,
233  typename BinaryFunction1, typename BinaryFunction2>
234  inline T
235  inner_product(InputIterator1 first1, InputIterator1 last1,
236  InputIterator2 first2, T init, BinaryFunction1 binary_op1,
237  BinaryFunction2 binary_op2,
238  __gnu_parallel::_Parallelism parallelism_tag)
239  {
240  typedef iterator_traits<InputIterator1> traits1_type;
241  typedef typename traits1_type::iterator_category iterator1_category;
242 
243  typedef iterator_traits<InputIterator2> traits2_type;
244  typedef typename traits2_type::iterator_category iterator2_category;
245 
246  return inner_product_switch(first1, last1, first2, init, binary_op1,
247  binary_op2, iterator1_category(),
248  iterator2_category(), parallelism_tag);
249  }
250 
251  template<typename InputIterator1, typename InputIterator2, typename T,
252  typename BinaryFunction1, typename BinaryFunction2>
253  inline T
254  inner_product(InputIterator1 first1, InputIterator1 last1,
255  InputIterator2 first2, T init, BinaryFunction1 binary_op1,
256  BinaryFunction2 binary_op2)
257  {
258  typedef iterator_traits<InputIterator1> traits1_type;
259  typedef typename traits1_type::iterator_category iterator1_category;
260 
261  typedef iterator_traits<InputIterator2> traits2_type;
262  typedef typename traits2_type::iterator_category iterator2_category;
263 
264  return inner_product_switch(first1, last1, first2, init, binary_op1,
265  binary_op2, iterator1_category(),
266  iterator2_category());
267  }
268 
269  template<typename InputIterator1, typename InputIterator2, typename T>
270  inline T
271  inner_product(InputIterator1 first1, InputIterator1 last1,
272  InputIterator2 first2, T init,
273  __gnu_parallel::_Parallelism parallelism_tag)
274  {
275  typedef iterator_traits<InputIterator1> traits_type1;
276  typedef typename traits_type1::value_type value_type1;
277  typedef iterator_traits<InputIterator2> traits_type2;
278  typedef typename traits_type2::value_type value_type2;
279 
280  typedef typename
282  multiplies_result_type;
283  return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init,
285  __gnu_parallel::
287  parallelism_tag);
288  }
289 
290  template<typename InputIterator1, typename InputIterator2, typename T>
291  inline T
292  inner_product(InputIterator1 first1, InputIterator1 last1,
293  InputIterator2 first2, T init)
294  {
295  typedef iterator_traits<InputIterator1> traits_type1;
296  typedef typename traits_type1::value_type value_type1;
297  typedef iterator_traits<InputIterator2> traits_type2;
298  typedef typename traits_type2::value_type value_type2;
299 
300  typedef typename
302  multiplies_result_type;
303  return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init,
305  __gnu_parallel::
307  }
308 
309  // Sequential fallback.
310  template<typename InputIterator, typename OutputIterator>
311  inline OutputIterator
312  partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
314  { return _GLIBCXX_STD_P::partial_sum(begin, end, result); }
315 
316  // Sequential fallback.
317  template<typename InputIterator, typename OutputIterator,
318  typename BinaryOperation>
319  inline OutputIterator
320  partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
321  BinaryOperation bin_op, __gnu_parallel::sequential_tag)
322  { return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op); }
323 
324  // Sequential fallback for input iterator case.
325  template<typename InputIterator, typename OutputIterator,
326  typename BinaryOperation, typename IteratorTag1,
327  typename IteratorTag2>
328  inline OutputIterator
329  partial_sum_switch(InputIterator begin, InputIterator end,
330  OutputIterator result, BinaryOperation bin_op,
331  IteratorTag1, IteratorTag2)
332  { return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op); }
333 
334  // Parallel algorithm for random access iterators.
335  template<typename InputIterator, typename OutputIterator,
336  typename BinaryOperation>
337  OutputIterator
338  partial_sum_switch(InputIterator begin, InputIterator end,
339  OutputIterator result, BinaryOperation bin_op,
341  {
343  static_cast<__gnu_parallel::sequence_index_t>(end - begin)
344  >= __gnu_parallel::_Settings::get().partial_sum_minimal_n))
345  return __gnu_parallel::parallel_partial_sum(begin, end,
346  result, bin_op);
347  else
348  return partial_sum(begin, end, result, bin_op,
350  }
351 
352  // Public interface.
353  template<typename InputIterator, typename OutputIterator>
354  inline OutputIterator
355  partial_sum(InputIterator begin, InputIterator end, OutputIterator result)
356  {
357  typedef typename iterator_traits<InputIterator>::value_type value_type;
358  return _GLIBCXX_STD_P::partial_sum(begin, end, result,
360  }
361 
362  // Public interface
363  template<typename InputIterator, typename OutputIterator,
364  typename BinaryOperation>
365  inline OutputIterator
366  partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
367  BinaryOperation binary_op)
368  {
369  typedef iterator_traits<InputIterator> traitsi_type;
370  typedef typename traitsi_type::iterator_category iteratori_category;
371 
372  typedef iterator_traits<OutputIterator> traitso_type;
373  typedef typename traitso_type::iterator_category iteratoro_category;
374 
375  return partial_sum_switch(begin, end, result, binary_op,
376  iteratori_category(), iteratoro_category());
377  }
378 
379  // Sequential fallback.
380  template<typename InputIterator, typename OutputIterator>
381  inline OutputIterator
382  adjacent_difference(InputIterator begin, InputIterator end,
383  OutputIterator result, __gnu_parallel::sequential_tag)
384  { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result); }
385 
386  // Sequential fallback.
387  template<typename InputIterator, typename OutputIterator,
388  typename BinaryOperation>
389  inline OutputIterator
390  adjacent_difference(InputIterator begin, InputIterator end,
391  OutputIterator result, BinaryOperation bin_op,
393  { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result, bin_op); }
394 
395  // Sequential fallback for input iterator case.
396  template<typename InputIterator, typename OutputIterator,
397  typename BinaryOperation, typename IteratorTag1,
398  typename IteratorTag2>
399  inline OutputIterator
400  adjacent_difference_switch(InputIterator begin, InputIterator end,
401  OutputIterator result, BinaryOperation bin_op,
402  IteratorTag1, IteratorTag2)
403  { return adjacent_difference(begin, end, result, bin_op,
405 
406  // Parallel algorithm for random access iterators.
407  template<typename InputIterator, typename OutputIterator,
408  typename BinaryOperation>
409  OutputIterator
410  adjacent_difference_switch(InputIterator begin, InputIterator end,
411  OutputIterator result, BinaryOperation bin_op,
414  __gnu_parallel::_Parallelism parallelism_tag
416  {
418  static_cast<__gnu_parallel::sequence_index_t>(end - begin)
419  >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n
420  && __gnu_parallel::is_parallel(parallelism_tag)))
421  {
422  bool dummy = true;
423  typedef __gnu_parallel::iterator_pair<InputIterator, OutputIterator,
425  *result = *begin;
426  ip begin_pair(begin + 1, result + 1),
427  end_pair(end, result + (end - begin));
430  for_each_template_random_access_ed(begin_pair, end_pair, bin_op,
431  functionality,
433  dummy, dummy, -1);
434  return functionality.finish_iterator;
435  }
436  else
437  return adjacent_difference(begin, end, result, bin_op,
439  }
440 
441  // Public interface.
442  template<typename InputIterator, typename OutputIterator>
443  inline OutputIterator
444  adjacent_difference(InputIterator begin, InputIterator end,
445  OutputIterator result,
446  __gnu_parallel::_Parallelism parallelism_tag)
447  {
448  typedef iterator_traits<InputIterator> traits_type;
449  typedef typename traits_type::value_type value_type;
450  return adjacent_difference(begin, end, result, std::minus<value_type>(),
451  parallelism_tag);
452  }
453 
454  template<typename InputIterator, typename OutputIterator>
455  inline OutputIterator
456  adjacent_difference(InputIterator begin, InputIterator end,
457  OutputIterator result)
458  {
459  typedef iterator_traits<InputIterator> traits_type;
460  typedef typename traits_type::value_type value_type;
461  return adjacent_difference(begin, end, result, std::minus<value_type>());
462  }
463 
464  template<typename InputIterator, typename OutputIterator,
465  typename BinaryOperation>
466  inline OutputIterator
467  adjacent_difference(InputIterator begin, InputIterator end,
468  OutputIterator result, BinaryOperation binary_op,
469  __gnu_parallel::_Parallelism parallelism_tag)
470  {
471  typedef iterator_traits<InputIterator> traitsi_type;
472  typedef typename traitsi_type::iterator_category iteratori_category;
473 
474  typedef iterator_traits<OutputIterator> traitso_type;
475  typedef typename traitso_type::iterator_category iteratoro_category;
476 
477  return adjacent_difference_switch(begin, end, result, binary_op,
478  iteratori_category(),
479  iteratoro_category(), parallelism_tag);
480  }
481 
482  template<typename InputIterator, typename OutputIterator,
483  typename BinaryOperation>
484  inline OutputIterator
485  adjacent_difference(InputIterator begin, InputIterator end,
486  OutputIterator result, BinaryOperation binary_op)
487  {
488  typedef iterator_traits<InputIterator> traitsi_type;
489  typedef typename traitsi_type::iterator_category iteratori_category;
490 
491  typedef iterator_traits<OutputIterator> traitso_type;
492  typedef typename traitso_type::iterator_category iteratoro_category;
493 
494  return adjacent_difference_switch(begin, end, result, binary_op,
495  iteratori_category(),
496  iteratoro_category());
497  }
498 } // end namespace
499 } // end namespace
500 
501 #endif /* _GLIBCXX_NUMERIC_H */
static const _Settings & get()
Get the global settings.
Parallel STL function calls corresponding to stl_numeric.h. The functions defined here mainly do case...
#define _GLIBCXX_PARALLEL_CONDITION(c)
Determine at compile(?)-time if the parallel variant of an algorithm should be called.
Definition: settings.h:95
OutputIterator parallel_partial_sum(InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op)
Parallel partial sum front-end.
Definition: partial_sum.h:196
Parallel unbalanced (equal-sized chunks).
Definition: types.h:48
std::accumulate() selector.
_Parallelism
Run-time equivalents for the compile-time tags.
Definition: types.h:42
One of the math functors.
Definition: stl_function.h:153
It finish_iterator
Iterator on last element processed; needed for some algorithms (e. g. std::transform()).
Helper iterator classes for the std::transform() functions. This file is a GNU parallel extension to ...
Functor doing nothing.
Parallel implementation of std::partial_sum(), i. e. prefix sums. This file is a GNU parallel extensi...
A pair of iterators. The usual iterator operations are applied to both child iterators.
Definition: iterator.h:44
Forces sequential execution at compile time.
Definition: tags.h:42
Parallel balanced (work-stealing).
Definition: types.h:51
One of the math functors.
Definition: stl_function.h:144
Op for_each_template_random_access_ed(RandomAccessIterator begin, RandomAccessIterator end, Op o, Fu &f, Red r, Result base, Result &output, typename std::iterator_traits< RandomAccessIterator >::difference_type bound)
Embarrassingly parallel algorithm for random access iterators, using hand-crafted parallelization by ...
Definition: par_loop.h:68
Functors representing different tasks to be plugged into the generic parallelization methods for emba...
Similar to std::multiplies, but allows two different types.
Definition: base.h:306
std::inner_product() selector.
Random-access iterators support a superset of bidirectional iterator operations.
Reduction function doing nothing.
Selector that returns the difference between two adjacent elements.
One of the math functors.
Definition: stl_function.h:135
Similar to std::plus, but allows two different types.
Definition: base.h:281
Main interface for embarrassingly parallel functions.