Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Сборщик мусора на С

Anna | 24.06.2014 | нет комментариев
Привет, Прогр! Эту статью я замыслил достаточно давным-давно. Речь в ней пойдет о простейшем копирующем сборщике мусора на С . У него достаточно много ограничений (часть не мешает, часть дозволено обойти, если задаться целью написать какую-то солидную библиотеку, а для кое-чего недурно было бы заиметь зачаточную поддержку от языка), но и кода в нем чуть огромнее 100 строк. Заинтересовавшихся умоляю под кат. Там минимум ООП, простейшие образцы и ужасные волшебные обряды с указателями.

Начнем с начала. Что такое сборщик мусора и для чего он необходим?Сборщик мусора (Gargabe Collector, GC) — это такой метод управления источниками, традиционно — оперативной памятью, выделяемой в куче. Суть примитивна — программист умоляет сборщик мусора выделить ему кусок памяти, а тот теснее сам определяет, когда он станет не необходим и может быть освобожден. Это решает множество задач с утратами памяти, правда и лишает вероятности мужественно превознемогать ошибки сегментации. Какая жалость.

Сборщики мусора бывают 2-х видов — консервативные и копирующие.

Кое-что как бы первого типа реализовано в последнем эталоне. Механизм shared_ptr разрешает отказаться от очевидного применения операторов new и delete. Он считает ссылки, которые указывают на объект и избавляется от него, когда их число становится нулевым. Задачи с этим подходом появляются, когда создается уйма мелких объектов с коротким, но не идентичным сроком жизни. В итоге, куча превращается в багряное месиво из валидных объектов и лоскутков свободной памяти по несколько десятков байт. Из-за этого создание новых объектов начинает занимать целую вечность и нативный код начинает завидовать Питону.

Для решения этой задачи — фрагментации кучи – придуман 2-й тип сборщиков — копирующий. До поры до времени, его тактика борьбы с мусором — созерцание. Когда же его становится слишком много, он делает следующее:
1. Копирует все надобные данные в иную область памяти.
2. Меняет все указатели на актуальные.
3. Освобождает всю память, которая теснее не применяется.

Сразу уточню, что я не глядел впритирку ни одного алгорифма сборки мусора, ни как работают «взрослые» библиотеки GC для С . Возможно, у алгорифма, тот, что я теперь опишу, есть наименование, допустимо, именное, но в здесь я обойдусь без ссылок на источники.

Дабы определить объекты, которые еще необходимы программе, предлагаю рассматривать память как обыкновенный граф. Тогда «живыми» объектами позже сборки мусора будут считаться те, которые достигаемы через цепочку указателей. Тут появляются вопросы. Во-первых — как для всякого потенциального объекта, тот, что программист может попросить сделать, определить, где у него находятся указатели. 1-й метод — с поддержкой шаблонной магии для всякого класса объектов создавать свой личный аллокатор. Страшная идея по многим причинам. 2-й — в заголовке всякого объекта писать всю информацию, которая необходима для работы GC (ах да, для классов с виртуальными функциями эта реализация не годится. Пара идей у меня есть, при необходимости).

Заголовок тоже дозволено применять многими методами. Мой — самый примитивный, тот, что вообще может быть (для реализации, но не применения). Во-первых, всякий объект, тот, что планирует создаваться через сборщик мусора, должен иметь в начале своего определения эту структурку:

enum { STRUCT_SZ = 0, REF_COUNT = 1 }; 
struct gcHeader { 
    union { 
        int gcData[2]; 
        gcHeader* post_gcAddress; 
    }; 
};

Во-вторых, сразу позже заголовка, и нигде больше, обязаны идти все указатели, которые также относятся к сборщику мусора. Соответственно, в gcData[REF_COUNT] будет хранится их число. Это одно из ограничений, которое накладывает моя реализация. В gcData[STRUCT_SZ] будет храниться размер конструкции в байтах. Предназначение указателя я раскрою позже. Что комфортно, размер конструкции оказался равен размеру указателя (теперь 2014, народ!).

Отменно, сейчас мы сумеем обойти всю нашу память. Вопрос в том, откуда начать обход. Исключительная область памяти, которая нам стопроцентно доступна в всякий момент — это стек. Задача та же, что и с указателями в конструкциях — мы представления не имеем, какая кучка байт указывает на объект GC. Следственно, необходимо расположение всякого такого указателя записывать очевидно.

vector<gcHeader**> referencesStack;

