Шаблон проектирования пула памяти C ++ 11?
У меня есть программа, которая содержит фазу обработки, которая должна использовать кучу разных экземпляров объектов (все они размещены в куче) из дерева полиморфных типов, которые все в конечном итоге происходят из общего базового класса.
Поскольку экземпляры могут циклически ссылаться друг на друга и не имеют явного владельца, я хочу выделить их с newобработайте их с помощью необработанных указателей и оставьте их в памяти для фазы (даже если они не имеют ссылок), а затем после фазы программы, которая использует эти экземпляры, я хочу удалить их все сразу.
Как я думал структурировать это следующим образом:
struct B; // common base class
vector<unique_ptr<B>> memory_pool;
struct B
{
B() { memory_pool.emplace_back(this); }
virtual ~B() {}
};
struct D : B { ... }
int main()
{
...
// phase begins
D* p = new D(...);
...
// phase ends
memory_pool.clear();
// all B instances are deleted, and pointers invalidated
...
}
Помимо того, что все экземпляры B выделены с новым и никто не использует указатели на них после очистки пула памяти, есть ли проблемы с этой реализацией?
В частности, меня беспокоит тот факт, что this указатель используется для построения std::unique_ptr в конструкторе базового класса, до завершения конструктора производного класса. Приводит ли это к неопределенному поведению? Если так, есть ли обходной путь?
Решение
Ваша идея великолепна, и миллионы приложений уже используют ее. Этот паттерн наиболее известен как «пул автозапуска». Он формирует основу для «умного» управления памятью в средах Cocoa и Cocoa Touch Objective-C. Несмотря на то, что C ++ предоставляет чертовски много других альтернатив, я все еще думаю, что эта идея получила много преимуществ. Но есть несколько вещей, где я думаю, что ваша реализация в ее нынешнем виде может не сработать.
Первая проблема, о которой я могу подумать, это безопасность потоков. Например, что происходит, когда объекты одной и той же базы создаются из разных потоков? Решением может быть защита доступа к пулу с помощью взаимоисключающих блокировок. Хотя я думаю, что лучший способ сделать это — сделать этот пул объектом, специфичным для потока.
Вторая проблема — вызвать неопределенное поведение в случае, когда конструктор производного класса генерирует исключение. Видите ли, если это произойдет, производный объект не будет построен, но ваш Bконструктор уже бы нажал указатель на this к вектору. Позже, когда вектор очищается, он пытается вызвать деструктор через виртуальную таблицу объекта, который либо не существует, либо фактически является другим объектом (поскольку new может повторно использовать этот адрес).
Третье, что мне не нравится, это то, что у вас есть только один глобальный пул, даже если он ориентирован на потоки, который просто не позволяет более детально контролировать область распределенных объектов.
Учитывая вышесказанное, я бы сделал пару улучшений:
- Имейте стек пулов для более детального контроля объема.
- Сделайте этот пул стека специфичным для потока объектом.
- В случае сбоев (например, исключение в конструкторе производного класса) убедитесь, что в пуле нет висящего указателя.
Вот мое буквально 5-минутное решение, не судите за быстрое и грязное:
#include <new>
#include <set>
#include <stack>
#include <cassert>
#include <memory>
#include <stdexcept>
#include <iostream>
#define thread_local __thread // Sorry, my compiler doesn't C++11 thread locals
struct AutoReleaseObject {
AutoReleaseObject();
virtual ~AutoReleaseObject();
};
class AutoReleasePool final {
public:
AutoReleasePool() {
stack_.emplace(this);
}
~AutoReleasePool() noexcept {
std::set<AutoReleaseObject *> obj;
obj.swap(objects_);
for (auto *p : obj) {
delete p;
}
stack_.pop();
}
static AutoReleasePool &instance() {
assert(!stack_.empty());
return *stack_.top();
}
void add(AutoReleaseObject *obj) {
objects_.insert(obj);
}
void del(AutoReleaseObject *obj) {
objects_.erase(obj);
}
AutoReleasePool(const AutoReleasePool &) = delete;
AutoReleasePool &operator = (const AutoReleasePool &) = delete;
private:
// Hopefully, making this private won't allow users to create pool
// not on stack that easily... But it won't make it impossible of course.
void *operator new(size_t size) {
return ::operator new(size);
}
std::set<AutoReleaseObject *> objects_;
struct PrivateTraits {};
AutoReleasePool(const PrivateTraits &) {
}
struct Stack final : std::stack<AutoReleasePool *> {
Stack() {
std::unique_ptr<AutoReleasePool> pool
(new AutoReleasePool(PrivateTraits()));
push(pool.get());
pool.release();
}
~Stack() {
assert(!stack_.empty());
delete stack_.top();
}
};
static thread_local Stack stack_;
};
thread_local AutoReleasePool::Stack AutoReleasePool::stack_;
AutoReleaseObject::AutoReleaseObject()
{
AutoReleasePool::instance().add(this);
}
AutoReleaseObject::~AutoReleaseObject()
{
AutoReleasePool::instance().del(this);
}
// Some usage example...
struct MyObj : AutoReleaseObject {
MyObj() {
std::cout << "MyObj::MyObj(" << this << ")" << std::endl;
}
~MyObj() override {
std::cout << "MyObj::~MyObj(" << this << ")" << std::endl;
}
void bar() {
std::cout << "MyObj::bar(" << this << ")" << std::endl;
}
};
struct MyObjBad final : AutoReleaseObject {
MyObjBad() {
throw std::runtime_error("oops!");
}
~MyObjBad() override {
}
};
void bar()
{
AutoReleasePool local_scope;
for (int i = 0; i < 3; ++i) {
auto o = new MyObj();
o->bar();
}
}
void foo()
{
for (int i = 0; i < 2; ++i) {
auto o = new MyObj();
bar();
o->bar();
}
}
int main()
{
std::cout << "main start..." << std::endl;
foo();
std::cout << "main end..." << std::endl;
}
Другие решения
Если вы еще этого не сделали, ознакомьтесь с Boost.Pool. Из документации Boost:
Что такое бассейн?
Распределение пула — это схема распределения памяти, которая очень быстрая, но
ограничено в его использовании. Для получения дополнительной информации о распределении пула (также
называется простое раздельное хранение, увидеть концепции концепции и Простое сегрегированное хранилище.Почему я должен использовать бассейн?
Использование пулов дает вам больше контроля над тем, как память используется в вашем
программа. Например, вы можете иметь ситуацию, когда вы хотите
выделить кучу небольших объектов в одной точке, а затем достичь точки
в вашей программе, где ни один из них больше не нужен. Использование пула
интерфейсы, вы можете запустить их деструкторы или просто удалить их
в забвение; интерфейс пула гарантирует, что нет
утечки системной памяти.Когда я должен использовать бассейн?
Бассейны, как правило, используются, когда есть много распределения и
освобождение от мелких предметов. Другая распространенная ситуация — это ситуация
выше, где многие объекты могут быть удалены из памяти.В общем, используйте Бассейны, когда вам нужен более эффективный способ сделать необычное
контроль памяти.Какой распределитель пулов я должен использовать?
pool_allocatorявляется более универсальным решением, ориентированным на
эффективное обслуживание запросов для любого количества смежных блоков.
fast_pool_allocatorтакже является универсальным решением, но оно ориентировано
для эффективного обслуживания запросов на один блок за раз; Это
будет работать для смежных кусков, но не так хорошо, какpool_allocator,Если вы серьезно обеспокоены производительностью, используйте
fast_pool_allocatorпри работе с контейнерами, такими какstd::list,
и использоватьpool_allocatorпри работе с контейнерами, такими как
std::vector,
Управление памятью — непростое дело (многопоточность, кэширование, выравнивание, фрагментация и т. Д. И т. Д.). Для серьезного производственного кода хорошо подходят хорошо спроектированные и тщательно оптимизированные библиотеки, если ваш профилировщик не обнаружит узкое место.
Хм, в последнее время мне нужно было почти то же самое (пул памяти для одной фазы программы, которая очищается сразу), за исключением того, что у меня было дополнительное конструктивное ограничение, что все мои объекты были бы довольно маленькими.
Я придумал следующий «пул памяти для небольших объектов» — возможно, он будет вам полезен:
#pragma once
#include "defs.h"#include <cstdint> // uintptr_t
#include <cstdlib> // std::malloc, std::size_t
#include <type_traits> // std::alignment_of
#include <utility> // std::forward
#include <algorithm> // std::max
#include <cassert> // assert// Small-object allocator that uses a memory pool.
// Objects constructed in this arena *must not* have delete called on them.
// Allows all memory in the arena to be freed at once (destructors will
// be called).
// Usage:
// SmallObjectArena arena;
// Foo* foo = arena::create<Foo>();
// arena.free(); // Calls ~Foo
class SmallObjectArena
{
private:
typedef void (*Dtor)(void*);
struct Record
{
Dtor dtor;
short endOfPrevRecordOffset; // Bytes between end of previous record and beginning of this one
short objectOffset; // From the end of the previous record
};
struct Block
{
size_t size;
char* rawBlock;
Block* prevBlock;
char* startOfNextRecord;
};
template<typename T> static void DtorWrapper(void* obj) { static_cast<T*>(obj)->~T(); }
public:
explicit SmallObjectArena(std::size_t initialPoolSize = 8192)
: currentBlock(nullptr)
{
assert(initialPoolSize >= sizeof(Block) + std::alignment_of<Block>::value);
assert(initialPoolSize >= 128);
createNewBlock(initialPoolSize);
}
~SmallObjectArena()
{
this->free();
std::free(currentBlock->rawBlock);
}
template<typename T>
inline T* create()
{
return new (alloc<T>()) T();
}
template<typename T, typename A1>
inline T* create(A1&& a1)
{
return new (alloc<T>()) T(std::forward<A1>(a1));
}
template<typename T, typename A1, typename A2>
inline T* create(A1&& a1, A2&& a2)
{
return new (alloc<T>()) T(std::forward<A1>(a1), std::forward<A2>(a2));
}
template<typename T, typename A1, typename A2, typename A3>
inline T* create(A1&& a1, A2&& a2, A3&& a3)
{
return new (alloc<T>()) T(std::forward<A1>(a1), std::forward<A2>(a2), std::forward<A3>(a3));
}
// Calls the destructors of all currently allocated objects
// then frees all allocated memory. Destructors are called in
// the reverse order that the objects were constructed in.
void free()
{
// Destroy all objects in arena, and free all blocks except
// for the initial block.
do {
char* endOfRecord = currentBlock->startOfNextRecord;
while (endOfRecord != reinterpret_cast<char*>(currentBlock) + sizeof(Block)) {
auto startOfRecord = endOfRecord - sizeof(Record);
auto record = reinterpret_cast<Record*>(startOfRecord);
endOfRecord = startOfRecord - record->endOfPrevRecordOffset;
record->dtor(endOfRecord + record->objectOffset);
}
if (currentBlock->prevBlock != nullptr) {
auto memToFree = currentBlock->rawBlock;
currentBlock = currentBlock->prevBlock;
std::free(memToFree);
}
} while (currentBlock->prevBlock != nullptr);
currentBlock->startOfNextRecord = reinterpret_cast<char*>(currentBlock) + sizeof(Block);
}
private:
template<typename T>
static inline char* alignFor(char* ptr)
{
const size_t alignment = std::alignment_of<T>::value;
return ptr + (alignment - (reinterpret_cast<uintptr_t>(ptr) % alignment)) % alignment;
}
template<typename T>
T* alloc()
{
char* objectLocation = alignFor<T>(currentBlock->startOfNextRecord);
char* nextRecordStart = alignFor<Record>(objectLocation + sizeof(T));
if (nextRecordStart + sizeof(Record) > currentBlock->rawBlock + currentBlock->size) {
createNewBlock(2 * std::max(currentBlock->size, sizeof(T) + sizeof(Record) + sizeof(Block) + 128));
objectLocation = alignFor<T>(currentBlock->startOfNextRecord);
nextRecordStart = alignFor<Record>(objectLocation + sizeof(T));
}
auto record = reinterpret_cast<Record*>(nextRecordStart);
record->dtor = &DtorWrapper<T>;
assert(objectLocation - currentBlock->startOfNextRecord < 32768);
record->objectOffset = static_cast<short>(objectLocation - currentBlock->startOfNextRecord);
assert(nextRecordStart - currentBlock->startOfNextRecord < 32768);
record->endOfPrevRecordOffset = static_cast<short>(nextRecordStart - currentBlock->startOfNextRecord);
currentBlock->startOfNextRecord = nextRecordStart + sizeof(Record);
return reinterpret_cast<T*>(objectLocation);
}
void createNewBlock(size_t newBlockSize)
{
auto raw = static_cast<char*>(std::malloc(newBlockSize));
auto blockStart = alignFor<Block>(raw);
auto newBlock = reinterpret_cast<Block*>(blockStart);
newBlock->rawBlock = raw;
newBlock->prevBlock = currentBlock;
newBlock->startOfNextRecord = blockStart + sizeof(Block);
newBlock->size = newBlockSize;
currentBlock = newBlock;
}
private:
Block* currentBlock;
};
Чтобы ответить на ваш вопрос, вы не вызываете неопределенное поведение, поскольку никто не использует указатель, пока объект не будет полностью создан (само значение указателя безопасно копировать до тех пор). Тем не менее, это довольно навязчивый метод, поскольку сами объекты должны знать о пуле памяти. Кроме того, если вы создаете большое количество небольших объектов, скорее всего будет быстрее использовать реальный пул памяти (как это делает мой пул) вместо вызова new для каждого объекта.
Какой бы подход вы ни использовали для бассейна, будьте осторожны, чтобы объекты никогда не обрабатывались вручную deleteЭд, потому что это привело бы к двойной свободе!
Я все еще думаю, что это интересный вопрос без однозначного ответа, но, пожалуйста, позвольте мне разбить его на различные вопросы, которые вы на самом деле задаете:
1.) Предотвращает ли вставка указателя на базовый класс в вектор перед инициализацией подкласса или вызывает проблемы с получением унаследованных классов из этого указателя? [нарезка например.]
Ответ: Нет, если вы на 100% уверены в соответствующем типе, который указан, этот механизм не вызывает этих проблем, однако обратите внимание на следующие моменты:
Если производный конструктор дает сбой, у вас останется проблема позже, когда вы, вероятно, будете иметь висячий указатель, по крайней мере, сидящий в векторе, поскольку это адресное пространство, которое он [производный класс] думал, что получал, будет освобождено для операционной среды. при ошибке, но вектор по-прежнему имеет адрес базового класса.
Обратите внимание, что вектор, хотя и полезный, не является лучшей структурой для этого, и даже если бы это было так, здесь должна быть некоторая инверсия управления, чтобы позволить векторному объекту контролировать инициализацию ваших объектов, чтобы у вас была осведомленность успеха / неудачи.
Эти пункты приводят к подразумеваемому второму вопросу:
2.) Это хороший шаблон для объединения?
Ответ: Не совсем, по причинам, указанным выше, а также по другим причинам (проталкивание вектора за его конечную точку в основном заканчивается malloc, который не нужен и будет влиять на производительность.) В идеале вы хотите использовать библиотеку пула или класс шаблона, и, что еще лучше, отделите реализацию политики распределения / выделения от реализации пула с помощью уже намекаемого решения низкого уровня, которое состоит в выделении адекватной памяти пула из инициализации пула, и затем используйте это, используя указатели для аннулирования изнутри адресное пространство пула (см. решение Алекса Цивицкого выше.) Используя этот шаблон, уничтожение пула является безопасным, так как пул, который будет представлять собой непрерывную память, может быть уничтожен в массе без каких-либо проблем, или утечки памяти из-за потери всех ссылок на объект ( потеря всей ссылки на объект, адрес которого выделен через пул диспетчером хранилища, оставляет вас с грязными порциями, но не приведет к утечке памяти, так как он управляется пулом ementation.
В первые дни C / C ++ (до массового распространения STL) это был хорошо обсуждаемый паттерн, и в хорошей литературе можно найти много реализаций и конструкций: Например:
Кнут (1973 г. Искусство компьютерного программирования: несколько томов), а более полный список с более подробной информацией о пуле см. В:
http://www.ibm.com/developerworks/library/l-memory/
3-й подразумеваемый вопрос, по-видимому:
3) Является ли это допустимым сценарием использования пула?
Ответ: Это локализованное проектное решение, основанное на том, с чем вам удобно, но, если честно, ваша реализация (без контролирующей структуры / агрегата, возможно, циклического совместного использования поднаборов объектов) подсказывает мне, что вам будет лучше с базовый связанный список объектов-оболочек, каждый из которых содержит указатель на ваш суперкласс, используемый только для целей адресации. Ваши циклические структуры построены на этом, и вы просто изменяете / расширяете список по мере необходимости, чтобы приспособить все ваши первоклассные объекты по мере необходимости, а когда закончите, вы можете легко уничтожить их, эффективно используя операцию O (1). из связанного списка.
Сказав это, я лично рекомендовал бы в это время (когда у вас есть сценарий, в котором пул действительно используется, и поэтому вы находитесь в правильном настроении), чтобы выполнить создание набора управления / хранения пула классов, который сейчас находятся в параматериализированном состоянии / без типа, так как это поможет вам в будущем.
Это звучит, как я слышал, под названием «Линейный распределитель».
Я объясню основы того, как я понимаю, как это работает.
- Выделите блок памяти, используя :: operator new (size);
- Имейте void *, который является вашим Указателем на следующее свободное место в памяти.
- У вас будет функция alloc (size_t size), которая даст вам указатель на местоположение в блоке с первого шага, чтобы вы могли перейти к использованию Placement New.
- Размещение new выглядит следующим образом … int * i = new (location) int (); где location — это пустота * для блока памяти, выделенного вами из распределителя.
- Когда вы закончите со всей своей памятью, вы вызовете функцию Flush (), которая освободит память из пула или, по крайней мере, очистит данные.
Я недавно запрограммировал один из них, и я опубликую свой код здесь для вас, а также постараюсь объяснить.
#include <iostream>
class LinearAllocator:public ObjectBase
{
public:
LinearAllocator();
LinearAllocator(Pool* pool,size_t size);
~LinearAllocator();
void* Alloc(Size_t size);
void Flush();
private:
void** m_pBlock;
void* m_pHeadFree;
void* m_pEnd;
};
не беспокойся о том, что я наследую. Я использовал этот распределитель в сочетании с пулом памяти. но в основном вместо получения памяти от оператора new я получаю память из пула памяти. внутренняя работа одинакова по сути.
Вот реализация:
LinearAllocator::LinearAllocator():ObjectBase::ObjectBase()
{
m_pBlock = nullptr;
m_pHeadFree = nullptr;
m_pEnd=nullptr;
}
LinearAllocator::LinearAllocator(Pool* pool,size_t size):ObjectBase::ObjectBase(pool)
{
if (pool!=nullptr) {
m_pBlock = ObjectBase::AllocFromPool(size);
m_pHeadFree = * m_pBlock;
m_pEnd = (void*)((unsigned char*)*m_pBlock+size);
}
else{
m_pBlock = nullptr;
m_pHeadFree = nullptr;
m_pEnd=nullptr;
}
}
LinearAllocator::~LinearAllocator()
{
if (m_pBlock!=nullptr) {
ObjectBase::FreeFromPool(m_pBlock);
}
m_pBlock = nullptr;
m_pHeadFree = nullptr;
m_pEnd=nullptr;
}
MemoryBlock* LinearAllocator::Alloc(size_t size)
{
if (m_pBlock!=nullptr) {
void* test = (void*)((unsigned char*)m_pEnd-size);
if (m_pHeadFree<=test) {
void* temp = m_pHeadFree;
m_pHeadFree=(void*)((unsigned char*)m_pHeadFree+size);
return temp;
}else{
return nullptr;
}
}else return nullptr;
}
void LinearAllocator::Flush()
{
if (m_pBlock!=nullptr) {
m_pHeadFree=m_pBlock;
size_t size = (unsigned char*)m_pEnd-(unsigned char*)*m_pBlock;
memset(*m_pBlock,0,size);
}
}
Этот код полностью функционален, за исключением нескольких строк, которые необходимо будет изменить из-за моего наследования и использования пула памяти. но держу пари, вы можете выяснить, что нужно изменить, и просто дайте мне знать, если вам нужна рука, чтобы изменить код. Этот код не был протестирован в каком-либо профессиональном поместье и не гарантированно безопасен для потоков или чего-то подобного. я просто взбил его и подумал, что могу поделиться им с вами, потому что вам, казалось, нужна помощь.
У меня также есть рабочая реализация полностью общего пула памяти, если вы думаете, что это может вам помочь. Я могу объяснить, как это работает, если вам нужно.
Еще раз, если вам нужна помощь, дайте мне знать. Удачи.