C++: библиотека программиста

 
229 
Оптимизация в особых ситуациях 
Если адрес переменной класса получать не требуется, ее можно хранить в виде внедренного объекта. 
Впрочем, как показывает следующий фрагмент, ситуация не всегда находится под контролем 
разработчика класса: 
void f(int); 
class Foo { 
private: 
int 
x; 
// 
Адрес получать не нужно, поэтому храним непосредственно 
public: 
void F() { f(x); } 
}; 
Вышядит вполне безопасно, не правда ли? А теперь предположим, что автор функции 
f()
привел ее 
интерфейс к следующему виду: 
void f(int&); 
И вот вся тщательно спроектированная оптимизация обрушивается вам на голову. У внедренных 
объектов есть еще одна проблема: вы должны проследить не только за тем, чтобы никогда не получать 
адрес объекта, но и за тем, чтобы никогда не получать адресов рекурсивно внедренных членов. 
class Bar { 
private: 
Foo 
foo; 
}; 
Допустим, вы сможете доказать, что ни одна из функций 
Bar
не получает адрес 
foo
. Но вам придется 
сделать следующий шаг и проследить еще и за тем, чтобы все функции 
Foo
тоже были безопасными. 
Та же логика относится и к базовым классам. Важно понимать, что такая оптимизация должна 
осуществляться на уровне всей программы, а не только проектируемого класса. 
Алгоритм Бейкера 
Один из алгоритмов уплотнения жертвует неимоверным количеством (а точнее, половиной) памяти в 
интересах скорости. Процесс уплотнения понемногу вплетается в обычную работу программы. Этот 
алгоритм называется алгоритмом Бейкера (Baker’s Algorithm). 
Пул памяти делится на две половины, A и B. В любой момент времени одна из этих половин является 
активной (то есть в ней создаются новые объекты). Память выделяется снизу вверх, а в момент 
удаления объекта не делается никаких попыток вернуть занимаемую им память. Время от времени все 
активные объекты копируются из одной половины памяти в другую. В процессе копирования 
автоматически происходит уплотнение нижней части новой активной половины. Активным называется 
объект, для которого в стане ведущих указателей найдется ссылающийся на него ведущий указатель (в 
нашем случае 
VoidPtr
). 
Пространства объектов 
Половины представлены в виде пространств памяти для создания объектов. Класс 
HalfSpace
изображает одну половину, а 
Space
— всю память, видимую клиентам. 
Класс HalfSpace 
Каждая половина по отдельности выглядит как обычное пространство памяти со специализированной 
функцией 
Allocate()
. Парная функция 
Deallocate()
не понадобится. 
class HalfSpace { 
private: 
unsigned long next_byte; // Следующий выделяемый байт 
unsigned char bytes[HALFSIZE]; 
public: 

---

 230 
HalfSpace() : next_byte(0) {} 
void* 
Allocate(size_t 
size); 
void Reinitialize() { next_byte = 0; } 
}; 
void* HalfSpace::Allocate(size_t size) 
{ 
// 
Выровнять до границы слова 
size = ROUNDUP(size); 
if (next_byte + size >= HALFSIZE) 
return 
NULL; 
// 
Не хватает памяти 
void* space = &bytes[next_byte]; 
next_byte += size; 
return 
space; 
} 
Класс Space 
Общий пул представляет собой совокупность двух половин. Он также имеет функцию 
Allocate()
, 
которая в обычных ситуациях просто поручает работу активной половине. Если в активной половине 
не найдется достаточно памяти, происходит переключение половин и копирование активных объектов 
в другую половину функцией 
Swap()
. Эта схема основана на предыдущем материале — 
специализированном пуле 
VoidPtr
со средствами перебора. 
class Space { 
private: 
HalfSpace A, B; 
HalfSpace* 
active; 
HalfSpace* 
inactive; 
void 
Swap(); 
// 
Переключить активную половину, скопировать объекты 
public: 
Space() : active(&A), inactive(&B) {}; 
void* 
Allocate(size_t 
size); 
}; 
void* Space::Allocate(size_t size) 
{ 
void* space = active->Allocate(size); 
if (space != NULL) return space; 
Swap(); 
Space 
= 
active->Allocate(size); 
if (space == NULL) 
// 
Исключение – нехватка памяти 
return 
space; 
} 
void Space::Swap() 
{ 
if (active == &A) 
{ 
active = &B; 
inactive 
= 
&A; 
} 
else 

---