template <class T>
class stackRef {
    public: 
        T* ref;
        stackRef(){
            ref = nullptr;
            referencesStack.push_back(reinterpret_cast<gcHeader**>(&ref));
        }

        ~stackRef(){
            referencesStack.pop_back();
        }
};

Класс stackRef действует легко. При инициализации, он каждого-лишь добавляет свой адрес в стек ссылок. Деструктор, соответственно, удаляет неактуальный адрес из того же стека. Работа стека вызовов и конструкторов с деструкторами синхронизирована, так что аномалий появляться не будет.

В классе необходимо переопределить кучу операторов — разыменования, присваивания, etc, но этим появится толк заниматься не прежде, чем со мною свяжутся парни из Boost Foundation.

Вспомогательные конструкции готовы. Дозволено перейти к выделению памяти.

Изумительной фичей такого метода управления источниками является именно метод их выделения. Стандартному аллокатору С доводится позже всякого delete обновлять списки свободных блоков, а позже new находить среди блоков подходящий, потом дробить его на два мелких блока, а потом что-то еще, что там делают современные аллокаторы. В случае сборщика мусора, операция delete легко не необходима, так что каждая занятая память будет идти одним сплошным блоком. Дабы сделать новейший объект, необходимо каждого лишь увеличить размер этого блока, т. е. сдвинуть один указатель. Простая операция, которая выполняется за O(1). Реально перестало это казаться такой уж восхитительной идеей, из-за того, что провоцирует кучу сборок тогда, когда дозволено было бы легко переиспользовать теснее не надобную память, но пока дозволено остановиться на этом.

Поделим память, подконтрольную сборщику мусора на куски по 4 килобайта и свяжем их в список. На самом деле, чуть огромнее 4 килобайт, но это вопрос моей лени.

const int CHUNK_SIZE = 4096;
const int OVERDRAFT = 128;
const int ACTUAL_SIZE = CHUNK_SIZE   OVERDRAFT; //Я только что сэкономил себе минут 15 на отладку, если где-то ошибусь в арифметике.
struct gcChunk {
    gcChunk* next;
    char data[ACTUAL_SIZE];//Эта память и будет выдаваться программе.
};

gcChunk* firstChunk;
gcChunk* currentChunk;
int chunkCount;
int currentOffset;

firstChunk — предисловие списка, currentChunk — конечный сделанный блок памяти. сurrentOffset — предисловие свободного сегмента памяти касательно currentChunk.

gcHeader* gcRawAlloc(int size, int refCount){
    if (size > CHUNK_SIZE)// Ради proof of concept, уметь создавать крупные объекты необязательно
        return nullptr;
    if (currentOffset   size > CHUNK_SIZE){ // Было бы положительнее применять list<gcChunk> из STL,  но мне показалось, что отменнее будет очевидно показать каждый процесс. 
          chunkCount;
        currentChunk->next = new gcChunk();
        currentChunk = currentChunk->next;
        currentChunk->next = nullptr;
        currentOffset = 0;
    }
    gcHeader* new_obj = reinterpret_cast<gcHeader*>(&(currentChunk->data[currentOffset]));
    new_obj->gcData[STRUCT_SZ] = size;
    new_obj->gcData[REF_COUNT] = (refCount << 1)| 1;
    currentOffset  = size;
    if (currentOffset % 4)//выравнивание по 4 байтам. Скорее каждого, условие не сработает никогда, т.к. компилятор сам будет дополнять все конструкции до надобного размера.
        currentOffset  = 4 - currentOffset % 4;
    return new_obj;//Возвращается сырой указатель Если сборка мусора начнется до того, как данный указатель будет скопирован куда нужно, всё закончится нехорошо — появится висящая ссылка.
} 

Тут неочевидных моментов теснее огромнее. Разберем 12-ую строчку.
На этом этапе нам комфортнее не думать о том, какой именно тип у нового объекта. Мы верно знаем, что у него есть наш gcHeader, и этого пока довольно.
Позже того, как мы выделили память для нового объекта, необходимо инициализировать его заголовок. Что может обозначать таинственное присваивание

temp->gcData[REF_COUNT] = (refCount << 1)| 1;

?

Для этого вновь посмотрим на определение заголовка

struct gcHeader { 
    union { 
        int gcData[2]; 
        gcHeader* post_gcAddress; 
    }; 
};

