diff options
author | Jacques Lucke <jacques@blender.org> | 2020-04-23 12:57:58 +0300 |
---|---|---|
committer | Jacques Lucke <jacques@blender.org> | 2020-04-23 13:02:06 +0300 |
commit | 614621747ea214efc72a095fbef6695bf98a2bb4 (patch) | |
tree | e8a54ae3373f7e965ecc3d0bf74a44db0a9b077a /source/blender/blenlib | |
parent | 68cfce1519ed63dc0a231c7de81c26f3f9c810f1 (diff) |
BLI: optimize VectorSet implementation
Instead of building on top of `BLI::Vector`, just use a raw array
and handle the growing in `BLI::VectorSet`.
After this change, the existing `EdgeSet` can be reimplemented using
`BLI::VectorSet` without performance regressions.
Diffstat (limited to 'source/blender/blenlib')
-rw-r--r-- | source/blender/blenlib/BLI_open_addressing.hh | 7 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_vector.hh | 2 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_vector_set.hh | 103 |
3 files changed, 87 insertions, 25 deletions
diff --git a/source/blender/blenlib/BLI_open_addressing.hh b/source/blender/blenlib/BLI_open_addressing.hh index fa2ea6d8f94..7b8adcf9bd2 100644 --- a/source/blender/blenlib/BLI_open_addressing.hh +++ b/source/blender/blenlib/BLI_open_addressing.hh @@ -70,7 +70,7 @@ class OpenAddressingArray { /* Can be used to map a hash value into the range of valid slot indices. */ uint32_t m_slot_mask; Allocator m_allocator; - AlignedBuffer<sizeof(Item) * ItemsInSmallStorage, alignof(Item)> m_local_storage; + AlignedBuffer<(uint)sizeof(Item) * ItemsInSmallStorage, (uint)alignof(Item)> m_local_storage; public: explicit OpenAddressingArray(uint8_t item_exponent = 0) @@ -171,6 +171,11 @@ class OpenAddressingArray { return *this; } + Allocator &allocator() + { + return m_allocator; + } + /* Prepare a new array that can hold a minimum of min_usable_slots elements. All entries are * empty. */ OpenAddressingArray init_reserved(uint32_t min_usable_slots) const diff --git a/source/blender/blenlib/BLI_vector.hh b/source/blender/blenlib/BLI_vector.hh index a44962e50cc..450242a349a 100644 --- a/source/blender/blenlib/BLI_vector.hh +++ b/source/blender/blenlib/BLI_vector.hh @@ -49,7 +49,7 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve T *m_end; T *m_capacity_end; Allocator m_allocator; - AlignedBuffer<sizeof(T) * N, alignof(T)> m_small_buffer; + AlignedBuffer<(uint)sizeof(T) * N, (uint)alignof(T)> m_small_buffer; #ifndef NDEBUG /* Storing size in debug builds, because it makes debugging much easier sometimes. */ diff --git a/source/blender/blenlib/BLI_vector_set.hh b/source/blender/blenlib/BLI_vector_set.hh index c3cecfc0acf..b3f19d32060 100644 --- a/source/blender/blenlib/BLI_vector_set.hh +++ b/source/blender/blenlib/BLI_vector_set.hh @@ -76,7 +76,7 @@ template<typename T, typename Allocator = GuardedAllocator> class VectorSet { return m_value == IS_DUMMY; } - bool has_value(const T &value, const Vector<T> &elements) const + bool has_value(const T &value, const T *elements) const { return this->is_set() && elements[this->index()] == value; } @@ -112,12 +112,14 @@ template<typename T, typename Allocator = GuardedAllocator> class VectorSet { using ArrayType = OpenAddressingArray<Slot, 4, Allocator>; ArrayType m_array; - Vector<T, 4, Allocator> m_elements; + + /* The capacity of the array should always be at least m_array.slots_usable(). */ + T *m_elements = nullptr; public: VectorSet() { - BLI_assert(m_array.slots_usable() <= m_elements.capacity()); + m_elements = this->allocate_elements_array(m_array.slots_usable()); } VectorSet(ArrayRef<T> values) : VectorSet() @@ -135,6 +137,43 @@ template<typename T, typename Allocator = GuardedAllocator> class VectorSet { this->add_multiple(values); } + VectorSet(const VectorSet &other) : m_array(other.m_array) + { + m_elements = this->allocate_elements_array(m_array.slots_usable()); + copy_n(other.m_elements, m_array.slots_set(), m_elements); + } + + VectorSet(VectorSet &&other) : m_array(std::move(other.m_array)), m_elements(other.m_elements) + { + other.m_elements = other.allocate_elements_array(other.m_array.slots_usable()); + } + + ~VectorSet() + { + destruct_n(m_elements, m_array.slots_usable()); + this->deallocate_elements_array(m_elements); + } + + VectorSet &operator=(const VectorSet &other) + { + if (this == &other) { + return *this; + } + this->~VectorSet(); + new (this) VectorSet(other); + return *this; + } + + VectorSet &operator=(VectorSet &&other) + { + if (this == &other) { + return *this; + } + this->~VectorSet(); + new (this) VectorSet(std::move(other)); + return *this; + } + /** * Allocate memory such that at least min_usable_slots can be added without having to grow again. */ @@ -203,17 +242,17 @@ template<typename T, typename Allocator = GuardedAllocator> class VectorSet { BLI_assert(this->contains(value)); ITER_SLOTS_BEGIN (value, m_array, , slot) { if (slot.has_value(value, m_elements)) { - uint old_index = m_elements.size() - 1; + uint old_index = m_array.slots_set() - 1; uint new_index = slot.index(); - m_elements.remove_and_reorder(new_index); + if (new_index < old_index) { + m_elements[new_index] = std::move(m_elements[old_index]); + this->update_slot_index(m_elements[new_index], old_index, new_index); + } + + destruct(m_elements + old_index); slot.set_dummy(); m_array.update__set_to_dummy(); - - if (old_index != new_index) { - T &moved_value = m_elements[new_index]; - this->update_slot_index(moved_value, old_index, new_index); - } return; } } @@ -226,11 +265,12 @@ template<typename T, typename Allocator = GuardedAllocator> class VectorSet { T pop() { BLI_assert(this->size() > 0); - T value = m_elements.pop_last(); - uint old_index = m_elements.size(); + uint index_to_pop = m_array.slots_usable() - 1; + T value = std::move(m_elements[index_to_pop]); + destruct(m_elements + index_to_pop); ITER_SLOTS_BEGIN (value, m_array, , slot) { - if (slot.has_index(old_index)) { + if (slot.has_index(index_to_pop)) { slot.set_dummy(); m_array.update__set_to_dummy(); return value; @@ -279,16 +319,17 @@ template<typename T, typename Allocator = GuardedAllocator> class VectorSet { const T *begin() const { - return m_elements.begin(); + return m_elements; } const T *end() const { - return m_elements.end(); + return m_elements + m_array.slots_set(); } const T &operator[](uint index) const { + BLI_assert(index <= m_array.slots_set()); return m_elements[index]; } @@ -299,7 +340,7 @@ template<typename T, typename Allocator = GuardedAllocator> class VectorSet { operator ArrayRef<T>() const { - return m_elements; + return ArrayRef<T>(m_elements, m_array.slots_set()); } void print_stats() const @@ -326,9 +367,9 @@ template<typename T, typename Allocator = GuardedAllocator> class VectorSet { template<typename ForwardT> void add_new_in_slot(Slot &slot, ForwardT &&value) { - uint index = m_elements.size(); + uint index = m_array.slots_set(); slot.set_index(index); - m_elements.append_unchecked(std::forward<ForwardT>(value)); + new (m_elements + index) T(std::forward<ForwardT>(value)); m_array.update__empty_to_set(); } @@ -341,14 +382,20 @@ template<typename T, typename Allocator = GuardedAllocator> class VectorSet { BLI_NOINLINE void grow(uint min_usable_slots) { + uint size = this->size(); + ArrayType new_array = m_array.init_reserved(min_usable_slots); + T *new_elements = this->allocate_elements_array(new_array.slots_usable()); - for (uint i = 0; i < m_elements.size(); i++) { + for (uint i : IndexRange(size)) { this->add_after_grow(i, new_array); } + uninitialized_relocate_n(m_elements, size, new_elements); + this->deallocate_elements_array(m_elements); + m_array = std::move(new_array); - m_elements.reserve(m_array.slots_usable()); + m_elements = new_elements; } void add_after_grow(uint index, ArrayType &new_array) @@ -365,15 +412,15 @@ template<typename T, typename Allocator = GuardedAllocator> class VectorSet { float compute_average_collisions() const { - if (m_elements.size() == 0) { + if (this->size() == 0) { return 0.0f; } uint collisions_sum = 0; - for (const T &value : m_elements) { + for (const T &value : this->as_ref()) { collisions_sum += this->count_collisions(value); } - return (float)collisions_sum / (float)m_elements.size(); + return (float)collisions_sum / (float)this->size(); } uint count_collisions(const T &value) const @@ -415,6 +462,16 @@ template<typename T, typename Allocator = GuardedAllocator> class VectorSet { } ITER_SLOTS_END; } + + T *allocate_elements_array(uint size) + { + return (T *)m_array.allocator().allocate_aligned((uint)sizeof(T) * size, alignof(T), __func__); + } + + void deallocate_elements_array(T *elements) + { + m_array.allocator().deallocate(elements); + } }; #undef ITER_SLOTS_BEGIN |