forum.boolean.name - Простой пул объектов переменного размера

Часто мы имеем множество объектов одного семантического типа, но разных размеров, к примеру : строки, изображения, геометрия и тд. Предлагаю рассмотреть несколько паттернов которые позволяют упростить организацию, хранение и работу с такими объектами.

Для примеров будем брать хранение изображений в виде raw RGBA по 8 бит на канал.

Рассмотрим самый банальный вариант который приходит в голову :

Код:

struct image_t

{

        unsigned short width, height;

        unsigned char * raw;



        void init(unsigned short setWidth, unsigned short setHeight, void * setRaw)

        {

                width = setWidth;

                height = setHeight;

                raw = (unsigned char*)malloc(width * height * 4);

                memcpy(raw, setRaw, width * height * 4)

        }



        void clear()

        {

                free(raw);

                width = 0;

                height = 0;

        }

};



...



std::vector<image_t*> images;



while(!eof())

{

        ...

        image_t * image = (image_t*)malloc(sizeof(image_t));

        image->init(...);

        images.push_back(image);

}

Пример немного утрирован, но на практике и такой код попадается. Как мы видим тут происходит как минимум три типа аллокаций : в самом векторе, самой структуры изображения, самих данных. При большом количестве изображений это приводит к нас к излишней фрагментации хипа, излишним задержкам на аллокации и тд.

Первая оптимизация заключается в самом векторе, представим его так : (malloc для последующих нужд)

Код:

size_t count = ...;

image_t * images = (image_t*)malloc(sizeof(image_t) * count);



for(size_t i = 0; i < count; ++i)

{

        ...

        images[i]->init(...);

}

Теперь у нас одна аллокация на пул, и N аллокаций на изображения, уже лучше.

Как теперь можно поместить данные изображения в этот пул ? самый банальный вариант это просто выделить место под все изображения, первую часть пула использовать как массив структур, а вторую часть пула для данных. В общем такой способ достаточно хорош, но не слишком уж и изящный.

Write in C (видео)

Изящный подход будет основываться на хаке, который пришел к нам из системного программирования, официально утверждён только в C99, отсутствует в стандартах C++, но его поддерживают большинство современных компиляторов. Он называется flexible array member.

Суть в том что мы получаем структуру, с массивом на конце, но мы не указываем его размер. Банально да ?

Пример синтаксиса :

Код:

struct foo

{

        int a, b, c;

        int d[];

};



struct foo2

{

        int a, b, c;

        int * d;

};

Отличие состоит в том что sizeof(foo) = 12 (на 32 битах, при выравнивании в 4 байт), когда sizeof(foo2) = 16, те в первой структуре нет указателя, и данных нет :)
Но все операции работают как и с обычный массивом.

К примеру :

Код:

foo test;



test.a = 1;

test.d[100] = 5;



int * d2 = test.d;

Вполне рабочий код (вместо foo можете подставить foo2 и будет работать так же), а памяти кушает меньше.
Используя этот подход мы сможем организовать пул с такой схемой расположения в памяти : img_struct, img_data, img_struct, img_data ...

Код:

struct image_t

{

        unsigned short width, height;

        unsigned char raw[];



        void init(unsigned short setWidth, unsigned short setHeight, void * setRaw)

        {

                width = setWidth;

                height = setHeight;

                memcpy(raw, setRaw, width * height * 4)

        }



        void clear()

        {

                width = 0;

                height = 0;

        }

        

        inline size_t size() const

        {

                return sizeof(image_t) + width * height * 4;

        }

};



...



// создание пула



size_t count = ...;

size_t totalImageSize = ...;

size_t totalBytes = sizeof(image_t) * count + totalImageSize;



unsigned char * images = (unsigned char*)malloc(totalBytes);



size_t offset = 0;



while(offset < totalBytes)

{

        ...

        image_t * image = images + offset;

        image->init(...);

        

        offset += image->size();

}



...



// обходим все элементы



size_t totalBytes = ...;

size_t offset = 0;



while(offset < totalBytes)

{

        image_t * image = images + offset;

        ...

        offset += image->size();

}

Вот и всё ! Теперь такой пул можно просто сохранять на диск как бинарные данные, и читать с диска при загрузке за один fread, не нужно делать каких либо действий при загрузке.

Теперь разбор полётов, aka faq.

1) Мне нужен класс, а не структура, нужен конструктор и деструктор.
Без проблем, руками вызываем placement new и placement delete.

Синтаксис такой :

Код:

class foo

{

public:

        foo() { ... }

        ~foo() { ... }

        ...

};



...



char temp[100];



foo * data = (foo*)temp;



// вызов конструктора

new (data) foo;



// вызов деструктора

foo->~foo();

2) Я хочу обращатся к элементам по индексу.

Если вам нужно постоянно обращатся к элементам переменного размера по индексу то проще всего будет использовать пул где в структуре используется указатель на массив данных (пример с unsigned char * raw, описан выше). Но если данных несколько (к примеру изображение с массивом мип-мапов) то дешевле всего в начало пула поместить массив указателей на структуры изображения в пуле, а сами данные размещать за структурой изображения как описано в этой статье, очевидно что описать все массивы с помощью поля переменного размера не получится, к второму и последующим массивам прийдется рассчитывать указатель руками.

Так же возможен немного другой обход указаний по индексу, переделайте свои индексы в указатели, когда данные на диске храните в указателях смещение в пуле (или всё же индекс элемента), а после загрузки пройдитесь по всем элементам и замените индексы на указатели, и во время работы вам не понадобится обращаться к элементам по индексам.

3) А как мне удалять элементы, создавать новые и тд ?

Пулы элементов переменного размера в общем не предназначены для динамического изменения. Вам нужно использовать другие структуры, например хип.