Ключевое слово union обозначает, что и массив gcData и указатель post_gcAddress располагаются по одному адресу. Это благотворно для экономии памяти, но задача в том, что С не запоминает, как данные в union применялись в конечный раз — как массив, либо как ссылка. Помогает такая специфика архитектур процессоров, как надобность выравнивания данных.

Если лаконично, то всякие переменные длиннее одного байта, обязаны располагаться на адресах, которые кратны машинному слову в байтах. Нарушение выравнивания на современных процессорах крепко замедляет работу программы, а ветхие ARM вообще отказreinterpret_cast<gcHeader**>(temp) 1;

получает указатель на первую ссылку в структуре (если она есть, безусловно). Помним, что sizeof(gcHeader) == sizeof(void*). В отвратном случае, это будет занимать на пару строк огромнее.
Что делать дальше, вопрос теснее спорный. Я легко для всякого указателя рекурсивно вызываю функцию gcMove. Такой алгорифм соответствует обходу графа в глубину. Впрочем, это не наилучший выбор.
Киллер-фича копирующих сборщиков мусора для меня — это вероятность поддерживать локальность по ссылкам. Если коротко, объекты, которые ссылаются друг на друга, и в памяти тоже обязаны находиться как дозволено ближе. Так процессор сумеет результативнее применять свою кэш-память.

Спрятанный текст

Дозволено провести эксперимент. Сделать связный список и в произвольные места начать вставлять элементы. А после этого — легко обойти и распечатать каждый список. Скорее каждого, программа на С будет исполнять конечный этап дольше, чем Java либо C# позже принудительной сборки мусора. Всё из-за того, что в случае С , процессор будет непрерывно стопориться на кеш-промахи и ожидать, пока прибудут данные из неторопливой оперативной памяти. В случае Java, это будет фактически обход цельного массива.

Мой GC такого не может. Я предпочел обход в глубину из-за простоты. Желанно перемещать объекты в порядке обхода в ширину. Будет вовсе здорово заморочиться и выстраивать объекты в памяти в соответствии со статистикой обращений к ним, как в этом алгорифме, Дабы добиться оптимального числа промахов.

На этом всё. Осталось продемонстрировать работу со сборщиком.

В качестве примера возьму простейшее дерево поиска.

struct searchTree { 
    gcHeader gc; 
    searchTree* left; 
    searchTree* right; 
    int key; 
    static const int refCount = 2; 
};

Как теснее упоминалось, в начале должен стоять заголовок, а позже заголовка все указатели на объекты нашей кучи.

void stAdd(searchTree* &target, int key){ 
    if (target == nullptr){ 

        target = gcAlloc<searchTree>(); 
        target->left = target->right = nullptr; 
        target->key = key; 

        return; 
    } 
    if (target->key == key) 
        return; 
    if (target->key < key) 
        stAdd(target->left, key); 
    else 
        stAdd(target->right, key); 
} 

Обыкновенное добавление в дерево. Обратите внимание, как применяется gcAlloc.

searchTree* stFind(searchTree* target, int key){ 
    if (target == nullptr || target->key == key) 
        return target; 
    if (target->key < key) 
        return stFind(target->left, key); 
    else 
        return stFind(target->right, key); 
} 

void stPrint(searchTree* t, int indent = 0){ 
    if (t == nullptr) 
        return; 
    for (int i = 0; i < indent;   i) 
        cout << "  "; 
    cout << t << ' ' << t->key << endl; 
    stPrint(t->left, indent   1); 
    stPrint(t->right, indent   1); 

} 

void stCut(searchTree* &target, int key){ 
    if (target == nullptr || target->key == key){ 
        target = nullptr; 
        return; 
    } 
    if (target->key < key) 
        stCut(target->left, key); 
    else 
        stCut(target->right, key); 
} 

stFind возвращает ссылку на поддерево с необходимым ключом, stPrint распечатывает ключи и адреса поддеревьев, stCut обрезает поддерево, в котором хранится желанный ключ.

Наконец, main.

