Бързо и лесно заделяне на място

Въведение

Всеки знае за димачното заделяне на паметта. Никое сериозно приложение не може без този механизъм - директно или индиректно. Неизбежно подразбиращата се имплементация на динамично заделяне на паметта трябва да бъде много опростена и генерална, за да се покрие широк спектър от възможни вариации. За тази всеобхватност често се заплаща с времето за заделяне/освобождаване на памет или заделяне на излишна памет.

Някои очевидни примери са имплементациите на заделяне на памет в стандартната C/C++ библиотека и бързата библиотека , която има оригиналната дистрибуция BSD 4.2 . Първата е относително икономична и мнооого бавна, докато втората е по-бърза, но консумира средно 50 процента повече памет от стандартната. Неефективното използване на паметта се получава от факта, че библиотеката заделя фиксирани по големина блокове памет(Всеки следващ е два пъти по-голям от предишния). Ако има заявка за блок от памет малко по-голям от най-близкия възможен размер ще се задели почти два ъти повече от заявката.

C++ ни позволява да си напишем собствен ефективен алокатор на памет, а след това да го интегрираме невидимо в класовете, които правим. За съжаление много програмисти/практици са прекалено обхжанати от всекидневната разработка, за да мислят за подобни проблеми като оптимизация на производителността и използването на паметта, преди да е станало прекалено късно за интегриране на подобрения в съществуващия дизайн. Попадайки неведнъж в подобна ситуация реших да отделя няколко нощи, за да напиша практичен и лесен за употреба класс за заделяне на памет. Моите цели включваха:

• оптимизация на механизма на заделяне/освобождаване на памет,
• простота на употреба и интеграция с други класове,
• минимално използване на излишна статична и операционна памет, и
  
• възможност за проверка на цялосста на заделените блокове с памет.

Имам чувството, че останалите програмисти ще има полза от тази имплементация.

Основната идея не е нова. тя е обяснена в доста списания и книги. Стартовата точка за оптимизация е предположението,че повечето заделяния на памет са свързани с инстанции на клас. Това означава,че блокове с еднакъв размер се заделят и освонождават отново и отново. Този размер е размерът на инстанцията. Тъй като знаем размера можем да заделим достаъчно големи блокове, които да съдържат повече от една инстанция и да поддържаме пуул от освободени блокове, за да ги използваме по-късно пак, вместо постоянно да ги освобождаваме.

Нищо ново. Но след като пробвах предварителната имплементация на идеята бях изумен от откритието, че тя работеше единадесет(!) пъти по-бързо от стандартното заделяне. В крайна сметка, с помощта на малко подозрителни операции успях да подобря производителността с десет до 20 пъти, в зависимост от шаблона за заделяне и опците на компилатора.

Примерна употреба

Освен за производителността доста помислих и за простотата на употреба и интегриране в останалите класове. Алокаторите са единствено поддържащи класове и ,което е важно, те играят второстепенна роля в разработката на софтуер. Порати това интерфейса на класа алокатор трябва да е минимален, а капсулацията максимална. Например:

class Foo
{
public:    // the Foo specific stuff

void* operator new (size_t)
{ return _allocator.allocate(); }
void operator delete (void* storage)
{_allocator.deallocate(storage); }

private:    // more of the Foo stuff
static TheAllocator _allocator;
};

TheAllocator Foo::_allocator;

операторите new и delete на класа Foo са предефинирани, за да се замени заделянето на памет по подразбиране. Целият нов механизъм за заделяне е напълно капсулиран в класа TheAllocator. Непретенциозния интерфейс - allocate() и deallocate(void*) - е достатъчен. Инстанция от класа TheAllocator _allocator е свързана с класа Foo чрез статична декларация в класа. Алокатор с подобен интерфейс може да се включи за секунди и е много трудно да се сбърка. Като допълнителна опция е осигурен прост дебъгер, който се извиква чрез допълнителен параметър на конструктора на TheAllocator . Не някакво чудо, но може да е полезен в началото на разработката при преглеждане на цялостта на заделената памет. Просто променете статичното инициализиране от :

