25 const int start_offset)
27 int offset = start_offset;
28 int64_t offset_i64 = start_offset;
31 const int count = counts_to_offsets[i];
33 counts_to_offsets[i] = offset;
39 counts_to_offsets.
last() = offset;
55 const int count = counts_to_offsets[i];
57 counts_to_offsets[i] = offset;
60 counts_to_offsets.
last() = offset;
61 const bool has_overflow = offset >= std::numeric_limits<int>::max();
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;
102 threading::parallel_for(indices.index_range(), 4096, [&](const IndexRange range) {
103 for (const int i : range) {
104 sizes[i] = offsets[indices[i]].size();
113 for (
const int i : indices) {
114 count += offsets[i].
size();
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();
127 for (
const int64_t i : segment) {
128 count += offsets[i].
size();
137 const int start_offset,
143 int offset = start_offset;
145 dst_offsets[pos] = offset;
146 offset += src_offsets[i].
size();
148 dst_offsets.
last() = offset;
154 const int start_offset,
160 int offset = start_offset;
162 dst_offsets[i] = offset;
163 offset += src_offsets[selection[i]].
size();
165 dst_offsets.
last() = offset;
172 for (const int64_t i : range) {
173 r_map.slice(offsets[i]).fill(i);
180 BLI_assert(std::all_of(offsets.
begin(), offsets.
end(), [](
int value) { return value == 0; }));
191 for (const int64_t index : range) {
192 MutableSpan<int> group = indices.slice(groups[index]);
193 parallel_sort(group);
197 [&](
const IndexRange range) {
return groups[range].size(); }));
208 const int64_t min_counting_chunk_size = 1 << 15;
220template<
typename ValueSourceForeach>
223 const ValueSourceForeach &value_source_foreach,
231 Array<int> chunk_offsets(chunks_num * groups_num);
233 for (
const int64_t chunk : range) {
237 for (
const int group : group_indices.
slice_safe(chunk * chunk_size, chunk_size)) {
246 current_offsets[group] = int(offsets[group].start());
252 const int count = counts[group];
253 counts[group] = current_offsets[group];
254 current_offsets[group] += count;
260 for (
const int64_t chunk : range) {
266 const int position = group_offsets[group_indices[pos]]++;
277template<
typename ValueSourceForeach>
280 const ValueSourceForeach &value_source_foreach,
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;
297template<
typename ValueSourceForeach>
300 const ValueSourceForeach &value_source_foreach,
307 constexpr int64_t min_parallel_indices = 1 << 16;
311 chunks_num * offsets.
size() <= group_indices.
size() / 2)
344 const auto position_values = [](
const IndexRange range,
const auto &
fn) {
345 for (
const int64_t pos : range) {
367 const auto grouped_values = [&](
const IndexRange range,
const auto &
fn) {
369 int64_t group = std::ranges::upper_bound(value_group_offsets,
int(range.
start())) -
370 value_group_offsets.
begin() - 1;
374 value_groups[group].one_after_last());
375 for (; pos < group_end; pos++) {
391 const int value_group_size)
402 const auto uniform_grouped_values = [&](
const IndexRange range,
const auto &
fn) {
407 for (; pos < group_end; pos++) {
419 const int groups_num,
431 const int groups_num,
444 const auto mask_values = [&](
const IndexRange range,
const auto &
fn) {
449 fill_groups(indices, offsets, mask_values,
true, index_data);
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()
void reinitialize(const int64_t new_size)
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
constexpr void fill(const T &value) const
constexpr int64_t size_in_bytes() const
constexpr T * end() const
constexpr T * begin() const
constexpr IndexRange index_range() const
constexpr T & last(const int64_t n=0) const
constexpr Span slice_safe(const int64_t start, const int64_t size) const
constexpr int64_t size_in_bytes() const
constexpr int64_t size() const
constexpr const T * end() const
constexpr IndexRange index_range() const
constexpr const T * begin() const
constexpr bool is_empty() const
void foreach_index_optimized(Fn &&fn, Mode mode=exec_mode::serial) const
IndexMask slice(IndexRange range) const
IndexRange index_range() const
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))
auto accumulated_task_sizes(Fn &&fn)
void memory_bandwidth_bound_task(const int64_t approximate_bytes_touched, const Function &function)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
int BLI_system_thread_count()
MINLINE uint64_t divide_ceil_ul(uint64_t a, uint64_t b)