BLI: Generic key map
New container for Associative Find node for geometry node. Such container need can find elements by using random key count.
Details
Details
- Reviewers
- None
Summary
Diff Detail
Diff Detail
Event Timeline
Iliya Katueshenock (Moder) planned changes to this revision.
Iliya Katueshenock (Moder) created this revision.
Iliya Katueshenock (Moder) retitled this revision from BLI: Generic key map to WIP: BLI: Generic key map.Oct 15 2022, 3:06 PM
Comment Actions
Based on multiple tests (one of them)
I can understand that the implementation of this task based on several maps will be more productive than sorting.
It has more stable asymptotics, but its performance gain is noticeable only on huge problems.
| 1 | template<typename T> class TotalFieldInputFastValueInStruct final : public bke::GeometryFieldInput { |
|---|---|
| 2 | private: |
| 3 | Field<T> input_; |
| 4 | Field<int> group_index_; |
| 5 | eAttrDomain source_domain_; |
| 6 | |
| 7 | public: |
| 8 | TotalFieldInputFastValueInStruct(const eAttrDomain source_domain, Field<T> input, Field<int> group_index) |
| 9 | : bke::GeometryFieldInput(CPPType::get<T>(), "Total Value"), |
| 10 | input_(input), |
| 11 | group_index_(group_index), |
| 12 | source_domain_(source_domain) |
| 13 | { |
| 14 | } |
| 15 | |
| 16 | struct Element { |
| 17 | int index; |
| 18 | int group; |
| 19 | }; |
| 20 | |
| 21 | GVArray get_varray_for_context(const bke::GeometryFieldContext &context, |
| 22 | IndexMask /*mask*/) const final |
| 23 | { |
| 24 | const AttributeAccessor attributes = *context.attributes(); |
| 25 | const int64_t domain_size = attributes.domain_size(source_domain_); |
| 26 | if (domain_size == 0) { |
| 27 | return {}; |
| 28 | } |
| 29 | |
| 30 | const bke::GeometryFieldContext source_context{ |
| 31 | context.geometry(), context.type(), source_domain_}; |
| 32 | fn::FieldEvaluator evaluator{source_context, domain_size}; |
| 33 | evaluator.add(input_); |
| 34 | evaluator.add(group_index_); |
| 35 | evaluator.evaluate(); |
| 36 | const VArray<T> values = evaluator.get_evaluated<T>(0); |
| 37 | const VArray<int> group_indices = evaluator.get_evaluated<int>(1); |
| 38 | |
| 39 | if (group_indices.is_single()) { |
| 40 | T accumulation = T(); |
| 41 | for (const int i : values.index_range()) { |
| 42 | accumulation = values[i] + accumulation; |
| 43 | } |
| 44 | return VArray<T>::ForSingle(accumulation, domain_size); |
| 45 | } |
| 46 | Array<Element> elements(domain_size); |
| 47 | threading::parallel_for(elements.index_range(), 1024, [&](const IndexRange range){ |
| 48 | for (const int i : range){ |
| 49 | elements[i].index = i; |
| 50 | elements[i].group = group_indices[i]; |
| 51 | } |
| 52 | }); |
| 53 | parallel_sort(elements.begin(), elements.end(), [&](const Element &a, const Element &b){ |
| 54 | if (a.group < b.group){ |
| 55 | return true; |
| 56 | } |
| 57 | if (a.group > b.group){ |
| 58 | return false; |
| 59 | } |
| 60 | return a.index < b.index; |
| 61 | }); |
| 62 | Array<T> outputs(domain_size); |
| 63 | Vector<T> accumulations; |
| 64 | Vector<int> totals; |
| 65 | accumulations.reserve(domain_size); |
| 66 | totals.reserve(domain_size); |
| 67 | accumulations.append({}); |
| 68 | totals.append(0); |
| 69 | int group = elements.first().group; |
| 70 | for (const int index : elements.index_range()){ |
| 71 | const Element &element = elements[index]; |
| 72 | if (element.group == group) { |
| 73 | totals.last()++; |
| 74 | accumulations.last() += values[element.index]; |
| 75 | }else{ |
| 76 | group = element.group; |
| 77 | totals.append(1); |
| 78 | accumulations.append(values[element.index]); |
| 79 | } |
| 80 | } |
| 81 | int offsets = 0; |
| 82 | for (int &value : totals){ |
| 83 | const int v = value; |
| 84 | value = offsets; |
| 85 | offsets = value+v; |
| 86 | } |
| 87 | threading::parallel_for(totals.index_range(), 1024, [&](const IndexRange range){ |
| 88 | IndexRange fill_range = range; |
| 89 | if (totals.index_range().last() == range.last()){ |
| 90 | fill_range = fill_range.drop_back(1); |
| 91 | } |
| 92 | for (const int i : fill_range){ |
| 93 | const int index = totals[i]; |
| 94 | const int next_index = totals[i+1]; |
| 95 | const T value = accumulations[i]; |
| 96 | for (const Element &element : elements.as_span().slice(index, next_index-index)){ |
| 97 | outputs[element.index] = value; |
| 98 | } |
| 99 | } |
| 100 | if (fill_range != range){ |
| 101 | const int index = totals.last(); |
| 102 | const int next_index = offsets; |
| 103 | const T value = accumulations.last(); |
| 104 | for (const Element &element : elements.as_span().slice(index, next_index-index)){ |
| 105 | outputs[element.index] = value; |
| 106 | } |
| 107 | } |
| 108 | }); |
| 109 | return attributes.adapt_domain<T>(VArray<T>::ForContainer(std::move(outputs)), source_domain_, context.domain()); |
| 110 | } |
| 111 | }; |