1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
|
/*
* Copyright (C) 2015 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef ParallelHelperPool_h
#define ParallelHelperPool_h
#include <wtf/Condition.h>
#include <wtf/Lock.h>
#include <wtf/RefPtr.h>
#include <wtf/SharedTask.h>
#include <wtf/ThreadSafeRefCounted.h>
#include <wtf/Threading.h>
#include <wtf/Vector.h>
#include <wtf/WeakRandom.h>
namespace WTF {
// A ParallelHelperPool is a shared pool of threads that can be asked to help with some finite-time
// parallel activity. It's designed to work well when there are multiple concurrent tasks that may
// all want parallel help. In that case, we don't want each task to start its own thread pool. It's
// also designed to work well for tasks that do their own load balancing and do not wish to
// participate in microtask-style load balancing.
//
// A pool can have many clients, and each client may have zero or one tasks. The pool will have up
// to some number of threads, configurable with ParallelHelperPool::addThreads(); usually you bound
// this by the number of CPUs. Whenever a thread is idle and it notices that some client has a
// task, it will run the task. A task may be run on anywhere between zero and N threads, where N is
// the number of threads in the pool. Tasks run to completion. It's expected that a task will have
// its own custom ideas about how to participate in some parallel activity's load balancing, and it
// will return when the parallel activity is done. For example, a parallel marking task will return
// when the mark phase is done.
//
// Threads may have a choice between many tasks, since there may be many clients and each client
// may have a task. For the marking example, that may happen if there are multiple VM instances and
// each instance decides to start parallel marking at the same time. In that case, threads choose
// a task at random. So long as any client has a task, all threads in the pool will continue
// running the available tasks. Threads go idle when no client has tasks to run.
class ParallelHelperPool;
// A client is a placeholder for a parallel algorithm. A parallel algorithm will have a task that
// can be run concurrently. Whenever a client has a task set (you have called setTask() or
// setFunction()), threads in the pool may run that task. If a task returns on any thread, the
// client will assume that the task is done and will clear the task. If the task is cleared (the
// task runs to completion on any thread or you call finish()), any threads in the pool already
// running the last set task(s) will continue to run them. You can wait for all of them to finish
// by calling finish(). That method will clear the task and wait for any threads running the last
// set task to finish. There are two known-good patterns for using a client:
//
// 1) Tasks intrinsically know when the algorithm reaches termination, and simply returns when
// this happens. The main thread runs the task by doing:
//
// client->setFunction(
// [=] () {
// do things;
// });
// client->doSomeHelping();
// client->finish();
//
// Calling doSomeHelping() ensures that the algorithm runs on at least one thread (this one).
// Tasks will know when to complete, and will return when they are done. This will clear the
// task to ensure that no new threads will run the task. Then, finish() clears the current task
// and waits for any parallel tasks to finish after the main thread has finished. It's possible
// for threads to still be running the last set task (i.e. the one set by setFunction()) even
// after the task has been cleared. Waiting for idle ensures that no old tasks are running
// anymore.
//
// You can do this more easily by using the runFunctionInParallel() helper:
//
// clients->runFunctionInParallel(
// [=] () {
// do things;
// });
//
// 2) Tasks keep doing things until they are told to quit using some custom notification mechanism.
// The main thread runs the task by doing:
//
// bool keepGoing = true;
// client->setFunction(
// [=] () {
// while (keepGoing) {
// do things;
// }
// });
//
// When work runs out, the main thread will inform tasks that there is no more work, and then
// wait until no more tasks are running:
//
// keepGoing = false;
// client->finish();
//
// This works best when the main thread doesn't actually want to run the task that it set in the
// client. This happens for example in parallel marking. The main thread uses a somewhat
// different marking algorithm than the helpers. The main thread may provide work that the
// helpers steal. The main thread knows when termination is reached, and simply tells the
// helpers to stop upon termination.
//
// The known-good styles of using ParallelHelperClient all involve a parallel algorithm that has
// its own work distribution and load balancing.
//
// Note that it is not valid to use the same ParallelHelperClient instance from multiple threads.
// Each thread should have its own ParallelHelperClient in that case. Failure to follow this advice
// will lead to RELEASE_ASSERT's or worse.
class ParallelHelperClient {
WTF_MAKE_NONCOPYABLE(ParallelHelperClient);
WTF_MAKE_FAST_ALLOCATED;
public:
WTF_EXPORT_PRIVATE ParallelHelperClient(RefPtr<ParallelHelperPool>);
WTF_EXPORT_PRIVATE ~ParallelHelperClient();
WTF_EXPORT_PRIVATE void setTask(RefPtr<SharedTask<void ()>>);
template<typename Functor>
void setFunction(const Functor& functor)
{
setTask(createSharedTask<void ()>(functor));
}
WTF_EXPORT_PRIVATE void finish();
WTF_EXPORT_PRIVATE void doSomeHelping();
// Equivalent to:
// client->setTask(task);
// client->doSomeHelping();
// client->finish();
WTF_EXPORT_PRIVATE void runTaskInParallel(RefPtr<SharedTask<void ()>>);
// Equivalent to:
// client->setFunction(functor);
// client->doSomeHelping();
// client->finish();
template<typename Functor>
void runFunctionInParallel(const Functor& functor)
{
runTaskInParallel(createSharedTask<void ()>(functor));
}
ParallelHelperPool& pool() { return *m_pool; }
unsigned numberOfActiveThreads() const { return m_numActive; }
private:
friend class ParallelHelperPool;
void finish(const LockHolder&);
RefPtr<SharedTask<void ()>> claimTask(const LockHolder&);
void runTask(RefPtr<SharedTask<void ()>>);
RefPtr<ParallelHelperPool> m_pool;
RefPtr<SharedTask<void ()>> m_task;
unsigned m_numActive { 0 };
};
class ParallelHelperPool : public ThreadSafeRefCounted<ParallelHelperPool> {
public:
WTF_EXPORT_PRIVATE ParallelHelperPool();
WTF_EXPORT_PRIVATE ~ParallelHelperPool();
WTF_EXPORT_PRIVATE void ensureThreads(unsigned numThreads);
unsigned numberOfThreads() const { return m_numThreads; }
WTF_EXPORT_PRIVATE void doSomeHelping();
private:
friend class ParallelHelperClient;
void didMakeWorkAvailable(const LockHolder&);
void helperThreadBody();
bool hasClientWithTask(const LockHolder&);
ParallelHelperClient* getClientWithTask(const LockHolder&);
ParallelHelperClient* waitForClientWithTask(const LockHolder&);
Lock m_lock;
Condition m_workAvailableCondition;
Condition m_workCompleteCondition;
WeakRandom m_random;
Vector<ParallelHelperClient*> m_clients;
Vector<ThreadIdentifier> m_threads;
unsigned m_numThreads { 0 }; // This can be larger than m_threads.size() because we start threads only once there is work.
bool m_isDying { false };
};
} // namespace WTF
using WTF::ParallelHelperClient;
using WTF::ParallelHelperPool;
#endif // ParallelHelperPool_h
|
