Давным-давно, когда с ездовым котом приключилась "записка шестая", а знания об аллокаторах и опыт их применения ограничивался линейным и системным, перебросили мою команду в помощь другой команде, которая занималась системами навигации больших судов. Ездовые коты, особенно нестарые - это такие создания, которые редко изучают документацию детально, а чаще бегло читают там про интерфейсы систем в проекте, malloc, new, системные аллокаторы и думают, что теперь-то точно понятно, как всё устроено. А потом приходит работа и такая: “Забудь всё, что ты знал. Ты не дочитал до страницы восемьсот что-то там РД, тут есть свой аллокатор - и он реально плохой”.
Примерно так началось мое погружение в мир ненормального распределения памяти. Это сейчас я знаю с десяток разных аллокаторов, и специфику их работы, специфика правда больше игровая, но думаю многим будет интересно - зачем нужны все эти "танцы с аллокаторами". В той статье все аллокаторы еще более менее нормальные, но есть еще ненормальные и они оказывается тоже нужны, и в определенных сферах разработки очень даже важны и применяются.
А вот почему нужны и важны ненормальные - объяснений почти нет, как и самих реализаций в открытом доступе. В этой статье я расскажу, какие повстречал ненормальные алгоритмы распределения памяти, чем они живут, кого едят, и почему иногда malloc делает вид, что он не при делах и таки да, malloc может возвращать null и ту проверку мы убрали зря.
Чтобы понять, как устроен аллокатор, можно представить его как небольшую систему управления памятью внутри программы. Он отвечает за то, чтобы ��ыделять, отдавать, освобождать и при необходимости полностью уничтожать области памяти. Обычно можно выделить пять базовых операций, с помощью которых описывается работа любого аллокатора (хотя не каждый аллокатор обязательно поддерживает их все в явном виде).
create/создание аллокатора
Инициализирует аллокатор, ему выделяется определённый участок памяти и это может быть, например, заранее зарезервированный буфер фиксированного размера или блок, полученный из системного аллокатора (например, через malloc или VirtualAlloc).
По сути, аллокатор начинает «жить» внутри этого участка и управлять им самостоятельно, раздавая память по запросу программы. Главная идея в том, что после вызова create аллокатор больше не обращается напрямую к операционной системе. Он работает внутри выделенного ему пространства, что делает выделения памяти быстрее и предсказуемее.
allocate/выделение блока
Используется для запроса памяти из управляемой области, программа сообщает, сколько байт ей нужно, а аллокатор ищет подходящий участок внутри своего пространства и возвращает указатель. В зависимости от типа аллокатора это может быть просто линейное смещение или более сложный поиск подходящего блока. Ключевая особенность — скорость (за этот параметр борются все разработчики) и allocate часто работает за O(1), потому что аллокатор знает, как устроена его память, и не нуждается в сложных алгоритмах системных менеджеров памяти.
deallocate/освобождение блока
Делает обратное - освобождает конкретный блок, что тоже не бесплатно, ранее выделенный через allocate. В простых аллокаторах (линейных) эта операция может быть вообще не предусмотрена, и тогда память очищается вся разом в при наступлении некоторого события. Освобождение блока не всегда означает физическое стирание данных иногда просто обновляются внутренние таблицы или флаги.
free/сброс всех выделений
Очищаем все выделенные блоки, но не уничтожаем сам аллокатор и не возвращаем память системе. Фактически это «массовый сброс», после которого снова можно обслуживать новые запросы, начиная с начала своего буфера.
destroy/уничтожение аллокатора
Завершает жизнь аллокатора, освобождает участок памяти, который был выделен ему при создании, и удаляет его внутренние структуры. После вызова destroy пользоваться аллокатором уже нельзя, а все указатели, выданные им, становятся недействительными.
Все описанное выше справедливо для всех типов и видов аллокаторов, но вот конкретные цели "ненормальных" аллокаторов часто находятся очень далеко от понимания разработчика, который с ними сталкивается впервые.
Хороший...
Тут скорее уместно сказать, оптимизирующий, но тогда бы не получилось красивого заголовка. При разработке рабочего места вахтенного штурмана, который организует работу навигационной службы и контролирует работу штурманов один из крупных заказчиков потребовал использовать свою версию GCC (clang тогда ходил пешком под стол) с возможностью выгрузки статистики по памяти, т.е. буквально сколько и какие объекты были созданы, где располагались, когда уничтожались и т.д. В процессе портирования софта на этот форк, а там были не только эти требования, но и еще часть приколов и расширений, вроде невозможности выделить за раз более 1Мб памяти, появился кастомный аллокатор с отслеживанием времени жизни объектов.
Он распределял объекты по страницам памяти на основе их прогнозируемого времени жизни, которое было собрано на предыдущих запусках в виде некоторого конфига. Например, объекты, существующие всего несколько кадров, помещались в один пул, а долгоживущие — в другой. По ТЗ это "в теории" должно было уменьшать фрагментацию, и давать возможность объекты с похожими сроками существования освобождать пакетно (странично), т.е. при наступлении некоторого события страницы с короткоживущими объектами предполагалось очищать целиком (не взлетело в реальности).
Но интеграция с инструментами статистики после запусков позволила автоматически (через конфиг) "обучать" аллокатор предсказывать время жизни на основе реальных данных выполнения, снижая необходимость ручной настройки.
В действительности такой подход показал неплохие результаты при использовании в базе данных АРМ штурмана, т.е. памяти оно стало есть действительно меньше, но не в плане ускорения работы. Зато появился отдельный форк аллокатора, который помогал при профилировании утечек, так как каждая страница памяти связана с конкретной категорией времени жизни. В итоге система как аллокатор показала себя посредственно, но дала старт специализированному софту, которое позволяло отслеживать утечки памяти в рантайме без значительного снижения производительности. Позже часть наработок этой системы была портирована (уже другой командой) в общий репозиторий сlang'a и позволила сделать сам санитайзер немного быстрее.
Условно использование ASan’a приводит к двух- и трех-кратному замедлению работы, а "хороший" замедлял программу не более чем на 10%. Каждая страница памяти получала метаданные с привязкой к категории времени жизни и обеспечивала детальную трассировку утечек, позволяя идентифицировать проблемные области кода с точностью до конкретных функций и модулей. Но необходимость предварительной ручной настройки, сложность внедрения и переделки большой части кода приложений так и оставили эту разработку в стенах одной компании.
В рамках этой же работы велась разработка другого типа аллокатора, нацеленного на имитацию длительного использования программ, потому что время непрерывного функционирования навигационных комплексов составляет недели и месяцы без возможности перезапуска.
АЛЛОКАТОР С ОТСЛЕЖИВАНИЕМ ВРЕМЕНИ ЖИЗНИ ═══════════════════════════════════════════════════════════════════ ┌─────────────────────┐ │ НОВЫЙ ОБЪЕКТ │ │ запрос памяти │ └──────────┬──────────┘ ▼ ┌─────────────────────┐ │ АНАЛИЗ/ПРЕДСКАЗАНИЕ│ │ времени жизни │ |эвристика+статистика │ └──────────┬──────────┘ ┌──────────────┼──────────────┐ ▼ ▼ ▼ ╔═══════════════╗ ╔═══════════════╗ ╔═══════════════╗ ║ СТРАНИЦА A ║ ║ СТРАНИЦА B ║ ║ СТРАНИЦА C ║ ║ Короткоживущие║ ║ Средний срок ║ ║ Долгоживущие ║ ║ (1-3 кадра) ║ ║ (минуты/часы) ║ ║(дни/недели) ║ ╠═══════════════╣ ╠═══════════════╣ ╠═══════════════╣ ║ [obj][obj][ ] ║ ║ [obj][ ][obj] ║ ║ [obj][obj] ║ ║ [obj][ ][ ] ║ ║ [ ][obj][ ] ║ ║ [obj] ║ ║ [ ][ ][obj] ║ ║ [obj][obj] ║ ║ [ ][obj] ║ ╠───────────────╣ ╠───────────────╣ ╠───────────────╣ ║ META: TTL=3 ║ ║ META: TTL=600 ║ ║ META: TTL=∞ ║ ║ Категория: 1 ║ ║ Категория: 2 ║ ║ Категория: 3 ║ ║ Trace: func_A ║ ║ Trace: func_B ║ ║ Trace: func_C ║ ╚═══════════════╝ ╚═══════════════╝ ╚═══════════════╝ ▼ ▼ ▼ ┌─────────┐ ┌─────────┐ ┌─────────┐ │ ОЧИСТКА │ │ ОЧИСТКА │ │ ОЧИСТКА │ │ целиком │ │ частями │ │ редко │ │ каждый │ │ по мере │ │ по │ │ кадр │ │истечения│ │ запросу │ └─────────┘ └─────────┘ └─────────┘ ОТСЛЕЖИВАНИЕ УТЕЧЕК: ════════════════════ Time N: [A: ████░░] [B: ███░░░] [C: ████░░] ← состояние Time N+10: [A: ████░░] [B: ████░░] [C: ████░░] ← норма Time N+50: [A: ████░░] [B: █████░] [C: █████░] ← растет Time N+99: [A: ████░░] [B: ██████] [C: ██████] УТЕЧКА ▲ ▲ ┌───────┴───────────┴────────┐ │ ДЕТАЛЬНАЯ ТРАССИРОВКА B: │ │ • Функция: path_trace() │ │ • Модуль: ppath.cpp:342 │ │ • Ожидалось: 600 сек │ │ • Фактически: ∞ │ └────────────────────────────┘
Плохой...
Во время тестирования сложных и долго работающих систем, как из примера софта в предыдущей части, возникает необходимость "доказательства" стабильности системы на долгих сроках использования, что вообще-то практически нереализуемо на этапе разработки - ну какое долгосрочное тестирование, если апдейты прилетают каждый день. Добавьте сюда трудности с выявлением ошибок управления памятью, когда они проявляются крайне редко — иногда лишь спустя дни или недели непрерывной реальной работы. У компании было несколько полнофункциональных рабочих стендов максимально приближенных к условиям и данным судна, где софт, что называется "жил" по реальным записям с судов, но их было всего три, и очередь на то, чтобы туда пропихнуть тестирование своего модуля была на месяц вперед.
Чтобы как-то ускорить обнаружение такого рода ошибок, был разработан отдельный вид аллокатора — рандомизирующий (chaos), представляющий собой специализированную систему управления памятью, созданную для поиска ошибок, связанных с длительным использованием программ.
В отличие от "хороших" аллокаторов, где разработчик стремится к стабильности размещения объектов для оптимизации кеша и предсказуемости выборки данных, этот аллокатор действует прямо противоположным образом — намеренно нарушает стабильность адресного пространства. При каждой новой аллокации система может случайным образом перемещать уже существующие объекты в произвольные области памяти, создавая условия, близкие к непредсказуемым. Ну не при каждой, конечно - это самый жесткий случай, но при наступлении некоторого события и таймера. Что конечно помогает относительно быстро выявлять участки кода (относительно обычной разработки), которые полагаются на неизменность адресов — один из типичных источников трудноуловимых ошибок.
Чтобы подобное перемещение не приводило к нарушению работы программы, аллокатор использует внутреннюю таблицу трансляции адресов, разновидность дескрипторов. Она сопоставляет «логические» адреса, с которыми работает приложение, и реальные физические адреса в памяти. Благодаря этому объекты могут свободно перемещаться, а корректно написанный код продолжает функционировать, не замечая изменений. Программа как обычно «думает», что данные находятся на прежнем месте, хотя на самом деле они уже были перемещены в другую часть памяти.
Применение такого подхода позволяло выявлять ряд ошибок на ранних стадиях, которые в обычных условиях проявились бы только после длительной работы. В одном случае приложение, полагавшееся на стабильность адресов, стало аварийно завершаться уже через несколько часов после включения агрессивной рандомизации адресов, хотя без неё аналогичные сбои происходили лишь спустя недели и скорее всего уже на оборудовании заказчика, т.е. где-то в море, а вытащить дампы оттуда практически нереально и это грозило серьезным окриком со стороны начальства и некоторыми финансовыми проблемами. Для избежания разного рода проблем на судне всегда крутится 2, а то и больше резервных инстансов каждого АРМ, работающих параллельно, чтобы в случае чего просто переключиться на живой, если вдруг один отвалился, это конечно было, но очень-очень редко.
В другом случае, в модуле навигации, работающем с многопоточными запросами к базе данных, удалось обнаружить гонки по данным. Один поток кэшировал адрес структуры, а другой инициировал её перемещение, что приводило к повреждению данных и ошибке позиционирования судна. При анализе и длительном разборе пришли к выводу, что подобная ситуация не могла бы случиться на реальном железе и скорее всего это был эффект самого подхода в аллокаторе, но прецедент был и такой код починили. Повторюсь, что в реальных условиях эта ошибка могла случиться одна на пару миллиардов обращений к БД, что в среднем превышало в три раза это количество за один рейс, но ценой такой ошибки было бы смещение точки судна на несколько десятков метров от его реальной позиции.
Такой аллокатор можно рассматривать как стресс-тестер для подсистем памяти, который моделирует непредсказуемое поведение среды и помогает выявлять ошибки, зависящие от времени и порядка выполнения операций, позволяя заранее проверить устойчивость архитектуры к фрагментации, случайным сбоям и некорректным обращениям. Надо сказать, что после запуска тестов на таком аллокаторе очень много нашего тогдашнего софта "посыпалось", что привело к раздаче большого числа тасок разным подразделениям и в целом к пересмотру подхода работы с памятью.
Цветной...
Немного расскажу об очень специализированном аллокаторе, которые вы скорее всего не встретите в обычной жизни и никогда не будете использовать. Обычно - это либо внутренняя разработка-исследование студии, направленная на поиск ошибок, дебажные сборки и внутренние тулы. Их еще иногда показывают на GDC в секции - “а смотрите какую штуку мы нафигачили". Такие вещи направлены уже не на производительность, а решают свои узкоспециальные задачи.
“Цветной” аллокатор вводит концепцию "цветов памяти", чтобы жёстко разграничить данные разных подсистем. Каждое выделение сопровождается тегом цвета (RED, BLUE, GREEN и т.д.), и поддерживает внутреннюю таблицу сопоставлений страниц памяти цветам. Операции между разными цветами запрещены на уровне отладочного режима и аллокатором предоставляются собственные функции memset, memcpy и др - попытка копирования, перемещения или работы с памятью другого цвета из “цветного компонента” вызывает предупреждение или запись в лог, либо сообщение об ошибке, что помогает находить случаи ошибочного смешивания данных между системами.
В боевом режиме проверка отключена для лучшей производительности, но в отладочном режиме аллокатор способен отслеживать цвет каждой страницы памяти, предотвращая обращения к памяти "не своего" цвета. Дополнительно иногда делают механизм "цветовых барьеров", когда один цвет может читать другой, но не модифицировать его (полезно для реализации immutable-паттернов или защиты данных потоков).
ColorAllocator alloc; auto red_data = alloc.allocate<RED>(256); auto blue_data = alloc.allocate<BLUE>(256); // Безопасно: работа внутри одного цвета alloc::memset(red_data, 0, 256); // Ошибка: попытка скопировать память между цветами alloc::memcpy(blue_data, red_data, 256); // assert: page color mismatch!
Мне довелось работать в качестве консультанта с командой Arkane над AI логикой персонажей в Deathloop и одной из проблем разработки стала сложность взаимодействия между тасками и потоками, какие-то таски помещались в общую очередь, другие становились потоками на время. Логика игрового мира, система рендера и физика постоянно обращались к общим данным, что приводило к крайне сложным для отладки багам и гонкам данных, которые очень негативно влияли на поведение игровых болванчиков, которые и так то "умом не блистали", а тут еще и периодически откровенно тупили при взаимодействиях с игроком и миром.
Не для нужд АI, а в целом для дебага, в движке решили внедрить экспериментальный механизм аллокации памяти на основе цветов, каждому потоку был присвоен свой цвет. Условно красный поток отвечал за игровую логику, синий — за рендер, зелёный — за физику, оттенки задач получались из цвета того потока, который их создавал. Попытка записать данные одного цвета из другого потока вызывала ошибку, и выявила просто громадное число проблем синхронизации. Такой цветной аллокатор был сделан на основе TLSF.
Отловили кучу разных проблем, скрытой порчи памяти и разных несоответствий. Помимо потоков, чуть позже этот механизм применили для изоляции подсистем и там уже нашли «протечки» данных между рендером и остальным игровым кодом. Нашли на тестах, что подсистема анимации "случайно" модифицировала данные физики, и это приводило к странным «дергам и телепортам» персонажей, починили.
Или другой пример использования был сделан для неизменяемых (immutable) данных. Это мы так думали что они неизменяемые, а игре было на это просто пофиг. Ресурсы, которые были помечены как «read-only» (PURPLE) не разрешалось менять после старта уровня, там тоже нашли немало багов, чем сильно упростили жизнь QA отдела перед релизом.
┌───────────────┐ ┌──────────────────┐ ┌──────────────────┐ │ RED │ │ BLUE │ │ GREEN │ │ (Game Logic) │ │ (Rendering) │ │ (Physics) │ │---------------│ │------------------│ │------------------│ │ Object A │ │ Vertex Buffer │ │ Collision Map │ │ Object B │ │ Texture Data │ │ Rigid Bodies │ └───────┬───────┘ └────────┬─────────┘ └────────┬─────────┘ │ копирование │ копирование │ │ запрещено V разрешено │ ^----------------------V ^-----------------V
... и быстрый (TLSF)
В разработке софта нет единого стандарта или алгоритма распределения памяти, который был бы одинаково эффективен для всех случаев использования. Игровые движки сильно отличаются от обычных приложений по шаблонам использования памяти: требуют предсказуемой производительности, тут они ближе к РТОС, минимальных задержек при аллокации - тут мы заимствуем часть от встроенных систем и строгого контроля фрагментации памяти, это уже чисто игродевовская хотелка.
Лучше всего по этим трех параметрам подходит алгоритм двухуровневых списков с разделением по размерам, реализацию можно найти тут (https://github.com/mattconte/tlsf) , который обеспечивает постоянное время выполнения операций аллокации, освобождения памяти и низкий уровень фрагментации.
Аллокатор использует стратегию "подходящих блоков" (good fit), выделяя минимальный объем памяти, достаточный для размещения запрашиваемых данных. Это больше всего подходит к шаблону использования памяти игровыми движками - аллокации происходят в относительно узких диапазонах размеров: игровые объекты, компоненты систем, временные буферы. Этот метод также минимизирует фрагментацию памяти по сравнению с альтернативными стратегиями, такими как "первый подходящий блок" (first fit), поскольку фрагментация в этих случаях может привести к невозможности выделения памяти для больших ресурсов (модели, AI или звуковые файлы) даже при нали��ии достаточного общего объема свободной памяти. “Лучший среди доступных” (best fit) лучше подходит для минимизации фрагментации, но проигрывает по скорости работы - поэтому эту стратегию выбирают реже (иллюстрация @Serpentine)
TLSF не очищает и не проверяет права доступа выделяемой памяти, как делают некоторые аллокаторы, что повышает общую производительность. Это оправдано, поскольку игровые движки работают в контролируемой среде, где программисты не рассматриваются как потенциальная угроза безопасности. Инициализация памяти требует дополнительных вычислительных ресурсов, которые лучше использовать для игровой логики, рендеринга и обработки игровых систем и ответственность за корректную инициализацию данных лежит на самом разработчике. Зато он очень быстрый, ниже в таблице показано количество циклов процессора (*), которое требуется для одной аллокации разными реализациями.
Size | malloc (std, win) | malloc (std, win) | DL’s malloc* | Binary Вuddy* | TLSF* |
128 | 25636 | 112566 | 7376 | 4140 | 155 |
243 | 22124 | 91216 | 5660 | 4448 | 168 |
512 | 15974 | 82162 | 5445 | 4248 | 159 |
4097 | 14743 | 65661 | 3346 | 4135 | 162 |
... заключение
Знаете, что я заметил за время работы над играми? Куча памяти, которую мы выделяем, живет всего один кадр. Серьезно, всего один кадр! Рождается, живет свои 16 - 33 миллисекунды и умирает, но даже в этом случае универсального ответа на вопрос "какой аллокатор лучше" не существует - все зависит только конкретной задачи.
Может показаться старомодным, но я часто я беру бумагу и карандаш (да-да, у нас тут двадцать первый век на дворе, поэтому карандаш) и рисую откуда приходит память и куда потом уходит. Или медитирую над профайлером использования памяти, многие смеются, пока не видят результат. Звучит странно, но такая медитация правда помогает понять, как система создает и использует данные, так что никогда не рано начать думать о памяти. Когда бы вы ни начали об этом задумываться, все равно будете жалеть, что не сделали это еще раньше - проверено на собственном горьком опыте!
Немного рекламы моего курса по программированию на Stepik
Примерно с полгода назад, я опубликовал на Хабре цикл статей про игровую разработку (начинать можно отсюда https://habr.com/ru/articles/873016/), которая была хорошо принята сообществом. Мои знакомые и некоторые Хабровчане просили выложить эту информацию в более удобном и концентрированном виде, в виде курса по С++ или одной большой статьи. Решил сделать пробный шар в виде небольшого курса по программированию на С++ без аллокаций, он действительно небольшой - всего 45 уроков и захватил пару статей из цикла, но если вам понравится можно попробовать сделать еще один по интересным темам (Нескучное программирование. С++ без аллокаций памяти). Курс платный, дабы отсеять охотников на халявные сертификаты и любителей пошуметь в коментах. Тем кто меня читает - промокод (HABR50), если нужна скидка больше или бесплатный инвайт напишите в личку.
Ссылки на интересные материалы и статьи
https://habr.com/ru/articles/274827/
https://habr.com/ru/articles/505632/
github.com/mtrebi/memory-allocators
https://www.ibm.com/support/knowledgecenter/ssw_ibm_i_72/rtref/defaultmemorymanager.htm
https://www.ibm.com/support/knowledgecenter/ssw_ibm_i_72/rtref/debug_memory_manager.htm
https://www.ibm.com/support/knowledgecenter/ssw_ibm_i_72/rtref/quick_pool_memory_manager.htm
https://en.cppreference.com/w/cpp/memory/polymorphic_allocator
