10#include <fmt/ranges.h>
43 mask.foreach_index_optimized<
T>([&](
const T src,
const T dst) { r_map[src] = dst; },
51 std::array<int16_t, max_segment_size>
data;
52 for (
int16_t i = 0; i < max_segment_size; i++) {
60 static constexpr int64_t size_shift = 31;
62 static constexpr int64_t segments_num = max_size / max_segment_size;
81 for (
const int64_t segment_i : range) {
82 indices_by_segment[segment_i] = static_offsets;
83 segment_offsets[segment_i] = segment_i * max_segment_size;
87 segment_offsets.
last() = max_size;
91 data.indices_num_ = max_size;
92 data.segments_num_ = segments_num;
93 data.indices_by_segment_ = indices_by_segment.
data();
94 data.segment_offsets_ = segment_offsets.
data();
95 data.cumulative_segment_sizes_ = segment_offsets.
data();
96 data.begin_index_in_segment_ = 0;
97 data.end_index_in_segment_ = max_segment_size;
112 if (std::holds_alternative<IndexRange>(segment)) {
113 const IndexRange range = std::get<IndexRange>(segment);
117 const Span<int64_t> segment_indices = std::get<Span<int64_t>>(segment);
118 parts.
append(fmt::format(
"{}", fmt::join(segment_indices,
", ")));
121 stream << fmt::format(
"(Size: {} | {})",
mask.size(), fmt::join(parts,
", "));
134 sliced.indices_num_ =
size;
136 sliced.indices_by_segment_ += first_it.
segment_i;
137 sliced.segment_offsets_ += first_it.
segment_i;
138 sliced.cumulative_segment_sizes_ += first_it.
segment_i;
150 sliced.indices_num_ =
size;
152 sliced.indices_by_segment_ += first_it.
segment_i;
153 sliced.segment_offsets_ += first_it.
segment_i;
154 sliced.cumulative_segment_sizes_ += first_it.
segment_i;
172 if (!first_it || !last_it) {
177 if (last_index < first_index) {
180 const int64_t sliced_mask_size = last_index - first_index + 1;
181 return this->
slice(*first_it, *last_it, sliced_mask_size);
199 if (std::optional<IndexRange> range = this->
to_range()) {
200 return range->slice(start,
size).shift(offset);
214 if (std::optional<IndexRange> range = this->
to_range()) {
215 return range->shift(offset);
222 shifted_mask.segment_offsets_ = new_segment_offsets.
data();
236 int64_t group_start_segment_i = 0;
237 int64_t group_first = segments[0][0];
241 auto finish_group = [&](
const int64_t last_segment_i) {
242 if (group_start_segment_i == last_segment_i) {
249 for (
int64_t i = group_start_segment_i + 1; i <= last_segment_i; i++) {
256 const std::optional<IndexRange> segment_base_range =
258 const bool segment_is_range = segment_base_range.has_value();
260 if (group_as_range && segment_is_range) {
261 if (group_last + 1 == segment[0]) {
262 if (segment.last() - group_first + 1 < max_segment_size) {
264 group_last = segment.last();
269 finish_group(segment_i - 1);
271 group_start_segment_i = segment_i;
272 group_first = segment[0];
273 group_last = segment.last();
274 group_as_range = segment_is_range;
276 finish_group(segments.
size() - 1);
279 const int64_t new_segments_num = std::remove_if(segments.
begin(),
282 return segment.is_empty();
285 return new_segments_num;
313 cumulative_segment_sizes[0] = 0;
316 indices_by_segment[segment_i] =
segment.base_span().data();
317 segment_offsets[segment_i] =
segment.offset();
318 cumulative_segment_sizes[segment_i + 1] = cumulative_segment_sizes[segment_i] +
segment.size();
324 data.indices_num_ = cumulative_segment_sizes.last();
326 data.indices_by_segment_ = indices_by_segment.
data();
327 data.segment_offsets_ = segment_offsets.data();
328 data.cumulative_segment_sizes_ = cumulative_segment_sizes.data();
329 data.begin_index_in_segment_ = 0;
330 data.end_index_in_segment_ = segments.
last().size();
338template<
typename T,
int64_t InlineBufferSize>
345 for (
int64_t start = 0; start < indices.
size(); start += max_segment_size) {
352 for (
const auto &segment : segments) {
353 if (std::holds_alternative<IndexRange>(segment)) {
354 const IndexRange segment_range = std::get<IndexRange>(segment);
358 Span<T> segment_indices = std::get<Span<T>>(segment);
360 segment_indices.
size());
361 while (!segment_indices.
is_empty()) {
362 const int64_t offset = segment_indices[0];
365 [&](
const T value) { return value - offset >= max_segment_size; });
367 const int64_t offset_index = segment_indices[i] - offset;
372 segment_indices = segment_indices.
drop_front(next_segment_size);
429 constexpr int64_t min_grain_size = 4096;
430 constexpr int64_t max_grain_size = max_segment_size;
431 if (indices.
size() <= min_grain_size) {
437 const int64_t grain_size = std::clamp(
438 indices.
size() / (threads_num * 4), min_grain_size, max_grain_size);
442 ParallelSegmentsCollector::LocalData &local_data = segments_collector.data_by_thread.local();
443 segments_from_indices(indices.slice(range), local_data.allocator, local_data.segments);
445 segments_collector.
reduce(memory, segments);
448 segments.
resize(consolidated_segments_num);
461 const int64_t segment_start = universe_segment[0];
468 const int64_t segment_end = universe_segment.
last() + 1;
471 const int64_t global_index = universe_segment[i];
472 const int64_t local_index = global_index - segment_start;
476 if (bits_slice[local_index]) {
477 local_bits[local_index].set();
482 return segment_start;
496 universe_segment.
last());
511 const int64_t segment_shift = batch_predicate(universe_segment, builder);
521 constexpr int64_t threshold = 64;
522 int64_t next_range_to_process = 0;
523 int64_t skipped_indices_num = 0;
527 auto consolidate_skipped_ranges = [&](
int64_t end_range_i) {
528 if (skipped_indices_num == 0) {
536 counter += range.
size();
543 if (range.
size() > threshold || builder.
size() == 1) {
544 consolidate_skipped_ranges(i);
546 next_range_to_process = i + 1;
547 skipped_indices_num = 0;
550 skipped_indices_num += range.
size();
553 consolidate_skipped_ranges(builder.
size());
568 constexpr int fallback_grain_size = 4096;
584 universe_segment,
data.allocator, batch_predicate,
data.segments);
587 segments_collector.
reduce(memory, segments);
624 universe_segment.
last());
655 return *
static_cast<const bool *
>(info.
data) ? universe :
IndexMask();
674 return *
static_cast<const bool *
>(info.
data) ?
IndexMask() : universe;
723 const Expr &expr = builder.
subtract({&mask_a}, {&mask_b});
741 if (
const auto *range = std::get_if<IndexRange>(&item)) {
742 for (
const int64_t i : *range) {
746 else if (
const auto *span_i64 = std::get_if<
Span<int64_t>>(&item)) {
747 for (
const int64_t i : *span_i64) {
751 else if (
const auto *span_i32 = std::get_if<
Span<int>>(&item)) {
752 for (
const int i : *span_i32) {
756 else if (
const auto *
index = std::get_if<int64_t>(&item)) {
762 std::ranges::sort(values_vec);
771 r_indices[pos] = T(i);
788 for (
const int64_t i : shifted_indices) {
834 std::array<int16_t, max_segment_size> indices_array;
835 const int64_t true_indices_num = filter_indices(universe_segment, indices_array.data());
836 if (true_indices_num == 0) {
839 const Span<int16_t> true_indices{indices_array.data(), true_indices_num};
845 for (
const auto &true_segment : true_segments) {
846 if (std::holds_alternative<IndexRange>(true_segment)) {
847 const IndexRange segment_range = std::get<IndexRange>(true_segment);
851 const Span<int16_t> segment_indices = std::get<Span<int16_t>>(true_segment);
869 constexpr int fallback_grain_size = 4096;
885 universe_segment,
data.allocator, filter_indices,
data.segments);
888 segments_collector.
reduce(memory, segments);
892 segments.
resize(consolidated_segments_num);
899 if (
const std::optional<RawMaskIterator> it = this->
find_larger_equal(query_index)) {
900 if ((*
this)[*it] == query_index) {
918 if (query_index <
segment[0]) {
920 const int64_t index_in_segment = segment_begin_index;
921 BLI_assert(index_in_segment < max_segment_size);
927 segment.base_span(), [&](
const int16_t i) { return i >= local_index; });
928 const int64_t actual_index_in_segment = index_in_segment + segment_begin_index;
929 BLI_assert(actual_index_in_segment < max_segment_size);
938 const std::optional<RawMaskIterator> larger_equal_it = this->
find_larger_equal(query_index);
939 if (!larger_equal_it) {
943 if ((*
this)[*larger_equal_it] == query_index) {
945 return larger_equal_it;
947 if (larger_equal_it->segment_i > 0) {
948 if (larger_equal_it->index_in_segment > 0) {
951 int16_t(larger_equal_it->index_in_segment - 1)};
967 return this->
find(query_index).has_value();
991 BLI_assert(n * repetitions <= max_segment_size);
996 return data.as_span().take_front(repetitions);
1000 return data.as_span().take_front(repetitions);
1004 return data.as_span().take_front(repetitions);
1028 if (repetitions == 0) {
1031 if (repetitions == 1 && initial_offset == 0) {
1033 return mask_to_repeat;
1035 const std::optional<IndexRange> range_to_repeat = mask_to_repeat.
to_range();
1036 if (range_to_repeat && range_to_repeat->first() == 0 && range_to_repeat->size() == stride) {
1038 return IndexRange(initial_offset, repetitions * stride);
1045 if (
segments_num == 1 && stride <= max_segment_size / 2 && mask_to_repeat.
size() <= 256) {
1048 const int64_t inline_repetitions_num = std::min(repetitions, max_segment_size / stride);
1050 if (src_segment.
size() == 1) {
1057 inline_repetitions_num * src_segment.
size());
1060 const int64_t index = src_segment[i] - src_segment[0] + repetition * stride;
1062 repeated_indices_mut[repetition * src_segment.
size() + i] =
int16_t(
index);
1065 repeated_indices = repeated_indices_mut;
1072 const int64_t used_repetitions = std::min(inline_repetitions_num,
1073 repetitions - i * inline_repetitions_num);
1074 repeated_segments.
append(
1076 repeated_indices.
take_front(used_repetitions * src_segment.
size())));
1087 segment.offset() + repetition * stride + initial_offset,
segment.base_span()));
1107 return masks[0].size() == maks.size();
1122 if (start_iter[mask_i] == 0) {
1123 segments[mask_i] = masks[mask_i].segment(segment_iter[mask_i]);
1127 int16_t next_common_sequence_size = std::numeric_limits<int16_t>::max();
1129 next_common_sequence_size =
math::min(next_common_sequence_size,
1130 int16_t(segments[mask_i].
size() - start_iter[mask_i]));
1134 sequences[mask_i] = segments[mask_i].
slice(start_iter[mask_i], next_common_sequence_size);
1137 if (!
fn(sequences)) {
1142 if (segments[mask_i].
size() - start_iter[mask_i] == next_common_sequence_size) {
1143 segment_iter[mask_i]++;
1144 start_iter[mask_i] = 0;
1147 start_iter[mask_i] += next_common_sequence_size;
1155 if (a.
size() !=
b.size()) {
1168 if (a_is_range || b_is_range) {
1169 return a_is_range && b_is_range;
1177 BLI_assert(a_indices[0] >= 0 && b_indices[0] >= 0);
1178 BLI_assert(b_indices[0] == a_indices[0] - offset_difference);
1180 return std::equal(a_indices.
begin(),
1182 b.base_span().begin(),
1183 [offset_difference](
const int16_t a_index,
const int16_t b_index) ->
bool {
1184 return a_index - offset_difference == b_index;
1190 if (a.
size() !=
b.size()) {
1194 const std::optional<IndexRange> a_as_range = a.
to_range();
1195 const std::optional<IndexRange> b_as_range =
b.to_range();
1196 if (a_as_range.has_value() || b_as_range.has_value()) {
1197 return a_as_range == b_as_range;
1225 group_ids_span, universe, group_indices);
1230 group_indices, groups_num, offset_data, index_data, universe);
1239 LinearAllocator<> &allocator = allocators.local();
1240 for (const int64_t group : range) {
1241 result_masks[group] = IndexMask::from_indices(indices_by_group[group], allocator);
1245 [&](
const IndexRange range) {
return indices_by_group.offsets[range].size(); }));
1249 return result_masks;
1272 const float probability,
1276 const auto next_bool_random_value = [&]() {
return rng.
get_float() <= probability; };
1280 [&](
const int64_t i) {
random[i] = next_bool_random_value(); });
1287 const float probability,
1291 return random_mask(selection, universe_size, random_seed, probability, memory);
#define UNUSED_VARS_NDEBUG(...)
const T & last(const int64_t n=0) const
static Vector< IndexMask, 4 > from_group_ids(const VArray< int > &group_ids, LinearAllocator<> &memory)
constexpr int64_t first() const
constexpr int64_t one_after_last() const
constexpr IndexRange shift(int64_t n) const
constexpr int64_t last(const int64_t n=0) const
constexpr int64_t size() const
static constexpr IndexRange from_begin_end(const int64_t begin, const int64_t end)
constexpr IndexRange()=default
constexpr int64_t start() const
static constexpr IndexRange from_begin_end_inclusive(const int64_t begin, const int64_t last)
constexpr IndexRange drop_front(int64_t n) const
IndexRange index_range() const
MutableSpan< T > allocate_array(int64_t size)
MutableSpan< T > construct_array_copy(Span< T > src)
void transfer_ownership_from(LinearAllocator<> &other)
constexpr int64_t size() const
constexpr MutableSpan slice(const int64_t start, const int64_t size) const
constexpr bool is_empty() const
constexpr T * data() const
constexpr void fill(const T &value) const
constexpr T * end() const
constexpr T * begin() const
constexpr IndexRange index_range() const
constexpr T & last(const int64_t n=0) const
IndexRange index_range() const
T last(const int64_t n=0) const
Span< BaseT > base_span() const
constexpr Span drop_front(int64_t n) const
constexpr Span slice_safe(const int64_t start, const int64_t size) const
constexpr Span slice(int64_t start, int64_t size) const
constexpr int64_t size() const
constexpr const T & last(const int64_t n=0) const
constexpr const T * end() const
constexpr IndexRange index_range() const
constexpr const T * begin() const
constexpr Span take_front(int64_t n) const
constexpr bool is_empty() const
IndexRange index_range() const
CommonVArrayInfo common_info() const
void append(const T &value)
IndexRange index_range() const
void resize(const int64_t new_size)
void extend(Span< T > array)
Span< T > as_span() const
void append_as(ForwardValue &&...value)
MutableBitSpan slice(const IndexRange range) const
const IntersectionExpr & intersect(const Span< Term > terms)
const UnionExpr & merge(const Span< Term > terms)
const DifferenceExpr & subtract(const Term &main_term, const Span< Term > subtract_terms)
IndexMaskSegment shift(const int64_t shift) const
IndexMaskSegment(const OffsetSpan< int64_t, int16_t > span)
static IndexMask from_segments(Span< IndexMaskSegment > segments, LinearAllocator<> &memory)
void foreach_range(ForeachRangeFn auto &&fn) const
void foreach_index_optimized(Fn &&fn, Mode mode=exec_mode::serial) const
IndexMaskSegment segment(int64_t segment_i) const
static IndexMask from_predicate(const IndexMask &universe, LinearAllocator<> &memory, Fn &&predicate, exec_mode::Mode mode=exec_mode::parallel)
IndexMask slice_content(IndexRange range) const
Vector< IndexRange > to_ranges_invert(IndexRange universe) const
Vector< IndexRange > to_ranges() const
std::optional< RawMaskIterator > find(int64_t query_index) const
static IndexMask from_bools(Span< bool > bools, LinearAllocator<> &memory)
std::optional< IndexRange > to_range() const
IndexMask shift(const int64_t offset, LinearAllocator<> &memory) const
static IndexMask from_difference(const IndexMask &mask_a, const IndexMask &mask_b, LinearAllocator<> &memory)
static IndexMask from_ranges(OffsetIndices< T > offsets, const IndexMask &mask, LinearAllocator<> &memory)
std::optional< RawMaskIterator > find_larger_equal(int64_t query_index) const
IndexMask slice(IndexRange range) const
void foreach_segment(Fn &&fn, Mode mode=exec_mode::serial) const
IndexRange bounds() const
Vector< T > to_indices() const
int64_t iterator_to_index(const RawMaskIterator &it) const
static IndexMask from_union(const IndexMask &mask_a, const IndexMask &mask_b, LinearAllocator<> &memory)
static IndexMask from_repeating(const IndexMask &mask_to_repeat, int64_t repetitions, int64_t stride, int64_t initial_offset, LinearAllocator<> &memory)
void foreach_segment_optimized(Fn &&fn, Mode mode=exec_mode::serial) const
int64_t min_array_size() const
void set_bits(MutableBitSpan r_bits, int64_t offset=0) const
static IndexMask from_bits(BitSpan bits, LinearAllocator<> &memory)
std::optional< RawMaskIterator > find_smaller_equal(int64_t query_index) const
bool contains(int64_t query_index) const
static IndexMask from_bools_inverse(Span< bool > bools, LinearAllocator<> &memory)
void to_bits(MutableBitSpan r_bits, int64_t offset=0) const
IndexMask complement(const IndexMask &universe, LinearAllocator<> &memory) const
static IndexMask from_indices(Span< T > indices, LinearAllocator<> &memory)
static IndexMask from_batch_predicate(const IndexMask &universe, LinearAllocator<> &memory, FunctionRef< int64_t(const IndexMaskSegment &universe_segment, IndexRangesBuilder< int16_t > &builder)> batch_predicate, exec_mode::Mode mode=exec_mode::parallel)
friend bool operator==(const IndexMask &a, const IndexMask &b)
static IndexMask from_every_nth(int64_t n, int64_t indices_num, const int64_t initial_offset, LinearAllocator<> &memory)
void to_bools(MutableSpan< bool > r_bools) const
static IndexMask from_initializers(const Span< Initializer > initializers, LinearAllocator<> &memory)
RawMaskIterator index_to_iterator(int64_t index) const
static void foreach_segment_zipped(Span< IndexMask > masks, FunctionRef< bool(Span< IndexMaskSegment > segments)> fn)
int64_t segments_num() const
std::variant< IndexRange, Span< int64_t >, Span< int >, int64_t > Initializer
IndexMask slice_and_shift(IndexRange range, int64_t offset, LinearAllocator<> &memory) const
static IndexMask from_intersection(const IndexMask &mask_a, const IndexMask &mask_b, LinearAllocator<> &memory)
static Vector< IndexMask, 4 > from_group_ids(const VArray< int > &group_ids, LinearAllocator<> &memory)
void fill_index_range(MutableSpan< T > span, const T start=0)
int group_ids_to_indices(Span< int > ids, const IndexMask &mask, MutableSpan< int > r_group_indices, Vector< int > *r_first_indices=nullptr)
int64_t first_if(const Range &range, Predicate &&predicate)
bool or_bools_into_bits(Span< bool > bools, MutableBitSpan r_bits, int64_t allowed_overshoot=0)
void bits_to_index_ranges(const BitSpan bits, IndexRangesBuilder< IntT > &builder)
void invert(BitSpanT &&data)
constexpr ParallelGrainSize grain_size(int grain_size)
static void segments_from_predicate_filter(const IndexMaskSegment universe_segment, LinearAllocator<> &allocator, const FunctionRef< int64_t(IndexMaskSegment indices, int16_t *r_true_indices)> filter_indices, Vector< IndexMaskSegment, 16 > &r_segments)
IndexMask from_predicate_impl(const IndexMask &universe, LinearAllocator<> &memory, FunctionRef< int64_t(IndexMaskSegment indices, int16_t *r_true_indices)> filter_indices, exec_mode::Mode mode)
IndexMask evaluate_expression(const Expr &expression, LinearAllocator<> &memory)
IndexMask random_mask(const IndexMask &mask, const int64_t universe_size, const uint32_t random_seed, const float probability, LinearAllocator<> &memory)
static Span< int16_t > get_every_nth_index(const int64_t n, const int64_t repetitions, LinearAllocator<> &memory)
void index_range_to_mask_segments(const IndexRange range, Vector< IndexMaskSegment, N > &r_segments)
static void segments_from_batch_predicate(const IndexMaskSegment universe_segment, LinearAllocator<> &allocator, const FunctionRef< int64_t(const IndexMaskSegment &universe_segment, IndexRangesBuilder< int16_t > &builder)> batch_predicate, Vector< IndexMaskSegment, 16 > &r_segments)
static void segments_from_indices(const Span< T > indices, LinearAllocator<> &allocator, Vector< IndexMaskSegment, InlineBufferSize > &r_segments)
void build_reverse_map(const IndexMask &mask, MutableSpan< T > r_map)
std::ostream & operator<<(std::ostream &stream, const IndexMask &mask)
std::array< int16_t, max_segment_size > build_static_indices_array()
static Array< int16_t > build_every_nth_index_array(const int64_t n)
static int64_t from_bits_batch_predicate(const IndexMaskSegment universe_segment, IndexRangesBuilder< int16_t > &builder, const BitSpan bits_slice)
const IndexMask & get_static_index_mask_for_min_size(const int64_t min_size)
static bool segments_is_equal(const IndexMaskSegment &a, const IndexMaskSegment &b)
int64_t consolidate_index_mask_segments(MutableSpan< IndexMaskSegment > segments, LinearAllocator<> &memory)
const std::array< int16_t, max_segment_size > & get_static_indices_array()
void masked_fill(MutableSpan< T > data, const T &value, const IndexMask &mask)
T min(const T &a, const T &b)
GroupedSpan< int > build_groups_from_indices(Span< int > indices, int groups_num, Array< int > &offset_data, Array< int > &index_data)
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)
auto isolate_task(const Function &function)
std::optional< IndexRange > non_empty_as_range_try(const Span< T > indices)
int64_t split_to_ranges_and_spans(const Span< T > indices, const int64_t range_threshold, Vector< std::variant< IndexRange, Span< T > >, InlineBufferSize > &r_segments)
bool non_empty_is_range(const Span< T > indices)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void parallel_sort(RandomAccessIterator begin, RandomAccessIterator end)
int BLI_system_thread_count()
BMesh const char void * data
constexpr IntT ceil_division(const IntT x, const IntT y)
constexpr int grain_size(const int fallback) const
std::optional< int > grain_size_override
const int64_t * cumulative_segment_sizes_
const int16_t ** indices_by_segment_
int64_t end_index_in_segment_
int64_t begin_index_in_segment_
const int64_t * segment_offsets_
LinearAllocator allocator
Vector< IndexMaskSegment, 16 > segments
threading::EnumerableThreadSpecific< LocalData > data_by_thread
void reduce(LinearAllocator<> &main_allocator, Vector< IndexMaskSegment, 16 > &main_segments)