Источник: habr

Дата: 2019-09-08

Скажу сразу: я никогда не жду развёрнутого ответа на этот вопрос на собесах. Это глупо и в моем случае — эгоистично. Однако, на мой взгляд, помимо общего интереса к платформе, знать, как он работает очень полезно, т.к. это снимает целый ряд вопросов. Например, исключает вариант, когда разработчик считает, что Dispose вызывается автоматически и вызывать его самому не надо. Или же если разработчик более опытен, помогает ему автоматически, на уровне мышечной памяти писать код, приводящий к наименьшему количеству проблем.

Другой вопрос, что мне субъективно не очень нравится, как объясняется его работа. Потому, предлагаю альтернативный подход, описанный в моей книге, .NET Platform Architecture.

Если мы с вами будем досконально разбираться, почему были выбраны именно эти два алгоритма управления памятью: Sweep и Compact, нам для этого придётся рассматривать десятки алгоритмов управления памятью, которые существуют в мире: начиная обычными словарями, заканчивая очень сложными lock-free структурами. Вместо этого, оставив голову мыслям о полезном, мы просто обоснуем выбор и тем самым поймём, почему выбор был сделан именно таким. Мы более не смотрим в рекламный буклет ракеты-носителя: у нас на руках полный набор документации.

Спор взаимовыгоден: если будет не понятно, я подправлю не ясные моменты в книге, маленькой частью которой является данный текст.

Я выбрал формат рассуждения чтобы вы почувствовали себя архитекторами платформы и сами пришли к тем же самым выводам, к каким пришли реальные архитекторы в штаб-квартире Microsoft в Рэдмонде.

Исходя из классификации выделяемых объектов на основании их размера можно разделить места под выделение памяти на два больших раздела: на место с объектами размером ниже определенного порога и на место с размером выше этого порога и посмотреть, какую разницу можно внести в управление этими группами (исходя из их размера) и что из этого выйдет.

Если рассматривать вопросы управления условно “маленьких” объектов, то можно заметить, что если придерживаться идеи сохранения информации о каждом объекте, нам будет очень дорого поддерживать структуры данных управления памятью, которые будут хранить в себе ссылки на каждый такой объект. В конечном счёте может оказаться, что для того, чтобы хранить информацию об одном объекте понадобится столько же памяти, сколько занимает сам объект. Вместо этого стоит подумать: если при сборке мусора мы пляшем от корней, уходя вглубь графа через исходящие поля объекта, а линейный проход по куче нам понадобится только для идентификации мусорных объектов, так ли нам необходимо в алгоритмах менеджмента памяти хранить информацию о каждом объекте? Ответ очевиден: надобности в этом нет никакой. А значит, можно попробовать исходить из того, что такую информацию мы хранить не должны: пройти кучу линейно мы можем, зная размер каждого объекта и смещая указатель каждый раз на размер очередного объекта.

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

Однако, тем не менее, когда память нам более не нужна, мы должны её освобождать. А при освобождении памяти нам становится трудно полагаться на линейное прохождение кучи: это долго и не эффективно. Как следствие, мы приходим к мысли, что надо как-то хранить информацию о свободных участках памяти.

В куче есть списки свободных участков памяти.

Если, как мы решили, хранить информацию о свободных участках, и при этом при освобождении памяти участки эти оказались слишком малы, то во-первых мы приходим к той-же проблеме хранения информации о свободных участках, с которой столкнулись при рассмотрении занятых (если по бокам от занятых освободился один объект, то чтобы хранить о нём информацию, надо в худшем случае 2/3 его размера. Указатель + размер против SyncBlockIndex + VMT + какое-либо поле — в случае объекта). Это снова звучит расточительно, согласитесь: не всегда выпадает удача освобождения группы объектов, следующих друг за другом. Обычно, они освобождаются в хаотичном порядке. Но в отличии от занятых участков, которые нам нет надобности линейно искать, искать свободные участки нам необходимо потому что при выделении памяти они нам снова могут понадобиться. А потому возникает вполне естественное желание уменьшить фрагментацию и сжать кучу, переместив все занятые участки на места свободных, образовав тем самым большую зону свободного участка, где можно выделять память.

Отсюда рождается идея алгоритма Compacting.

Но, подождите, скажите вы. Ведь эта операция может быть очень тяжёлой. Представьте только, что вы освободили объект в самом начале кучи. И что, скажете вы, надо двигать вообще всё?? Ну конечно, можно пофантазировать на тему векторных инструкций CPU, которыми можно воспользоваться для копирования огромного занятого участка памяти. Но это ведь только начало работы. Надо ещё исправить все указатели с полей объектов на объекты, которые подверглись передвижениям. Эта операция может занять дичайше длительное время. Нет, надо исходить из чего-то другого. Например, разделив весь отрезок памяти кучи на сектора и работать с ними по отдельности. Если работать отдельно в каждом секторе (для предсказуемости и масштабирования этой предсказмуемости — желательно, фиксированных размеров), идея сжатия уже не кажется такой уж тяжёлой: достаточно сжать отдельно взятый сектор и тогда можно даже начать рассуждать о времени, которое необходимо для сжатия одного такого сектора.

Теперь осталось понять, на основании чего делить на сектора. Тут надо обратиться ко второй классификации, которая введена на платформе: разделение памяти, исходя из времени жизни отдельных её элементов.

Деление простое: если учесть, что выделять память мы будем по мере возрастания адресов, то первые выделенные объекты становятся самыми старыми, а те, что находятся в старших адресах — самыми молодыми. Далее, проявив смекалку, можно прийти к выводам, что в приложениях объекты делятся на две группы: те, что создали для долгой жизни и те, которые были созданы жить очень мало. Например, для временного хранения указателей на другие объекты в виде коллекции. Или те же DTO объекты. Соответственно, время от времени сжимая кучу мы получаем ряд долгоживущих объектов — в младших адресах и ряд короткоживущих — в старших.

Таким образом мы получили поколения.

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