3 Copyright (C) 2019-2022 Free Software Foundation, Inc.
5 This file is part of GDB.
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3 of the License, or
10 (at your option) any later version.
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <http://www.gnu.org/licenses/>. */
20 #ifndef GDBSUPPORT_PARALLEL_FOR_H
21 #define GDBSUPPORT_PARALLEL_FOR_H
24 #include <type_traits>
25 #include "gdbsupport/invoke-result.h"
26 #include "gdbsupport/thread-pool.h"
27 #include "gdbsupport/function-view.h"
35 /* This is a helper class that is used to accumulate results for
36 parallel_for. There is a specialization for 'void', below. */
38 struct par_for_accumulator
42 explicit par_for_accumulator (size_t n_threads
)
43 : m_futures (n_threads
)
47 /* The result type that is accumulated. */
48 typedef std::vector
<T
> result_type
;
50 /* Post the Ith task to a background thread, and store a future for
52 void post (size_t i
, std::function
<T ()> task
)
55 = gdb::thread_pool::g_thread_pool
->post_task (std::move (task
));
58 /* Invoke TASK in the current thread, then compute all the results
59 from all background tasks and put them into a result vector,
61 result_type
finish (gdb::function_view
<T ()> task
)
63 result_type
result (m_futures
.size () + 1);
65 result
.back () = task ();
67 for (size_t i
= 0; i
< m_futures
.size (); ++i
)
68 result
[i
] = m_futures
[i
].get ();
75 /* A vector of futures coming from the tasks run in the
77 std::vector
<gdb::future
<T
>> m_futures
;
80 /* See the generic template. */
82 struct par_for_accumulator
<void>
86 explicit par_for_accumulator (size_t n_threads
)
87 : m_futures (n_threads
)
91 /* This specialization does not compute results. */
92 typedef void result_type
;
94 void post (size_t i
, std::function
<void ()> task
)
97 = gdb::thread_pool::g_thread_pool
->post_task (std::move (task
));
100 result_type
finish (gdb::function_view
<void ()> task
)
104 for (auto &future
: m_futures
)
106 /* Use 'get' and not 'wait', to propagate any exception. */
113 std::vector
<gdb::future
<void>> m_futures
;
118 /* A very simple "parallel for". This splits the range of iterators
119 into subranges, and then passes each subrange to the callback. The
120 work may or may not be done in separate threads.
122 This approach was chosen over having the callback work on single
123 items because it makes it simple for the caller to do
124 once-per-subrange initialization and destruction.
126 The parameter N says how batching ought to be done -- there will be
127 at least N elements processed per thread. Setting N to 0 is not
130 If the function returns a non-void type, then a vector of the
131 results is returned. The size of the resulting vector depends on
132 the number of threads that were used. */
134 template<class RandomIt
, class RangeFunction
>
135 typename
gdb::detail::par_for_accumulator
<
136 typename
gdb::invoke_result
<RangeFunction
, RandomIt
, RandomIt
>::type
138 parallel_for_each (unsigned n
, RandomIt first
, RandomIt last
,
139 RangeFunction callback
,
140 gdb::function_view
<size_t(RandomIt
)> task_size
= nullptr)
143 = typename
gdb::invoke_result
<RangeFunction
, RandomIt
, RandomIt
>::type
;
145 /* If enabled, print debug info about how the work is distributed across
147 const bool parallel_for_each_debug
= false;
149 size_t n_worker_threads
= thread_pool::g_thread_pool
->thread_count ();
150 size_t n_threads
= n_worker_threads
;
151 size_t n_elements
= last
- first
;
152 size_t elts_per_thread
= 0;
153 size_t elts_left_over
= 0;
154 size_t total_size
= 0;
155 size_t size_per_thread
= 0;
156 size_t max_element_size
= n_elements
== 0 ? 1 : SIZE_MAX
/ n_elements
;
160 if (task_size
!= nullptr)
163 for (RandomIt i
= first
; i
!= last
; ++i
)
165 size_t element_size
= task_size (i
);
166 gdb_assert (element_size
> 0);
167 if (element_size
> max_element_size
)
168 /* We could start scaling here, but that doesn't seem to be
170 element_size
= max_element_size
;
171 size_t prev_total_size
= total_size
;
172 total_size
+= element_size
;
173 /* Check for overflow. */
174 gdb_assert (prev_total_size
< total_size
);
176 size_per_thread
= total_size
/ n_threads
;
180 /* Require that there should be at least N elements in a
183 if (n_elements
/ n_threads
< n
)
184 n_threads
= std::max (n_elements
/ n
, (size_t) 1);
185 elts_per_thread
= n_elements
/ n_threads
;
186 elts_left_over
= n_elements
% n_threads
;
187 /* n_elements == n_threads * elts_per_thread + elts_left_over. */
191 size_t count
= n_threads
== 0 ? 0 : n_threads
- 1;
192 gdb::detail::par_for_accumulator
<result_type
> results (count
);
194 if (parallel_for_each_debug
)
196 debug_printf (_("Parallel for: n_elements: %zu\n"), n_elements
);
197 if (task_size
!= nullptr)
199 debug_printf (_("Parallel for: total_size: %zu\n"), total_size
);
200 debug_printf (_("Parallel for: size_per_thread: %zu\n"), size_per_thread
);
204 debug_printf (_("Parallel for: minimum elements per thread: %u\n"), n
);
205 debug_printf (_("Parallel for: elts_per_thread: %zu\n"), elts_per_thread
);
209 size_t remaining_size
= total_size
;
210 for (int i
= 0; i
< count
; ++i
)
213 size_t chunk_size
= 0;
214 if (task_size
== nullptr)
216 end
= first
+ elts_per_thread
;
217 if (i
< elts_left_over
)
218 /* Distribute the leftovers over the worker threads, to avoid having
219 to handle all of them in a single thread. */
225 for (j
= first
; j
< last
&& chunk_size
< size_per_thread
; ++j
)
227 size_t element_size
= task_size (j
);
228 if (element_size
> max_element_size
)
229 element_size
= max_element_size
;
230 chunk_size
+= element_size
;
233 remaining_size
-= chunk_size
;
235 if (parallel_for_each_debug
)
237 debug_printf (_("Parallel for: elements on worker thread %i\t: %zu"),
238 i
, (size_t)(end
- first
));
239 if (task_size
!= nullptr)
240 debug_printf (_("\t(size: %zu)"), chunk_size
);
241 debug_printf (_("\n"));
243 results
.post (i
, [=] ()
245 return callback (first
, end
);
250 for (int i
= count
; i
< n_worker_threads
; ++i
)
251 if (parallel_for_each_debug
)
253 debug_printf (_("Parallel for: elements on worker thread %i\t: 0"), i
);
254 if (task_size
!= nullptr)
255 debug_printf (_("\t(size: 0)"));
256 debug_printf (_("\n"));
259 /* Process all the remaining elements in the main thread. */
260 if (parallel_for_each_debug
)
262 debug_printf (_("Parallel for: elements on main thread\t\t: %zu"),
263 (size_t)(last
- first
));
264 if (task_size
!= nullptr)
265 debug_printf (_("\t(size: %zu)"), remaining_size
);
266 debug_printf (_("\n"));
268 return results
.finish ([=] ()
270 return callback (first
, last
);
274 /* A sequential drop-in replacement of parallel_for_each. This can be useful
275 when debugging multi-threading behaviour, and you want to limit
276 multi-threading in a fine-grained way. */
278 template<class RandomIt
, class RangeFunction
>
279 typename
gdb::detail::par_for_accumulator
<
280 typename
gdb::invoke_result
<RangeFunction
, RandomIt
, RandomIt
>::type
282 sequential_for_each (unsigned n
, RandomIt first
, RandomIt last
,
283 RangeFunction callback
,
284 gdb::function_view
<size_t(RandomIt
)> task_size
= nullptr)
286 using result_type
= typename
gdb::invoke_result
<RangeFunction
, RandomIt
, RandomIt
>::type
;
288 gdb::detail::par_for_accumulator
<result_type
> results (0);
290 /* Process all the remaining elements in the main thread. */
291 return results
.finish ([=] ()
293 return callback (first
, last
);
299 #endif /* GDBSUPPORT_PARALLEL_FOR_H */