1.. _Cook_Until_Done_parallel_do:
2
3Cook Until Done: parallel_for_each
4==================================
5
6
7For some loops, the end of the iteration space is not known in advance,
8or the loop body may add more iterations to do before the loop exits.
9You can deal with both situations using the template class ``oneapi::tbb::parallel_for_each``.
10
11
12A linked list is an example of an iteration space that is not known in
13advance. In parallel programming, it is usually better to use dynamic
14arrays instead of linked lists, because accessing items in a linked list
15is inherently serial. But if you are limited to linked lists, the items
16can be safely processed in parallel, and processing each item takes at
17least a few thousand instructions, you can use ``parallel_for_each`` to
18gain some parallelism.
19
20
21For example, consider the following serial code:
22
23
24::
25
26
27   void SerialApplyFooToList( const std::list<Item>& list ) {
28       for( std::list<Item>::const_iterator i=list.begin() i!=list.end(); ++i )
29           Foo(*i);
30   }
31
32
33If ``Foo`` takes at least a few thousand instructions to run, you can
34get parallel speedup by converting the loop to use
35``parallel_for_each``. To do so, define an object with a ``const``
36qualified ``operator()``. This is similar to a C++ function object from
37the C++ standard header ``<functional>``, except that ``operator()``
38must be ``const``.
39
40
41::
42
43
44   class ApplyFoo {
45   public:
46       void operator()( Item& item ) const {
47           Foo(item);
48       }
49   };
50
51
52The parallel form of ``SerialApplyFooToList`` is as follows:
53
54
55::
56
57
58   void ParallelApplyFooToList( const std::list<Item>& list ) {
59       parallel_for_each( list.begin(), list.end(), ApplyFoo() );
60   }
61
62
63An invocation of ``parallel_for_each`` never causes two threads to act
64on an input iterator concurrently. Thus typical definitions of input
65iterators for sequential programs work correctly. This convenience makes
66``parallel_for_each`` unscalable, because the fetching of work is
67serial. But in many situations, you still get useful speedup over doing
68things sequentially.
69
70
71There are two ways that ``parallel_for_each`` can acquire work scalably.
72
73
74-  The iterators can be random-access iterators.
75
76
77-  The body argument to ``parallel_for_each``, if it takes a second
78   argument *feeder* of type ``parallel_for_each<Item>&``, can add more
79   work by calling ``feeder.add(item)``. For example, suppose processing
80   a node in a tree is a prerequisite to processing its descendants.
81   With ``parallel_for_each``, after processing a node, you could use
82   ``feeder.add`` to add the descendant nodes. The instance of
83   ``parallel_for_each`` does not terminate until all items have been
84   processed.
85