TheAllocator Foo::_allocator;

в:

TheAllocator Foo::_allocator(true);

и всяко парче памет ще бъде тествано преди да се освободи. Ако парчето е повредено по някакъв начин( презаписано е началото или в края) ще се появи изключение. За да обработите изключението може да промените оператора delete :

void operator delete (void* storage)
{
try {
_allocator.deallocate(storage);
}
catch(char*) {
// Do something about it.
}
};

Подобна проста помощ не може да се сравни с продуктите за дебъг на паметта като Purify и подобните му, но го има и може да го използвате. Струва си да се спомене, че премахването на кода за проверка на цялостта на паметта подобрява производителността с осем процента.

Имплементацията

Имплементацията се състои от два класа - MemoryAllocator и TheAllocator. Функционалността лесно може да бъде реализирана и само с един клас. Самодостатъчният, основен и безтипов MemoryAllocator реализира целият механизъм без да има нужда от шаблонни методиTheAllocator осигурява по-добър интерфейс за класа. Когато създаваме инстанция от класа подаваме размера на паметта за обекта, която да бъде заделена(unit_size) и броят на обектите, които да се заделят на един път (block_size). Останалото е почти автоматично - всяко извикване на allocate() връща парче от памет с размер unit_size. Методът взема първата налична свободна памет от списък със свободни. Неговата единствена допълнителна работа е да поиска повече свободни парчета, ако списъкът е празен. Методът deallocate(void*) е прост и бърз като allocate(). Той прави обратното - слага блост свободна памет в листа със свободни за бъдещо използване. Не е чудно , че алокаторът е бърз - методите не правят много. Само методите allocate() и deallocate(void*) са inline, поради производителността, но дори и те може да не са такива. Имплементацията на по-малко използваните функции бе преместена от хедърен файл в сорс файл за намаляване на inline функциите. Не забелязах намаляне на производителността. Кода на тези функции е :

#include "include/allocmem.h"
   
#define TRAILING_ 0x55555555
#define HEADING_ 0x55555555
   
MemoryAllocator::MemoryAllocator(uint unit_size, uint block_size)
   : _allocated_size (max(unit_size, sizeof(Free))),
   _requested_size(unit_size),
   _block_size(block_size),
   _num_allocated_blocks(0),
   _allocated_blocks(0),
   _free(0),
   _debug (false)
   {}
   
MemoryAllocator::MemoryAllocator(uint unit_size, uint block_size,
   bool debug)
   : _allocated_size(max(unit_size, sizeof(Free))),
   _requested_size(unit_size),
   _block_size(block_size),
   _num_allocated_blocks(0),
   _allocated_blocks(0),
   _free(0),
   _debug(debug)
   {
   if (_debug)
       _allocated_size += 2 * sizeof(int);
   }
   
MemoryAllocator::~MemoryAllocator()
   {
   for (int k = 0; k < _num_allocated_blocks; ++k)
       {
       ::operator delete(_allocated_blocks[k]);
       }
   ::operator delete(_allocated_blocks);
   }
   
void
MemoryAllocator::more() throw(char*)
   {
   Free* new_block = (Free*)
       ::operator new(_allocated_size *_block_size);
   void** new_blocks = (void**) ::operator new(sizeof(void*)
       * (_num_allocated_blocks + 1));
   int last_element = _block_size - 1;
   if (!new_block || !new_blocks)
       throw("Memory allocation failed.");
   if (_allocated_blocks)
       {
       memcpy(new_blocks, _allocated_blocks, sizeof(void*)
           * _num_allocated_blocks);
       ::operator delete(_allocated_blocks);
       }
   _allocated_blocks = new_blocks;
   _allocated_blocks[_num_allocated_blocks++] = new_block;
   _free = new_block;
   
   for (int k = 0; knext)
       {
       new_block->next = (Free*) ((char*) new_block
           + _allocated_size);
       }

   new_block->next = 0;
   }
   
