Sourcemeta Core 0.0.0
Loading...
Searching...
No Matches
parallel_for_each.h
1#ifndef SOURCEMETA_CORE_PARALLEL_FOR_EACH_H_
2#define SOURCEMETA_CORE_PARALLEL_FOR_EACH_H_
3
4#include <sourcemeta/core/parallel_error.h>
5
6#include <algorithm> // std::max
7#include <climits> // UINT_MAX
8#include <concepts> // std::copyable, std::invocable
9#include <exception> // std::exception_ptr, std::current_exception, std::rethrow_exception
10#include <functional> // std::function
11#include <iterator> // std::input_iterator, std::iter_reference_t
12#include <mutex> // std::mutex, std::scoped_lock, std::unique_lock
13#include <optional> // std::optional, std::nullopt
14#include <queue> // std::queue
15#include <thread> // std::thread
16#include <utility> // std::forward
17#include <vector> // std::vector
18
19#if defined(_WIN32)
20#include <process.h> // _beginthreadex
21#ifndef NOMINMAX
22#define NOMINMAX
23#endif
24#include <windows.h>
25#else
26#include <pthread.h>
27#endif
28
29namespace sourcemeta::core {
30
31#ifndef DOXYGEN
32#if defined(_WIN32)
33// See
34// https://learn.microsoft.com/en-us/cpp/c-runtime-library/reference/beginthread-beginthreadex?view=msvc-170
35inline unsigned __stdcall parallel_for_each_windows_thread_start(
36 void *argument) {
37 auto *function_ptr = static_cast<std::function<void()> *>(argument);
38 (*function_ptr)();
39 delete function_ptr;
40 return 0;
41}
42#endif
43#endif
44
45// The first exception a worker runs into is the one the caller is handed, so
46// one that arrives after it is dropped rather than replacing it
47inline auto hold_first_exception(std::mutex &mutex, std::exception_ptr &holder,
48 const std::exception_ptr &pointer) -> void {
49 std::scoped_lock lock{mutex};
50 if (!holder) {
51 holder = pointer;
52 }
53}
54
89template <typename Iterator, typename Callback>
90 requires std::input_iterator<Iterator> && std::copyable<Iterator> &&
91 std::invocable<Callback, std::iter_reference_t<Iterator>,
92 std::size_t, std::size_t>
94 Iterator first, Iterator last, Callback &&callback,
95 const std::size_t parallelism = std::thread::hardware_concurrency(),
96 const std::size_t stack_size_bytes = 0) -> void {
97 const auto effective_parallelism{
98 std::forward_iterator<Iterator> ? (std::max)(parallelism, 1uz) : 1uz};
99
100 // Empty list
101 if (first == last) {
102 return;
103 }
104
105 // If it is a single element or there is no parallelism,
106 // just do a normal loop without dealing with threads
107 if (effective_parallelism == 1 || std::ranges::next(first) == last) {
108 std::size_t cursor{1};
109 for (auto iterator = first; iterator != last; ++iterator, ++cursor) {
110 callback(*iterator, effective_parallelism, cursor);
111 }
112
113 return;
114 }
115
116 std::queue<Iterator> tasks;
117 for (auto iterator = first; iterator != last; ++iterator) {
118 tasks.push(iterator);
119 }
120
121 std::mutex queue_mutex;
122 std::mutex exception_mutex;
123
124 auto effective_callback = std::forward<Callback>(callback);
125
126 std::exception_ptr exception = nullptr;
127
128 std::vector<std::thread> workers;
129 workers.reserve(effective_parallelism);
130
131 const auto total{tasks.size()};
132
133 // Worker function that runs the actual per-item work and captures the
134 // environment by reference. It will be heap-copied into the native thread
135 // API.
136 auto worker_callable = [&tasks, &queue_mutex, &effective_callback, &exception,
137 &exception_mutex,
138 worker_parallelism = effective_parallelism, total] {
139 try {
140 while (true) {
141 // The lock is given up before the work runs, as holding it across the
142 // callback would leave the other workers waiting on the queue for as
143 // long as this one takes
144 std::unique_lock lock{queue_mutex};
145 if (tasks.empty()) {
146 return;
147 }
148
149 const auto iterator{tasks.front()};
150 const auto cursor{total - tasks.size() + 1};
151 tasks.pop();
152 lock.unlock();
153 effective_callback(*iterator, worker_parallelism, cursor);
154 }
155 } catch (...) {
156 hold_first_exception(exception_mutex, exception,
157 std::current_exception());
158 }
159 };
160
161 std::optional<StaticString> creation_error;
162
163 // TODO: Replace std::function with std::move_only_function once
164 // Apple Clang ships libc++ 19+ (__cpp_lib_move_only_function)
165#if defined(_WIN32)
166 for (std::size_t index = 0; index < effective_parallelism; ++index) {
167 auto *heap_function = new std::function<void()>(worker_callable);
168 if (stack_size_bytes > static_cast<std::size_t>(UINT_MAX)) {
169 delete heap_function;
170 creation_error =
171 StaticString{"The requested stack size is too large for this "
172 "platform"};
173 break;
174 }
175
176 auto raw_handle = _beginthreadex(
177 nullptr, static_cast<unsigned>(stack_size_bytes),
178 &parallel_for_each_windows_thread_start, heap_function, 0, nullptr);
179 if (raw_handle == 0) {
180 delete heap_function;
181 creation_error = StaticString{"Could not create thread"};
182 break;
183 }
184
185 HANDLE thread_handle = reinterpret_cast<HANDLE>(raw_handle);
186 workers.emplace_back([thread_handle] {
187 WaitForSingleObject(thread_handle, INFINITE);
188 CloseHandle(thread_handle);
189 });
190 }
191#else
192 for (std::size_t index = 0; index < effective_parallelism; ++index) {
193 // We can't use std::thread, as it doesn't let us tweak the thread stack
194 // size
195 pthread_attr_t attr;
196 pthread_attr_init(&attr);
197 // A stack size the platform cannot honour, such as one below its minimum
198 // or one that is not a multiple of its page size, must be reported rather
199 // than dropped in favour of the default, as the caller asked for it to
200 // bound how deep the work it hands over may recurse
201 if (stack_size_bytes > 0 &&
202 pthread_attr_setstacksize(&attr, stack_size_bytes) != 0) {
203 pthread_attr_destroy(&attr);
204 creation_error =
205 StaticString{"The requested stack size is not supported by this "
206 "platform"};
207 break;
208 }
209
210 auto *heap_function = new std::function<void()>(worker_callable);
211 pthread_t pthread_handle;
212 auto raw_handle = pthread_create(
213 &pthread_handle, &attr,
214 [](void *arg) -> void * {
215 auto *function_ptr = static_cast<std::function<void()> *>(arg);
216 (*function_ptr)();
217 delete function_ptr;
218 return nullptr;
219 },
220 heap_function);
221 if (raw_handle != 0) {
222 pthread_attr_destroy(&attr);
223 delete heap_function;
224 creation_error = StaticString{"Could not create thread"};
225 break;
226 }
227 workers.emplace_back(
228 [pthread_handle] { pthread_join(pthread_handle, nullptr); });
229 pthread_attr_destroy(&attr);
230 }
231#endif
232
233 // If thread creation failed after some workers have already started, those
234 // workers keep referencing the stack locals of this frame, so unwinding past
235 // them must be avoided. Drain the remaining tasks so the running workers stop
236 // pulling new work and exit, then join every already-created worker before
237 // propagating the failure
238 if (creation_error.has_value()) {
239 std::scoped_lock lock{queue_mutex};
240 std::queue<Iterator> empty;
241 tasks.swap(empty);
242 }
243
244 for (auto &worker_thread : workers) {
245 worker_thread.join();
246 }
247
248 if (creation_error.has_value()) {
249 throw ParallelThreadError{creation_error.value()};
250 }
251
252 if (exception) {
253 std::rethrow_exception(exception);
254 }
255}
256
257} // namespace sourcemeta::core
258
259#endif
Definition parallel_error.h:10
auto parallel_for_each(Iterator first, Iterator last, Callback &&callback, const std::size_t parallelism=std::thread::hardware_concurrency(), const std::size_t stack_size_bytes=0) -> void
Definition parallel_for_each.h:93
Definition text_static_string.h:20