blender
/
blender
136
404
Fork 586
Code Issues 6.2k Pull Requests 762 Projects 19 Wiki Activity

BLI: refactor how buffers for small object optimization are stored

This commit is contained in:
Jacques Lucke 2020-07-05 16:30:26 +02:00
parent 464aaf2701
commit 5d79f9f276
Notes: blender-bot 2023-02-14 10:11:49 +01:00 
Referenced by commit 247a28f242, Revert "BLI: refactor how buffers for small object optimization are stored"
7 changed files with 142 additions and 103 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

15
source/blender/blenlib/BLI_array.hh
View File

@ -74,7 +74,7 @@ class Array {
Allocator allocator_;
/** A placeholder buffer that will remain uninitialized until it is used. */
AlignedBuffer<sizeof(T) * InlineBufferCapacity, alignof(T)> inline_buffer_;
TypedBuffer<T, InlineBufferCapacity> inline_buffer_;
public:
/**
@ -82,7 +82,7 @@ class Array {
*/
Array()
{
data_ = this->inline_buffer();
data_ = inline_buffer_;
size_ = 0;
}
@ -167,7 +167,7 @@ class Array {
uninitialized_relocate_n(other.data_, size_, data_);
}
other.data_ = other.inline_buffer();
other.data_ = other.inline_buffer_;
other.size_ = 0;
}
@ -335,18 +335,13 @@ class Array {
T *get_buffer_for_size(uint size)
{
if (size <= InlineBufferCapacity) {
return this->inline_buffer();
return inline_buffer_;
}
else {
return this->allocate(size);
}
}
T *inline_buffer() const
{
return (T *)inline_buffer_.ptr();
}
T *allocate(uint size)
{
return (T *)allocator_.allocate(size * sizeof(T), alignof(T), AT);
@ -354,7 +349,7 @@ class Array {
bool uses_inline_buffer() const
{
return data_ == this->inline_buffer();
return data_ == inline_buffer_;
}
};

66
source/blender/blenlib/BLI_map_slots.hh
View File

@ -53,8 +53,8 @@ template<typename Key, typename Value> class SimpleMapSlot {
};
State state_;
AlignedBuffer<sizeof(Key), alignof(Key)> key_buffer_;
AlignedBuffer<sizeof(Value), alignof(Value)> value_buffer_;
TypedBuffer<Key> key_buffer_;
TypedBuffer<Value> value_buffer_;
public:
/**
@ -71,8 +71,8 @@ template<typename Key, typename Value> class SimpleMapSlot {
~SimpleMapSlot()
{
if (state_ == Occupied) {
this->key()->~Key();
this->value()->~Value();
key_buffer_->~Key();
value_buffer_->~Value();
}
}
@ -84,8 +84,8 @@ template<typename Key, typename Value> class SimpleMapSlot {
{
state_ = other.state_;
if (other.state_ == Occupied) {
new ((void *)this->key()) Key(*other.key());
new ((void *)this->value()) Value(*other.value());
new (&key_buffer_) Key(*other.key_buffer_);
new (&value_buffer_) Value(*other.value_buffer_);
}
}
@ -98,8 +98,8 @@ template<typename Key, typename Value> class SimpleMapSlot {
{
state_ = other.state_;
if (other.state_ == Occupied) {
new ((void *)this->key()) Key(std::move(*other.key()));
new ((void *)this->value()) Value(std::move(*other.value()));
new (&key_buffer_) Key(std::move(*other.key_buffer_));
new (&value_buffer_) Value(std::move(*other.value_buffer_));
}
}
@ -108,7 +108,7 @@ template<typename Key, typename Value> class SimpleMapSlot {
*/
Key *key()
{
return (Key *)key_buffer_.ptr();
return key_buffer_;
}
/**
@ -116,7 +116,7 @@ template<typename Key, typename Value> class SimpleMapSlot {
*/
const Key *key() const
{
return (const Key *)key_buffer_.ptr();
return key_buffer_;
}
/**
@ -124,7 +124,7 @@ template<typename Key, typename Value> class SimpleMapSlot {
*/
Value *value()
{
return (Value *)value_buffer_.ptr();
return value_buffer_;
}
/**
@ -132,7 +132,7 @@ template<typename Key, typename Value> class SimpleMapSlot {
*/
const Value *value() const
{
return (const Value *)value_buffer_.ptr();
return value_buffer_;
}
/**
@ -158,7 +158,7 @@ template<typename Key, typename Value> class SimpleMapSlot {
template<typename Hash> uint32_t get_hash(const Hash &hash)
{
BLI_assert(this->is_occupied());
return hash(*this->key());
return hash(*key_buffer_);
}
/**
@ -170,10 +170,10 @@ template<typename Key, typename Value> class SimpleMapSlot {
BLI_assert(!this->is_occupied());
BLI_assert(other.is_occupied());
state_ = Occupied;
new ((void *)this->key()) Key(std::move(*other.key()));
new ((void *)this->value()) Value(std::move(*other.value()));
other.key()->~Key();
other.value()->~Value();
new (&key_buffer_) Key(std::move(*other.key_buffer_));
new (&value_buffer_) Value(std::move(*other.value_buffer_));
other.key_buffer_->~Key();
other.value_buffer_->~Value();
}
/**
@ -184,7 +184,7 @@ template<typename Key, typename Value> class SimpleMapSlot {
bool contains(const ForwardKey &key, const IsEqual &is_equal, uint32_t UNUSED(hash)) const
{
if (state_ == Occupied) {
return is_equal(key, *this->key());
return is_equal(key, *key_buffer_);
}
return false;
}
@ -198,7 +198,7 @@ template<typename Key, typename Value> class SimpleMapSlot {
{
BLI_assert(!this->is_occupied());
this->occupy_without_value(std::forward<ForwardKey>(key), hash);
new ((void *)this->value()) Value(std::forward<ForwardValue>(value));
new (&value_buffer_) Value(std::forward<ForwardValue>(value));
}
/**
@ -209,7 +209,7 @@ template<typename Key, typename Value> class SimpleMapSlot {
{
BLI_assert(!this->is_occupied());
state_ = Occupied;
new ((void *)this->key()) Key(std::forward<ForwardKey>(key));
new (&key_buffer_) Key(std::forward<ForwardKey>(key));
}
/**
@ -220,8 +220,8 @@ template<typename Key, typename Value> class SimpleMapSlot {
{
BLI_assert(this->is_occupied());
state_ = Removed;
this->key()->~Key();
this->value()->~Value();
key_buffer_->~Key();
value_buffer_->~Value();
}
};
@ -236,7 +236,7 @@ template<typename Key, typename Value> class SimpleMapSlot {
template<typename Key, typename Value, typename KeyInfo> class IntrusiveMapSlot {
private:
Key key_ = KeyInfo::get_empty();
AlignedBuffer<sizeof(Value), alignof(Value)> value_buffer_;
TypedBuffer<Value> value_buffer_;
public:
IntrusiveMapSlot() = default;
@ -244,21 +244,21 @@ template<typename Key, typename Value, typename KeyInfo> class IntrusiveMapSlot
~IntrusiveMapSlot()
{
if (KeyInfo::is_not_empty_or_removed(key_)) {
this->value()->~Value();
value_buffer_->~Value();
}
}
IntrusiveMapSlot(const IntrusiveMapSlot &other) : key_(other.key_)
{
if (KeyInfo::is_not_empty_or_removed(key_)) {
new ((void *)this->value()) Value(*other.value());
new (&value_buffer_) Value(*other.value_buffer_);
}
}
IntrusiveMapSlot(IntrusiveMapSlot &&other) noexcept : key_(other.key_)
{
if (KeyInfo::is_not_empty_or_removed(key_)) {
new ((void *)this->value()) Value(std::move(*other.value()));
new (&value_buffer_) Value(std::move(*other.value_buffer_));
}
}
@ -274,12 +274,12 @@ template<typename Key, typename Value, typename KeyInfo> class IntrusiveMapSlot
Value *value()
{
return (Value *)value_buffer_.ptr();
return value_buffer_;
}
const Value *value() const
{
return (const Value *)value_buffer_.ptr();
return value_buffer_;
}
bool is_occupied() const
@ -295,7 +295,7 @@ template<typename Key, typename Value, typename KeyInfo> class IntrusiveMapSlot
template<typename Hash> uint32_t get_hash(const Hash &hash)
{
BLI_assert(this->is_occupied());
return hash(*this->key());
return hash(key_);
}
void relocate_occupied_here(IntrusiveMapSlot &other, uint32_t UNUSED(hash))
@ -303,9 +303,9 @@ template<typename Key, typename Value, typename KeyInfo> class IntrusiveMapSlot
BLI_assert(!this->is_occupied());
BLI_assert(other.is_occupied());
key_ = std::move(other.key_);
new ((void *)this->value()) Value(std::move(*other.value()));
new (&value_buffer_) Value(std::move(*other.value_buffer_));
other.key_.~Key();
other.value()->~Value();
other.value_buffer_->~Value();
}
template<typename ForwardKey, typename IsEqual>
@ -321,7 +321,7 @@ template<typename Key, typename Value, typename KeyInfo> class IntrusiveMapSlot
BLI_assert(!this->is_occupied());
BLI_assert(KeyInfo::is_not_empty_or_removed(key));
this->occupy_without_value(std::forward<ForwardKey>(key), hash);
new ((void *)this->value()) Value(std::forward<ForwardValue>(value));
new (&value_buffer_) Value(std::forward<ForwardValue>(value));
}
template<typename ForwardKey> void occupy_without_value(ForwardKey &&key, uint32_t UNUSED(hash))
@ -335,7 +335,7 @@ template<typename Key, typename Value, typename KeyInfo> class IntrusiveMapSlot
{
BLI_assert(this->is_occupied());
KeyInfo::remove(key_);
this->value()->~Value();
value_buffer_->~Value();
}
};

67
source/blender/blenlib/BLI_memory_utils.hh
View File

@ -218,12 +218,8 @@ template<typename T> struct DestructValueAtAddress {
template<typename T> using destruct_ptr = std::unique_ptr<T, DestructValueAtAddress<T>>;
/**
* An `AlignedBuffer` is simply a byte array with the given size and alignment. The buffer will
* An `AlignedBuffer` is a byte array with at least the given size and alignment. The buffer will
* not be initialized by the default constructor.
*
* This can be used to reserve memory for C++ objects whose lifetime is different from the
* lifetime of the object they are embedded in. It's used by containers with small buffer
* optimization and hash table implementations.
*/
template<size_t Size, size_t Alignment> class alignas(Alignment) AlignedBuffer {
private:
@ -231,6 +227,16 @@ template<size_t Size, size_t Alignment> class alignas(Alignment) AlignedBuffer {
char buffer_[(Size > 0) ? Size : 1];
public:
operator void *()
{
return (void *)buffer_;
}
operator const void *() const
{
return (void *)buffer_;
}
void *ptr()
{
return (void *)buffer_;
@ -242,6 +248,57 @@ template<size_t Size, size_t Alignment> class alignas(Alignment) AlignedBuffer {
}
};
/**
* This can be used to reserve memory for C++ objects whose lifetime is different from the
* lifetime of the object they are embedded in. It's used by containers with small buffer
* optimization and hash table implementations.
*/
template<typename T, size_t Size = 1> class TypedBuffer {
private:
AlignedBuffer<sizeof(T) * Size, alignof(T)> buffer_;
public:
operator T *()
{
return (T *)&buffer_;
}
operator const T *() const
{
return (const T *)&buffer_;
}
T *operator->()
{
return (T *)&buffer_;
}
const T *operator->() const
{
return (const T *)&buffer_;
}
T &operator*()
{
return *(T *)&buffer_;
}
const T &operator*() const
{
return *(const T *)&buffer_;
}
T *ptr()
{
return (T *)&buffer_;
}
const T *ptr() const
{
return (const T *)&buffer_;
}
};
/**
* This can be used by container constructors. A parameter of this type should be used to indicate
* that the constructor does not construct the elements.

46
source/blender/blenlib/BLI_set_slots.hh
View File

@ -51,7 +51,7 @@ template<typename Key> class SimpleSetSlot {
};
State state_;
AlignedBuffer<sizeof(Key), alignof(Key)> buffer_;
TypedBuffer<Key> key_buffer_;
public:
/**
@ -68,7 +68,7 @@ template<typename Key> class SimpleSetSlot {
~SimpleSetSlot()
{
if (state_ == Occupied) {
this->key()->~Key();
key_buffer_->~Key();
}
}
@ -80,7 +80,7 @@ template<typename Key> class SimpleSetSlot {
{
state_ = other.state_;
if (other.state_ == Occupied) {
new ((void *)this->key()) Key(*other.key());
new (&key_buffer_) Key(*other.key_buffer_);
}
}
@ -93,7 +93,7 @@ template<typename Key> class SimpleSetSlot {
{
state_ = other.state_;
if (other.state_ == Occupied) {
new ((void *)this->key()) Key(std::move(*other.key()));
new (&key_buffer_) Key(std::move(*other.key_buffer_));
}
}
@ -102,7 +102,7 @@ template<typename Key> class SimpleSetSlot {
*/
Key *key()
{
return (Key *)buffer_.ptr();
return key_buffer_;
}
/**
@ -110,7 +110,7 @@ template<typename Key> class SimpleSetSlot {
*/
const Key *key() const
{
return (const Key *)buffer_.ptr();
return key_buffer_;
}
/**
@ -136,7 +136,7 @@ template<typename Key> class SimpleSetSlot {
template<typename Hash> uint32_t get_hash(const Hash &hash) const
{
BLI_assert(this->is_occupied());
return hash(*this->key());
return hash(*key_buffer_);
}
/**
@ -148,8 +148,8 @@ template<typename Key> class SimpleSetSlot {
BLI_assert(!this->is_occupied());
BLI_assert(other.is_occupied());
state_ = Occupied;
new ((void *)this->key()) Key(std::move(*other.key()));
other.key()->~Key();
new (&key_buffer_) Key(std::move(*other.key_buffer_));
other.key_buffer_->~Key();
}
/**
@ -160,7 +160,7 @@ template<typename Key> class SimpleSetSlot {
bool contains(const ForwardKey &key, const IsEqual &is_equal, uint32_t UNUSED(hash)) const
{
if (state_ == Occupied) {
return is_equal(key, *this->key());
return is_equal(key, *key_buffer_);
}
return false;
}
@ -173,7 +173,7 @@ template<typename Key> class SimpleSetSlot {
{
BLI_assert(!this->is_occupied());
state_ = Occupied;
new ((void *)this->key()) Key(std::forward<ForwardKey>(key));
new (&key_buffer_) Key(std::forward<ForwardKey>(key));
}
/**
@ -183,7 +183,7 @@ template<typename Key> class SimpleSetSlot {
{
BLI_assert(this->is_occupied());
state_ = Removed;
this->key()->~Key();
key_buffer_->~Key();
}
};
@ -201,7 +201,7 @@ template<typename Key> class HashedSetSlot {
uint32_t hash_;
State state_;
AlignedBuffer<sizeof(Key), alignof(Key)> buffer_;
TypedBuffer<Key> key_buffer_;
public:
HashedSetSlot()
@ -212,7 +212,7 @@ template<typename Key> class HashedSetSlot {
~HashedSetSlot()
{
if (state_ == Occupied) {
this->key()->~Key();
key_buffer_->~Key();
}
}
@ -221,7 +221,7 @@ template<typename Key> class HashedSetSlot {
state_ = other.state_;
if (other.state_ == Occupied) {
hash_ = other.hash_;
new ((void *)this->key()) Key(*other.key());
new (&key_buffer_) Key(*other.key_buffer_);
}
}
@ -230,18 +230,18 @@ template<typename Key> class HashedSetSlot {
state_ = other.state_;
if (other.state_ == Occupied) {
hash_ = other.hash_;
new ((void *)this->key()) Key(std::move(*other.key()));
new (&key_buffer_) Key(std::move(*other.key_buffer_));
}
}
Key *key()
{
return (Key *)buffer_.ptr();
return key_buffer_;
}
const Key *key() const
{
return (const Key *)buffer_.ptr();
return key_buffer_;
}
bool is_occupied() const
@ -266,8 +266,8 @@ template<typename Key> class HashedSetSlot {
BLI_assert(other.is_occupied());
state_ = Occupied;
hash_ = hash;
new ((void *)this->key()) Key(std::move(*other.key()));
other.key()->~Key();
new (&key_buffer_) Key(std::move(*other.key_buffer_));
key_buffer_->~Key();
}
template<typename ForwardKey, typename IsEqual>
@ -276,7 +276,7 @@ template<typename Key> class HashedSetSlot {
/* hash_ might be uninitialized here, but that is ok. */
if (hash_ == hash) {
if (state_ == Occupied) {
return is_equal(key, *this->key());
return is_equal(key, *key_buffer_);
}
}
return false;
@ -287,14 +287,14 @@ template<typename Key> class HashedSetSlot {
BLI_assert(!this->is_occupied());
state_ = Occupied;
hash_ = hash;
new ((void *)this->key()) Key(std::forward<ForwardKey>(key));
new (&key_buffer_) Key(std::forward<ForwardKey>(key));
}
void remove()
{
BLI_assert(this->is_occupied());
state_ = Removed;
this->key()->~Key();
key_buffer_->~Key();
}
};

21
source/blender/blenlib/BLI_stack.hh
View File

@ -106,7 +106,7 @@ class Stack {
uint size_;
/** The buffer used to implement small object optimization. */
AlignedBuffer<sizeof(T) * InlineBufferCapacity, alignof(T)> inline_buffer_;
TypedBuffer<T, InlineBufferCapacity> inline_buffer_;
/**
* A chunk referencing the inline buffer. This is always the bottom-most chunk.
@ -123,14 +123,12 @@ class Stack {
*/
Stack(Allocator allocator = {}) : allocator_(allocator)
{
T *inline_buffer = this->inline_buffer();
inline_chunk_.below = nullptr;
inline_chunk_.above = nullptr;
inline_chunk_.begin = inline_buffer;
inline_chunk_.capacity_end = inline_buffer + InlineBufferCapacity;
inline_chunk_.begin = inline_buffer_;
inline_chunk_.capacity_end = inline_buffer_ + InlineBufferCapacity;
top_ = inline_buffer;
top_ = inline_buffer_;
top_chunk_ = &inline_chunk_;
size_ = 0;
}
@ -168,8 +166,8 @@ class Stack {
Stack(Stack &&other) noexcept : Stack(other.allocator_)
{
uninitialized_relocate_n(
other.inline_buffer(), std::min(other.size_, InlineBufferCapacity), this->inline_buffer());
uninitialized_relocate_n<T>(
other.inline_buffer_, std::min(other.size_, InlineBufferCapacity), inline_buffer_);
inline_chunk_.above = other.inline_chunk_.above;
size_ = other.size_;
@ -180,7 +178,7 @@ class Stack {
if (size_ <= InlineBufferCapacity) {
top_chunk_ = &inline_chunk_;
top_ = this->inline_buffer() + size_;
top_ = inline_buffer_ + size_;
}
else {
top_chunk_ = other.top_chunk_;
@ -339,11 +337,6 @@ class Stack {
}
private:
T *inline_buffer() const
{
return (T *)inline_buffer_.ptr();
}
/**
* Changes top_chunk_ to point to a new chunk that is above the current one. The new chunk might
* be smaller than the given size_hint. This happens when a chunk that has been allocated before

19
source/blender/blenlib/BLI_vector.hh
View File

@ -92,7 +92,7 @@ class Vector {
Allocator allocator_;
/** A placeholder buffer that will remain uninitialized until it is used. */
AlignedBuffer<(uint)sizeof(T) * InlineBufferCapacity, (uint)alignof(T)> inline_buffer_;
TypedBuffer<T, InlineBufferCapacity> inline_buffer_;
/**
* Store the size of the vector explicitly in debug builds. Otherwise you'd always have to call
@ -120,7 +120,7 @@ class Vector {
*/
Vector()
{
begin_ = this->inline_buffer();
begin_ = inline_buffer_;
end_ = begin_;
capacity_end_ = begin_ + InlineBufferCapacity;
UPDATE_VECTOR_SIZE(this);
@ -227,7 +227,7 @@ class Vector {
if (other.is_inline()) {
if (size <= InlineBufferCapacity) {
/* Copy between inline buffers. */
begin_ = this->inline_buffer();
begin_ = inline_buffer_;
end_ = begin_ + size;
capacity_end_ = begin_ + InlineBufferCapacity;
uninitialized_relocate_n(other.begin_, size, begin_);
@ -248,7 +248,7 @@ class Vector {
capacity_end_ = other.capacity_end_;
}
other.begin_ = other.inline_buffer();
other.begin_ = other.inline_buffer_;
other.end_ = other.begin_;
other.capacity_end_ = other.begin_ + OtherInlineBufferCapacity;
UPDATE_VECTOR_SIZE(this);
@ -399,7 +399,7 @@ class Vector {
allocator_.deallocate(begin_);
}
begin_ = this->inline_buffer();
begin_ = inline_buffer_;
end_ = begin_;
capacity_end_ = begin_ + InlineBufferCapacity;
UPDATE_VECTOR_SIZE(this);
@ -763,14 +763,9 @@ class Vector {
}
private:
T *inline_buffer() const
{
return (T *)inline_buffer_.ptr();
}
bool is_inline() const
{
return begin_ == this->inline_buffer();
return begin_ == inline_buffer_;
}
void ensure_space_for_one()
@ -817,7 +812,7 @@ class Vector {
uint capacity;
if (size <= InlineBufferCapacity) {
begin_ = this->inline_buffer();
begin_ = inline_buffer_;
capacity = InlineBufferCapacity;
}
else {

11
tests/gtests/blenlib/BLI_array_test.cc
View File

@ -138,23 +138,22 @@ TEST(array, NoInitializationSizeConstructor)
{
using MyArray = Array<ConstructibleType>;
AlignedBuffer<sizeof(MyArray), alignof(MyArray)> buffer;
char *buffer_ptr = (char *)buffer.ptr();
memset(buffer_ptr, 100, sizeof(MyArray));
TypedBuffer<MyArray> buffer;
memset(buffer, 100, sizeof(MyArray));
/* Doing this to avoid some compiler optimization. */
for (uint i : IndexRange(sizeof(MyArray))) {
EXPECT_EQ(buffer_ptr[i], 100);
EXPECT_EQ(((char *)buffer.ptr())[i], 100);
}
{
MyArray &array = *new (buffer.ptr()) MyArray(1, NoInitialization());
MyArray &array = *new (buffer) MyArray(1, NoInitialization());
EXPECT_EQ(array[0].value, 100);
array.clear_without_destruct();
array.~Array();
}
{
MyArray &array = *new (buffer.ptr()) MyArray(1);
MyArray &array = *new (buffer) MyArray(1);
EXPECT_EQ(array[0].value, 42);
array.~Array();
}