void*
MemoryAllocator::debug_correct(void*& storage)
   {
   *(int*) storage = HEADING_;
   storage = (int*) storage + 1;
   *(int*) ((char*) storage + _requested_size) = TRAILING_;
   return storage;
   }
   
void*
MemoryAllocator::debug_check(void*& storage) throw(char*)
   {
   int* tail = (int*) ((char*) storage + _requested_size);
   int* head = (int*) (storage = (int*) storage - 1);
   
   if (*tail != TRAILING_)
       throw("Block tail has been overrun.");
   if (*head !=  HEADING_)
       throw("Block header has been overrun.");
   return storage;
   }
//End of File

Както е отбелязано по-горе, когато даден блок от памет не се използва той се добавя в списъка със свободни. Мястото на обект,който се освобождава се използва за запазване на указател на следващия свободен обект. Указателят се записва в началото на текущото паряе . Това означава, че размера на блока не може да е по-малък от размера на указател. Това изискване се изпълнява в конструктора на MemoryAllocator, в който размера на блока памет е:

_allocated_size = max(unit_size, sizeof(Free))

който може да е различен от реално поисканото място. Методът, който върши работата е по-голям. Той иска от системата повече памет и подготвя листа със свободните. Но тъй като заделяме памет за няколко обекта (по подразбиране 16) , правим доста по-рядко заявки от стандартната имплементация. Още повече, че подобно заделяне не причинява използване на толкова излишна памет, както стандартната имплементация. Ако искаме да разрешим проверка на цялостта ще се заделя малко повече памет за всеки обект:

if (_debug)
 _allocated_size += 2 * sizeof(int);

Информационната част от парчето памет е оградено с две целочислени числа, глава и опашка. Методът debug_correct извършва необходимите корекции. Тези числа се проверяват при освобождаване на парчета памет, за да е сигурно . че техните стойности не са променени. тази проверка се извършва от метода debug_check . Класът MemoryAllocator е завършен и може да се използва самостоятелно. Но мисля, че не е много добър. Липсва визуална асоциация с класа за който заделя памет , Foo в нашия пример. Шаблонния клас TheAllocator изпълнява ролята на посредник. Той позволява използването на MemoryAllocator без нищо допълнително. Неговият публияен интерфайс е :

template
class TheAllocator : public MemoryAllocator
 {
public:
 TheAllocator(bool debug = false, uint block_size =16)
   : MemoryAllocator(sizeof(T), block_size, debug)
   {}
 };

Тестване

Тствах имплементацията на IBM PC с OS/2 версия 2.11 и UnixWare 2.03. Тестът беше много прост - само измерих времето за изпълнение на този код:

#define NUM_CYCLES 50000
#define NUM_CHUNKS 18
   
CLASS* array[222];
   
for (int n = 0; n < NUM_CYCLES; ++n) {
 for (int k = 0; k < NUM_CHUNKS; ++k)
   array[k] = new CLASS;
 for (k = 0; k < NUM_CHUNKS; ++k)
   delete array[k];
 }

Тествах следните два подобни класа, използвайки стандартната и оптимизираната схема :

struct Std
 {
 int _1;
 int _2;
 int _3;
 int _4;
 };
struct New
 {
 int _1;
 int _2;
 int _3;
 int _4;
 void* operator new(size_t)
   { return _allocator.allocate(); }
 void operator delete(void* p)
   { _allocator.deallocate(p); }
 static TheAllocator _allocator;
 };

