Blender V5.3
BLI_array_utils.hh
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#pragma once
10
11#include <numeric>
12
13#include "BLI_execution_mode.hh"
14#include "BLI_generic_span.hh"
16#include "BLI_index_mask.hh"
17#include "BLI_math_base_c.hh"
18#include "BLI_offset_indices.hh"
19#include "BLI_task.hh"
20#include "BLI_virtual_array.hh"
21
22#include "PRF_profile.hh"
23
25
26constexpr int64_t calc_copy_grain_size(const exec_mode::Tag auto mode, const int64_t type_size)
27{
28 /* The grain size should roughly depend on the work being done per index, which roughly
29 * corresponds with the size of the type being copied. */
30 return mode.grain_size(std::max<int64_t>(1, 32768 / type_size));
31}
32
33constexpr int64_t calc_copy_grain_size(const exec_mode::Mode mode, const int64_t type_size)
34{
35 return mode.grain_size(std::max<int64_t>(1, 32768 / type_size));
36}
37
39template<exec_mode::Tag Mode>
40constexpr auto exec_mode_tag_for_copy(const Mode mode, const int64_t type_size)
41{
42 if constexpr (mode.is_parallel) {
43 return exec_mode::ParallelGrainSize{mode.grain_size(std::max<int64_t>(1, 32768 / type_size))};
44 }
45 else {
46 return Mode{mode};
47 }
48}
49
53void copy(const GVArray &src, GMutableSpan dst, exec_mode::Mode mode = exec_mode::parallel);
54template<typename T, exec_mode::Tag Mode = exec_mode::Parallel>
55inline void copy(const VArray<T> &src, MutableSpan<T> dst, const Mode mode = {})
56{
57 BLI_assert(src.size() == dst.size());
58 if constexpr (!mode.is_parallel) {
59 src.materialize_compressed(dst.index_range(), dst);
60 }
61 else {
62 const int64_t grain_size = calc_copy_grain_size(mode, sizeof(T));
63 threading::parallel_for(src.index_range(), grain_size, [&](const IndexRange range) {
64 src.materialize(range, dst);
65 });
66 }
67}
68
72template<typename T, exec_mode::Tag Mode = exec_mode::Parallel>
73inline void copy(const Span<T> src, MutableSpan<T> dst, const Mode mode = {})
74{
75 BLI_assert(src.size() == dst.size());
76 if constexpr (!mode.is_parallel) {
77 dst.copy_from(src);
78 }
79 else {
80 const int64_t grain_size = calc_copy_grain_size(mode, sizeof(T));
81 threading::parallel_for(src.index_range(), grain_size, [&](const IndexRange range) {
82 copy(src.slice(range), dst.slice(range), exec_mode::serial);
83 });
84 }
85}
86
90void copy(const GVArray &src,
91 const IndexMask &selection,
92 GMutableSpan dst,
93 exec_mode::Mode mode = exec_mode::parallel);
94
98template<typename T, exec_mode::Tag Mode = exec_mode::Parallel>
99inline void copy(const Span<T> src,
100 const IndexMask &selection,
101 MutableSpan<T> dst,
102 const Mode mode = {})
103{
104 BLI_assert(src.size() == dst.size());
105 selection.foreach_index_optimized<int64_t>([&](const int64_t i) { dst[i] = src[i]; },
106 exec_mode_tag_for_copy(mode, sizeof(T)));
107}
108
109template<typename T> T compute_sum(const Span<T> data)
110{
111 /* Explicitly splitting work into chunks for a couple of reasons:
112 * - Improve numerical stability. While there are even more stable algorithms (e.g. Kahan
113 * summation), they also add more complexity to the hot code path. So far, this simple approach
114 * seems to solve the common issues people run into.
115 * - Support computing the sum using multiple threads.
116 * - Ensure deterministic results even with floating point numbers.
117 */
118 constexpr int64_t chunk_size = 1024;
119 const int64_t chunks_num = divide_ceil_ul(data.size(), chunk_size);
120 Array<T> partial_sums(chunks_num);
121 threading::parallel_for(partial_sums.index_range(), 1, [&](const IndexRange range) {
122 for (const int64_t i : range) {
123 const int64_t start = i * chunk_size;
124 const Span<T> chunk = data.slice_safe(start, chunk_size);
125 const T partial_sum = std::accumulate(chunk.begin(), chunk.end(), T());
126 partial_sums[i] = partial_sum;
127 }
128 });
129 return std::accumulate(partial_sums.begin(), partial_sums.end(), T());
130}
131
135template<typename T, typename IndexT, exec_mode::Tag Mode = exec_mode::Parallel>
136inline void scatter(const Span<T> src,
137 const Span<IndexT> indices,
138 MutableSpan<T> dst,
139 const Mode mode = {})
140{
141 BLI_assert(indices.size() == src.size());
142 if constexpr (!mode.is_parallel) {
143 for (const int64_t i : indices.index_range()) {
144 dst[indices[i]] = src[i];
145 }
146 }
147 else {
148 const int64_t grain_size = calc_copy_grain_size(mode, sizeof(T));
149 threading::parallel_for(indices.index_range(), grain_size, [&](const IndexRange range) {
150 scatter(src.slice(range), indices.slice(range), dst, exec_mode::serial);
151 });
152 }
153}
154
155template<typename T, exec_mode::Tag Mode = exec_mode::Parallel>
156inline void scatter(const Span<T> src,
157 const IndexMask &indices,
158 MutableSpan<T> dst,
159 const Mode mode = {})
160{
161 BLI_assert(indices.size() == src.size());
162 BLI_assert(indices.min_array_size() <= dst.size());
164 [&](const int64_t index, const int64_t pos) { dst[index] = src[pos]; },
165 exec_mode_tag_for_copy(mode, sizeof(T)));
166}
167
171void gather(const GVArray &src,
172 const IndexMask &indices,
173 GMutableSpan dst,
174 exec_mode::Mode mode = exec_mode::parallel);
175
179void gather(GSpan src,
180 const IndexMask &indices,
181 GMutableSpan dst,
182 exec_mode::Mode mode = exec_mode::parallel);
183
187template<typename T, exec_mode::Tag Mode = exec_mode::Parallel>
188inline void gather(const VArray<T> &src,
189 const IndexMask &indices,
190 MutableSpan<T> dst,
191 const Mode mode = {})
192{
193 PRF_scope_with_name("array_utils::gather", ProfileCategory::Default);
194 BLI_assert(indices.size() >= dst.size());
195 if constexpr (!mode.is_parallel) {
196 src.materialize_compressed(indices, dst);
197 }
198 else {
199 const int64_t grain_size = calc_copy_grain_size(mode, sizeof(T));
200 threading::parallel_for(indices.index_range(), grain_size, [&](const IndexRange range) {
201 src.materialize_compressed(indices.slice(range), dst.slice(range));
202 });
203 }
204}
205
209template<typename T, typename IndexT, exec_mode::Tag Mode = exec_mode::Parallel>
210inline void gather(const Span<T> src,
211 const Span<IndexT> indices,
212 const IndexMask &dst_mask,
213 MutableSpan<T> dst,
214 const Mode mode = {})
215{
216 PRF_scope_with_name("array_utils::gather", ProfileCategory::Default);
217 BLI_assert(indices.size() >= dst.size());
218 dst_mask.foreach_index_optimized<int64_t>([&](const int64_t i) { dst[i] = src[indices[i]]; },
219 exec_mode_tag_for_copy(mode, sizeof(T)));
220}
221
225template<typename T, typename IndexT, exec_mode::Tag Mode = exec_mode::Parallel>
226inline void gather(const Span<T> src,
227 const Span<IndexT> indices,
228 MutableSpan<T> dst,
229 const Mode mode = {})
230{
231 gather(src, indices, IndexMask(dst.size()), dst, mode);
232}
233
237template<typename T, typename IndexT, exec_mode::Tag Mode = exec_mode::Parallel>
238inline void gather(const VArray<T> &src,
239 const Span<IndexT> indices,
240 const IndexMask &dst_mask,
241 MutableSpan<T> dst,
242 const Mode mode = {})
243{
244 PRF_scope_with_name("array_utils::gather", ProfileCategory::Default);
245 BLI_assert(indices.size() >= dst_mask.min_array_size());
246 const CommonVArrayInfo info = src.common_info();
247 switch (info.type) {
249 dst_mask.foreach_index_optimized<int64_t>([&](const int64_t i) { dst[i] = src[indices[i]]; },
250 exec_mode_tag_for_copy(mode, sizeof(T)));
251 break;
252 }
253 case CommonVArrayInfo::Type::Span: {
254 const Span span(static_cast<const T *>(info.data), src.size());
255 gather(span, indices, dst_mask, dst, mode);
256 break;
257 }
258 case CommonVArrayInfo::Type::Single: {
259 index_mask::masked_fill(dst, *static_cast<const T *>(info.data), dst_mask);
260 break;
261 }
262 }
263}
264
268template<typename T, typename IndexT, exec_mode::Tag Mode = exec_mode::Parallel>
269inline void gather(const VArray<T> &src,
270 const Span<IndexT> indices,
271 MutableSpan<T> dst,
272 const Mode mode = {})
273{
274 gather(src, indices, dst.index_range(), dst, mode);
275}
276
277template<typename T>
278inline void gather_group_to_group(const OffsetIndices<int> src_offsets,
279 const OffsetIndices<int> dst_offsets,
280 const IndexMask &selection,
281 const Span<T> src,
282 MutableSpan<T> dst)
283{
284 selection.foreach_index(
285 [&](const int64_t src_i, const int64_t dst_i) {
286 dst.slice(dst_offsets[dst_i]).copy_from(src.slice(src_offsets[src_i]));
287 },
289}
290
291template<typename T>
292inline void gather_group_to_group(const OffsetIndices<int> src_offsets,
293 const OffsetIndices<int> dst_offsets,
294 const Span<int> selection,
295 const Span<T> src,
296 MutableSpan<T> dst)
297{
298 threading::parallel_for(selection.index_range(), 512, [&](const IndexRange range) {
299 for (const int dst_i : range) {
300 dst.slice(dst_offsets[dst_i]).copy_from(src.slice(src_offsets[selection[dst_i]]));
301 }
302 });
303}
304
305template<typename T>
306inline void gather_group_to_group(const OffsetIndices<int> src_offsets,
307 const OffsetIndices<int> dst_offsets,
308 const IndexMask &selection,
309 const VArray<T> src,
310 MutableSpan<T> dst)
311{
312 selection.foreach_index(
313 [&](const int64_t src_i, const int64_t dst_i) {
314 src.materialize_compressed(src_offsets[src_i], dst.slice(dst_offsets[dst_i]));
315 },
317}
318
319template<typename T>
320inline void gather_to_groups(const OffsetIndices<int> dst_offsets,
321 const IndexMask &src_selection,
322 const Span<T> src,
323 MutableSpan<T> dst)
324{
325 src_selection.foreach_index(
326 [&](const int src_i, const int dst_i) { dst.slice(dst_offsets[dst_i]).fill(src[src_i]); },
328}
329
335void copy_group_to_group(OffsetIndices<int> src_offsets,
336 OffsetIndices<int> dst_offsets,
337 const IndexMask &selection,
338 GSpan src,
339 GMutableSpan dst);
340template<typename T>
342 OffsetIndices<int> dst_offsets,
343 const IndexMask &selection,
344 Span<T> src,
345 MutableSpan<T> dst)
346{
347 copy_group_to_group(src_offsets, dst_offsets, selection, GSpan(src), GMutableSpan(dst));
348}
349
358void count_indices(Span<int> indices, MutableSpan<int> counts);
359
369int group_ids_to_indices(Span<int> ids,
370 const IndexMask &mask,
371 MutableSpan<int> r_group_indices,
372 Vector<int> *r_first_indices = nullptr);
373
374void invert_booleans(MutableSpan<bool> span);
375void invert_booleans(MutableSpan<bool> span, const IndexMask &mask);
376
377int64_t count_booleans(const VArray<bool> &varray);
378int64_t count_booleans(const VArray<bool> &varray, const IndexMask &mask);
379
386BooleanMix booleans_mix_calc(const VArray<bool> &varray, IndexRange range_to_check);
388{
389 return booleans_mix_calc(varray, varray.index_range());
390}
391
393bool contains(const VArray<bool> &varray, const IndexMask &indices_to_check, bool value);
394
396IndexMask indices_non_negative(const IndexMask &universe,
397 Span<int> values,
398 LinearAllocator<> &memory);
400IndexMask indices_in_range(const IndexMask &universe,
401 Span<int> values,
402 IndexRange range,
403 LinearAllocator<> &memory);
404
408template<typename T> inline Vector<IndexRange> find_all_ranges(const Span<T> span, const T &value)
409{
410 if (span.is_empty()) {
411 return Vector<IndexRange>();
412 }
413 Vector<IndexRange> ranges;
414 int64_t length = (span.first() == value) ? 1 : 0;
415 for (const int64_t i : span.index_range().drop_front(1)) {
416 if (span[i - 1] == value && span[i] != value) {
418 length = 0;
419 }
420 else if (span[i] == value) {
421 length++;
422 }
423 }
424 if (length > 0) {
426 }
427 return ranges;
428}
429
434template<typename T> inline void fill_index_range(MutableSpan<T> span, const T start = 0)
435{
436 std::iota(span.begin(), span.end(), start);
437}
438
439template<typename T, exec_mode::Tag Mode = exec_mode::Parallel>
440inline void fill_index_range(const IndexMask &mask, MutableSpan<T> span, const Mode mode = {})
441{
442 mask.foreach_index_optimized<T>([&](const T index) { span[index] = index; }, mode);
443}
444
445template<typename T, exec_mode::Tag Mode = exec_mode::Parallel>
446inline void fill_index_range(const IndexMask &mask,
447 MutableSpan<T> span,
448 const T start,
449 const Mode mode = {})
450{
451 if (start == 0) {
452 fill_index_range(mask, span, mode);
453 }
454 else {
455 mask.foreach_index_optimized<T>([&](const T index) { span[index] = start + index; }, mode);
456 }
457}
458
459template<typename T>
460bool indexed_data_equal(const Span<T> all_values, const Span<int> indices, const Span<T> values)
461{
462 BLI_assert(indices.size() == values.size());
463 for (const int i : indices.index_range()) {
464 if (all_values[indices[i]] != values[i]) {
465 return false;
466 }
467 }
468 return true;
469}
470
471bool indices_are_range(Span<int> indices, IndexRange range);
472
477template<typename T>
478inline std::optional<int64_t> max_element_index(const Span<T> &span,
479 const int64_t grain_size = 8192)
480{
481 const T *max_it = threading::parallel_reduce(
482 span.index_range(),
483 grain_size,
484 span.begin(),
485 [&](const IndexRange range, const T *init_max) {
486 const Span<T> sub_span = span.slice(range);
487 const T *max_elem = std::max_element(sub_span.begin(), sub_span.end());
488 if (*max_elem < *init_max) {
489 return init_max;
490 }
491 return max_elem;
492 },
493 [&](const T *a, const T *b) {
494 if (*a < *b) {
495 return a;
496 }
497 return b;
498 });
499 return std::distance(span.begin(), max_it);
500}
501template<typename T>
502inline std::optional<int64_t> max_element_index(const VArray<T> &array,
503 const int64_t grain_size = 8192)
504{
505 if (!array || array.is_empty()) {
506 return std::nullopt;
507 }
508 if (array.is_single()) {
509 return array.first();
510 }
511 if (array.is_span()) {
512 return max_element_index(array.get_internal_span(), grain_size);
513 }
515 array.index_range(),
516 grain_size,
517 array.first(),
518 [&](const IndexRange range, const int64_t init_i) {
519 int64_t max_index = init_i;
520 T max_elem = array[max_index];
521 for (const int i : range) {
522 if (max_elem < array[i]) {
523 max_index = i;
524 max_elem = array[i];
525 }
526 }
527 return max_index;
528 },
529 [&](const int64_t index_a, const int64_t index_b) {
530 if (array[index_a] < array[index_b]) {
531 return index_b;
532 }
533 return index_a;
534 });
535}
536
537} // namespace blender::array_utils
#define PRF_scope_with_name(ui_name, category)
long long int int64_t
IndexRange index_range() const
Definition BLI_array.hh:371
static constexpr IndexRange from_end_size(const int64_t end, const int64_t size)
constexpr IndexRange drop_front(int64_t n) const
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr MutableSpan slice(const int64_t start, const int64_t size) const
Definition BLI_span.hh:579
constexpr void fill(const T &value) const
Definition BLI_span.hh:523
constexpr T * end() const
Definition BLI_span.hh:554
constexpr T * begin() const
Definition BLI_span.hh:550
constexpr IndexRange index_range() const
Definition BLI_span.hh:676
constexpr void copy_from(Span< T > values) const
Definition BLI_span.hh:745
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 IndexRange index_range() const
Definition BLI_span.hh:405
constexpr const T * begin() const
Definition BLI_span.hh:224
constexpr bool is_empty() const
Definition BLI_span.hh:264
IndexRange index_range() const
void materialize_compressed(const IndexMask &mask, MutableSpan< T > r_span) const
CommonVArrayInfo common_info() const
void append(const T &value)
void foreach_index_optimized(Fn &&fn, Mode mode=exec_mode::serial) const
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
#define index(i)
float length(VecOp< float, D >) RET
ccl_device_inline float2 mask(const MaskType mask, const float2 a)
#define T
void gather(const GVArray &src, const IndexMask &indices, GMutableSpan dst, exec_mode::Mode mode=exec_mode::parallel)
void gather_to_groups(const OffsetIndices< int > dst_offsets, const IndexMask &src_selection, const Span< T > src, MutableSpan< T > dst)
T compute_sum(const Span< T > data)
void copy_group_to_group(OffsetIndices< int > src_offsets, OffsetIndices< int > dst_offsets, const IndexMask &selection, GSpan src, GMutableSpan dst)
Vector< IndexRange > find_all_ranges(const Span< T > span, const T &value)
void scatter(const Span< T > src, const Span< IndexT > indices, MutableSpan< T > dst, const Mode mode={})
void gather_group_to_group(const OffsetIndices< int > src_offsets, const OffsetIndices< int > dst_offsets, const IndexMask &selection, const Span< T > src, MutableSpan< T > dst)
void copy(const GVArray &src, GMutableSpan dst, exec_mode::Mode mode=exec_mode::parallel)
std::optional< int64_t > max_element_index(const Span< T > &span, const int64_t grain_size=8192)
bool indexed_data_equal(const Span< T > all_values, const Span< int > indices, const Span< T > values)
constexpr auto exec_mode_tag_for_copy(const Mode mode, const int64_t type_size)
BooleanMix booleans_mix_calc(const VArray< bool > &varray, IndexRange range_to_check)
void fill_index_range(MutableSpan< T > span, const T start=0)
constexpr int64_t calc_copy_grain_size(const exec_mode::Tag auto mode, const int64_t type_size)
void gather(GSpan src, Span< int > map, GMutableSpan dst)
constexpr ParallelGrainSize grain_size(int grain_size)
constexpr Parallel parallel
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
MINLINE uint64_t divide_ceil_ul(uint64_t a, uint64_t b)
BMesh const char void * data
constexpr int grain_size(const int fallback) const