Blender V5.3
offset_indices.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
11#include "BLI_array_utils.hh"
12#include "BLI_index_mask.hh"
13#include "BLI_math_base_c.hh"
14#include "BLI_offset_indices.hh"
15#include "BLI_sort.hh"
16#include "BLI_task.hh"
18#include "BLI_threads.hh"
19
20#include "atomic_ops.h"
21
23
25 const int start_offset)
26{
27 int offset = start_offset;
28 int64_t offset_i64 = start_offset;
29
30 for (const int i : counts_to_offsets.index_range().drop_back(1)) {
31 const int count = counts_to_offsets[i];
32 BLI_assert(count >= 0);
33 counts_to_offsets[i] = offset;
34 offset += count;
35#ifndef NDEBUG
36 offset_i64 += count;
37#endif
38 }
39 counts_to_offsets.last() = offset;
40
41 BLI_assert_msg(offset == offset_i64, "Integer overflow occurred");
42 UNUSED_VARS_NDEBUG(offset_i64);
43
44 return OffsetIndices<int>(counts_to_offsets);
45}
46
47std::optional<OffsetIndices<int>> accumulate_counts_to_offsets_with_overflow_check(
48 MutableSpan<int> counts_to_offsets, int start_offset)
49{
50 /* This variant was measured to be about ~8% slower than the version without overflow check.
51 * Since this function is often a serial bottleneck, we use a separate code path for when an
52 * overflow check is requested. */
53 int64_t offset = start_offset;
54 for (const int i : counts_to_offsets.index_range().drop_back(1)) {
55 const int count = counts_to_offsets[i];
56 BLI_assert(count >= 0);
57 counts_to_offsets[i] = offset;
58 offset += count;
59 }
60 counts_to_offsets.last() = offset;
61 const bool has_overflow = offset >= std::numeric_limits<int>::max();
62 if (has_overflow) {
63 return std::nullopt;
64 }
65 return OffsetIndices<int>(counts_to_offsets);
66}
67
68void fill_constant_group_size(const int size, const int start_offset, MutableSpan<int> offsets)
69{
71 threading::parallel_for(offsets.index_range(), 1024, [&](const IndexRange range) {
72 for (const int64_t i : range) {
73 offsets[i] = size * i + start_offset;
74 }
75 });
76 });
77}
78
80 const IndexMask &mask,
81 MutableSpan<int> sizes)
82{
83 mask.foreach_index_optimized<int64_t>([&](const int64_t i) { sizes[i] = offsets[i].size(); },
85}
86
88 const IndexMask &mask,
89 MutableSpan<int> sizes)
90{
91 mask.foreach_index_optimized<int64_t>(
92 [&](const int64_t i, const int64_t pos) { sizes[pos] = offsets[i].size(); },
94}
95
97 const Span<int> indices,
98 MutableSpan<int> sizes)
99{
101 sizes.size_in_bytes() + offsets.data().size_in_bytes() + indices.size_in_bytes(), [&]() {
102 threading::parallel_for(indices.index_range(), 4096, [&](const IndexRange range) {
103 for (const int i : range) {
104 sizes[i] = offsets[indices[i]].size();
105 }
106 });
107 });
108}
109
110int sum_group_sizes(const OffsetIndices<int> offsets, const Span<int> indices)
111{
112 int count = 0;
113 for (const int i : indices) {
114 count += offsets[i].size();
115 }
116 return count;
117}
118
120{
121 int count = 0;
122 mask.foreach_segment_optimized([&](const auto segment) {
123 if constexpr (std::is_same_v<std::decay_t<decltype(segment)>, IndexRange>) {
124 count += offsets[segment].size();
125 }
126 else {
127 for (const int64_t i : segment) {
128 count += offsets[i].size();
129 }
130 }
131 });
132 return count;
133}
134
136 const IndexMask &selection,
137 const int start_offset,
138 MutableSpan<int> dst_offsets)
139{
140 if (selection.is_empty()) {
141 return {};
142 }
143 int offset = start_offset;
144 selection.foreach_index_optimized<int>([&](const int i, const int pos) {
145 dst_offsets[pos] = offset;
146 offset += src_offsets[i].size();
147 });
148 dst_offsets.last() = offset;
149 return OffsetIndices<int>(dst_offsets);
150}
151
153 const Span<int> selection,
154 const int start_offset,
155 MutableSpan<int> dst_offsets)
156{
157 if (selection.is_empty()) {
158 return {};
159 }
160 int offset = start_offset;
161 for (const int i : selection.index_range()) {
162 dst_offsets[i] = offset;
163 offset += src_offsets[selection[i]].size();
164 }
165 dst_offsets.last() = offset;
166 return OffsetIndices<int>(dst_offsets);
167}
168
170{
171 threading::parallel_for(offsets.index_range(), 1024, [&](const IndexRange range) {
172 for (const int64_t i : range) {
173 r_map.slice(offsets[i]).fill(i);
174 }
175 });
176}
177
179{
180 BLI_assert(std::all_of(offsets.begin(), offsets.end(), [](int value) { return value == 0; }));
181 array_utils::count_indices(indices, offsets);
183}
184
186{
188 groups.index_range(),
189 1024,
190 [&](const IndexRange range) {
191 for (const int64_t index : range) {
192 MutableSpan<int> group = indices.slice(groups[index]);
193 parallel_sort(group);
194 }
195 },
197 [&](const IndexRange range) { return groups[range].size(); }));
198}
199
205static int64_t counting_chunk_size(const int64_t indices_num)
206{
207 const int64_t max_chunks = BLI_system_thread_count() * 4;
208 const int64_t min_counting_chunk_size = 1 << 15;
209 return std::max(min_counting_chunk_size, int64_t(divide_ceil_ul(indices_num, max_chunks)));
210}
211
220template<typename ValueSourceForeach>
221static void reverse_indices_in_groups_counting(const Span<int> group_indices,
222 const OffsetIndices<int> offsets,
223 const ValueSourceForeach &value_source_foreach,
224 MutableSpan<int> results)
225{
226 const int64_t groups_num = offsets.size();
227 const int64_t chunk_size = counting_chunk_size(group_indices.size());
228 const int64_t chunks_num = divide_ceil_ul(group_indices.size(), chunk_size);
229
230 /* Count how many indices of each chunk fall into each group. */
231 Array<int> chunk_offsets(chunks_num * groups_num);
232 threading::parallel_for(IndexRange(chunks_num), 1, [&](const IndexRange range) {
233 for (const int64_t chunk : range) {
234 MutableSpan<int> counts = chunk_offsets.as_mutable_span().slice(chunk * groups_num,
235 groups_num);
236 counts.fill(0);
237 for (const int group : group_indices.slice_safe(chunk * chunk_size, chunk_size)) {
238 counts[group]++;
239 }
240 }
241 });
242
243 /* Accumulate into the offset where each chunk starts writing in each group. */
244 Array<int> current_offsets(groups_num);
245 for (const int64_t group : IndexRange(groups_num)) {
246 current_offsets[group] = int(offsets[group].start());
247 }
248 for (const int64_t chunk : IndexRange(chunks_num)) {
249 MutableSpan<int> counts = chunk_offsets.as_mutable_span().slice(chunk * groups_num,
250 groups_num);
251 for (const int64_t group : IndexRange(groups_num)) {
252 const int count = counts[group];
253 counts[group] = current_offsets[group];
254 current_offsets[group] += count;
255 }
256 }
257
258 /* Write the index of every element into its group. */
259 threading::parallel_for(IndexRange(chunks_num), 1, [&](const IndexRange range) {
260 for (const int64_t chunk : range) {
261 MutableSpan<int> group_offsets = chunk_offsets.as_mutable_span().slice(chunk * groups_num,
262 groups_num);
263 const int64_t begin = chunk * chunk_size;
264 const int64_t size = std::min(chunk_size, group_indices.size() - begin);
265 value_source_foreach(IndexRange(begin, size), [&](const int64_t pos, const int value) {
266 const int position = group_offsets[group_indices[pos]]++;
267 results[position] = value;
268 });
269 }
270 });
271}
272
277template<typename ValueSourceForeach>
278static void reverse_indices_in_groups_atomic(const Span<int> group_indices,
279 const OffsetIndices<int> offsets,
280 const ValueSourceForeach &value_source_foreach,
281 MutableSpan<int> results)
282{
283 Array<int> counts(offsets.size(), 0);
284 threading::parallel_for(group_indices.index_range(), 1024, [&](const IndexRange range) {
285 value_source_foreach(range, [&](const int64_t pos, const int value) {
286 const int group_index = group_indices[pos];
287 const int index_in_group = atomic_fetch_and_add_int32(&counts[group_index], 1);
288 results[offsets[group_index][index_in_group]] = value;
289 });
290 });
291}
292
297template<typename ValueSourceForeach>
298static void fill_groups(const Span<int> group_indices,
299 const OffsetIndices<int> offsets,
300 const ValueSourceForeach &value_source_foreach,
301 const bool sort,
302 MutableSpan<int> results)
303{
304 /* Counting avoids both the atomic contention of filling the groups in parallel and the
305 * sorting afterwards, but needs an offset per group for every chunk of indices. Use it while
306 * that stays small, when there are many indices and few groups. */
307 constexpr int64_t min_parallel_indices = 1 << 16;
308 const int64_t chunks_num = divide_ceil_ul(group_indices.size(),
309 counting_chunk_size(group_indices.size()));
310 if (group_indices.size() >= min_parallel_indices && BLI_system_thread_count() >= 4 &&
311 chunks_num * offsets.size() <= group_indices.size() / 2)
312 {
313 reverse_indices_in_groups_counting(group_indices, offsets, value_source_foreach, results);
314 return;
315 }
316 reverse_indices_in_groups_atomic(group_indices, offsets, value_source_foreach, results);
317 if (sort) {
318 sort_groups(offsets, results);
319 }
320}
321
323static void assert_group_indices_valid(const Span<int> group_indices,
324 const OffsetIndices<int> offsets)
325{
326 BLI_assert(*std::max_element(group_indices.begin(), group_indices.end()) < offsets.size());
327 BLI_assert(*std::min_element(group_indices.begin(), group_indices.end()) >= 0);
328 UNUSED_VARS_NDEBUG(group_indices, offsets);
329}
330
331void reverse_indices_in_groups(const Span<int> group_indices,
332 const OffsetIndices<int> offsets,
333 MutableSpan<int> results,
334 const bool sort)
335{
336 if (group_indices.is_empty()) {
337 return;
338 }
339 BLI_assert(results.size() == group_indices.size());
340 BLI_assert(results.size() == offsets.total_size());
341 assert_group_indices_valid(group_indices, offsets);
342
343 /* The value stored for a position is the position itself. */
344 const auto position_values = [](const IndexRange range, const auto &fn) {
345 for (const int64_t pos : range) {
346 fn(pos, int(pos));
347 }
348 };
349
350 fill_groups(group_indices, offsets, position_values, sort, results);
351}
352
353void reverse_indices_in_groups(const Span<int> group_indices,
354 const OffsetIndices<int> offsets,
355 MutableSpan<int> results,
356 const OffsetIndices<int> value_groups)
357{
358 if (group_indices.is_empty()) {
359 return;
360 }
361 BLI_assert(results.size() == group_indices.size());
362 BLI_assert(results.size() == offsets.total_size());
363 BLI_assert(value_groups.total_size() == group_indices.size());
364 assert_group_indices_valid(group_indices, offsets);
365
366 /* The value stored is the index of the group containing it. */
367 const auto grouped_values = [&](const IndexRange range, const auto &fn) {
368 const Span<int> value_group_offsets = value_groups.data();
369 int64_t group = std::ranges::upper_bound(value_group_offsets, int(range.start())) -
370 value_group_offsets.begin() - 1;
371 int64_t pos = range.start();
372 while (pos < range.one_after_last()) {
373 const int64_t group_end = std::min(range.one_after_last(),
374 value_groups[group].one_after_last());
375 for (; pos < group_end; pos++) {
376 fn(pos, int(group));
377 }
378 group++;
379 }
380 };
381
382 /* Counting per chunk is not used here, since these relations always have many groups relative
383 * to the number of indices. */
384 reverse_indices_in_groups_atomic(group_indices, offsets, grouped_values, results);
385 sort_groups(offsets, results);
386}
387
388void reverse_indices_in_groups(const Span<int> group_indices,
389 const OffsetIndices<int> offsets,
390 MutableSpan<int> results,
391 const int value_group_size)
392{
393 if (group_indices.is_empty()) {
394 return;
395 }
396 BLI_assert(results.size() == group_indices.size());
397 BLI_assert(results.size() == offsets.total_size());
398 BLI_assert(group_indices.size() % value_group_size == 0);
399 assert_group_indices_valid(group_indices, offsets);
400
401 /* The value stored is the index of the group containing it. */
402 const auto uniform_grouped_values = [&](const IndexRange range, const auto &fn) {
403 int64_t group = range.start() / value_group_size;
404 int64_t pos = range.start();
405 while (pos < range.one_after_last()) {
406 const int64_t group_end = std::min(range.one_after_last(), (group + 1) * value_group_size);
407 for (; pos < group_end; pos++) {
408 fn(pos, int(group));
409 }
410 group++;
411 }
412 };
413
414 reverse_indices_in_groups_atomic(group_indices, offsets, uniform_grouped_values, results);
415 sort_groups(offsets, results);
416}
417
419 const int groups_num,
420 Array<int> &offset_data,
421 Array<int> &index_data)
422{
423 offset_data = Array<int>(groups_num + 1, 0);
424 const OffsetIndices offsets = build_reverse_offsets(indices, offset_data.as_mutable_span());
425 index_data.reinitialize(offsets.total_size());
426 reverse_indices_in_groups(indices, offsets, index_data);
427 return {OffsetIndices<int>(offsets), index_data};
428}
429
431 const int groups_num,
432 Array<int> &offset_data,
433 Array<int> &index_data,
434 const IndexMask &values)
435{
436 offset_data = Array<int>(groups_num + 1, 0);
437 const OffsetIndices offsets = build_reverse_offsets(indices, offset_data.as_mutable_span());
438 index_data.reinitialize(offsets.total_size());
439 if (!indices.is_empty()) {
440 BLI_assert(values.size() == indices.size());
441 assert_group_indices_valid(indices, offsets);
442
443 /* The value stored is the index at that position in the mask. */
444 const auto mask_values = [&](const IndexRange range, const auto &fn) {
445 values.slice(range).foreach_index_optimized<int>(
446 [&](const int index, const int64_t pos) { fn(range.start() + pos, index); });
447 };
448
449 fill_groups(indices, offsets, mask_values, true, index_data);
450 }
451 return {OffsetIndices<int>(offsets), index_data};
452}
453
454} // namespace blender::offset_indices
Provides wrapper around system-specific atomic primitives, and some extensions (faked-atomic operatio...
#define UNUSED_VARS_NDEBUG(...)
#define BLI_assert_msg(a, msg)
void sort(btMatrix3x3 &U, btVector3 &sigma, btMatrix3x3 &V, int t)
Helper function of 3X3 SVD for sorting singular values.
MutableSpan< T > as_mutable_span()
Definition BLI_array.hh:259
void reinitialize(const int64_t new_size)
Definition BLI_array.hh:430
constexpr int64_t one_after_last() const
constexpr IndexRange drop_back(int64_t n) const
constexpr int64_t start() const
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr void fill(const T &value) const
Definition BLI_span.hh:523
constexpr int64_t size_in_bytes() const
Definition BLI_span.hh:507
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 T & last(const int64_t n=0) const
Definition BLI_span.hh:695
constexpr Span slice_safe(const int64_t start, const int64_t size) const
Definition BLI_span.hh:158
constexpr int64_t size_in_bytes() const
Definition BLI_span.hh:272
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
constexpr bool is_empty() const
Definition BLI_span.hh:264
void foreach_index_optimized(Fn &&fn, Mode mode=exec_mode::serial) const
IndexMask slice(IndexRange range) const
#define position
void count_indices(Span< int > indices, MutableSpan< int > counts)
constexpr ParallelGrainSize grain_size(int grain_size)
void sort_groups(OffsetIndices< int > groups, MutableSpan< int > indices)
static void assert_group_indices_valid(const Span< int > group_indices, const OffsetIndices< int > offsets)
static int64_t counting_chunk_size(const int64_t indices_num)
void copy_group_sizes(OffsetIndices< int > offsets, const IndexMask &mask, MutableSpan< int > sizes)
void build_reverse_map(OffsetIndices< int > offsets, MutableSpan< int > r_map)
static void reverse_indices_in_groups_atomic(const Span< int > group_indices, const OffsetIndices< int > offsets, const ValueSourceForeach &value_source_foreach, MutableSpan< int > results)
OffsetIndices< int > accumulate_counts_to_offsets(MutableSpan< int > counts_to_offsets, int start_offset=0)
GroupedSpan< int > build_groups_from_indices(Span< int > indices, int groups_num, Array< int > &offset_data, Array< int > &index_data)
std::optional< OffsetIndices< int > > accumulate_counts_to_offsets_with_overflow_check(MutableSpan< int > counts_to_offsets, int start_offset=0)
static void fill_groups(const Span< int > group_indices, const OffsetIndices< int > offsets, const ValueSourceForeach &value_source_foreach, const bool sort, MutableSpan< int > results)
void gather_group_sizes(OffsetIndices< int > offsets, const IndexMask &mask, MutableSpan< int > sizes)
OffsetIndices< int > build_reverse_offsets(Span< int > indices, MutableSpan< int > offsets)
void fill_constant_group_size(int size, int start_offset, MutableSpan< int > offsets)
static void reverse_indices_in_groups_counting(const Span< int > group_indices, const OffsetIndices< int > offsets, const ValueSourceForeach &value_source_foreach, MutableSpan< int > results)
void reverse_indices_in_groups(Span< int > group_indices, OffsetIndices< int > offsets, MutableSpan< int > results, bool sort=true)
int sum_group_sizes(OffsetIndices< int > offsets, const IndexMask &mask)
OffsetIndices< int > gather_selected_offsets(OffsetIndices< int > src_offsets, const IndexMask &selection, int start_offset, MutableSpan< int > dst_offsets)
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
auto accumulated_task_sizes(Fn &&fn)
void memory_bandwidth_bound_task(const int64_t approximate_bytes_touched, const Function &function)
Definition BLI_task.hh:251
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
MINLINE uint64_t divide_ceil_ul(uint64_t a, uint64_t b)
iter begin(iter)