Тази реализация бе от 10.6 до 10.9 пъти по-производителна от стандартнатапри операционна система OS/2 . Дори с увеличаване на NUM_CHUKS на 180 се постига резултат от 11.5 до 11.7 . На UnixWare резултатът бе още по-впечатляващ. За NUM_CHUNKS равно на 18 и 180 съответното подобрение в производителността беше 13.0 и 19.9 пъти. Като интересно наблюдение искам да отбележа, че нашият алокатор се представя константно, независимо от броя на парчетата памет, коиото се заделят. Подобрението в относителната производителност при по-голям брой заделени парчета памет (180) е заради намалянето на производителността на стандартния алокатор.

Ограничения и подобрения

Първото и очевидно "ограничение" е ,че TheAllocator не е напълно общ клас. Негови инстанции се прикрепът към класа, за който заделя памет- в нашия пример класа Foo. Сложих "ограничение" в кавички, защото това не е истинско ограничение. Точно обратното - това е логичен начин за капсулиране на всички свързани с класа детайли, включително заделянето на паметта, в рамките на този клас. Сигурна катастрофа е използването на MemoryAllocator за постигане на допълнителна оптимизация, например:

class ABAllocator : public MemoryAllocator
 {
public:
 ABAllocator(bool debug = false, uint block_size =16)
   : MemoryAllocator(8, block_size, debug)
  {}
 };
extern ABAllocator allocator;
   
class A
 {
public:
 void* operator new(size_t)
   { return allocator.allocate(); }
 void operator delete(void* p)
   { allocator.deallocate(p); }
private:
 int _1;
 int _2;
 };
   
// Instances of B happened to be the
// same size as instances of A
class B
 {
public:
 void* operator new(size_t)
   { return allocator.allocate(); }
 void operator delete(void* p)
   { allocator.deallocate(p); }
private:
 int _1;
 int _2;
 };

Второ ограничение може да е неспособността на класа TheAllocator да заделя памет за масив от обекти от клас Foo. Аз не мисля че това е голям проблем. Лично аз не съм стигал до подобно положение, защото използвам масиви от указатели за самостоятелно заделени инстанции от класа Foo. Масивите от указатели не са тежки за паметта, а са по-гъвкави за употреба. Очевидно тези масиви поддържат сортиране, вмъкване, премахване и други подобни. С заделянето на инстанциите една по една вместо заделянето им в масив не губим от производителността. Освен това получаваме възможноостта да създаваме елементите на тези масиви с помощта на специфични конструктори, а не само конструктора по подразбиране. Трето ограничение е повече предупреждение или добавяне на фукционалност. Деструкторът на MemoryAllocator просто обикаля списъка от заделени блокове и ги освобождава като блок памет. Очевидно ако създадем инстанция от класа Foo и не я изтрием преди да сме премахнем инстанцията на алокатора, няма да се извика деструктора на Foo. Това трябва да се очаква, защото MemoryAllocator само заделя памет. Той не знае абсолютно нищо за това как заделената памет се използва. Този проблем може да се реши с предефниране на деструктора на TheAllocator. За всеки обект в паметта във всеки заделен блок трябва да сканираме списъка със свободни, за да проверим дали обектът е бил освободен. Ако не е може да извикаме нарочно деструкторът на Foo. Деструкторът на алокаторът най-вероятно ще бъде извикан при затваряне на приложението, така че ще има предостатъчно време за минаване през подобни пруцедури, за да подсигурим освобождаването на цялата памет. Сега деструктора на TheAllocator е:

template
TheAllocator::~TheAllocator()
 {
 for (int k = 0;
      k < _num_allocated_blocks;
      ++k)
   {
   void* the_block =
       _allocated_blocks[k];
   for (int n = 0;
        n < _block_size; ++n)
     {
     void* the_unit =
         (char*) the_block + n *
       _allocated_size;
     for (Free* free_unit = _free;
       free_unit;
       free_unit = free_unit->next)
       {
       if (free_unit == the_unit)
         // The unit has already
         // been freed
         break;
       }
     if (!free_unit)
       // is still in use
       ((T*) the_unit)->~T();
     }
   }
 }

Владимир Батов в софтуерен разработчик, живеещ в Австралия.