[Bf-blender-cvs] [2ae80403739] functions-experimental-refactor: improve aligned allocation in monotonic allocator
Jacques Lucke
noreply at git.blender.org
Tue Nov 5 15:55:12 CET 2019
Commit: 2ae804037398383c62bc95dacfb0006e5a7de148
Author: Jacques Lucke
Date: Tue Nov 5 15:32:53 2019 +0100
Branches: functions-experimental-refactor
https://developer.blender.org/rB2ae804037398383c62bc95dacfb0006e5a7de148
improve aligned allocation in monotonic allocator
===================================================================
M source/blender/blenlib/BLI_monotonic_allocator.h
M source/blender/functions2/FN_attributes_ref.h
M source/blender/functions2/FN_generic_vector_array.h
M source/blender/simulations/bparticles/node_frontend.cpp
A tests/gtests/blenlib/BLI_monotonic_allocator_test.cc
M tests/gtests/blenlib/CMakeLists.txt
===================================================================
diff --git a/source/blender/blenlib/BLI_monotonic_allocator.h b/source/blender/blenlib/BLI_monotonic_allocator.h
index b700aa413bd..74fb6ea1d72 100644
--- a/source/blender/blenlib/BLI_monotonic_allocator.h
+++ b/source/blender/blenlib/BLI_monotonic_allocator.h
@@ -29,7 +29,7 @@
namespace BLI {
-template<typename Allocator = GuardedAllocator>
+template<uint N = 0, typename Allocator = GuardedAllocator>
class MonotonicAllocator : NonCopyable, NonMovable {
private:
Allocator m_allocator;
@@ -39,9 +39,13 @@ class MonotonicAllocator : NonCopyable, NonMovable {
uint m_remaining_capacity;
uint m_next_min_alloc_size;
+ AlignedBuffer<N, 8> m_inline_buffer;
+
public:
MonotonicAllocator()
- : m_current_buffer(nullptr), m_remaining_capacity(0), m_next_min_alloc_size(16)
+ : m_current_buffer(m_inline_buffer.ptr()),
+ m_remaining_capacity(N),
+ m_next_min_alloc_size(N * 2)
{
}
@@ -52,31 +56,9 @@ class MonotonicAllocator : NonCopyable, NonMovable {
}
}
- void *allocate(uint size)
- {
- if (size <= m_remaining_capacity) {
- void *ptr = m_current_buffer;
- m_remaining_capacity -= size;
- m_current_buffer = POINTER_OFFSET(ptr, size);
- return ptr;
- }
- else {
- uint byte_size = std::max({m_next_min_alloc_size, size, m_allocator.min_allocated_size()});
-
- void *ptr = m_allocator.allocate(byte_size, __func__);
- m_pointers.append(ptr);
-
- m_current_buffer = POINTER_OFFSET(ptr, size);
- m_next_min_alloc_size = byte_size * 2;
- m_remaining_capacity = byte_size - size;
-
- return ptr;
- }
- }
-
template<typename T> T *allocate()
{
- return (T *)this->allocate(sizeof(T));
+ return (T *)this->allocate(sizeof(T), alignof(T));
}
template<typename T> MutableArrayRef<T> allocate_array(uint length)
@@ -84,16 +66,39 @@ class MonotonicAllocator : NonCopyable, NonMovable {
return MutableArrayRef<T>((T *)this->allocate(sizeof(T) * length), length);
}
- void *allocate_aligned(uint size, uint alignment)
+ void *allocate(uint size, uint alignment = 4)
{
- /* TODO: Don't overallocate when not necessary. */
+ BLI_assert(alignment >= 1);
BLI_assert(is_power_of_2_i(alignment));
- size_t space = size + alignment - 1;
- void *ptr = this->allocate(space);
- void *aligned_ptr = std::align(alignment, size, ptr, space);
- BLI_assert(aligned_ptr != nullptr);
- BLI_assert((POINTER_AS_UINT(aligned_ptr) & (alignment - 1)) == 0);
- return aligned_ptr;
+
+ uintptr_t alignment_mask = alignment - 1;
+
+ uintptr_t current_buffer = (uintptr_t)m_current_buffer;
+ uintptr_t potential_allocation_begin = (current_buffer + alignment - 1) & ~alignment_mask;
+ uintptr_t potential_allocation_end = potential_allocation_begin + size;
+ uintptr_t required_size = potential_allocation_end - current_buffer;
+
+ if (required_size <= m_remaining_capacity) {
+ m_remaining_capacity -= required_size;
+ m_current_buffer = (void *)potential_allocation_end;
+ return (void *)potential_allocation_begin;
+ }
+ else {
+ this->allocate_new_buffer(size + alignment);
+ return this->allocate(size, alignment);
+ }
+ };
+
+ private:
+ void allocate_new_buffer(uint min_allocation_size)
+ {
+ uint size_in_bytes = std::max(min_allocation_size, m_next_min_alloc_size);
+ m_next_min_alloc_size *= 2;
+
+ void *buffer = m_allocator.allocate(size_in_bytes, __func__);
+ m_pointers.append(buffer);
+ m_remaining_capacity = size_in_bytes;
+ m_current_buffer = buffer;
}
};
diff --git a/source/blender/functions2/FN_attributes_ref.h b/source/blender/functions2/FN_attributes_ref.h
index dab294d1cc6..d4a2672032d 100644
--- a/source/blender/functions2/FN_attributes_ref.h
+++ b/source/blender/functions2/FN_attributes_ref.h
@@ -346,7 +346,7 @@ class AttributesDefaults : BLI::NonCopyable, BLI::NonMovable {
m_index_by_name.add_new(name, index);
const CPPType &type = GET_TYPE<T>();
m_type_by_index.append(&type);
- void *value_buffer = m_allocator.allocate_aligned(type.size(), type.alignment());
+ void *value_buffer = m_allocator.allocate(type.size(), type.alignment());
new (value_buffer) T(std::move(value));
m_values.append(value_buffer);
}
diff --git a/source/blender/functions2/FN_generic_vector_array.h b/source/blender/functions2/FN_generic_vector_array.h
index 64c280435f3..c1f43dbdd91 100644
--- a/source/blender/functions2/FN_generic_vector_array.h
+++ b/source/blender/functions2/FN_generic_vector_array.h
@@ -177,8 +177,8 @@ class GenericVectorArray : BLI::NonCopyable, BLI::NonMovable {
{
BLI_assert(m_capacities[index] < min_capacity);
min_capacity = power_of_2_max_u(min_capacity);
- void *new_buffer = m_elements_allocator.allocate_aligned(m_element_size * min_capacity,
- m_type.alignment());
+ void *new_buffer = m_elements_allocator.allocate(m_element_size * min_capacity,
+ m_type.alignment());
for (uint i = 0; i < m_lengths[index]; i++) {
void *src = POINTER_OFFSET(m_starts[index], m_element_size * i);
diff --git a/source/blender/simulations/bparticles/node_frontend.cpp b/source/blender/simulations/bparticles/node_frontend.cpp
index a5712dc77ed..f0d8ef4fc97 100644
--- a/source/blender/simulations/bparticles/node_frontend.cpp
+++ b/source/blender/simulations/bparticles/node_frontend.cpp
@@ -88,7 +88,7 @@ class VTreeData {
template<typename T, typename... Args> destruct_ptr<T> construct_new(Args &&... args)
{
- void *buffer = m_allocator.allocate_aligned(sizeof(T), alignof(T));
+ void *buffer = m_allocator.allocate(sizeof(T), alignof(T));
T *value = new (buffer) T(std::forward<Args>(args)...);
return destruct_ptr<T>(value);
}
diff --git a/tests/gtests/blenlib/BLI_monotonic_allocator_test.cc b/tests/gtests/blenlib/BLI_monotonic_allocator_test.cc
new file mode 100644
index 00000000000..82261027c1a
--- /dev/null
+++ b/tests/gtests/blenlib/BLI_monotonic_allocator_test.cc
@@ -0,0 +1,48 @@
+#include "testing/testing.h"
+#include "BLI_monotonic_allocator.h"
+
+using namespace BLI;
+
+static bool is_aligned(void *ptr, uint alignment)
+{
+ BLI_assert(is_power_of_2_i(alignment));
+ return (POINTER_AS_UINT(ptr) & (alignment - 1)) == 0;
+}
+
+TEST(monotonic_allocator, AllocationAlignment)
+{
+ MonotonicAllocator<> allocator;
+
+ EXPECT_TRUE(is_aligned(allocator.allocate(10, 4), 4));
+ EXPECT_TRUE(is_aligned(allocator.allocate(10, 4), 4));
+ EXPECT_TRUE(is_aligned(allocator.allocate(10, 4), 4));
+ EXPECT_TRUE(is_aligned(allocator.allocate(10, 8), 8));
+ EXPECT_TRUE(is_aligned(allocator.allocate(10, 4), 4));
+ EXPECT_TRUE(is_aligned(allocator.allocate(10, 16), 16));
+ EXPECT_TRUE(is_aligned(allocator.allocate(10, 4), 4));
+ EXPECT_TRUE(is_aligned(allocator.allocate(10, 64), 64));
+ EXPECT_TRUE(is_aligned(allocator.allocate(10, 64), 64));
+ EXPECT_TRUE(is_aligned(allocator.allocate(10, 8), 8));
+ EXPECT_TRUE(is_aligned(allocator.allocate(10, 128), 128));
+}
+
+TEST(monotonic_allocator, PackedAllocation)
+{
+ MonotonicAllocator<256> allocator;
+ allocator.allocate(32, 32);
+
+ uintptr_t ptr1 = (uintptr_t)allocator.allocate(10, 4); /* 0 - 10 */
+ uintptr_t ptr2 = (uintptr_t)allocator.allocate(10, 4); /* 12 - 22 */
+ uintptr_t ptr3 = (uintptr_t)allocator.allocate(8, 32); /* 32 - 40 */
+ uintptr_t ptr4 = (uintptr_t)allocator.allocate(16, 8); /* 40 - 56 */
+ uintptr_t ptr5 = (uintptr_t)allocator.allocate(1, 8); /* 56 - 57 */
+ uintptr_t ptr6 = (uintptr_t)allocator.allocate(1, 4); /* 60 - 61 */
+ uintptr_t ptr7 = (uintptr_t)allocator.allocate(1, 1); /* 61 - 62 */
+
+ EXPECT_EQ(ptr2 - ptr1, 12); /* 12 - 0 = 12 */
+ EXPECT_EQ(ptr3 - ptr2, 20); /* 32 - 12 = 20 */
+ EXPECT_EQ(ptr4 - ptr3, 8); /* 40 - 32 = 8 */
+ EXPECT_EQ(ptr5 - ptr4, 16); /* 56 - 40 = 16 */
+ EXPECT_EQ(ptr6 - ptr5, 4); /* 60 - 56 = 4 */
+ EXPECT_EQ(ptr7 - ptr6, 1); /* 61 - 60 = 1 */
+}
diff --git a/tests/gtests/blenlib/CMakeLists.txt b/tests/gtests/blenlib/CMakeLists.txt
index 3b401da1aaf..9327bb790f7 100644
--- a/tests/gtests/blenlib/CMakeLists.txt
+++ b/tests/gtests/blenlib/CMakeLists.txt
@@ -62,6 +62,7 @@ BLENDER_TEST(BLI_math_base "bf_blenlib")
BLENDER_TEST(BLI_math_color "bf_blenlib")
BLENDER_TEST(BLI_math_geom "bf_blenlib")
BLENDER_TEST(BLI_memiter "bf_blenlib")
+BLENDER_TEST(BLI_monotonic_allocator "bf_blenlib")
BLENDER_TEST(BLI_multi_vector "bf_blenlib")
BLENDER_TEST(BLI_optional "bf_blenlib")
BLENDER_TEST(BLI_path_util "${BLI_path_util_extra_libs}")
More information about the Bf-blender-cvs
mailing list