Blender V5.3
task_range.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
10
11#include <cstdlib>
12
13#include "MEM_guardedalloc.h"
14
15#include "BLI_array.hh"
16#include "BLI_lazy_threading.hh"
17#include "BLI_offset_indices.hh"
18#include "BLI_task.hh"
19#include "BLI_task_c.hh"
20#include "BLI_threads.hh"
21#include "BLI_vector.hh"
22
23#include "atomic_ops.h"
24
25#ifdef WITH_TBB
26# include <tbb/blocked_range.h>
27# include <tbb/enumerable_thread_specific.h>
28# include <tbb/parallel_for.h>
29# include <tbb/parallel_reduce.h>
30#endif
31
32namespace blender {
33
34#ifdef WITH_TBB
35
36/* Functor for running TBB parallel_for and parallel_reduce. */
37struct RangeTask {
39 void *userdata;
40 const TaskParallelSettings *settings;
41
42 void *userdata_chunk;
43
44 /* Root constructor. */
45 RangeTask(TaskParallelRangeFunc func, void *userdata, const TaskParallelSettings *settings)
46 : func(func), userdata(userdata), settings(settings)
47 {
48 init_chunk(settings->userdata_chunk);
49 }
50
51 /* Copy constructor. */
52 RangeTask(const RangeTask &other)
53 : func(other.func), userdata(other.userdata), settings(other.settings)
54 {
55 init_chunk(settings->userdata_chunk);
56 }
57
58 /* Splitting constructor for parallel reduce. */
59 RangeTask(RangeTask &other, tbb::split /*unused*/)
60 : func(other.func), userdata(other.userdata), settings(other.settings)
61 {
62 init_chunk(settings->userdata_chunk);
63 }
64
65 ~RangeTask()
66 {
67 if (settings->func_free != nullptr && userdata_chunk != nullptr) {
68 settings->func_free(userdata, userdata_chunk);
69 }
70 MEM_SAFE_DELETE_VOID(userdata_chunk);
71 }
72
73 void init_chunk(void *from_chunk)
74 {
75 if (from_chunk) {
76 userdata_chunk = MEM_new_uninitialized(settings->userdata_chunk_size, "RangeTask");
77 memcpy(userdata_chunk, from_chunk, settings->userdata_chunk_size);
78 }
79 else {
80 userdata_chunk = nullptr;
81 }
82 }
83
84 void operator()(const tbb::blocked_range<int> &r) const
85 {
86 TaskParallelTLS tls;
87 tls.userdata_chunk = userdata_chunk;
88 for (int i = r.begin(); i != r.end(); ++i) {
89 func(userdata, i, &tls);
90 }
91 }
92
93 void join(const RangeTask &other)
94 {
95 settings->func_reduce(userdata, userdata_chunk, other.userdata_chunk);
96 }
97};
98
99#endif
100
101void BLI_task_parallel_range(const int start,
102 const int stop,
103 void *userdata,
105 const TaskParallelSettings *settings)
106{
107#ifdef WITH_TBB
108 /* Multithreading. */
109 if (settings->use_threading && BLI_task_scheduler_num_threads() > 1) {
110 RangeTask task(func, userdata, settings);
111 const size_t grainsize = std::max(settings->min_iter_per_thread, 1);
112 const tbb::blocked_range<int> range(start, stop, grainsize);
113
115
116 if (settings->func_reduce) {
117 parallel_reduce(range, task);
118 if (settings->userdata_chunk) {
119 memcpy(settings->userdata_chunk, task.userdata_chunk, settings->userdata_chunk_size);
120 }
121 }
122 else {
123 parallel_for(range, task);
124 }
125 return;
126 }
127#endif
128
129 /* Single threaded. Nothing to reduce as everything is accumulated into the
130 * main userdata chunk directly. */
131 TaskParallelTLS tls;
132 tls.userdata_chunk = settings->userdata_chunk;
133 for (int i = start; i < stop; i++) {
134 func(userdata, i, &tls);
135 }
136 if (settings->func_free != nullptr && settings->userdata_chunk != nullptr) {
137 settings->func_free(userdata, settings->userdata_chunk);
138 }
139}
140
142{
143#ifdef WITH_TBB
144 /* Get a unique thread ID for texture nodes. In the future we should get rid
145 * of the thread ID and change texture evaluation to not require per-thread
146 * storage that can't be efficiently allocated on the stack. */
147 static tbb::enumerable_thread_specific<int> tbb_thread_id(-1);
148 static int tbb_thread_id_counter = 0;
149
150 int &thread_id = tbb_thread_id.local();
151 if (thread_id == -1) {
152 thread_id = atomic_fetch_and_add_int32(&tbb_thread_id_counter, 1);
153 if (thread_id >= BLENDER_MAX_THREADS) {
154 BLI_assert_msg(0, "Maximum number of threads exceeded for sculpting");
155 thread_id = thread_id % BLENDER_MAX_THREADS;
156 }
157 }
158 return thread_id;
159#else
160 return 0;
161#endif
162}
163
164namespace threading::detail {
165
166#ifdef WITH_TBB
167static void parallel_for_impl_static_size(const IndexRange range,
168 const int64_t grain_size,
169 const FunctionRef<void(IndexRange)> function)
170{
171 tbb::parallel_for(tbb::blocked_range<int64_t>(range.first(), range.one_after_last(), grain_size),
172 [function](const tbb::blocked_range<int64_t> &subrange) {
173 function(IndexRange(subrange.begin(), subrange.size()));
174 });
175}
176#endif /* WITH_TBB */
177
178#ifdef WITH_TBB
179static void parallel_for_impl_individual_size_lookup(
180 const IndexRange range,
181 const int64_t grain_size,
182 const FunctionRef<void(IndexRange)> function,
183 const TaskSizeHints_IndividualLookup &size_hints)
184{
185 /* Shouldn't be too small, because then there is more overhead when the individual tasks are
186 * small. Also shouldn't be too large because then the serial code to split up tasks causes extra
187 * overhead. */
188 const int64_t outer_grain_size = std::min<int64_t>(grain_size, 512);
189 threading::parallel_for(range, outer_grain_size, [&](const IndexRange sub_range) {
190 /* Compute the size of every task in the current range. */
191 Array<int64_t, 1024> task_sizes(sub_range.size());
192 size_hints.lookup_individual_sizes(sub_range, task_sizes);
193
194 /* Split range into multiple segments that have a size that approximates the grain size. */
195 Vector<int64_t, 256> offsets_vec;
196 offsets_vec.append(0);
197 int64_t counter = 0;
198 for (const int64_t i : sub_range.index_range()) {
199 counter += task_sizes[i];
200 if (counter >= grain_size) {
201 offsets_vec.append(i + 1);
202 counter = 0;
203 }
204 }
205 if (offsets_vec.last() < sub_range.size()) {
206 offsets_vec.append(sub_range.size());
207 }
208 const OffsetIndices<int64_t> offsets = offsets_vec.as_span();
209
210 /* Run the dynamically split tasks in parallel. */
211 threading::parallel_for(offsets.index_range(), 1, [&](const IndexRange offsets_range) {
212 for (const int64_t i : offsets_range) {
213 const IndexRange actual_range = offsets[i].shift(sub_range.start());
214 function(actual_range);
215 }
216 });
217 });
218}
219
220#endif /* WITH_TBB */
221
223 const IndexRange range,
224 const int64_t grain_size,
225 const FunctionRef<void(IndexRange)> function,
226 const TaskSizeHints_AccumulatedLookup &size_hints)
227{
228 BLI_assert(!range.is_empty());
229 if (range.size() == 1) {
230 /* Can't subdivide further. */
231 function(range);
232 return;
233 }
234 const int64_t total_size = size_hints.lookup_accumulated_size(range);
235 if (total_size <= grain_size) {
236 function(range);
237 return;
238 }
239 const int64_t middle = range.size() / 2;
240 const IndexRange left_range = range.take_front(middle);
241 const IndexRange right_range = range.drop_front(middle);
243 [&]() {
244 parallel_for_impl_accumulated_size_lookup(left_range, grain_size, function, size_hints);
245 },
246 [&]() {
247 parallel_for_impl_accumulated_size_lookup(right_range, grain_size, function, size_hints);
248 });
249}
250
252 const int64_t grain_size,
253 const FunctionRef<void(IndexRange)> function,
254 const TaskSizeHints &size_hints)
255{
256#ifdef WITH_TBB
258 switch (size_hints.type) {
260 const int64_t task_size = static_cast<const detail::TaskSizeHints_Static &>(size_hints).size;
261 const int64_t final_grain_size = task_size == 1 ?
262 grain_size :
263 std::max<int64_t>(1, grain_size / task_size);
264 parallel_for_impl_static_size(range, final_grain_size, function);
265 break;
266 }
268 parallel_for_impl_individual_size_lookup(
269 range,
270 grain_size,
271 function,
272 static_cast<const detail::TaskSizeHints_IndividualLookup &>(size_hints));
273 break;
274 }
277 range,
278 grain_size,
279 function,
280 static_cast<const detail::TaskSizeHints_AccumulatedLookup &>(size_hints));
281 break;
282 }
283 }
284
285#else
286 UNUSED_VARS(grain_size, size_hints);
287 function(range);
288#endif
289}
290
292{
293#ifdef WITH_TBB
294 /* This is the maximum number of threads that may perform these memory bandwidth bound tasks at
295 * the same time. Often fewer threads are already enough to use up the full bandwidth capacity.
296 * Additional threads usually have a negligible benefit and can even make performance worse.
297 *
298 * It's better to use fewer threads here so that the CPU cores can do other tasks at the same
299 * time which may be more compute intensive. */
300 const int num_threads = 8;
301 if (num_threads >= BLI_task_scheduler_num_threads()) {
302 /* Avoid overhead of using a task arena when it would not have any effect anyway. */
303 function();
304 return;
305 }
306 static tbb::task_arena arena{num_threads};
307
308 /* Make sure the lazy threading hints are send now, because they shouldn't be send out of an
309 * isolated region. */
312
313 arena.execute(function);
314#else
315 function();
316#endif
317}
318
319void max_threads_task_impl(const int max_threads, const FunctionRef<void()> function)
320{
321 BLI_assert(max_threads >= 1);
322
323#ifdef WITH_TBB
324 if (max_threads >= BLI_task_scheduler_num_threads()) {
325 function();
326 return;
327 }
328
329 tbb::task_arena arena{max_threads};
332
333 arena.execute(function);
334#else
335 UNUSED_VARS(max_threads);
336 function();
337#endif
338}
339
340} // namespace threading::detail
341} // namespace blender
#define BLENDER_MAX_THREADS
Read Blender memory allocation and freeing.
Provides wrapper around system-specific atomic primitives, and some extensions (faked-atomic operatio...
ATOMIC_INLINE int32_t atomic_fetch_and_add_int32(int32_t *p, int32_t x)
#define UNUSED_VARS(...)
#define BLI_assert_msg(a, msg)
long long int int64_t
SIMD_FORCE_INLINE btVector3 operator()(const btVector3 &x) const
Return the transform of the vector.
Definition btTransform.h:90
constexpr int64_t size() const
constexpr bool is_empty() const
constexpr IndexRange take_front(int64_t n) const
constexpr IndexRange drop_front(int64_t n) const
virtual int64_t lookup_accumulated_size(IndexRange range) const =0
void * MEM_new_uninitialized(size_t len, const char *str)
Definition mallocn.cc:124
void parallel_for_impl(IndexRange range, int64_t grain_size, FunctionRef< void(IndexRange)> function, const TaskSizeHints &size_hints)
void max_threads_task_impl(int max_threads, FunctionRef< void()> function)
void memory_bandwidth_bound_task_impl(FunctionRef< void()> function)
static void parallel_for_impl_accumulated_size_lookup(const IndexRange range, const int64_t grain_size, const FunctionRef< void(IndexRange)> function, const TaskSizeHints_AccumulatedLookup &size_hints)
void parallel_invoke(Functions &&...functions)
Definition BLI_task.hh:197
void parallel_for(const IndexRange range, const int64_t grain_size, const Function &function, const TaskSizeHints &size_hints=detail::TaskSizeHints_Static(1))
Definition BLI_task.hh:69
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void(*) TaskParallelRangeFunc(void *__restrict userdata, int iter, const TaskParallelTLS *__restrict tls)
__int64 int64_t
Definition BKE_text.h:90
int BLI_task_scheduler_num_threads()
void BLI_task_parallel_range(int start, int stop, void *userdata, TaskParallelRangeFunc func, const TaskParallelSettings *settings)
int BLI_task_parallel_thread_id(const TaskParallelTLS *tls)
TaskParallelReduceFunc func_reduce
TaskParallelFreeFunc func_free