Commit: d8678e02ecec9375bec1dcf1388c6fc8b4ce3ad2 Author: Jacques Lucke Date: Tue Jun 9 10:10:56 2020 +0200 Branches: master https://developer.blender.org/rBd8678e02ecec9375bec1dcf1388c6fc8b4ce3ad2
BLI: generally improve C++ data structures The main focus here was to improve the docs significantly. Furthermore, I reimplemented `Set`, `Map` and `VectorSet`. They are now (usually) faster, simpler and more customizable. I also rewrote `Stack` to make it more efficient by avoiding unnecessary copies. Thanks to everyone who helped with constructive feedback. Approved by brecht and sybren. Differential Revision: https://developer.blender.org/D7931 =================================================================== M .clang-format M source/blender/blenlib/BLI_allocator.hh M source/blender/blenlib/BLI_array.hh M source/blender/blenlib/BLI_array_ref.hh M source/blender/blenlib/BLI_dot_export.hh M source/blender/blenlib/BLI_hash.hh A source/blender/blenlib/BLI_hash_tables.hh M source/blender/blenlib/BLI_index_range.hh M source/blender/blenlib/BLI_linear_allocator.hh M source/blender/blenlib/BLI_listbase_wrapper.hh M source/blender/blenlib/BLI_map.hh A source/blender/blenlib/BLI_map_slots.hh M source/blender/blenlib/BLI_math_bits.h M source/blender/blenlib/BLI_memory_utils.hh D source/blender/blenlib/BLI_open_addressing.hh M source/blender/blenlib/BLI_optional.hh A source/blender/blenlib/BLI_probing_strategies.hh M source/blender/blenlib/BLI_set.hh A source/blender/blenlib/BLI_set_slots.hh M source/blender/blenlib/BLI_stack.hh D source/blender/blenlib/BLI_string_map.hh M source/blender/blenlib/BLI_string_ref.hh M source/blender/blenlib/BLI_utility_mixins.hh M source/blender/blenlib/BLI_vector.hh M source/blender/blenlib/BLI_vector_set.hh A source/blender/blenlib/BLI_vector_set_slots.hh M source/blender/blenlib/CMakeLists.txt M source/blender/blenlib/intern/BLI_index_range.cc M source/blender/blenlib/intern/math_bits_inline.c M source/blender/depsgraph/intern/node/deg_node_id.cc M source/blender/depsgraph/intern/node/deg_node_id.h M source/blender/functions/FN_cpp_type.hh M tests/gtests/blenlib/BLI_array_ref_test.cc M tests/gtests/blenlib/BLI_array_test.cc M tests/gtests/blenlib/BLI_index_range_test.cc M tests/gtests/blenlib/BLI_linear_allocator_test.cc M tests/gtests/blenlib/BLI_map_test.cc A tests/gtests/blenlib/BLI_math_bits_test.cc M tests/gtests/blenlib/BLI_optional_test.cc M tests/gtests/blenlib/BLI_set_test.cc M tests/gtests/blenlib/BLI_stack_cxx_test.cc D tests/gtests/blenlib/BLI_string_map_test.cc M tests/gtests/blenlib/BLI_string_ref_test.cc D tests/gtests/blenlib/BLI_type_construct_mock.hh M tests/gtests/blenlib/BLI_vector_set_test.cc M tests/gtests/blenlib/BLI_vector_test.cc M tests/gtests/blenlib/CMakeLists.txt =================================================================== diff --git a/.clang-format b/.clang-format index 88d06a56417..cb5cdab496f 100644 --- a/.clang-format +++ b/.clang-format @@ -257,6 +257,10 @@ ForEachMacros: - SURFACE_QUAD_ITER_BEGIN - foreach - ED_screen_areas_iter + - SLOT_PROBING_BEGIN + - SET_SLOT_PROBING_BEGIN + - MAP_SLOT_PROBING_BEGIN + - VECTOR_SET_SLOT_PROBING_BEGIN # Use once we bump the minimum version to version 8. # # Without this string literals that in-line 'STRINGIFY' behave strangely (a bug?). diff --git a/source/blender/blenlib/BLI_allocator.hh b/source/blender/blenlib/BLI_allocator.hh index c52db4aab53..cf81b024277 100644 --- a/source/blender/blenlib/BLI_allocator.hh +++ b/source/blender/blenlib/BLI_allocator.hh @@ -19,14 +19,23 @@ /** \file * \ingroup bli * - * This file offers a couple of memory allocators that can be used with containers such as Vector - * and Map. Note that these allocators are not designed to work with standard containers like + * An `Allocator` can allocate and deallocate memory. It is used by containers such as BLI::Vector. + * The allocators defined in this file do not work with standard library containers such as * std::vector. * - * Also see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html for why the standard - * allocators are not a good fit applications like Blender. The current implementations in this - * file are fairly simple still, more complexity can be added when necessary. For now they do their - * job good enough. + * Every allocator has to implement two methods: + * void *allocate(size_t size, size_t alignment, const char *name); + * void deallocate(void *ptr); + * + * We don't use the std::allocator interface, because it does more than is really necessary for an + * allocator and has some other quirks. It mixes the concepts of allocation and construction. It is + * essentially forced to be a template, even though the allocator should not care about the type. + * Also see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html#std_allocator. Some + * of these aspects have been improved in new versions of C++, so we might have to reevaluate the + * strategy later on. + * + * The allocator interface dictated by this file is very simplistic, but for now that is all we + * need. More complexity can be added when it seems necessary. */ #include <algorithm> @@ -40,18 +49,14 @@ namespace BLI { /** - * Use Blenders guarded allocator (aka MEM_malloc). This should always be used except there is a + * Use Blender's guarded allocator (aka MEM_*). This should always be used except there is a * good reason not to use it. */ class GuardedAllocator { public: - void *allocate(uint size, const char *name) - { - return MEM_mallocN(size, name); - } - - void *allocate_aligned(uint size, uint alignment, const char *name) + void *allocate(size_t size, size_t alignment, const char *name) { + /* Should we use MEM_mallocN, when alignment is small? If yes, how small must alignment be? */ return MEM_mallocN_aligned(size, alignment, name); } @@ -62,8 +67,9 @@ class GuardedAllocator { }; /** - * This is a simple wrapper around malloc/free. Only use this when the GuardedAllocator cannot be - * used. This can be the case when the allocated element might live longer than Blenders Allocator. + * This is a wrapper around malloc/free. Only use this when the GuardedAllocator cannot be + * used. This can be the case when the allocated memory might live longer than Blender's + * allocator. For example, when the memory is owned by a static variable. */ class RawAllocator { private: @@ -72,14 +78,7 @@ class RawAllocator { }; public: - void *allocate(uint size, const char *UNUSED(name)) - { - void *ptr = malloc(size + sizeof(MemHead)); - ((MemHead *)ptr)->offset = sizeof(MemHead); - return POINTER_OFFSET(ptr, sizeof(MemHead)); - } - - void *allocate_aligned(uint size, uint alignment, const char *UNUSED(name)) + void *allocate(size_t size, size_t alignment, const char *UNUSED(name)) { BLI_assert(is_power_of_2_i((int)alignment)); void *ptr = malloc(size + alignment + sizeof(MemHead)); diff --git a/source/blender/blenlib/BLI_array.hh b/source/blender/blenlib/BLI_array.hh index 9dd8341aa76..09eeb321abf 100644 --- a/source/blender/blenlib/BLI_array.hh +++ b/source/blender/blenlib/BLI_array.hh @@ -19,8 +19,23 @@ /** \file * \ingroup bli * - * This is a container that contains a fixed size array. Note however, the size of the array is not - * a template argument. Instead it can be specified at the construction time. + * A `BLI::Array<T>` is a container for a fixed size array the size of which is NOT known at + * compile time. + * + * If the size is known at compile time, `std::array<T, N>` should be used instead. + * + * BLI::Array should usually be used instead of BLI::Vector whenever the number of elements is + * known at construction time. Note however, that BLI::Array will default construct all elements + * when initialized with the size-constructor. For trivial types, this does nothing. In all other + * cases, this adds overhead. If this becomes a problem, a different constructor which does not do + * default construction can be added. + * + * A main benefit of using Array over Vector is that it expresses the intent of the developer + * better. It indicates that the size of the data structure is not expected to change. Furthermore, + * you can be more certain that an array does not overallocate. + * + * BLI::Array supports small object optimization to improve performance when the size turns out to + * be small at run-time. */ #include "BLI_allocator.hh" @@ -31,42 +46,83 @@ namespace BLI { -template<typename T, uint InlineBufferCapacity = 4, typename Allocator = GuardedAllocator> +template< + /** + * The type of the values stored in the array. + */ + typename T, + /** + * The number of values that can be stored in the array, without doing a heap allocation. + * + * When T is large, the small buffer optimization is disabled by default to avoid large + * unexpected allocations on the stack. It can still be enabled explicitely though. + */ + uint InlineBufferCapacity = (sizeof(T) < 100) ? 4 : 0, + /** + * The allocator used by this array. Should rarely be changed, except when you don't want that + * MEM_* functions are used internally. + */ + typename Allocator = GuardedAllocator> class Array { private: + /** The beginning of the array. It might point into the inline buffer. */ T *m_data; + + /** Number of elements in the array. */ uint m_size; + + /** Used for allocations when the inline buffer is too small. */ Allocator m_allocator; - AlignedBuffer<sizeof(T) * InlineBufferCapacity, alignof(T)> m_inline_storage; + + /** A placeholder buffer that will remain uninitialized until it is used. */ + AlignedBuffer<sizeof(T) * InlineBufferCapacity, alignof(T)> m_inline_buffer; public: + /** + * By default an empty array is created. + */ Array() { - m_data = this->inline_storage(); + m_data = this->inline_buffer(); m_size = 0; } + /** + * Create a new array that contains copies of all values. + */ Array(ArrayRef<T> values) { m_size = values.size(); m_data = this->get_buffer_for_size(values.size()); - uninitialized_copy_n(values.begin(), m_size, m_data); + uninitialized_copy_n(values.data(), m_size, m_data); } + /** + * Create a new array that contains copies of all values. + */ Array(const std::initializer_list<T> &values) : Array(ArrayRef<T>(values)) { } + /** + * Create a new array with the given size. All values will be default constructed. For trivial + * types like int, default construction does nothing. + * + * We might want another version of this in the future, that does not do default construction + * even for non-trivial types. This should not be the default though, because one can easily mess + * up when dealing with uninitialized memory. + */ explicit Array(uint size) { m_size = size; m_data = this->get_buffer_for_size(size); - - for (uint i = 0; i < m_size; i++) { - new (m_data + i) T(); - } + default_construct_n(m_data, size); } + /** + * Create a new array with the given size. All values will be initialized by copying the given + * default. + */ Array(uint size, const T &value) { m_size = size; @@ -74,21 +130,19 @@ class Array { uninitialized_fill_n(m_data, m_size, value); } - Array(const Array &other) + Array(const Array &other) : m_allocator(other.m_allocator) { m_size = other.size(); - m_allocator = other.m_allocator; m_data = this->get_buffer_for_size(other.size()); - uninitialized_copy_n(other.begin(), m_size, m_data); + uninitialized_copy_n(other.data(), m_size, m_data); } - Array(Array &&other) noexcept + Array(Array &&other) noexcept : m_allocator(other.m_allocator) { m_size = other.m_size; - m_allocator = other.m_allocator; - if (!other.uses_inline_storage()) { + if (!other.uses_inline_buffer()) { m_data = other.m_data; } else { @@ -96,14 +150,14 @@ class Array { uninitialized_relocate_n(other.m_data, m_size, m_data); } - other.m_data = other.inline_storage(); + other.m_data = other.inline_buffer(); other.m_size = 0; } ~Array() { destruct_n(m_data, m_size); - if (!this->uses_inline_storage()) { + if (!this->uses_inline_buffer()) { m_allocator.deallocate((void *)m_data); } } @@ -162,21 +216,50 @@ class Array { return m_data[index]; } + /** + * Returns the number of elements in the array. + */ uint size() const { return m_size; } + /** + * Returns true when the number of elements in the array is zero. + */ + bool is_empty() const + { + return m_size == 0; + } + + /** + * Copies the value to all indices in the array. + */ void fill(const T &value) { - MutableArrayRef<T>(*this).fill(value); + initialized_fill_n(m_data, m_size, value); } + /** + * Copies the value to the given indices in the array @@ Diff output truncated at 10240 characters. @@ _______________________________________________ Bf-blender-cvs mailing list [email protected] https://lists.blender.org/mailman/listinfo/bf-blender-cvs
