Хороший курс по тому, как работать с памятью на низком уровне. Построение курса такое: мы вроде как знаем язык python, но он нам оказался не удел и поэтому мы пишем преемника Sneklang. Мы хотим сделать язык, где не надо будет следить за памятью, поэтому нам нужен будет реализовать сборщик мусора. Чтобы это сделать надо разобраться с следующим набором вещей:
- синтаксис C
- доступные операции для построения структур: struct, union, enum
- union для меня оказался открытием, потому что это область памяти с одним значением разных типов
- при этом перед использованием ты должен как-то понять что там лежит, иначе получишь белиберду
- union для меня оказался открытием, потому что это область памяти с одним значением разных типов
- реализовать примитив Stack
- послушать как устроена память: а именно стек, и хип
- стек - создаётся на вызове функции и представляет собой линейную адресацию памяти в рамках неё
- хип/куча - память, которая будет жить после окончания функции и которой требуется ручной контроль “жизни”
- разобраться с указателями, массивами и указателями на указатели
- указатель - это адрес начала данных в массиве памяти, и здесь массив памяти имеется в виду как классический массив
- при работе со структурами обращение
->- это синтаксис на зарезолвить значение и обратиться по полю - array decay - при передаче указателя на массив в функцию, sizeof будет возвращать размер указателя, а не массива
- собрать на основе всех пунктов структуры, которые смогут одновременно держать строки, числа и динамические массивы
- здесь мы узнаём, что typedef нам нужен для будущих объявлений структур при работе с рекурсивными типами
- написать для них сборщик через подсчёт ссылок
- добавляем в структуру числовой счётчик
- при указании и использование объекта (например, добавление в массив) счётчик увеличиваем
- при удаление объекта уменьшаем счётчик, если тут ещё и ноль ⇒ освобождаем память
- не работает с циклическими зависимостями
- написать для них сборщик через mark-and-sweep - это просто!
- mark - пометить всё как неиспользуемое
- trace - от корня стека пометить всё используемое как true
- sweep - пройтись по всем объектам, если неиспользуется, то освободить память
- этот сборщик может отработать циклические зависимости (похоже на disjoint union), НО может приводить к stop the world операции
Важное про garbage collector здесь, что это всегда порожняя работа. То есть, из-за того что поленились писать alloc/free в рамках программ, мы перекладываем это на автоматический алгоритм, которому требуется процессорное время. Оно хорошо работает на обнаруженных эвристиках (большинство объектов живут только в рамках своей же функции), но всё равно может приводить к неравномерному времени обработки данных.
В результате курса, за вычетом парсинга и грамматики, под конец будет вполне себе готовый к расширению операций язык.
Пример понятных картинок из курса про указатели на указатели:
