Хочу поделится очередным велосипедом собственной сборки на С++. Велосипед умеет быстро создавать и выдавать объекты. В результате получаем скорость создания (не отдачи) объектов на 30% быстрее чем просто с new. Объектный пул — вещь не новая, и в общем — чего о нем и говорить то. Но как говорится — главное в деталях.
Так случилось, что потребовалось мне огромнейшее количество небольших объектов в проекте на С++. При чем потребовались они, как потом оказалось, в куче. Объекты же были не чем иным как описанием положения в пространстве. И содержали матрицу 4х4 типа double и несколько вспомогательных переменных. Упростив первоначальную форму, положим что класс (в данном случае структура) имеет вид:
struct Position{
double m[16];
int s;
}
То есть — порядка 132 байт.
Перепробовав несколько способов, в числе которых было и создание объектов просто через new, пришёл к тому что лучше это сделать с помощью объектного пула. Ибо new прямо в лоб — операция ресурсоемкая.
Сразу оговорюсь, что с boost, и иже с ними знаком весьма отдаленно. И потому, возможно описываю здесь велосипед. Тем не менее, лично я подобного не нашел (весьма вероятно, от того что и не знал как это правильней назвать), а то что получилось работает весьма шустро.
Объектный пул довольно известный, и в общем-то несложный в реализации паттерн. Казалось бы что тут сложного — создай стек из объектов и по мере необходимости отдавай. Когда все роздано — создавай ещё. Если объект больше не нужен — возвращаем его в стек свободных объектов, вместо того чтобы удалять. Приведем пример класса реализующего данный паттерн:
template <typename T, unsigned int chunk_size = 100>
class Factory
{
public:
inline T* get(){
if(free_ptrs.empty()){
makeMore();
}
T* obj = free_ptrs.back();
free_ptrs.pop_back();
return obj;
}
inline void free(T* obj){
free_ptrs.push_back(obj);
}
private:
std::vector<T> buffer;
std::vector<T*> free_ptrs;
// создаем пачками (либо поштучно, если chunk_size = 1 ). При chunk_size = 1 компилятор уберёт loop.
void makeMore(){
// НЕ делаем vector.reserve() здесь, в силу того что reserve имеет линейное время работы
// по vector.size() , а не количеству добавляемых элементов. Оставляем расширение
// массива на рассмотрение STL.
for (int i = 0; i < chunk_size ; ++i) {
buffer.emplace_back(); // у создаваемого класса объектов должен быть конструктор по умолчанию!
free_ptrs.emplace_back(&buffer.back()); // заносим в список свободных
}
}
}
Применение:
Factory<Position> pool;
pool.get();
Рассмотрим минусы приведенного способа:
— На практике создание огромного количества (10000 — 1000000) небольших объектов в куче вызвало значительное проседание в производительности. Конечно, подобные запинки в работе будут наблюдаться лишь при первоначальной инициализации. Но все же. Если можно сделать хорошо, зачем не сделать?
— У создаваемого класса объектов должен быть конструктор по умолчанию!
— Объект возвращается в неопределенном состоянии. Можно конечно добавить вызов конструктора/ инициализатора, но об этом ниже.
Было замечено что объекты ну ооочень шустро создаются в нативных массивах:
T* array = new T[];
А по сему, пробуем создавать и хранить объекты подобным способом.
Казалось бы достаточно было бы сделать STL'ный buffer.reserve. Но при каждом увеличении массива происходит создание НОВОГО нативного массива, а потом ещё и создание поштучно конструктором копии/переноса в нем всех уже существующих элементов. То есть — если мы не хотим добавлять конструктор переноса в класс наших объектов — то работать будет очень медленно.
Итак — перепишем наш пул, с тем чтобы хранить объекты в такого рода буферах:
template <typename T, unsigned int chunk_size = 100>
class Factory
{
public:
inline T* get(){
if(free_ptrs.empty()){
makeMore();
}
T* obj = free_ptrs.back();
free_ptrs.pop_back();
return obj;
}
inline void free(T* obj){
free_ptrs.push_back(obj);
}
private:
/**
* @brief Use this against std::vector - because
* vector have linear size complexity on reserve.
* NOT grow size, but whole size!
*/
struct Buffer{
T* array;
int size;
Buffer(int num = chunk_size){
array = new T[num];
size = num;
}
/**
* @brief IMPORTANT! Due to ussage with vector must have it.
* @param other
*/
Buffer(Buffer&& other) noexcept{
size = other.size;
array = other.array;
other.array = nullptr;
}
~Buffer(){
if (array != nullptr){
delete []array;
}
}
};
std::vector<Buffer> buffers;
std::vector<T*> free_ptrs;
void makeMore(){
buffers.emplace_back(chunk_size);
Buffer &buf = buffers.back();
for (int i = 0; i < buf.size; ++i) {
free_ptrs.emplace_back(&buf.array[i]);
}
}
};
Как видите — у класса буфера есть конструктор копии. Он нам необходим для тех случаев, когда std::vector вздумается выполнить reallocate массива.
В результате — первоначальная инициализации пула ускорилась практически в разы.
Последний штрих — пользуясь многообразием команды new разделяем процесс выделение памяти под буфер, и собственно вызов конструктора. Что в результате позволяет нам, во первых — получить «не грязный» объект, а во вторых позволит использовать объекты без конструктора по умолчанию.
template <typename T, unsigned int chunk_size = 100>
class PoolFactory
{
public:
template<typename... Args>
inline T* get(Args&&...args){
T* obj = getRaw();
new (obj) T(args...);
return obj;
}
inline T* getRaw(){
if(free_ptrs.empty()){
makeMore();
}
T* obj = free_ptrs.back();
free_ptrs.pop_back();
return obj;
}
inline void free(T* obj){
free_ptrs.push_back(obj);
}
inline void clearPool(){
buffers.clear();
free_ptrs.clear();
}
void freeAll(){
free_ptrs.clear();
int buf_count = buffers.size();
for (int buf_id = 0; buf_id < buf_count; ++buf_id) {
Buffer &buf = buffers[buf_id];
for (int i = 0; i < buf.size; ++i) {
free_ptrs.emplace_back(&buf.array[i]);
}
}
}
private:
/**
* @brief Use this against std::vector - because
* vector have linear size complexity on reserve.
* NOT grow size, but whole size!
*/
struct Buffer{
T* array;
int size;
Buffer(int num = chunk_size){
// allocate, but not construct
array = static_cast<T*> (::operator new (sizeof(T[num])));
size = num;
}
/**
* @brief IMPORTANT! Due to ussage with vector must have it.
* @param other
*/
Buffer(Buffer&& other) noexcept{
size = other.size;
array = other.array;
other.array = nullptr;
}
~Buffer(){
if (array != nullptr){
// destructors
for (int i = 0; i < size; ++i) {
array[i].~T();
}
// deallocate
::operator delete(array);
}
}
};
std::vector<Buffer> buffers;
std::vector<T*> free_ptrs;
void makeMore(){
buffers.emplace_back(chunk_size);
Buffer &buf = buffers.back();
for (int i = 0; i < buf.size; ++i) {
free_ptrs.emplace_back(&buf.array[i]);
}
}
};
Основной задачей, для меня, было именно быстрое заполнение std::vector этими мелкими объектами. От того тесты несколько специфичны. В моем случае — время заполнения с пулом и с emplace_back — одинаково. При повторном использовании пула — естественно пул выигрывает.
class BaseClass {
public:
BaseClass(){}
BaseClass(int value){
s = value;
}
int getS(){
return s;
}
int s;
int m[16];
};
std::vector< BaseClass > ar;
std::vector< BaseClass* > ptr_ar;
const unsigned int total = 1000000;
int main(int argc, char *argv[])
{
PoolFactory<BaseClass> bPool;
ar.reserve(total);
timer.start();
for (int var = 0; var < total; ++var) {
ar.emplace_back(var);
}
qDebug()<<"1 : "<<timer.elapsed();
ptr_ar.clear();
ptr_ar.reserve(total);
timer.start();
for (int var = 0; var < total; ++var) {
ptr_ar.push_back(bPool.get(var));
}
qDebug()<<"2 : "<<timer.elapsed();
bPool.freeAll();
ptr_ar.clear();
ptr_ar.reserve(total);
timer.start();
for (int var = 0; var < total; ++var) {
ptr_ar.push_back(bPool.get(var));
}
qDebug()<<"3 : "<<timer.elapsed();
ptr_ar.clear();
ptr_ar.reserve(total);
timer.start();
for (int var = 0; var < total; ++var) {
ptr_ar.push_back(new BaseClass(var));
}
qDebug()<<"4 : "<<timer.elapsed();
}
Вывод:
1: 21
2: 22
3: 5
4: 37
Без reserve:
1: 135 (сказывается отсутствие конструктора переноса у заполняемого класса BaseClass)
2: 22
3: 4
4: 38
Автор: tower120
