Объектный пул и быстрое создание объектов в куче

в 17:55, , рубрики: c++, stl, велосипеды, ооп, паттерны проектирования, С++, с++11, метки: , , , ,

Хочу поделится очередным велосипедом собственной сборки на С++. Велосипед умеет быстро создавать и выдавать объекты. В результате получаем скорость создания (не отдачи) объектов на 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

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js