Введение

Привет, Хабр! Текущая статья будет полезна тем, кто уже знаком с основами языка программирования Golang и хочет более углублённо изучить его. Исходя из названия стати понятно, что речь пойдёт об аллокаторах, основных видах, плюсах и минусах, а также о том, какой аллокатор используется в Go. Я настоятельно рекомендую прочитать статью целиком, прежде, чем приступать к чтению части конкретно относящейся к аллокатору Go.

Что такое аллокатор?

Аллокатор - это некоторая сущность (программа), которая отвечает за выделение, отслеживание и освобождение областей памяти. Без аллокаторов некоторые современные языки не могли бы функционировать, так как большая часть операций - это операции работы с памятью. Отличия, которые можно выделить между аллокаторами в современных языках, помимо возможности замены аллокатора, стратегии управления и наличия и отсутствия сборщика мусора, заключаются в явности или не явности работы аллокатора. В Go аллокатор скрыт внутри Runtime, разработчик не может его заменить или напрямую влиять на стратегию выделения памяти.
Для большего понимания необходимо выделить основные виды аллокаторов и дать им характеристики.

Основные виды аллокаторов

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

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

  На рисунке ниже виден примерный процесс работы подобного аллокатора. Данный аллокатор, чтобы избежать неявное выделение памяти производит выравниваение и закрывает последнее свободное пространство.

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

• Блочный аллокатор: память делится на куски (блоки) одинакового размера, который фиксируется при создании аллокатора. Отличается нулевой фрагментацией и быстрым выделением, так как аллокатор просто берёт первый свободный блок. Применяется часто в очередях, пулах и системах, где часто создаются и удаляются объекты одного класса.

  Блочный аллокатор поддерживает освобождение определённого участка памяти, что отображено на рисунке ниже.

В связи с тем, что этот тип аллокатора может высвобождать определённый участок памяти, появляется проблема с безопасностью. Если разработчик передаст в подобный аллокатор адрес, который не соответствует ни началу определённого блока, ни концу. Эта проблема решается проверкой валидности адреса, но такое решение делает аллокатор более медленным.

• Стековый аллокатор: это своего рода разновидность линейного аллокатора, где память выделяется по принципу LIFO (последним пришёл - первым ушёл). Выделение и освобождение происходит мгновенно, но удалять можно только самый последний выделенный блок. Как правило, применяется в парсерах.
  Работает схожим образом, как и линейный аллокатор, только появляется header, где хранится информация о том, сколько было выделено байт, при header находится перед блоком данных, по смещению от переданного указателя. Таким образом, при выделении памяти, создаётся header с указанием выделенной памяти, а при освобождении аллокатор читает размер блока из header, затем сдвигает указатель вершины стека назад на этот размер. Вся память остаётся и может быть переиспользована для следующих выделений.

Таким образом, каждый тип аллокатора имеет, как свои плюсы, так и минусы. Невозможно выделить какой-то универсальный сценарий использования для каждого.Дальше, хотелось бы затрнонуть тему эталонной реализации аллокаторов - MALLOC.

Приблизительная реализация аллокатора общего назначения "MALLOC"

Здесь предоставлена лишь приблизительная реализация подобного аллокатора, в этом плане моя статья не является конкретной документацией, для более точного понимания рекомендую обратиться к статьям и документациям, посвящённым конкретно MALLOC.

Основным смыслом такого аллокатора является:

• Поддержка свободного освобождения памяти, не в обязательном порядке выделения, как в аллокаторах линейного типа.

• Умение выделять блоки любого размера.

• Хранит списки свободных блоков, объединяет соседние свободные участки для борьбы с фрагментацией.

В концепции MALLOC имеется header, который указывает на количество свободной памяти, а также указатель MaxBlock, который необходим для быстрого нахождения максимального размера памяти в каком-то определённом блоке. При выделении памяти, в header записывается количество занятых байт c помощью определённого флага. В случае, если память в конкретном блоке заканчивается, MALLOC заводит новый блок и записывает в него. Недостатком такого подходя является то, что данные могут быть разбросаны по всей куче.

Основной причиной гневных отзывов касательно аллокатора MALLOC является сильная фрагментация памяти. Куски свободной памяти могут быть сильно разбросаны по куче и из-за этого могут происходить ошибки при выделении памяти. Пример такой ошибки: в памяти есть 200 байт, но они разбросаны по 50. Из-за такого разброса, аллокатор может решить, что свободной памяти нет и не записать в неё данные.

Аллокатор в Go

Основываясь на информации выше, можно рассмотреть примерное устройство аллокатора Go, а также выделить присущие ему преимущества и недостатки.

В случае необходимости аллокатор в Go запрашивает память у операционной системы большими кусками (аренами), размер арен может отличаться. Такие арены разбиваются на "страницы" - определённые части, определённого размера, при этом важно понимать, что это страницы Go, а не страница ОС. Из этих страниц арены Go выстраивает иерархическую модель хранения данных, образуя при этом spans разного размера. Spans - это несколько соединённых страниц, к примеру может быть span, состоящий из двух страниц по 8КБ.

Предсказуемая фрагментация размера в аллокаторе Go - это важная тема, исходя из которой можно понять, как именно функционирует аллокатор. В Go есть классы размеров, логика там достаточно простая: 1 класс - элементы от 0 до 8 байт, 2 класс - от 9 до 16 байт и так далее. Ключевым моментом тут является наличие показателя максимальных потерь (max waste), которые варьируются от класса к классу. Самое большое количество максимальных потерь у класса 1 (от 0 до 8 байт). К примеру, если в память будет загружаться объект размером в 1 байт, он попадёт в класс 1 (до 8 байт), но остальные 7 байт не будут свободны, они будут не доступны, а значит потеряны. Также будет происходить, если аллоцировать объекты 25 байт, с таким размером они не попадут под класс 3, а значит будут аллоцироваться в класс 4 (до 32 байт), из которых будут пустовать 7 байт.

Где аллоцируются объекты в Go?

В Go есть фундаментальный процесс во время компиляции - Escape analysis. Этот процесс определяет где в программе создаются объекты и как они используются. То есть, текущий процесс определяет, нужно ли выделять память для объекта в куче, или можно разместить его в стеке.

Важно понимать, что компилятор Go по возможности будет аллоцировать память на стеке, но в случае, если компилятор не может доказать, что переменная не ссылается за пределами функции, компилятор должен аллоцировать переменную в куче (heap) для избежания "висячих указателей".

Преимущества и недостатки аллокатора Go

К преимуществам можно отнести:

• Высокая скорость работы для "стандартных" случаев. Аллокатор Go достаточно хорошо оптимизирован для эффективной работы в большинстве случаев.

• Минимальные накладные расходы на блокировки. Для маленьких объектов аллокация происходит через локальный кэш, который привязан к каждому потоку выполнения. Это позволяет выделять память без использования блокировок.

К недостаткам относятся:

• Накладные расходы на GC. Каждая аллокация в куче создаёт дополнительную нагрузку на сборщик мусора.

• Большие потери при не оптимальном размере аллоцируемого объекта. Как было сказано выше, у подхода с классами размеров есть недостаток, при котором остаётся большое количество расходуемой памяти не по назначению.

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

Заключение

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

Спасибо за внимание! В случае, если вы обнаружили какие-то ошибки или у вас есть, что добавить к текущей статье, вы можете указать это в комментариях.