Blender V5.3
array_utils.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
8
9#include <algorithm>
10#include <atomic>
11#include <cmath>
12#include <functional>
13
14#include "BLI_array.hh"
15#include "BLI_array_utils.hh"
16#include "BLI_bounds.hh"
18#include "BLI_threads.hh"
19#include "BLI_vector_set.hh"
20
21#include "PRF_profile.hh"
22
23#include "atomic_ops.h"
24
25namespace blender::array_utils {
26
27void copy(const GVArray &src, GMutableSpan dst, const exec_mode::Mode mode)
28{
30 BLI_assert(src.type() == dst.type());
31 BLI_assert(src.size() == dst.size());
32 if (!mode.is_parallel) {
33 src.materialize(src.index_range(), dst.data());
34 }
35 else {
36 const int64_t grain_size = calc_copy_grain_size(mode, src.type().size);
37 threading::parallel_for(src.index_range(), grain_size, [&](const IndexRange range) {
38 src.materialize(range, dst.data());
39 });
40 }
41}
42
43void copy(const GVArray &src,
44 const IndexMask &selection,
45 GMutableSpan dst,
46 const exec_mode::Mode mode)
47{
49 BLI_assert(src.type() == dst.type());
50 BLI_assert(src.size() >= selection.min_array_size());
51 BLI_assert(dst.size() >= selection.min_array_size());
52 if (!mode.is_parallel) {
53 src.materialize(selection, dst.data());
54 }
55 else {
56 const int64_t grain_size = calc_copy_grain_size(mode, src.type().size);
57 threading::parallel_for(selection.index_range(), grain_size, [&](const IndexRange range) {
58 src.materialize(selection.slice(range), dst.data());
59 });
60 }
61}
62
63void gather(const GVArray &src,
64 const IndexMask &indices,
65 GMutableSpan dst,
66 const exec_mode::Mode mode)
67{
68 PRF_scope_with_name("array_utils::gather", ProfileCategory::Default);
69 BLI_assert(src.type() == dst.type());
70 BLI_assert(indices.size() == dst.size());
71 if (!mode.is_parallel) {
72 src.materialize_compressed(indices, dst.data());
73 }
74 else {
75 const int64_t grain_size = calc_copy_grain_size(mode, src.type().size);
76 threading::parallel_for(indices.index_range(), grain_size, [&](const IndexRange range) {
77 src.materialize_compressed(indices.slice(range), dst.slice(range).data());
78 });
79 }
80}
81
82void gather(const GSpan src,
83 const IndexMask &indices,
84 GMutableSpan dst,
85 const exec_mode::Mode mode)
86{
87 gather(GVArray::from_span(src), indices, dst, mode);
88}
89
91 const OffsetIndices<int> dst_offsets,
92 const IndexMask &selection,
93 const GSpan src,
94 GMutableSpan dst)
95{
96 /* Each group might be large, so a threaded copy might make sense here too. */
97 selection.foreach_index(
98 [&](const int i) { dst.slice(dst_offsets[i]).copy_from(src.slice(src_offsets[i])); },
100}
101
102static void count_indices_serial(const Span<int> indices, MutableSpan<int> counts)
103{
104 for (const int i : indices) {
105 counts[i]++;
106 }
107}
108
109static void count_indices_atomics(const Span<int> indices, MutableSpan<int> counts)
110{
111 threading::parallel_for(indices.index_range(), 4096, [&](const IndexRange range) {
112 for (const int i : indices.slice(range)) {
113 atomic_add_and_fetch_int32(&counts[i], 1);
114 }
115 });
116}
117
118static void count_indices_thread_local(const Span<int> indices,
119 MutableSpan<int> counts,
120 const int64_t max_threads)
121{
122 /* Count into thread local buffers, parallelized with chunks of indices. The
123 * number of threads is limited to avoid using more memory and memory bandwidth
124 * than helpful. */
125 const int64_t groups_num = counts.size();
127 [&]() { return Array<int>(groups_num, 0); });
128 threading::max_threads_task(max_threads, [&]() {
129 threading::parallel_for(indices.index_range(), 4096, [&](const IndexRange range) {
130 Array<int> &local_counts = counts_by_thread.local();
131 for (const int i : indices.slice(range)) {
132 local_counts[i]++;
133 }
134 });
135 });
136
137 /* Sum counts for all threads. */
138 threading::parallel_for(IndexRange(groups_num), 4096, [&](const IndexRange range) {
139 for (const Array<int> &local_counts : counts_by_thread) {
140 for (const int64_t i : range) {
141 counts[i] += local_counts[i];
142 }
143 }
144 });
145}
146
147void count_indices(const Span<int> indices, MutableSpan<int> counts)
148{
149 PRF_scope_with_name("array_utils::count_indices", ProfileCategory::Default);
150
151 const int64_t indices_num = indices.size();
152 const int64_t groups_num = std::max<int64_t>(counts.size(), 1);
153
154 /* Thread local is fastest when the number of groups is small enough that the
155 * counters can stay in the per core caches. */
156 constexpr int64_t max_thread_local_groups = 1 << 18;
157 if (groups_num <= max_thread_local_groups) {
158 /* More threads add memory overhead, limit by groups per index so it's worth
159 * using dedicated memory for every thread. */
160 constexpr int64_t min_groups_per_index = 10;
161 const int64_t max_threads = std::clamp<int64_t>(
162 std::sqrt(min_groups_per_index * indices_num / groups_num), 1, BLI_system_thread_count());
163
164 /* Heuristic for when there are enough indices for thread local to work.
165 * Fixed minimum, enough indices per thread and not too much group overhead. */
166 constexpr int64_t min_parallel_indices = 1 << 16;
167 const int64_t min_thread_local_indices = min_parallel_indices + indices_num / max_threads +
168 max_threads * groups_num / min_groups_per_index;
169
170 if (indices_num < min_thread_local_indices) {
171 count_indices_serial(indices, counts);
172 }
173 else {
174 count_indices_thread_local(indices, counts, max_threads);
175 }
176 }
177 else {
178 /* Atomics are faster than serial when there are enough indices to justify the overhead
179 * and we hopefully don't get too much contention. */
180 constexpr int64_t min_atomic_indices = 1 << 19;
181 if (indices_num < min_atomic_indices) {
182 count_indices_serial(indices, counts);
183 }
184 else {
185 count_indices_atomics(indices, counts);
186 }
187 }
188}
189
196 const IndexMask &mask,
197 const Bounds<int> &id_bounds,
198 MutableSpan<int> r_group_indices,
199 Vector<int> *r_first_indices)
200{
201 const int64_t id_min = id_bounds.min;
202 const int64_t ids_range = int64_t(id_bounds.max) - int64_t(id_bounds.min) + 1;
203
204 /* Find the first element with each ID. */
205 Array<int, 64> first_elem(ids_range, std::numeric_limits<int>::max());
206 mask.foreach_index_optimized<int>(
207 [&](const int i) {
208 std::atomic_ref<int> first(first_elem[ids[i] - id_min]);
209 int prev = first.load(std::memory_order_relaxed);
210 while (i < prev && !first.compare_exchange_weak(prev, i, std::memory_order_relaxed)) {
211 }
212 },
214
215 /* Number the groups in the order of their first elements, replacing the first element index in
216 * the table with the group index. */
217 IndexMaskMemory memory;
218 const IndexMask first_indices = IndexMask::from_predicate(
219 mask, memory, [&](const int i) { return first_elem[ids[i] - id_min] == i; });
220 first_indices.foreach_index_optimized<int>(
221 [&](const int i, const int group) { first_elem[ids[i] - id_min] = group; },
223
224 /* Look up the group index of every element's ID. */
225 mask.foreach_index_optimized<int>(
226 [&](const int i, const int pos) { r_group_indices[pos] = first_elem[ids[i] - id_min]; },
228
229 if (r_first_indices) {
230 r_first_indices->resize(first_indices.size());
231 first_indices.to_indices(r_first_indices->as_mutable_span());
232 }
233 return first_indices.size();
234}
235
237 const IndexMask &mask,
238 MutableSpan<int> r_group_indices,
239 Vector<int> *r_first_indices)
240{
242 BLI_assert(r_group_indices.size() == mask.size());
243 const std::optional<Bounds<int>> id_bounds = bounds::min_max(mask, ids);
244 if (!id_bounds) {
245 return 0;
246 }
247
248 const int64_t ids_range = int64_t(id_bounds->max) - int64_t(id_bounds->min) + 1;
249 if (ids_range < mask.size() * 4) {
250 return count_indices_with_table(ids, mask, *id_bounds, r_group_indices, r_first_indices);
251 }
252
253 using IdSet = VectorSet<int,
254 4,
259 IdSet unique_ids;
260 mask.foreach_index_optimized<int>([&](const int i, const int pos) {
261 const int group = unique_ids.index_of_or_add(ids[i]);
262 if (r_first_indices && group == r_first_indices->size()) {
263 r_first_indices->append(i);
264 }
265 r_group_indices[pos] = group;
266 });
267 return unique_ids.size();
268}
269
271{
272 PRF_scope_with_name("array_utils::invert_booleans", ProfileCategory::Default);
273 threading::parallel_for(span.index_range(), 4096, [&](IndexRange range) {
274 for (const int i : range) {
275 span[i] = !span[i];
276 }
277 });
278}
279
281{
282 PRF_scope_with_name("array_utils::invert_booleans", ProfileCategory::Default);
283 mask.foreach_index_optimized<int64_t>([&](const int64_t i) { span[i] = !span[i]; });
284}
285
286static bool all_equal(const Span<bool> span, const bool test)
287{
288 return std::all_of(span.begin(), span.end(), [&](const bool value) { return value == test; });
289}
290
291static bool all_equal(const VArray<bool> &varray, const IndexRange range, const bool test)
292{
293 return std::all_of(
294 range.begin(), range.end(), [&](const int64_t i) { return varray[i] == test; });
295}
296
297BooleanMix booleans_mix_calc(const VArray<bool> &varray, const IndexRange range_to_check)
298{
299 if (varray.is_empty()) {
300 return BooleanMix::None;
301 }
302 PRF_scope_with_name("array_utils::booleans_mix_calc", ProfileCategory::Default);
303 const CommonVArrayInfo info = varray.common_info();
305 return *static_cast<const bool *>(info.data) ? BooleanMix::AllTrue : BooleanMix::AllFalse;
306 }
308 const Span<bool> span(static_cast<const bool *>(info.data), varray.size());
310 range_to_check,
311 4096,
313 [&](const IndexRange range, const BooleanMix init) {
314 if (init == BooleanMix::Mixed) {
315 return init;
316 }
317 const Span<bool> slice = span.slice(range);
318 const bool compare = (init == BooleanMix::None) ? slice.first() :
320 if (all_equal(slice, compare)) {
321 return compare ? BooleanMix::AllTrue : BooleanMix::AllFalse;
322 }
323 return BooleanMix::Mixed;
324 },
325 [&](BooleanMix a, BooleanMix b) { return (a == b) ? a : BooleanMix::Mixed; });
326 }
328 range_to_check,
329 2048,
331 [&](const IndexRange range, const BooleanMix init) {
332 if (init == BooleanMix::Mixed) {
333 return init;
334 }
335 /* Alternatively, this could use #materialize to retrieve many values at once. */
336 const bool compare = (init == BooleanMix::None) ? varray[range.first()] :
338 if (all_equal(varray, range, compare)) {
339 return compare ? BooleanMix::AllTrue : BooleanMix::AllFalse;
340 }
341 return BooleanMix::Mixed;
342 },
343 [&](BooleanMix a, BooleanMix b) { return (a == b) ? a : BooleanMix::Mixed; });
344}
345
347{
348 if (varray.is_empty() || mask.is_empty()) {
349 return 0;
350 }
351 PRF_scope_with_name("array_utils::count_booleans", ProfileCategory::Default);
352 /* Check if mask is full. */
353 if (varray.size() == mask.size()) {
354 const CommonVArrayInfo info = varray.common_info();
356 return *static_cast<const bool *>(info.data) ? varray.size() : 0;
357 }
359 const Span<bool> span(static_cast<const bool *>(info.data), varray.size());
361 varray.index_range(),
362 4096,
363 0,
364 [&](const IndexRange range, const int64_t init) {
365 const Span<bool> slice = span.slice(range);
366 return init + std::count(slice.begin(), slice.end(), true);
367 },
368 std::plus<>());
369 }
371 varray.index_range(),
372 2048,
373 0,
374 [&](const IndexRange range, const int64_t init) {
375 int64_t value = init;
376 /* Alternatively, this could use #materialize to retrieve many values at once. */
377 for (const int64_t i : range) {
378 value += int64_t(varray[i]);
379 }
380 return value;
381 },
382 std::plus<>());
383 }
384 const CommonVArrayInfo info = varray.common_info();
386 return *static_cast<const bool *>(info.data) ? mask.size() : 0;
387 }
388 int64_t value = 0;
389 mask.foreach_segment([&](const IndexMaskSegment segment) {
390 for (const int64_t i : segment) {
391 value += int64_t(varray[i]);
392 }
393 });
394 return value;
395}
396
397bool contains(const VArray<bool> &varray, const IndexMask &indices_to_check, const bool value)
398{
399 PRF_scope_with_name("array_utils::contains", ProfileCategory::Default);
400 const CommonVArrayInfo info = varray.common_info();
402 return *static_cast<const bool *>(info.data) == value;
403 }
405 const Span<bool> span(static_cast<const bool *>(info.data), varray.size());
407 indices_to_check.index_range(),
408 4096,
409 false,
410 [&](const IndexRange range, const bool init) {
411 if (init) {
412 return init;
413 }
414 const IndexMask sliced_mask = indices_to_check.slice(range);
415 if (std::optional<IndexRange> range = sliced_mask.to_range()) {
416 return span.slice(*range).contains(value);
417 }
418 for (const int64_t segment_i : IndexRange(sliced_mask.segments_num())) {
419 const IndexMaskSegment segment = sliced_mask.segment(segment_i);
420 for (const int i : segment) {
421 if (span[i] == value) {
422 return true;
423 }
424 }
425 }
426 return false;
427 },
428 std::logical_or());
429 }
430 return threading::parallel_reduce(
431 indices_to_check.index_range(),
432 2048,
433 false,
434 [&](const IndexRange range, const bool init) {
435 if (init) {
436 return init;
437 }
438 constexpr int64_t MaxChunkSize = 512;
439 const int64_t slice_end = range.one_after_last();
440 for (int64_t start = range.start(); start < slice_end; start += MaxChunkSize) {
441 const int64_t end = std::min<int64_t>(start + MaxChunkSize, slice_end);
442 const int64_t size = end - start;
443 const IndexMask sliced_mask = indices_to_check.slice(start, size);
444 std::array<bool, MaxChunkSize> values;
445 std::array<bool, MaxChunkSize>::iterator values_end = values.begin() + size;
446 varray.materialize_compressed(sliced_mask, values);
447 if (std::find(values.begin(), values_end, value) != values_end) {
448 return true;
449 }
450 }
451 return false;
452 },
453 std::logical_or());
454}
455
457 const Span<int> values,
458 LinearAllocator<> &memory)
459{
460 PRF_scope_with_name("array_utils::indices_non_negative", ProfileCategory::Default);
462 universe, memory, [&](const int i) { return values[i] >= 0; }, exec_mode::grain_size(4096));
463}
464
466 const Span<int> values,
467 const IndexRange range,
468 LinearAllocator<> &memory)
469{
470 PRF_scope_with_name("array_utils::indices_in_range", ProfileCategory::Default);
472 universe,
473 memory,
474 [&](const int i) { return range.contains(values[i]); },
476}
477
479{
480 return count_booleans(varray, IndexMask(varray.size()));
481}
482
484{
485 if (indices.size() != range.size()) {
486 return false;
487 }
488 PRF_scope_with_name("array_utils::indices_are_range", ProfileCategory::Default);
490 range.index_range(),
491 4096,
492 true,
493 [&](const IndexRange part, const bool is_range) {
494 const Span<int> local_indices = indices.slice(part);
495 const IndexRange local_range = range.slice(part);
496 return is_range &&
497 std::equal(local_indices.begin(), local_indices.end(), local_range.begin());
498 },
499 std::logical_and<>());
500}
501
502} // namespace blender::array_utils
#define PRF_scope_with_name(ui_name, category)
#define PRF_scope(category)
Provides wrapper around system-specific atomic primitives, and some extensions (faked-atomic operatio...
void init()
long long int int64_t
void copy_from(GSpan values)
GMutableSpan slice(const int64_t start, int64_t size) const
const CPPType & type() const
GSpan slice(const int64_t start, int64_t size) const
void materialize(void *dst) const
void materialize_compressed(const IndexMask &mask, void *dst) const
static GVArray from_span(GSpan span)
static IndexMask from_predicate(const IndexMask &universe, LinearAllocator<> &memory, Fn &&predicate, exec_mode::Mode mode=exec_mode::parallel)
constexpr int64_t first() const
constexpr Iterator end() const
constexpr int64_t size() const
constexpr Iterator begin() const
constexpr bool contains(int64_t value) const
constexpr IndexRange index_range() const
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr IndexRange index_range() const
Definition BLI_span.hh:676
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
constexpr const T & first() const
Definition BLI_span.hh:319
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr const T * end() const
Definition BLI_span.hh:228
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
constexpr const T * begin() const
Definition BLI_span.hh:224
IndexRange index_range() const
CommonVArrayInfo common_info() const
int64_t size() const
void append(const T &value)
void resize(const int64_t new_size)
MutableSpan< T > as_mutable_span()
void foreach_index_optimized(Fn &&fn, Mode mode=exec_mode::serial) const
IndexMask slice(IndexRange range) const
void to_indices(MutableSpan< T > r_indices) const
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
ccl_device_inline float2 mask(const MaskType mask, const float2 a)
IndexMask indices_in_range(const IndexMask &universe, Span< int > values, IndexRange range, LinearAllocator<> &memory)
void gather(const GVArray &src, const IndexMask &indices, GMutableSpan dst, exec_mode::Mode mode=exec_mode::parallel)
static void count_indices_atomics(const Span< int > indices, MutableSpan< int > counts)
void invert_booleans(MutableSpan< bool > span)
void count_indices(Span< int > indices, MutableSpan< int > counts)
IndexMask indices_non_negative(const IndexMask &universe, Span< int > values, LinearAllocator<> &memory)
bool indices_are_range(Span< int > indices, IndexRange range)
void copy_group_to_group(OffsetIndices< int > src_offsets, OffsetIndices< int > dst_offsets, const IndexMask &selection, GSpan src, GMutableSpan dst)
static void count_indices_thread_local(const Span< int > indices, MutableSpan< int > counts, const int64_t max_threads)
void copy(const GVArray &src, GMutableSpan dst, exec_mode::Mode mode=exec_mode::parallel)
BooleanMix booleans_mix_calc(const VArray< bool > &varray, IndexRange range_to_check)
bool contains(const VArray< bool > &varray, const IndexMask &indices_to_check, bool value)
constexpr int64_t calc_copy_grain_size(const exec_mode::Tag auto mode, const int64_t type_size)
static bool all_equal(const Span< bool > span, const bool test)
int group_ids_to_indices(Span< int > ids, const IndexMask &mask, MutableSpan< int > r_group_indices, Vector< int > *r_first_indices=nullptr)
static void count_indices_serial(const Span< int > indices, MutableSpan< int > counts)
static int count_indices_with_table(const Span< int > ids, const IndexMask &mask, const Bounds< int > &id_bounds, MutableSpan< int > r_group_indices, Vector< int > *r_first_indices)
int64_t count_booleans(const VArray< bool > &varray)
std::optional< Bounds< T > > min_max(const std::optional< Bounds< T > > &a, const T &b)
Definition BLI_bounds.hh:56
constexpr ParallelGrainSize grain_size(int grain_size)
void max_threads_task(const int max_threads, const Function &function)
Definition BLI_task.hh:239
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
Value parallel_reduce(IndexRange range, int64_t grain_size, const Value &identity, const Function &function, const Reduction &reduction)
Definition BLI_task.hh:127
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
__int64 int64_t
Definition BKE_text.h:90
int BLI_system_thread_count()
Definition threads.cc:258
PythonProbingStrategy<> DefaultProbingStrategy