Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

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

 

Источник: programmingmaster.ru

 

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB