Документация Engee

Сборка мусора в Julia

Введение

В Julia реализован неперемещаемый, с поддержкой частичного одновременного выполнения, параллельный, действующий с учетом поколений и в основном точный сборщик с поддержкой пометки и очистки (пользователям, которые хотят вызывать Julia из C, предоставляется интерфейс для консервативного сканирования стека).

Выделение

В Julia существует два типа средств выделения, причем конкретный используемый тип определяется запросом размера на выделение. Объекты размером до 2 КБ выделяются с помощью средства выделения пула списка свободной памяти для каждого потока, а объекты размером более 2 КБ выделяются через libc malloc.

Средство выделения пула Julia разделяет объекты на классы разных размеров, поэтому страница памяти, управляемая средством выделения пула (которая охватывает 4 страницы операционной системы на 64-разрядных платформах), содержит только объекты одного класса размеров. Каждая страница памяти из пула средства выделения работает в паре с определенными метаданными страницы, хранящимися в списках без блокировки для каждого потока. Метаданные страницы содержат такую информацию, как наличие на странице активных объектов, количество свободных слотов и смещения для первого и последнего объектов в списке свободной памяти, содержащемся на этой странице. Эти метаданные используются для оптимизации этапа сбора: например, страница, на которой нет ни одного активного объекта, может быть возвращена операционной системе без необходимости ее проверки.

В то время как страница, на которой нет объектов, может быть возвращена операционной системе, связанные с ней метаданные выделяются на постоянной основе и могут продолжать существовать дольше данной страницы. Как уже говорилось выше, метаданные для выделенных страниц хранятся в списках, свободных от блокировки, для каждого потока. Однако метаданные для страниц свободной памяти могут храниться в трех отдельных списках без блокировок в зависимости от того, была ли страница сопоставлена, но к ней не было доступа (page_pool_clean), или страница была очищена в отложенном режиме и ожидает вызова madvise от фонового потока сборки мусора (page_pool_lazily_freed), или страница получила вызов madvise (page_pool_freed).

Средство выделения пула Julia использует «многоуровневый» принцип выделения. При запросе страницы памяти для средства выделения Julia будет выполнять следующие действия:

  • Попытается получить страницу из page_pool_lazily_freed, содержащую страницы, которые были пустыми на последнем этапе остановки, но еще не получили вызов madvise от параллельного потока очистки GC.

  • Если получить страницу из page_pool_lazily_freed, не удалось, будет предпринята попытка получить страницу из the page_pool_clean, содержащей страницы, которые получили запрос mmap в предыдущем запросе на выделение страницы, но доступ к ним никогда не осуществлялся.

  • Если получить страницу из pool_page_clean и из page_pool_lazily_freed не удалось, будет предпринята попытка получить страницу из page_pool_freed, содержащей страницы, которые уже получили вызов madvise от параллельного потока очистки GC и базовый виртуальный адрес которых может быть переработан.

  • Если все вышеупомянутые попытки завершились ошибкой, будет выполнен вызов mmap к пакету страниц, запрошена одна страница для себя, а все остальные вставлены в page_pool_clean.

Пометка и сбор с учетом поколения

Этап пометки в Julia реализован через параллельный итеративный поиск в глубину по графу объектов. Сборщик в Julia является неподвижным, поэтому информация о возрасте объекта не может быть определена только через область памяти, в которой находится объект, а должна быть каким-то образом закодирована в заголовке объекта или боковой таблице. Два младших бита заголовка объекта используются для хранения, соответственно, бита пометки, который задается при сканировании объекта на этапе пометки, и бита возраста для сбора с учетом поколения.

Сбор с учетом поколения реализуется с помощью битов закрепления: объекты помещаются в стек пометок, а значит, и отслеживаются, только если их биты пометок не заданы. Когда объекты входят в самое старое поколение, их биты пометки не сбрасываются во время так называемой «быстрой очистки», что приводит к тому, что эти объекты не отслеживаются на последующем этапе пометки. Однако при «полной очистке» происходит сброс битов пометки всех объектов, что приводит к трассировке всех объектов на последующем этапе пометки. Объекты продвигаются до следующего поколения во время каждого пройденного этапа очистки. На стороне модификатора запись полей перехватывается с помощью барьера записи, который помещает адрес объекта в запоминаемый набор для каждого потока, если объект входит в последнее поколение, и если объект в записываемом поле не входит в него. Объекты из этого запоминаемого набора затем отслеживаются на этапе пометки.

Очистка

Очистку пулов объектов для Julia можно разделить на две категории: если данная страница, управляемая средством выделения пула, содержит хотя бы один активный объект, то необходимо провести список свободной памяти через ее неактивные объекты; если данная страница не содержит активных объектов, то ее базовая физическая память может быть возвращена операционной системе, например с помощью системных вызовов madvise в Linux.

Первая категория очистки распараллеливается за счет перехвата работы. Для второй категории очистки: если параллельная очистка страниц включена с помощью флага --gcthreads=X,1, выполняются системные вызовы madvise в фоновом потоке очистки параллельно с потоками модификатора. Во время этапа остановки сборщика выделенные в пуле страницы, не содержащие активных объектов, изначально отправляются в pool_page_lazily_freed. Затем пробуждается фоновый поток очистки, который отвечает за удаление страниц из pool_page_lazily_freed, выполнение для них вызова madvise и их вставку в pool_page_freed. Как описано выше, pool_page_lazily_freed также используется совместно с потоками модификатора. Это означает, что в многопоточных рабочих нагрузках с высоким уровнем выделения потоки модификаторов часто избегают ошибки страницы при выделении (в результате доступа к странице с вызовом mmap или доступа к странице с вызовом madvise), напрямую выполняя выделение из страницы в pool_page_lazily_freed, в то время как фоновый поток очистки должен выполнить вызов madvise для сокращения количества страниц, поскольку некоторые из них уже были запрошены модификаторами.

Эвристика

Эвристика сборки мусора корректирует сборку мусора путем изменения интервала выделения между сборками.

Эвристика сборки мусора измеряет, насколько велик размер кучи после сбора, и устанавливает следующую сборку в соответствии с алгоритмом, описанным на странице по адресу https://dl.acm.org/doi/10.1145/3563323. В результате говорится о том, что итоговый объем кучи должен иметь отношение на основе квадратного корня к активной куче, и что она также должна масштабироваться с учетом того, насколько быстро сборщик мусора освобождает объекты и насколько быстро модификаторы выполняют выделение. Эвристика измеряют размер кучи, подсчитывая количество используемых страниц и объектов, использующих malloc. Раньше мы измеряли размер кучи, подсчитывая активные объекты, но при этом не учитывалась фрагментация, которая могла привести к неверным решениям. Это также означало, что мы использовали локальную информацию о потоке (выделениях) для принятия решений о процессе в целом (когда выполнять сборку мусора), измерение страниц означает, что решение является глобальным.

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