Pull to refresh

«Облегчённая» реализация контейнера vector

C++ *
Sandbox
   Шаблон vector библиотеки STL выигрывает почти по всем параметрам у обычного С++ массива. Он позволяет добавлять и удалять элементы, освобождает выделенную память при уничтожении, позволяет контролировать выход за пределы массива и т.д. Тем не менее, у него есть один недостаток – для его работы требуется дополнительная память, небольшая, но в ряде случаев существенная. Ниже рассмотрена реализация контейнера, позволяющая немного снизить затраты памяти и повысить производительность.

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

// Стандартный базовый класс для шаблона массива
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 в куче. Но у такого решения есть ряд недостатков:
  1. для непустого массива требует дополнительной памяти на указатель (4 байта) и на блок в куче (используемая реализация кучи добавляет 4 служебных байта на блок);
  2. появляется дополнительная косвенность, так как vector лежит в отдельном блоке кучи, что тоже плохо для кэша;
  3. при использовании требуется постоянно проверять указатель, что приводит к ошибкам.
   Последний недостаток можно было бы легко устранить, сделав прокси-контейнер, хранящий указатель, и реализовать проверку внутри его методов.

   Более совершенное решение – разделить данные на две части. В объекте оставить только один указатель на начало массива, а остальные два указателя и распределитель памяти хранить в том же блоке памяти, что и элементы массива, в виде префикса непосредственно перед первым элементом. В этом случае для непустого массива памяти потребуется ровно столько же, сколько и для обычного 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%.
Tags:
Hubs:
Total votes 61: ↑51 and ↓10 +41
Views 15K
Comments 48
Comments Comments 48