diff options
author | Clément Foucault <foucault.clem@gmail.com> | 2022-09-06 18:20:29 +0300 |
---|---|---|
committer | Clément Foucault <foucault.clem@gmail.com> | 2022-09-06 18:51:25 +0300 |
commit | e047b2618a48a7d88ac606d6eb280b52c9c72ebd (patch) | |
tree | 9d827bf3e0800135fa11dfd87445e7dfafd3f920 | |
parent | 3484c6d4f116409ca55cdc46325f4703d21c20c8 (diff) |
BLI: Add new `blender::Pool` container
A `blender::Pool` can construct and destruct elements without reordering. Freed items memory
will be reused by next allocations.
Elements are allocated in chunks to reduce memory fragmentation and avoid reallocation.
Reviewed By: JacquesLucke
Differential Revision: https://developer.blender.org/D15894
-rw-r--r-- | source/blender/blenlib/BLI_pool.hh | 84 | ||||
-rw-r--r-- | source/blender/blenlib/CMakeLists.txt | 2 | ||||
-rw-r--r-- | source/blender/blenlib/tests/BLI_pool_test.cc | 51 |
3 files changed, 137 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_pool.hh b/source/blender/blenlib/BLI_pool.hh new file mode 100644 index 00000000000..7ed39fea195 --- /dev/null +++ b/source/blender/blenlib/BLI_pool.hh @@ -0,0 +1,84 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +/** \file + * \ingroup bli + * + * A `blender::Pool` allows fast allocation and deallocation of many elements of the same type. + * + * It is compatible with types that are not moveable. + * + * Freed elements memory will be reused by next allocations. + * Elements are allocated in chunks to reduce memory fragmentation and avoid reallocation. + */ + +#pragma once + +#include "BLI_stack.hh" +#include "BLI_utility_mixins.hh" +#include "BLI_vector.hh" + +namespace blender { + +template<typename T, int64_t ChunkLen = 64> class Pool : NonCopyable { + private: + using Chunk = TypedBuffer<T, ChunkLen>; + + /** Allocated item buffer. */ + Vector<std::unique_ptr<Chunk>> values_; + /** List of freed elements to be use for the next allocations. A Stack is best here to avoid + * overhead when growing the free list. It also offers better cache performance than a queue + * since last added entries will be reused first. */ + Stack<T *, 0> free_list_; + + public: + ~Pool() + { + /* All elements need to be freed before freeing the pool. */ + BLI_assert(this->size() == 0); + } + + /** + * Construct an object inside this pool's memory. + */ + template<typename... ForwardT> T &construct(ForwardT &&...value) + { + if (free_list_.is_empty()) { + values_.append(std::make_unique<Chunk>()); + T *chunk_start = values_.last()->ptr(); + for (auto i : IndexRange(ChunkLen)) { + free_list_.push(chunk_start + i); + } + } + T *ptr = free_list_.pop(); + new (ptr) T(std::forward<ForwardT>(value)...); + return *ptr; + } + + /** + * Destroy the given element inside this memory pool. Memory will be reused by next element + * construction. This invokes undefined behavior if the item is not from this pool. + */ + void destruct(T &value) + { + value.~T(); + free_list_.push(&value); + } + + /** + * Return the number of constructed elements in this pool. + */ + int64_t size() const + { + return values_.size() * ChunkLen - free_list_.size(); + } + + /** + * Returns true when the pool contains no elements, otherwise false. + */ + bool is_empty() const + { + return this->size() == 0; + } +}; + +} // namespace blender diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index 78455c44fe1..ded4127a0d8 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -283,6 +283,7 @@ set(SRC BLI_path_util.h BLI_polyfill_2d.h BLI_polyfill_2d_beautify.h + BLI_pool.hh BLI_probing_strategies.hh BLI_quadric.h BLI_rand.h @@ -474,6 +475,7 @@ if(WITH_GTESTS) tests/BLI_multi_value_map_test.cc tests/BLI_path_util_test.cc tests/BLI_polyfill_2d_test.cc + tests/BLI_pool_test.cc tests/BLI_ressource_strings.h tests/BLI_serialize_test.cc tests/BLI_session_uuid_test.cc diff --git a/source/blender/blenlib/tests/BLI_pool_test.cc b/source/blender/blenlib/tests/BLI_pool_test.cc new file mode 100644 index 00000000000..31cb255d997 --- /dev/null +++ b/source/blender/blenlib/tests/BLI_pool_test.cc @@ -0,0 +1,51 @@ +/* SPDX-License-Identifier: Apache-2.0 */ + +#include "BLI_exception_safety_test_utils.hh" +#include "BLI_pool.hh" +#include "BLI_strict_flags.h" +#include "testing/testing.h" + +namespace blender::tests { + +TEST(pool, DefaultConstructor) +{ + Pool<int> pool; + EXPECT_EQ(pool.size(), 0); +} + +TEST(pool, Allocation) +{ + Vector<int *> ptrs; + Pool<int> pool; + for (int i = 0; i < 100; i++) { + ptrs.append(&pool.construct(i)); + } + EXPECT_EQ(pool.size(), 100); + + for (int *ptr : ptrs) { + pool.destruct(*ptr); + } + EXPECT_EQ(pool.size(), 0); +} + +TEST(pool, Reuse) +{ + Vector<int *> ptrs; + Pool<int> pool; + for (int i = 0; i < 32; i++) { + ptrs.append(&pool.construct(i)); + } + + int *freed_ptr = ptrs[6]; + pool.destruct(*freed_ptr); + + ptrs[6] = &pool.construct(0); + + EXPECT_EQ(ptrs[6], freed_ptr); + + for (int *ptr : ptrs) { + pool.destruct(*ptr); + } +} + +} // namespace blender::tests |