int main(){
    gcInit();
    stackRef<searchTree> root;

    stAdd(root.ref, 2);
    stAdd(root.ref, 1);
    stAdd(root.ref, 3);
    stAdd(root.ref, 6);
    stAdd(root.ref, 5);
    stAdd(root.ref, 4);
    stAdd(root.ref, 8);
    stackRef<searchTree> additionalRef;
    additionalRef.ref = stFind(root.ref, 3);
    cout << "Before GC" << endl;
    cout << additionalRef.ref <<  ' ' <<  currentOffset << endl <<endl;
    stPrint(root.ref);
    cout << endl;

    gcCollect();
    cout << "After GC" << endl;
    cout << additionalRef.ref <<  ' ' <<  currentOffset << endl << endl;
    stPrint(root.ref);

    cout << endl;
    stCut(root.ref, 5);
    gcCollect();
    cout << "Deleted some elements and GC'd." << endl;
    cout << additionalRef.ref <<  ' ' <<  currentOffset << endl << endl;
    stPrint(root.ref);

    return 0;

}
Before GC
0xd92058 224

0xd92018 2
  0xd92058 3
    0xd92078 6
      0xd920d8 8
      0xd92098 5
        0xd920b8 4
  0xd92038 1

After GC
0xd93108 224

0xd930e8 2
  0xd93108 3
    0xd93128 6
      0xd93148 8
      0xd93168 5
        0xd93188 4
  0xd931a8 1

Deleted some elements and GC'd.
0xd92038 160

0xd92018 2
  0xd92038 3
    0xd92058 6
      0xd92078 8
  0xd92098 1

Как видно работа со конструкциями для программиста особенно не меняется. Что здесь происходит:
1. Мы произвольно заполняем дерево поиска.
2. Создаем еще одну стековую ссылку на один из элементов, Дабы проверить, как GC реагирует на множественные ссылки на один объект.
3. Распечатываем дерево, additionalReference и currentOffset.
4. Вхолостую вызываем сборку мусора.
5. Вновь распечатываем дерево. Все указатели, которые необходимы — поменялись.
6. Обрезаем одно поддерево и вновь вызываем сборку мусора. Всё вновь работает как нужно. Обратите внимание currentOffset уменьшился, а корень дерева возвратился на тот же адрес, по которому находился в 1-й раз.

Итоги

Выходит, в С дозволено применять Garbage Collector. Причем, абсолютно себе славный, на мой замыленный взор, да еще и с минимальным оверхедом. Испробую перечислить всё, что необходимо сделать, Дабы он был подлинно комфортным и пригодным.
Вначале — организационные моменты.

1. Всеобщии переменные — это, безусловно, вовсе не клёво. Необходимо всё оформить как человеческий класс и\или аллокатор С .
2. Принуждать в всякий класс вставлять хедер — примерно садизм. Необходимо легко давать отнаследоваться от абстрактного класса, у которого обязаны быть два способа — getSize и getLayout. Конечный должен возвращать ссылку на массив, в котором хранятся относительные координаты всех указателей (затея с «все ссылки стоят начале» ну вовсе не годится для чего-то серьезного). Данный массив однозначно должен заполняться механически, но я пока что не представляю, как это дозволено реализовать.

Дальнейший вопрос — механическая сборка. Когда выдвинули саму идею GC, никто не подразумевал, что кто-то реально будет непрерывно вызывать что-то как бы функции gcCollect, всё должно протекать само по себе. Но С — специальный случай. Он гордится тем, что каждый поток выполнения под носом, либо, по крайней мере, предсказуем. Своевольный Garbage Collector всякого иного языка тут — это фактически идеологическое правонарушение. Так что, у него должно быть как минимум два режима:

1. Прозрачный.
2. Бросок исключения позже исчерпания некой квоты памяти. Здесь теснее программисту решать — убраться либо выделить память форсированно.

И еще один вопрос. Многопоточность. Здесь всё нехорошо. Дабы начать сборку мусора, необходимо остановить все потоки, Дабы ничего не сломать. В результате придется написать половину JVM. Самым лучшим решением мне кажется его неимение. Для всякого потока дозволено легко создавать свой выделенный GC, а если потребуется передать что-то иному подпроцессу, то обыкновенные shared_ptr никто не отменял. Без разделяемой памяти жить, как правило, значительно веселее.

Завершим на грустной ноте. Такой сборщик мусора тотально несовместим ни с одной готовой библиотекой. Их объекты не сумеют предоставлять нужные данные. Невзирая на то, что std::list, std::map и std::set только выиграют, если переписать их намеренно под GC, переделывать N гигабайт исходников Boost, скажем, абсолютно бесперспективно. Впрочем, для борьбы с фрагментацией в случае маленьких объектов, мне такая штука кажется дюже даже пригодной.

Скачать и поиграться дозволено отсель.

 

Источник: programmingmaster.ru

 

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB