Для незнакомых с этой очень интересной тематикой советую посмотреть обзор на вики. Для более полного понимания проблемы: детальный обзор у Кнута в 1 томе Искусство программирования в разделе 2.5 Динамическое выделение памяти, на хабре, а также одну из лучших реализаций на C/C++ Hans Boehm.
Сразу оговорюсь, предлагаемый мною подход принципиально отличается от вышеизложенных и основан на реализации ООП в C++. В топики приведено описание готовой библиотеки и ссылка на исходники.
Основные положения
Вот цитата из ссылки на вики: Сборщик мусора может нормально функционировать только тогда, когда он может точно отследить все ссылки на все созданные объекты. Очевидно, если язык допускает преобразование ссылок (указателей) в другие типы данных (целые числа, массивы байтов и так далее), такой как Си/Си++, отследить использование таких преобразованных ссылок становится невозможно, и сборка мусора становится бессмысленной — она не защищает от «повисания» ссылок и утечек памяти. Поэтому языки, ориентированные на использование сборки мусора, обычно существенно ограничивают свободу использования указателей, адресной арифметики, преобразований типов указателей к другим типам данных. В части из них вообще нет типа данных «указатель», в части он есть, но не допускает ни преобразований типа, ни изменения.
Я предлагаю следующую альтернативу, ограничить использование указателей внутри класса C++ объявив их в закрытой области видимости. При правильной технологии ООП, а это свойство называется инкапсуляцией, это и так надо делать, пользователь не должен видеть как реализован класс, он должен использовать только его интерфейс. Во-вторых, в C++ имеется выделенный конструктор копирования, который позволяет построить копию объекта. Осталось для выбранного класса определить функцию swap, для подмены объекта на его копию, и можно организовывать «сборку мусора» на C++.
Пример использования
Рассмотрим простейший класс с динамическим выделением памяти, линейный однонаправленный список целых чисел.
01 #include "allocator.h"
02
03 class List {
04 struct Node {
05 int mData;
06 Node* mNext;
07
08 Node(int data, Node* next=NULL):
09 mData(data),
10 mNext(next) {
11 }
12 ~Node() {}
13 };
14
15 Allocator* mAllocator;
16 Node* mHead;
17
Основное отличие от обычного кода строчка 15, где содержится объявление переменной указателя на тип Allocator. В строках 23 и 27 показано его использование для выделения и освобождения памяти. Освобождение использует шаблонную функцию, поскольку перегрузку стандартого delete дополнительными аргументами позволяют не все компиляторы C++. Для базовых типов и классов, для которых в принципе не нужен вызов деструктора, определена шаблонная функция dealloc. Destroy и dealloc могут также дополнительно вызываться с дополнительным целочисленным аргументом для удаления массивов.
18 public:
19 List(Allocator *allocator):
20 …
21 List(const List& a, Allocator *allocator):
22 …
23 *mLink = new(mAllocator) Node(i, *mLink);
24 …
25 Node* tmp=*mLink;
26 *mLink = tmp->mNext;
27 mAllocator->destroy(tmp);
28 …
29 void swap(List &a) {
30 Allocator *tmp1=mAllocator;
31 mAllocator = a.mAllocator;
32 a.mAllocator = tmp1;
33
34 Node* tmp2 = mHead;
35 mHead = a.mHead;
36 a.mHead = tmp2;
37 }
38 …
39 };
В строчках 21 и 29 содержатся заголовки конструктора-копирования и функции swap, которые необходимы для замены текущего объекта на его копию. Если Вы хотите для своего класса использовать оператор =, то его тоже необходимо реализовать. Он, как известно, не наследуется, но поддержка в классе шаблона GC имеется.
Ниже дан пример его использования. На строке 41 объявляем новый тип GCList. Затем вызываем на строке 43 конструктор по умолчанию. Предположим на строке 44 производим массовые операции по выделению/освобождению памяти. Память выделяется блоками, кратными размеру страницы памяти, затем раздается внутри конкретного объекта класса List. Если процент не используемой памяти высок, то вызов reallocate на строке 45 приведет к построению копии объекта, с его последующей заменой на первоначальную переменную a.
40
41 typedef GC<List> GCList;
42 …
43 GCList a;
44 …
45 a.reallocate();
46 …
47
Естественно, вызов reallocate может происходит неоднократно, согласуясь с логикой программы. Также, за счет показанных в следующем разделе очень простых решений попутно выполняются учет работы времени GC, текущая память, максимальная память и в debug версии программы проверки на утечки памяти.
Выделение памяти большими блоками очень выгодно, особенно для большего количества мелких объектов. Стандартные new, delete, malloc, free должны хранить на каждое выделение информацию о начале и конце куска памяти. В данном подходе этого не нужно, поскольку конкретный объект может с помощью конструктора-копирования построить свою копию и обратно очистить используемую память.
Замечу, что предлагаемый подход, позволяет собирать объект из «кирпичиков» с общим Allocator-ом. Лишь бы в каждом инкапсулированом объекте память выделялась/освобождалась с помощью указателя на общий Allocator и были определены, соответствующие конструкторы-копирования и функция swap.
Можно также, как показано ниже, определять Allocator вначале блока и затем его использовать для работы с автоматическими переменными, использующими Allocator. После закрытия блока вся занятая ими память будет возвращена в систему.
{
Allocator a[1];
…
List lst(a);
…
}
Одной из причин, побудивших меня написать такую библиотеку, было заманчивое предложение использовать в качестве менеджера памяти следующей реализации Google. Мои первые тесты сразу показали ускорение на 10-20%, но сразу пришло и разочарование. При многих плюсах самой библиотеки, оказалось, что ускорение достигается за счет вынесения выделения памяти в отдельные потоки и если все процессоры были заняты, то ускорения практически не было. Предлагаемый подход лишен этого недостатка. Память в нем выделяется блоками, а затем уже раздается внутри объекта, поэтому при распараллеливании программы резко снижается количество обращений к глобальной памяти и его менеджеру. Т.е. уменьшается количество переключений между потоками.
Здесь приведены времена работы GC на разных примерах для задачи построения базисов Грёбнера булевых полиномов, которые решают SAT — задачи. Например, использование стандартных malloc и free замедлило, по сравнению с предлагаемым подходом, время расчета примера ezfact32_4.shuffled.cnf c 354.57 сек («сборка мусора» +1.31 сек) до 669.32 сек. В проекте много динамических структур данных и все они используют эту реализацию GC: мономы (в виде массивов номеров переменных разной длины), всевозможные списки, красно-черные деревья, деревья Janet и ZDD-диаграммы.
Ссылка на исходники. Следующий раздел описывает, если интересно, подробности реализации.
Технические детали
В приведенных ниже листингах приведены наглядные комментарии и я думаю не трудно понять, при чтении, основные элементы реализации. Для простоты в коде удаленно использование таймера и код ответственный за переключение на стандартные malloc, free.
01 #include <cstdlib>
02 #include <cassert>
03
04 class Allocator {
05 static size_t sCurrMemory; // Текущая память
06 static size_t sMaxMemory; // Максимальная память
07
08 struct Node {
09 void* mPointer; // Указатель на блок памяти
10 Node* mNext; // Следующий блок памяти
11
12 Node(size_t size, Node* next=NULL):
13 mPointer(malloc(size)),
14 mNext(next) {
15 }
16 ~Node() { free(mPointer); }
17 };
18
19 size_t mAlloc; // Выделенная память
20 size_t mSize; // Используемая память
21 Node* mRoot; // Список блоков памяти
22 size_t mNodeAlloc; // Выделенная память для последнего блока
23 size_t mNodeSize; // Используемая память для последнего блока
24
25 public:
26 static size_t maxMemory() { return sMaxMemory; }
27 static size_t currMemory() { return sCurrMemory; }
28
29 Allocator();
30 Allocator(const Allocator& a);
31 ~Allocator();
32
33 void* allocate(size_t n); // низкоуровневое выделение памяти
34 void deallocate(void* ptr, size_t n); // низкоуровневое освобождение памяти
35
36 template <typename T>
37 inline void dealloc(T *ptr) { // освобождение памяти
38 deallocate(ptr, sizeof(T));
39 }
40 template <typename T>
41 inline void dealloc(T *ptr, size_t n) { // освобождение памяти для массива
42 assert(n > 0);
43 deallocate(ptr, sizeof(T)*n);
44 }
45 template <typename T>
46 inline void destroy(T *ptr) { // освобождение памяти с вызовом деструктора
47 ptr->~T();
48 deallocate(ptr, sizeof(T));
49 }
50 template <typename T>
51 inline void destroy(T *ptr, size_t n) { // освобождение памяти с вызовом деструктора для массива
52 assert(n > 0);
53 for(int i=0; i < n; i++)
54 ptr[i].~T();
55 deallocate(ptr, sizeof(T)*n);
56 }
57
58 size_t alloc() const { return mAlloc; }
59 size_t size() const { return mSize; }
60 bool isGC() const; // возвращает true если нужно делать "сборку мусора"
61 };
62
Вспомогательный класс на строке 63, нужен только потому, что вызов конструктора наследуемого класса происходит раньше, чем для полей конструируемого класса, а деструкторов в обратном порядке. Другими словами конструктор AllocatorPtr будет вызван первым при создании класса GC, а его деструктор соответственно последним.
Кстати, этот пример показывает для чего нужно множественное наследование. А так пришлось бы вводить промежуточный класс, тем самым излишне усложняя код.
63 class AllocatorPtr { // Вспомогательный класс
64 Allocator* mAllocator;
65
66 public:
67 AllocatorPtr():
68 mAllocator(new Allocator) {
69 }
70 AllocatorPtr(const AllocatorPtr& a):
71 mAllocator(new Allocator(*a.mAllocator)) {
72 }
73 ~AllocatorPtr() { delete mAllocator; }
74
75 const Allocator* allocator() const { return mAllocator; }
76 Allocator* allocator() { return mAllocator; }
77
78 void swap(AllocatorPtr& a) {
79 Allocator *tmp=mAllocator;
80 mAllocator = a.mAllocator;
81 a.mAllocator = tmp;
82 }
83 };
84
85 template <typename T>
86 class GC: protected AllocatorPtr, public T {
87 public:
88 GC():
89 AllocatorPtr(),
90 T(allocator()) {
91 }
92 GC(const GC &a):
93 AllocatorPtr(a),
94 T(a, allocator()) {
95 }
96 GC(const T &a):
97 AllocatorPtr(),
98 T(a, allocator()) {
99 }
100 ~GC() {}
101
102 void operator=(const GC &a) {
103 assert(this != &a);
104 T::operator=(a);
105 }
106 void swap(GC &a) {
107 AllocatorPtr::swap(a);
108 T::swap(a);
109 }
110 void reallocate() {
111 if (allocator()->isGC()) {
112 GC a(*this);
113 swap(a);
114 }
115 }
116
117 size_t alloc() const { return allocator()->alloc(); }
118 size_t size() const { return allocator()->size(); }
119 bool isGC() const { return allocator()->isGC(); }
120 };
121
122 using namespace std;
123
124 inline void* operator new(size_t size, GInv::Allocator* allocator) {
125 return allocator->allocate(size);
126 }
127
128 inline void* operator new[](size_t size, GInv::Allocator* allocator) {
129 return allocator->allocate(size);
130 }
131
Здесь реализация в файле allocator.cpp
01 #include "allocator.h"
02
03 const size_t memoryPageSize=4096; // размер страницы
04
05 Allocator::Allocator():
06 mAlloc(0),
07 mSize(0),
08 mRoot(NULL),
09 mNodeAlloc(0),
10 mNodeSize(0) {
11 }
12
13 Allocator::Allocator(const Allocator& a):
14 mAlloc(0),
15 mSize(0),
16 mRoot(NULL),
17 mNodeAlloc(0),
18 mNodeSize(0) {
19 mNodeAlloc = memoryPageSize;
20 mAlloc = mNodeAlloc;
21 mRoot = new Node(mNodeAlloc);
22 sCurrMemory += mNodeAlloc;
23 sMaxMemory = (sMaxMemory > sCurrMemory) ? sMaxMemory: sCurrMemory;
24 }
25
26 Allocator::~Allocator() {
27 assert(mSize == 0);
28 sCurrMemory -= mAlloc;
29 while(mRoot) { // очистка списка блоков памяти
30 Node *tmp = mRoot;
31 mRoot = mRoot->mNext;
32 delete tmp;
33 }
34 }
35
36 void* Allocator::allocate(size_t n) {
37 assert(n > 0);
38 if (mNodeSize + n > mNodeAlloc) { // если памяти в текущем блоке мало
39 mNodeAlloc = ((n + memoryPageSize) / memoryPageSize)*memoryPageSize;
40 mAlloc += mNodeAlloc;
41 mRoot = new Node(mNodeAlloc, mRoot);
42 mNodeSize = 0;
43 sCurrMemory += mNodeAlloc;
44 sMaxMemory = (sMaxMemory >= sCurrMemory) ? sMaxMemory: sCurrMemory;
45 }
46 assert(mNodeSize + n <= mNodeAlloc);
47 void *r=(char*)mRoot->mPointer + mNodeSize;
48 mSize += n;
49 mNodeSize += n;
50 return r;
51 }
52
53 void Allocator::deallocate(void*, size_t n) {
54 assert(n > 0);
55 assert(mSize >= n);
56 mSize -= n;
57 }
58
59 bool Allocator::isGC() const { // чисто эмпирические соображения
60 return mAlloc > memoryPageSize && mAlloc > mSize*2;
61 }
Автор: bya
