Шаблон vector библиотеки STL выигрывает почти по всем параметрам у обычного С++ массива. Он позволяет добавлять и удалять элементы, освобождает выделенную память при уничтожении, позволяет контролировать выход за пределы массива и т.д. Тем не менее, у него есть один недостаток – для его работы требуется дополнительная память, небольшая, но в ряде случаев существенная. Ниже рассмотрена реализация контейнера, позволяющая немного снизить затраты памяти и повысить производительность.
Сначала нужно разобраться для чего эта память используется, и сколько её требуется. Помимо указателя на начало массива в шаблоне хранится указатель на конец заполненного массива, указатель на конец выделенного массива, и распределитель памяти. Для иллюстрации приведу кусочек кода:
Для 32-битного x86 кода, где на указатель требуется 4 байта, такой объект займёт 12 байт. Если используется распределитель памяти без полей данных и виртуальных функции (стандартный распределитель именно такой), то в удачной реализации он места не займёт, по крайней мере, в реализации STLPort это так. В библиотеке для VS2005 реализация менее удачная и распределитель добавит ещё 4 байта. Таким образом, требуется минимум 8 дополнительных байт, по сравнению с указателем на обычный массив.
Казалось бы, что такое эти 8 байт, мелочь, теряющаяся рядом с размером памяти, которая потребуется для хранения самих элементов массива. Тем не менее, часто бывает, что значительное число массивов будут пустыми. Например, есть игровая модель, у неё могут быть источники света, источники звука, повреждения и прочие атрибуты. Их нужно где-то хранить, и массивы для этого вполне подходят, но у большей части моделей есть только геометрия, и эти массивы останутся незаполненными.
Чем плохи эти лишние байты? Память в наше время дешева, и десяток-другой лишних байт на модель выльются в общей сложности в несколько сотен килобайт, что не такая уж большая потеря на фоне имеющихся гигабайтов. Дело в том, что лишние данные в объекте ещё и уменьшают производительность. Модель, вместо того, чтобы уместиться, скажем, в двух кэш-строках, начинает занимать уже три, что увеличивает время выборки её данных при обработке. Поэтому есть необходимость как-то избавиться от лишних данных, при этом сохранив функциональность vector.
Первым решением было хранить указатель auto_ptr<vector>. Указатель занимает всё те же 4 байта, пустой указатель означает, что массив пуст, непустой ссылается на объект vector в куче. Но у такого решения есть ряд недостатков:
Более совершенное решение – разделить данные на две части. В объекте оставить только один указатель на начало массива, а остальные два указателя и распределитель памяти хранить в том же блоке памяти, что и элементы массива, в виде префикса непосредственно перед первым элементом. В этом случае для непустого массива памяти потребуется ровно столько же, сколько и для обычного vector. Для пустого массива достаточно хранить один указатель на статический пустой массив. Это лучше, чем нулевой указатель, так как позволяет избежать лишних проверок во многих методах.
В следующем участке коде реализована та же функциональность что и в первом, но с хранением части данных в префиксе:
Дополнительная косвенность остаётся, хотя и не во всех методах. Чтобы взять элемент по индексу достаточно указателя на начало массива, но чтобы добавить или удалить элемент, потребуется информация из префиксного блока. Для прохода по элементам массива также потребуется указатель из префиксного блока, но в этом случае всё равно нужно будет выбирать данные из первого элемента массива, который часто будет в той же кэш-строке, что и префиксный блок. Если говорить о размере генерируемого кода, то он почти не возрастает. Например, рассмотрим обычный цикл прохода по всем элементам массива:
Компилятор VS2005 создаёт следующий код для стандартного vector-а:
И для «облегчённого» vector-а:
Как видно, код создался почти одинаковый, за исключением пятой строки, в первом случае указатель на конец массива берётся относительно указателя на объект vector ([eax+4]), а во втором – относительно указателя на первый элемент массива ([esi-8]).
Нужно отметить некоторые сложности с распределителями памяти, которые возникают при такой реализации. Если распределитель нестандартный, а, например, выравнивающий на границу кратную какой-то степени двойки, то он будет выравнивать начало префиксного блока, а элементы сместятся на размер этого блока. В таких случаях придётся либо делать специальный распределитель, учитывающий размер префиксного блока, либо вводить подобную возможность в сам шаблон массива.
В качестве заключения приведу цифры из реального проекта, в котором активно используется такой контейнер. При общем количестве объектов vector примерно 270 тысяч, пустыми остаются около 170 тысяч, что означает экономию более одного мегабайта памяти. По сравнению с кодом, использующим стандартный контейнер vector объём кода увеличился несущественно – на 48 кб, при общем объёме около 10 Мб. Производительность немного повысилась, примерно на 1%.
Сначала нужно разобраться для чего эта память используется, и сколько её требуется. Помимо указателя на начало массива в шаблоне хранится указатель на конец заполненного массива, указатель на конец выделенного массива, и распределитель памяти. Для иллюстрации приведу кусочек кода:
// Стандартный базовый класс для шаблона массива
template < class TEntry, class TAllocator > class TArrayBase
{
// Начало массива
TEntry* GetStart() const { return m_Start; }
// Конец массива (указатель на элемент, следующий после последнего)
TEntry* GetFinish() const { return m_Finish; }
// Конец выделенного массива (указатель на элемент, следующий после последнего)
TEntry* GetEndAllocated() const { return m_Storage._M_data; }
// три указателя и распределитель памяти
TEntry* m_Start;
TEntry* m_Finish;
// реализация, совмещающая распределитель и указатель
// на конец выделенного массива в одном объекте
_STLP_alloc_proxy<TEntry*, TEntry, allocator_type> m_Storage;
};
Для 32-битного x86 кода, где на указатель требуется 4 байта, такой объект займёт 12 байт. Если используется распределитель памяти без полей данных и виртуальных функции (стандартный распределитель именно такой), то в удачной реализации он места не займёт, по крайней мере, в реализации STLPort это так. В библиотеке для VS2005 реализация менее удачная и распределитель добавит ещё 4 байта. Таким образом, требуется минимум 8 дополнительных байт, по сравнению с указателем на обычный массив.
Казалось бы, что такое эти 8 байт, мелочь, теряющаяся рядом с размером памяти, которая потребуется для хранения самих элементов массива. Тем не менее, часто бывает, что значительное число массивов будут пустыми. Например, есть игровая модель, у неё могут быть источники света, источники звука, повреждения и прочие атрибуты. Их нужно где-то хранить, и массивы для этого вполне подходят, но у большей части моделей есть только геометрия, и эти массивы останутся незаполненными.
Чем плохи эти лишние байты? Память в наше время дешева, и десяток-другой лишних байт на модель выльются в общей сложности в несколько сотен килобайт, что не такая уж большая потеря на фоне имеющихся гигабайтов. Дело в том, что лишние данные в объекте ещё и уменьшают производительность. Модель, вместо того, чтобы уместиться, скажем, в двух кэш-строках, начинает занимать уже три, что увеличивает время выборки её данных при обработке. Поэтому есть необходимость как-то избавиться от лишних данных, при этом сохранив функциональность vector.
Первым решением было хранить указатель auto_ptr<vector>. Указатель занимает всё те же 4 байта, пустой указатель означает, что массив пуст, непустой ссылается на объект vector в куче. Но у такого решения есть ряд недостатков:
- для непустого массива требует дополнительной памяти на указатель (4 байта) и на блок в куче (используемая реализация кучи добавляет 4 служебных байта на блок);
- появляется дополнительная косвенность, так как vector лежит в отдельном блоке кучи, что тоже плохо для кэша;
- при использовании требуется постоянно проверять указатель, что приводит к ошибкам.
Более совершенное решение – разделить данные на две части. В объекте оставить только один указатель на начало массива, а остальные два указателя и распределитель памяти хранить в том же блоке памяти, что и элементы массива, в виде префикса непосредственно перед первым элементом. В этом случае для непустого массива памяти потребуется ровно столько же, сколько и для обычного vector. Для пустого массива достаточно хранить один указатель на статический пустой массив. Это лучше, чем нулевой указатель, так как позволяет избежать лишних проверок во многих методах.
В следующем участке коде реализована та же функциональность что и в первом, но с хранением части данных в префиксе:
// Класс хранения информации о параметрах компактного массива (префиксный блок)
template < class TAllocator >
class TTinyArrayStorage
{
// Конец массива
char *Finish;
// Распределитель и конец выделенного массива
_STLP_alloc_proxy<char*, char, allocator_type> Storage;
// Статический пустой массив
static TTinyArrayStorage<TAllocator> EmptyStorage;
};
// Облегчённый базовый класс для шаблона массива
template < class TEntry, class TAllocator >
class TTinyArrayBase
{
// Начало массива
TEntry* GetStart() const { return m_Data; }
// Конец массива (указатель на элемент, следующий после последнего)
TEntry* GetFinish() const { return (TEntry*)GetStorage()->Finish; }
// Конец выделенного массива (указатель на элемент, следующий после последнего)
TEntry* GetEndAllocated() const
{ return (TEntry*)GetStorage()->Storage._M_data; }
// Указатель на префикс с остальными параметрами массива
TTinyArrayStorage<TAllocator> *GetStorage() const
{ return (TTinyArrayStorage<TAllocator>*)(((char *)m_Data) -
sizeof(TTinyArrayStorage<TAllocator>)); }
// Начало массива
TEntry *m_Data;
};
Дополнительная косвенность остаётся, хотя и не во всех методах. Чтобы взять элемент по индексу достаточно указателя на начало массива, но чтобы добавить или удалить элемент, потребуется информация из префиксного блока. Для прохода по элементам массива также потребуется указатель из префиксного блока, но в этом случае всё равно нужно будет выбирать данные из первого элемента массива, который часто будет в той же кэш-строке, что и префиксный блок. Если говорить о размере генерируемого кода, то он почти не возрастает. Например, рассмотрим обычный цикл прохода по всем элементам массива:
for(vector<TFoo>::iterator i = in_data.begin(), e = in_data.end(); i != e; ++i)
i->Process();
Компилятор VS2005 создаёт следующий код для стандартного vector-а:
00401340 8B 44 24 04 mov eax,dword ptr [esp+4]
00401344 56 push esi
00401345 8B 30 mov esi,dword ptr [eax]
00401347 57 push edi
00401348 8B 78 04 mov edi,dword ptr [eax+4]
0040134B 3B F7 cmp esi,edi
0040134D 74 0F je Test+1Eh (40135Eh)
0040134F 90 nop
00401350 8B CE mov ecx,esi
00401352 E8 D9 FF FF FF call TFoo::Process (401330h)
00401357 83 C6 04 add esi,4
0040135A 3B F7 cmp esi,edi
0040135C 75 F2 jne Test+10h (401350h)
0040135E 5F pop edi
0040135F 5E pop esi
00401360 C3 ret
И для «облегчённого» vector-а:
00401370 8B 44 24 04 mov eax,dword ptr [esp+4]
00401374 56 push esi
00401375 8B 30 mov esi,dword ptr [eax]
00401377 57 push edi
00401378 8B 7E F8 mov edi,dword ptr [esi-8]
0040137B 3B F7 cmp esi,edi
0040137D 74 0F je Test+1Eh (40138Eh)
0040137F 90 nop
00401380 8B CE mov ecx,esi
00401382 E8 A9 FF FF FF call TFoo::Process (401330h)
00401387 83 C6 04 add esi,4
0040138A 3B F7 cmp esi,edi
0040138C 75 F2 jne Test+10h (401380h)
0040138E 5F pop edi
0040138F 5E pop esi
00401390 C3 ret
Как видно, код создался почти одинаковый, за исключением пятой строки, в первом случае указатель на конец массива берётся относительно указателя на объект vector ([eax+4]), а во втором – относительно указателя на первый элемент массива ([esi-8]).
Нужно отметить некоторые сложности с распределителями памяти, которые возникают при такой реализации. Если распределитель нестандартный, а, например, выравнивающий на границу кратную какой-то степени двойки, то он будет выравнивать начало префиксного блока, а элементы сместятся на размер этого блока. В таких случаях придётся либо делать специальный распределитель, учитывающий размер префиксного блока, либо вводить подобную возможность в сам шаблон массива.
В качестве заключения приведу цифры из реального проекта, в котором активно используется такой контейнер. При общем количестве объектов vector примерно 270 тысяч, пустыми остаются около 170 тысяч, что означает экономию более одного мегабайта памяти. По сравнению с кодом, использующим стандартный контейнер vector объём кода увеличился несущественно – на 48 кб, при общем объёме около 10 Мб. Производительность немного повысилась, примерно на 1%.