From 8f5a4a4da33375b591dd77e424096878ff2e2aaf Mon Sep 17 00:00:00 2001 From: Jacques Lucke Date: Thu, 23 Apr 2020 20:05:53 +0200 Subject: BLI: various data structure improvements * Rename template parameter N to InlineBufferCapacity * Expose InlineBufferCapacity parameter for Set and Map * Add some comments * Fixed an error that I introduced recently --- source/blender/blenlib/BLI_array.hh | 7 +- source/blender/blenlib/BLI_map.hh | 31 +++++---- source/blender/blenlib/BLI_open_addressing.hh | 97 ++++++++++++++++++++++----- source/blender/blenlib/BLI_set.hh | 25 +++---- source/blender/blenlib/BLI_stack.hh | 5 +- source/blender/blenlib/BLI_vector.hh | 25 ++++--- source/blender/blenlib/BLI_vector_set.hh | 14 ++-- 7 files changed, 138 insertions(+), 66 deletions(-) (limited to 'source/blender/blenlib') diff --git a/source/blender/blenlib/BLI_array.hh b/source/blender/blenlib/BLI_array.hh index c6536f6c1ed..61d57599619 100644 --- a/source/blender/blenlib/BLI_array.hh +++ b/source/blender/blenlib/BLI_array.hh @@ -31,12 +31,13 @@ namespace BLI { -template class Array { +template +class Array { private: T *m_data; uint m_size; Allocator m_allocator; - AlignedBuffer m_inline_storage; + AlignedBuffer m_inline_storage; public: Array() @@ -204,7 +205,7 @@ template class Ar private: T *get_buffer_for_size(uint size) { - if (size <= N) { + if (size <= InlineBufferCapacity) { return this->inline_storage(); } else { diff --git a/source/blender/blenlib/BLI_map.hh b/source/blender/blenlib/BLI_map.hh index 626c971c959..4e8c9f67338 100644 --- a/source/blender/blenlib/BLI_map.hh +++ b/source/blender/blenlib/BLI_map.hh @@ -53,7 +53,11 @@ namespace BLI { // clang-format on -template class Map { +template +class Map { private: static constexpr uint OFFSET_MASK = 3; static constexpr uint OFFSET_SHIFT = 2; @@ -65,8 +69,8 @@ template static constexpr uint8_t IS_DUMMY = 2; uint8_t m_status[4]; - char m_keys[4 * sizeof(KeyT)]; - char m_values[4 * sizeof(ValueT)]; + AlignedBuffer<4 * sizeof(KeyT), alignof(KeyT)> m_keys_buffer; + AlignedBuffer<4 * sizeof(ValueT), alignof(ValueT)> m_values_buffer; public: static constexpr uint slots_per_item = 4; @@ -134,12 +138,12 @@ template KeyT *key(uint offset) const { - return (KeyT *)(m_keys + offset * sizeof(KeyT)); + return (KeyT *)m_keys_buffer.ptr() + offset; } ValueT *value(uint offset) const { - return (ValueT *)(m_values + offset * sizeof(ValueT)); + return (ValueT *)m_values_buffer.ptr() + offset; } template @@ -167,7 +171,7 @@ template } }; - using ArrayType = OpenAddressingArray; + using ArrayType = OpenAddressingArray; ArrayType m_array; public: @@ -351,6 +355,12 @@ template ITER_SLOTS_END(offset); } + ValueT *lookup_ptr(const KeyT &key) + { + const Map *const_this = this; + return const_cast(const_this->lookup_ptr(key)); + } + /** * Lookup the value that corresponds to the key. * Asserts when the key does not exist. @@ -362,12 +372,6 @@ template return *ptr; } - ValueT *lookup_ptr(const KeyT &key) - { - const Map *const_this = this; - return const_cast(const_this->lookup_ptr(key)); - } - ValueT &lookup(const KeyT &key) { const Map *const_this = this; @@ -413,6 +417,9 @@ template return m_array.slots_set(); } + /** + * Calls the given function for each key-value-pair. + */ template void foreach_item(const FuncT &func) const { for (const Item &item : m_array) { diff --git a/source/blender/blenlib/BLI_open_addressing.hh b/source/blender/blenlib/BLI_open_addressing.hh index 7b8adcf9bd2..d466a915b2f 100644 --- a/source/blender/blenlib/BLI_open_addressing.hh +++ b/source/blender/blenlib/BLI_open_addressing.hh @@ -40,15 +40,76 @@ namespace BLI { -template +/** \name Constexpr utility functions. + * \{ */ + +inline constexpr int is_power_of_2_i_constexpr(int n) +{ + return (n & (n - 1)) == 0; +} + +inline constexpr uint32_t log2_floor_u_constexpr(uint32_t x) +{ + return x <= 1 ? 0 : 1 + log2_floor_u_constexpr(x >> 1); +} + +inline constexpr uint32_t log2_ceil_u_constexpr(uint32_t x) +{ + return (is_power_of_2_i_constexpr((int)x)) ? log2_floor_u_constexpr(x) : + log2_floor_u_constexpr(x) + 1; +} + +template inline constexpr IntT ceil_division(IntT x, IntT y) +{ + BLI_STATIC_ASSERT(!std::is_signed::value, ""); + return x / y + ((x % y) != 0); +} + +template inline constexpr IntT floor_division(IntT x, IntT y) +{ + BLI_STATIC_ASSERT(!std::is_signed::value, ""); + return x / y; +} + +inline constexpr uint8_t compute_item_exponent(uint32_t min_usable_slots, + uint32_t slots_per_item, + uint32_t max_load_factor_numerator, + uint32_t max_load_factor_denominator) +{ + // uint64_t min_total_slots = ceil_division((uint64_t)min_usable_slots * + // (uint64_t)max_load_factor_denominator, + // (uint64_t)max_load_factor_numerator); + // uint32_t min_total_items = (uint32_t)ceil_division(min_total_slots, (uint64_t)slots_per_item); + // uint8_t item_exponent = (uint8_t)log2_ceil_u_constexpr(min_total_items); + // return item_exponent; + + return (uint8_t)log2_ceil_u_constexpr((uint32_t)ceil_division( + ceil_division((uint64_t)min_usable_slots * (uint64_t)max_load_factor_denominator, + (uint64_t)max_load_factor_numerator), + (uint64_t)slots_per_item)); +} + +/** \} */ + +template class OpenAddressingArray { private: - static constexpr uint32_t slots_per_item = Item::slots_per_item; - static constexpr float max_load_factor = 0.5f; + static constexpr uint32_t s_max_load_factor_numerator = 1; + static constexpr uint32_t s_max_load_factor_denominator = 2; + static constexpr uint32_t s_slots_per_item = Item::slots_per_item; + + static constexpr uint8_t s_small_storage_item_exponent = compute_item_exponent( + MinUsableSlotsInSmallStorage, + s_slots_per_item, + s_max_load_factor_numerator, + s_max_load_factor_denominator); + static constexpr uint32_t s_items_in_small_storage = 1u << s_small_storage_item_exponent; /* Invariants: * 2^m_item_exponent = m_item_amount - * m_item_amount * slots_per_item = m_slots_total + * m_item_amount * s_slots_per_item = m_slots_total * m_slot_mask = m_slots_total - 1 * m_slots_set_or_dummy < m_slots_total */ @@ -70,20 +131,23 @@ 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<(uint)sizeof(Item) * ItemsInSmallStorage, (uint)alignof(Item)> m_local_storage; + AlignedBuffer<(uint)sizeof(Item) * s_items_in_small_storage, (uint)alignof(Item)> + m_local_storage; public: - explicit OpenAddressingArray(uint8_t item_exponent = 0) + explicit OpenAddressingArray(uint8_t item_exponent = s_small_storage_item_exponent) { - m_slots_total = ((uint32_t)1 << item_exponent) * slots_per_item; + m_item_exponent = item_exponent; + m_item_amount = 1u << item_exponent; + m_slots_total = m_item_amount * s_slots_per_item; + m_slot_mask = m_slots_total - 1; m_slots_set_or_dummy = 0; m_slots_dummy = 0; - m_slots_usable = (uint32_t)((float)m_slots_total * max_load_factor); - m_slot_mask = m_slots_total - 1; - m_item_amount = m_slots_total / slots_per_item; - m_item_exponent = item_exponent; + m_slots_usable = (uint32_t)floor_division((uint64_t)m_slots_total * + (uint64_t)s_max_load_factor_numerator, + (uint64_t)s_max_load_factor_denominator); - if (m_item_amount <= ItemsInSmallStorage) { + if (m_item_amount <= s_items_in_small_storage) { m_items = this->small_storage(); } else { @@ -118,7 +182,7 @@ class OpenAddressingArray { m_item_amount = other.m_item_amount; m_item_exponent = other.m_item_exponent; - if (m_item_amount <= ItemsInSmallStorage) { + if (m_item_amount <= s_items_in_small_storage) { m_items = this->small_storage(); } else { @@ -180,9 +244,10 @@ class OpenAddressingArray { * empty. */ OpenAddressingArray init_reserved(uint32_t min_usable_slots) const { - float min_total_slots = (float)min_usable_slots / max_load_factor; - uint32_t min_total_items = (uint32_t)std::ceil(min_total_slots / (float)slots_per_item); - uint8_t item_exponent = (uint8_t)log2_ceil_u(min_total_items); + uint8_t item_exponent = compute_item_exponent(min_usable_slots, + s_slots_per_item, + s_max_load_factor_numerator, + s_max_load_factor_denominator); OpenAddressingArray grown(item_exponent); grown.m_slots_set_or_dummy = this->slots_set(); return grown; diff --git a/source/blender/blenlib/BLI_set.hh b/source/blender/blenlib/BLI_set.hh index 2ef92bf1c48..b09dd910007 100644 --- a/source/blender/blenlib/BLI_set.hh +++ b/source/blender/blenlib/BLI_set.hh @@ -50,7 +50,8 @@ namespace BLI { // clang-format on -template class Set { +template +class Set { private: static constexpr uint OFFSET_MASK = 3; static constexpr uint OFFSET_SHIFT = 2; @@ -62,7 +63,7 @@ template class Set { static constexpr uint8_t IS_DUMMY = 2; uint8_t m_status[4]; - char m_values[4 * sizeof(T)]; + AlignedBuffer<4 * sizeof(T), alignof(T)> m_buffer; public: static constexpr uint slots_per_item = 4; @@ -114,7 +115,7 @@ template class Set { T *value(uint offset) const { - return (T *)(m_values + offset * sizeof(T)); + return (T *)m_buffer.ptr() + offset; } template void store(uint offset, ForwardT &&value) @@ -153,8 +154,8 @@ template class Set { } }; - using ArrayType = OpenAddressingArray; - ArrayType m_array = OpenAddressingArray(); + using ArrayType = OpenAddressingArray; + ArrayType m_array; public: Set() = default; @@ -202,6 +203,7 @@ template class Set { /** * Add a new value to the set if it does not exist yet. + * Returns true of the value has been newly added. */ bool add(const T &value) { @@ -266,16 +268,9 @@ template class Set { ITER_SLOTS_END(offset); } - Vector to_small_vector() const - { - Vector vector; - vector.reserve(this->size()); - for (const T &value : *this) { - vector.append(value); - } - return vector; - } - + /** + * Get the amount of values stored in the set. + */ uint32_t size() const { return m_array.slots_set(); diff --git a/source/blender/blenlib/BLI_stack.hh b/source/blender/blenlib/BLI_stack.hh index a0e8cec3b6f..7f1f9f9cc10 100644 --- a/source/blender/blenlib/BLI_stack.hh +++ b/source/blender/blenlib/BLI_stack.hh @@ -27,9 +27,10 @@ namespace BLI { -template class Stack { +template +class Stack { private: - Vector m_elements; + Vector m_elements; public: Stack() = default; diff --git a/source/blender/blenlib/BLI_vector.hh b/source/blender/blenlib/BLI_vector.hh index 450242a349a..40dc876d5a5 100644 --- a/source/blender/blenlib/BLI_vector.hh +++ b/source/blender/blenlib/BLI_vector.hh @@ -43,13 +43,14 @@ namespace BLI { -template class Vector { +template +class Vector { private: T *m_begin; T *m_end; T *m_capacity_end; Allocator m_allocator; - AlignedBuffer<(uint)sizeof(T) * N, (uint)alignof(T)> m_small_buffer; + AlignedBuffer<(uint)sizeof(T) * InlineBufferCapacity, (uint)alignof(T)> m_small_buffer; #ifndef NDEBUG /* Storing size in debug builds, because it makes debugging much easier sometimes. */ @@ -70,7 +71,7 @@ template class Ve { m_begin = this->small_buffer(); m_end = m_begin; - m_capacity_end = m_begin + N; + m_capacity_end = m_begin + InlineBufferCapacity; UPDATE_VECTOR_SIZE(this); } @@ -140,7 +141,7 @@ template class Ve /** * Create a copy of another vector. * The other vector will not be changed. - * If the other vector has less than N elements, no allocation will be made. + * If the other vector has less than InlineBufferCapacity elements, no allocation will be made. */ Vector(const Vector &other) : m_allocator(other.m_allocator) { @@ -164,11 +165,11 @@ template class Ve uint size = other.size(); if (other.is_small()) { - if (size <= N) { + if (size <= InlineBufferCapacity) { /* Copy between inline buffers. */ m_begin = this->small_buffer(); m_end = m_begin + size; - m_capacity_end = m_begin + N; + m_capacity_end = m_begin + InlineBufferCapacity; uninitialized_relocate_n(other.m_begin, size, m_begin); } else { @@ -283,7 +284,7 @@ template class Ve m_begin = this->small_buffer(); m_end = m_begin; - m_capacity_end = m_begin + N; + m_capacity_end = m_begin + InlineBufferCapacity; UPDATE_VECTOR_SIZE(this); } @@ -578,7 +579,8 @@ template class Ve std::cout << "Small Vector at " << (void *)this << ":" << std::endl; std::cout << " Elements: " << this->size() << std::endl; std::cout << " Capacity: " << (m_capacity_end - m_begin) << std::endl; - std::cout << " Small Elements: " << N << " Size on Stack: " << sizeof(*this) << std::endl; + std::cout << " Small Elements: " << InlineBufferCapacity + << " Size on Stack: " << sizeof(*this) << std::endl; } private: @@ -634,9 +636,9 @@ template class Ve uint size = other.size(); uint capacity = size; - if (size <= N) { + if (size <= InlineBufferCapacity) { m_begin = this->small_buffer(); - capacity = N; + capacity = InlineBufferCapacity; } else { m_begin = (T *)m_allocator.allocate_aligned( @@ -658,7 +660,8 @@ template class Ve * Use when the vector is used in the local scope of a function. It has a larger inline storage by * default to make allocations less likely. */ -template using ScopedVector = Vector; +template +using ScopedVector = Vector; } /* namespace BLI */ diff --git a/source/blender/blenlib/BLI_vector_set.hh b/source/blender/blenlib/BLI_vector_set.hh index b3f19d32060..6e1ab823e86 100644 --- a/source/blender/blenlib/BLI_vector_set.hh +++ b/source/blender/blenlib/BLI_vector_set.hh @@ -150,7 +150,7 @@ template class VectorSet { ~VectorSet() { - destruct_n(m_elements, m_array.slots_usable()); + destruct_n(m_elements, this->size()); this->deallocate_elements_array(m_elements); } @@ -242,7 +242,7 @@ template 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_array.slots_set() - 1; + uint old_index = this->size() - 1; uint new_index = slot.index(); if (new_index < old_index) { @@ -265,7 +265,7 @@ template class VectorSet { T pop() { BLI_assert(this->size() > 0); - uint index_to_pop = m_array.slots_usable() - 1; + uint index_to_pop = this->size() - 1; T value = std::move(m_elements[index_to_pop]); destruct(m_elements + index_to_pop); @@ -324,12 +324,12 @@ template class VectorSet { const T *end() const { - return m_elements + m_array.slots_set(); + return m_elements + this->size(); } const T &operator[](uint index) const { - BLI_assert(index <= m_array.slots_set()); + BLI_assert(index <= this->size()); return m_elements[index]; } @@ -340,7 +340,7 @@ template class VectorSet { operator ArrayRef() const { - return ArrayRef(m_elements, m_array.slots_set()); + return ArrayRef(m_elements, this->size()); } void print_stats() const @@ -367,7 +367,7 @@ template class VectorSet { template void add_new_in_slot(Slot &slot, ForwardT &&value) { - uint index = m_array.slots_set(); + uint index = this->size(); slot.set_index(index); new (m_elements + index) T(std::forward(value)); m_array.update__empty_to_set(); -- cgit v1.2.3