Intel(R) Threading Building Blocks Doxygen Documentation  version 4.2.3
parallel_do.h
Go to the documentation of this file.
1 /*
2  Copyright (c) 2005-2019 Intel Corporation
3 
4  Licensed under the Apache License, Version 2.0 (the "License");
5  you may not use this file except in compliance with the License.
6  You may obtain a copy of the License at
7 
8  http://www.apache.org/licenses/LICENSE-2.0
9 
10  Unless required by applicable law or agreed to in writing, software
11  distributed under the License is distributed on an "AS IS" BASIS,
12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  See the License for the specific language governing permissions and
14  limitations under the License.
15 
16 
17 
18 
19 */
20 
21 #ifndef __TBB_parallel_do_H
22 #define __TBB_parallel_do_H
23 
26 #include "task.h"
27 #include "aligned_space.h"
28 #include <iterator>
29 
30 namespace tbb {
31 namespace interface9 {
33 namespace internal {
34  template<typename Body, typename Item> class parallel_do_feeder_impl;
35 } // namespace internal
37 
39 
40  template<typename Item>
42  {
44  virtual ~parallel_do_feeder () {}
45  virtual void internal_add_copy( const Item& item ) = 0;
46 #if __TBB_CPP11_RVALUE_REF_PRESENT
47  virtual void internal_add_move( Item&& item ) = 0;
48 #endif
49  template<typename Body_, typename Item_> friend class internal::parallel_do_feeder_impl;
50  public:
52  void add( const Item& item ) {internal_add_copy(item);}
53 #if __TBB_CPP11_RVALUE_REF_PRESENT
54  void add( Item&& item ) {internal_add_move(std::move(item));}
55 #endif
56  };
57 
59 namespace internal {
60  template<typename Body> class do_group_task;
61 
63 
65  template<class Body, typename Item>
67  {
69  template<typename A1, typename A2, typename CvItem >
70  static void internal_call( const Body& obj, __TBB_FORWARDING_REF(A1) arg1, A2&, void (Body::*)(CvItem) const ) {
71  obj(tbb::internal::forward<A1>(arg1));
72  }
73  template<typename A1, typename A2, typename CvItem >
74  static void internal_call( const Body& obj, __TBB_FORWARDING_REF(A1) arg1, A2& arg2, void (Body::*)(CvItem, parallel_do_feeder<Item>&) const ) {
75  obj(tbb::internal::forward<A1>(arg1), arg2);
76  }
77  template<typename A1, typename A2, typename CvItem >
78  static void internal_call( const Body& obj, __TBB_FORWARDING_REF(A1) arg1, A2&, void (Body::*)(CvItem&) const ) {
79  obj(arg1);
80  }
81  template<typename A1, typename A2, typename CvItem >
82  static void internal_call( const Body& obj, __TBB_FORWARDING_REF(A1) arg1, A2& arg2, void (Body::*)(CvItem&, parallel_do_feeder<Item>&) const ) {
83  obj(arg1, arg2);
84  }
85  public:
86  template<typename A1, typename A2>
87  static void call( const Body& obj, __TBB_FORWARDING_REF(A1) arg1, A2& arg2 )
88  {
89  internal_call( obj, tbb::internal::forward<A1>(arg1), arg2, &Body::operator() );
90  }
91  };
92 
94 
96  template<typename Body, typename Item>
97  class do_iteration_task: public task
98  {
100 
101  Item my_value;
103 
104  do_iteration_task( const Item& value, feeder_type& feeder ) :
105  my_value(value), my_feeder(feeder)
106  {}
107 
108 #if __TBB_CPP11_RVALUE_REF_PRESENT
109  do_iteration_task( Item&& value, feeder_type& feeder ) :
110  my_value(std::move(value)), my_feeder(feeder)
111  {}
112 #endif
113 
115  {
117  return NULL;
118  }
119 
120  template<typename Body_, typename Item_> friend class parallel_do_feeder_impl;
121  }; // class do_iteration_task
122 
123  template<typename Iterator, typename Body, typename Item>
125  {
127 
128  Iterator my_iter;
130 
131  do_iteration_task_iter( const Iterator& iter, feeder_type& feeder ) :
132  my_iter(iter), my_feeder(feeder)
133  {}
134 
136  {
138  return NULL;
139  }
140 
141  template<typename Iterator_, typename Body_, typename Item_> friend class do_group_task_forward;
142  template<typename Body_, typename Item_> friend class do_group_task_input;
143  template<typename Iterator_, typename Body_, typename Item_> friend class do_task_iter;
144  }; // class do_iteration_task_iter
145 
147 
149  template<class Body, typename Item>
150  class parallel_do_feeder_impl : public parallel_do_feeder<Item>
151  {
152 #if __TBB_CPP11_RVALUE_REF_PRESENT
153  //Avoiding use of copy constructor in a virtual method if the type does not support it
154  void internal_add_copy_impl(std::true_type, const Item& item) {
155  typedef do_iteration_task<Body, Item> iteration_type;
156  iteration_type& t = *new (task::allocate_additional_child_of(*my_barrier)) iteration_type(item, *this);
157  task::spawn(t);
158  }
160  __TBB_ASSERT(false, "Overloading for r-value reference doesn't work or it's not movable and not copyable object");
161  }
162  void internal_add_copy( const Item& item ) __TBB_override
163  {
164 #if __TBB_CPP11_IS_COPY_CONSTRUCTIBLE_PRESENT
166 #else
168 #endif
169  }
170  void internal_add_move( Item&& item ) __TBB_override
171  {
172  typedef do_iteration_task<Body, Item> iteration_type;
173  iteration_type& t = *new (task::allocate_additional_child_of(*my_barrier)) iteration_type(std::move(item), *this);
174  task::spawn(t);
175  }
176 #else /* ! __TBB_CPP11_RVALUE_REF_PRESENT */
177  void internal_add_copy(const Item& item) __TBB_override {
178  typedef do_iteration_task<Body, Item> iteration_type;
179  iteration_type& t = *new (task::allocate_additional_child_of(*my_barrier)) iteration_type(item, *this);
180  task::spawn(t);
181  }
182 #endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
183  public:
184  const Body* my_body;
186 
188  {
190  __TBB_ASSERT(my_barrier, "root task allocation failed");
191  }
192 
193 #if __TBB_TASK_GROUP_CONTEXT
195  {
196  my_barrier = new( task::allocate_root(context) ) empty_task();
197  __TBB_ASSERT(my_barrier, "root task allocation failed");
198  }
199 #endif
200 
202  {
203  my_barrier->destroy(*my_barrier);
204  }
205  }; // class parallel_do_feeder_impl
206 
207 
209 
212  template<typename Iterator, typename Body, typename Item>
214  {
215  static const size_t max_arg_size = 4;
216 
218 
220  Iterator my_first;
221  size_t my_size;
222 
223  do_group_task_forward( Iterator first, size_t size, feeder_type& feeder )
224  : my_feeder(feeder), my_first(first), my_size(size)
225  {}
226 
228  {
229  typedef do_iteration_task_iter<Iterator, Body, Item> iteration_type;
230  __TBB_ASSERT( my_size>0, NULL );
231  task_list list;
232  task* t;
233  size_t k=0;
234  for(;;) {
235  t = new( allocate_child() ) iteration_type( my_first, my_feeder );
236  ++my_first;
237  if( ++k==my_size ) break;
238  list.push_back(*t);
239  }
240  set_ref_count(int(k+1));
241  spawn(list);
243  return NULL;
244  }
245 
246  template<typename Iterator_, typename Body_, typename _Item> friend class do_task_iter;
247  }; // class do_group_task_forward
248 
249  template<typename Body, typename Item>
250  class do_group_task_input: public task
251  {
252  static const size_t max_arg_size = 4;
253 
255 
257  size_t my_size;
259 
261  : my_feeder(feeder), my_size(0)
262  {}
263 
265  {
266 #if __TBB_CPP11_RVALUE_REF_PRESENT
267  typedef std::move_iterator<Item*> Item_iterator;
268 #else
269  typedef Item* Item_iterator;
270 #endif
272  __TBB_ASSERT( my_size>0, NULL );
273  task_list list;
274  task* t;
275  size_t k=0;
276  for(;;) {
277  t = new( allocate_child() ) iteration_type( Item_iterator(my_arg.begin() + k), my_feeder );
278  if( ++k==my_size ) break;
279  list.push_back(*t);
280  }
281  set_ref_count(int(k+1));
282  spawn(list);
284  return NULL;
285  }
286 
288  for( size_t k=0; k<my_size; ++k)
289  (my_arg.begin() + k)->~Item();
290  }
291 
292  template<typename Iterator_, typename Body_, typename Item_> friend class do_task_iter;
293  }; // class do_group_task_input
294 
296 
298  template<typename Iterator, typename Body, typename Item>
299  class do_task_iter: public task
300  {
302 
303  public:
304  do_task_iter( Iterator first, Iterator last , feeder_type& feeder ) :
305  my_first(first), my_last(last), my_feeder(feeder)
306  {}
307 
308  private:
309  Iterator my_first;
310  Iterator my_last;
312 
313  /* Do not merge run(xxx) and run_xxx() methods. They are separated in order
314  to make sure that compilers will eliminate unused argument of type xxx
315  (that is will not put it on stack). The sole purpose of this argument
316  is overload resolution.
317 
318  An alternative could be using template functions, but explicit specialization
319  of member function templates is not supported for non specialized class
320  templates. Besides template functions would always fall back to the least
321  efficient variant (the one for input iterators) in case of iterators having
322  custom tags derived from basic ones. */
324  {
325  typedef typename std::iterator_traits<Iterator>::iterator_category iterator_tag;
326  return run( (iterator_tag*)NULL );
327  }
328 
331  inline task* run( void* ) { return run_for_input_iterator(); }
332 
334  typedef do_group_task_input<Body, Item> block_type;
335 
336  block_type& t = *new( allocate_additional_child_of(*my_feeder.my_barrier) ) block_type(my_feeder);
337  size_t k=0;
338  while( !(my_first == my_last) ) {
339  // Move semantics are automatically used when supported by the iterator
340  new (t.my_arg.begin() + k) Item(*my_first);
341  ++my_first;
342  if( ++k==block_type::max_arg_size ) {
343  if ( !(my_first == my_last) )
345  break;
346  }
347  }
348  if( k==0 ) {
349  destroy(t);
350  return NULL;
351  } else {
352  t.my_size = k;
353  return &t;
354  }
355  }
356 
357  inline task* run( std::forward_iterator_tag* ) { return run_for_forward_iterator(); }
358 
361 
362  Iterator first = my_first;
363  size_t k=0;
364  while( !(my_first==my_last) ) {
365  ++my_first;
366  if( ++k==block_type::max_arg_size ) {
367  if ( !(my_first==my_last) )
369  break;
370  }
371  }
372  return k==0 ? NULL : new( allocate_additional_child_of(*my_feeder.my_barrier) ) block_type(first, k, my_feeder);
373  }
374 
375  inline task* run( std::random_access_iterator_tag* ) { return run_for_random_access_iterator(); }
376 
379  typedef do_iteration_task_iter<Iterator, Body, Item> iteration_type;
380 
381  size_t k = static_cast<size_t>(my_last-my_first);
382  if( k > block_type::max_arg_size ) {
383  Iterator middle = my_first + k/2;
384 
386  do_task_iter& b = *new( c.allocate_child() ) do_task_iter(middle, my_last, my_feeder);
388 
389  my_last = middle;
390  c.set_ref_count(2);
391  c.spawn(b);
392  return this;
393  }else if( k != 0 ) {
394  task_list list;
395  task* t;
396  size_t k1=0;
397  for(;;) {
398  t = new( allocate_child() ) iteration_type(my_first, my_feeder);
399  ++my_first;
400  if( ++k1==k ) break;
401  list.push_back(*t);
402  }
403  set_ref_count(int(k+1));
404  spawn(list);
406  }
407  return NULL;
408  }
409  }; // class do_task_iter
410 
412 
414  template<typename Iterator, typename Body, typename Item>
415  void run_parallel_do( Iterator first, Iterator last, const Body& body
417  , task_group_context& context
418 #endif
419  )
420  {
421  typedef do_task_iter<Iterator, Body, Item> root_iteration_task;
422 #if __TBB_TASK_GROUP_CONTEXT
423  parallel_do_feeder_impl<Body, Item> feeder(context);
424 #else
426 #endif
427  feeder.my_body = &body;
428 
429  root_iteration_task &t = *new( feeder.my_barrier->allocate_child() ) root_iteration_task(first, last, feeder);
430 
431  feeder.my_barrier->set_ref_count(2);
432  feeder.my_barrier->spawn_and_wait_for_all(t);
433  }
434 
436 
438  template<typename Iterator, typename Body, typename Item>
439  void select_parallel_do( Iterator first, Iterator last, const Body& body, void (Body::*)(Item) const
441  , task_group_context& context
442 #endif
443  )
444  {
446 #if __TBB_TASK_GROUP_CONTEXT
447  , context
448 #endif
449  );
450  }
451 
453 
455  template<typename Iterator, typename Body, typename Item, typename _Item>
456  void select_parallel_do( Iterator first, Iterator last, const Body& body, void (Body::*)(Item, parallel_do_feeder<_Item>&) const
458  , task_group_context& context
459 #endif
460  )
461  {
463 #if __TBB_TASK_GROUP_CONTEXT
464  , context
465 #endif
466  );
467  }
468 
469 } // namespace internal
470 } // namespace interface9
472 
495 
497 template<typename Iterator, typename Body>
498 void parallel_do( Iterator first, Iterator last, const Body& body )
499 {
500  if ( first == last )
501  return;
502 #if __TBB_TASK_GROUP_CONTEXT
503  task_group_context context(internal::PARALLEL_DO);
504 #endif
505  interface9::internal::select_parallel_do( first, last, body, &Body::operator()
507  , context
508 #endif
509  );
510 }
511 
512 template<typename Range, typename Body>
513 void parallel_do(Range& rng, const Body& body) {
515 }
516 
517 template<typename Range, typename Body>
518 void parallel_do(const Range& rng, const Body& body) {
520 }
521 
522 #if __TBB_TASK_GROUP_CONTEXT
523 
525 template<typename Iterator, typename Body>
526 void parallel_do( Iterator first, Iterator last, const Body& body, task_group_context& context )
527 {
528  if ( first == last )
529  return;
530  interface9::internal::select_parallel_do( first, last, body, &Body::operator(), context );
531 }
532 
533 template<typename Range, typename Body>
534 void parallel_do(Range& rng, const Body& body, task_group_context& context) {
535  parallel_do(tbb::internal::first(rng), tbb::internal::last(rng), body, context);
536 }
537 
538 template<typename Range, typename Body>
539 void parallel_do(const Range& rng, const Body& body, task_group_context& context) {
540  parallel_do(tbb::internal::first(rng), tbb::internal::last(rng), body, context);
541 }
542 
543 #endif // __TBB_TASK_GROUP_CONTEXT
544 
546 
547 using interface9::parallel_do_feeder;
548 
549 } // namespace
550 
551 #endif /* __TBB_parallel_do_H */
do_iteration_task(Item &&value, feeder_type &feeder)
Definition: parallel_do.h:109
#define __TBB_override
Definition: tbb_stddef.h:244
internal::allocate_child_proxy & allocate_child()
Returns proxy for overloaded new that allocates a child task of *this.
Definition: task.h:654
static void internal_call(const Body &obj, __TBB_FORWARDING_REF(A1) arg1, A2 &, void(Body::*)(CvItem &) const)
Definition: parallel_do.h:78
do_iteration_task(const Item &value, feeder_type &feeder)
Definition: parallel_do.h:104
parallel_do_feeder_impl(tbb::task_group_context &context)
Definition: parallel_do.h:194
T * begin() const
Pointer to beginning of array.
Definition: aligned_space.h:39
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:169
static void internal_call(const Body &obj, __TBB_FORWARDING_REF(A1) arg1, A2 &arg2, void(Body::*)(CvItem &, parallel_do_feeder< Item > &) const)
Definition: parallel_do.h:82
void add(const Item &item)
Add a work item to a running parallel_do.
Definition: parallel_do.h:52
task that does nothing. Useful for synchronization.
Definition: task.h:959
auto first(Container &c) -> decltype(begin(c))
Used to form groups of tasks.
Definition: task.h:335
bool_constant< true > true_type
Definition: tbb_stddef.h:472
parallel_do_feeder_impl< Body, Item > feeder_type
Definition: parallel_do.h:126
task * execute() __TBB_override
Should be overridden by derived classes.
Definition: parallel_do.h:264
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type type
Base class for types that should not be copied or assigned.
Definition: tbb_stddef.h:335
virtual void internal_add_copy(const Item &item)=0
A list of children.
Definition: task.h:990
void recycle_as_child_of(task &new_parent)
Change this to be a child of new_parent.
Definition: task.h:698
task * run(std::forward_iterator_tag *)
Definition: parallel_do.h:357
Base class for user-defined tasks.
Definition: task.h:592
task * run(std::random_access_iterator_tag *)
Definition: parallel_do.h:375
parallel_do_feeder_impl< Body, Item > feeder_type
Definition: parallel_do.h:99
parallel_do_feeder_impl< Body, Item > feeder_type
Definition: parallel_do.h:301
void spawn_and_wait_for_all(task &child)
Similar to spawn followed by wait_for_all, but more efficient.
Definition: task.h:773
auto last(Container &c) -> decltype(begin(c))
internal::allocate_continuation_proxy & allocate_continuation()
Returns proxy for overloaded new that allocates a continuation task of *this.
Definition: task.h:649
void run_parallel_do(Iterator first, Iterator last, const Body &body, task_group_context &context)
For internal use only.
Definition: parallel_do.h:415
do_iteration_task_iter(const Iterator &iter, feeder_type &feeder)
Definition: parallel_do.h:131
#define __TBB_FORWARDING_REF(A)
Definition: tbb_stddef.h:500
task * execute() __TBB_override
Should be overridden by derived classes.
Definition: parallel_do.h:227
The graph class.
void internal_add_copy_impl(std::true_type, const Item &item)
Definition: parallel_do.h:154
task * execute() __TBB_override
Should be overridden by derived classes.
Definition: parallel_do.h:323
Class the user supplied algorithm body uses to add new tasks.
Definition: parallel_do.h:41
void internal_add_copy(const Item &item) __TBB_override
Definition: parallel_do.h:162
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long value
static void call(const Body &obj, __TBB_FORWARDING_REF(A1) arg1, A2 &arg2)
Definition: parallel_do.h:87
static void internal_call(const Body &obj, __TBB_FORWARDING_REF(A1) arg1, A2 &, void(Body::*)(CvItem) const)
Definition: parallel_do.h:70
void push_back(task &task)
Push task onto back of list.
Definition: task.h:1007
task * execute() __TBB_override
Should be overridden by derived classes.
Definition: parallel_do.h:135
void recycle_to_reexecute()
Schedule this for reexecution after current execute() returns.
Definition: task.h:714
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:309
task * execute() __TBB_override
Should be overridden by derived classes.
Definition: parallel_do.h:114
void select_parallel_do(Iterator first, Iterator last, const Body &body, void(Body::*)(Item) const, task_group_context &context)
For internal use only.
Definition: parallel_do.h:439
static void internal_call(const Body &obj, __TBB_FORWARDING_REF(A1) arg1, A2 &arg2, void(Body::*)(CvItem, parallel_do_feeder< Item > &) const)
Definition: parallel_do.h:74
friend class internal::parallel_do_feeder_impl
Definition: parallel_do.h:49
parallel_do_feeder_impl< Body, Item > feeder_type
Definition: parallel_do.h:217
void internal_add_move(Item &&item) __TBB_override
Definition: parallel_do.h:170
void set_ref_count(int count)
Set reference count.
Definition: task.h:734
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t size
bool_constant< false > false_type
Definition: tbb_stddef.h:473
void parallel_do(Iterator first, Iterator last, const Body &body)
Parallel iteration over a range, with optional addition of more work.
Definition: parallel_do.h:498
static internal::allocate_root_proxy allocate_root()
Returns proxy for overloaded new that allocates a root task.
Definition: task.h:636
do_task_iter(Iterator first, Iterator last, feeder_type &feeder)
Definition: parallel_do.h:304
do_group_task_forward(Iterator first, size_t size, feeder_type &feeder)
Definition: parallel_do.h:223
virtual void internal_add_move(Item &&item)=0
aligned_space< Item, max_arg_size > my_arg
Definition: parallel_do.h:258
#define __TBB_TASK_GROUP_CONTEXT
Definition: tbb_config.h:546
void internal_add_copy_impl(std::false_type, const Item &)
Definition: parallel_do.h:159
parallel_do_feeder_impl< Body, Item > feeder_type
Definition: parallel_do.h:254

Copyright © 2005-2019 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.