[Bf-blender-cvs] [614621747ea] master: BLI: optimize VectorSet implementation
Jacques Lucke
noreply at git.blender.org
Thu Apr 23 12:02:20 CEST 2020
Commit: 614621747ea214efc72a095fbef6695bf98a2bb4
Author: Jacques Lucke
Date: Thu Apr 23 11:57:58 2020 +0200
Branches: master
https://developer.blender.org/rB614621747ea214efc72a095fbef6695bf98a2bb4
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.
===================================================================
M source/blender/blenlib/BLI_open_addressing.hh
M source/blender/blenlib/BLI_vector.hh
M source/blender/blenlib/BLI_vector_set.hh
M tests/gtests/blenlib/BLI_vector_set_test.cc
===================================================================
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
diff --git a/tests/gtests/blenlib/BLI_vector_set_test.cc b/tests/gtests/blenlib/BLI_vector_set_test.cc
index 410e7a1b319..816d5d653a5 100644
--- a/tests/gtests/blenlib/BLI_vector_set_test.cc
+++ b/tests/gtests/blenlib/BLI_vector_set_test.cc
@@ -39,6 +39,17 @@ TEST(vector_set, Copy)
EXPECT_EQ(set2.index(2), 1);
}
+TEST(vector_set, CopyAssignment)
+{
+ IntVectorSet set1 = {1, 2, 3};
+ IntVectorSet set2 = {};
+ set2 = set1;
+ EXPECT_EQ(set1.size(), 3);
+ EXPECT_EQ(set2.size(), 3);
+ EXPECT_EQ(set1.index(2), 1);
+ EXPECT_EQ(set2.index(2), 1);
+}
+
TEST(vector_set, Move)
{
IntVectorSet set1 = {1, 2, 3};
@@ -47,6 +58,15 @@ TEST(vector_set, Move)
EXPECT_EQ(set2.size(), 3);
}
+TEST(vector_set, MoveAssignment)
+{
+ IntVectorSet set1 = {1, 2, 3};
+ IntVectorSet set2 = {};
+ set2 = std::move(set1);
+ EXPECT_EQ(set1.size(), 0);
+ EXPECT_EQ(set2.size(), 3);
+}
+
TEST(vector_set, AddNewIncreasesSize)
{
IntVectorSet set;
More information about the Bf-blender-cvs
mailing list