Простой пул объектов переменного размера

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

Для примеров будем брать хранение изображений в виде 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) А как мне удалять элементы, создавать новые и тд ?

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