Когда нужен свой аллокатор в C++?

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

Потому что разные задачи требуют разных подходов в размещении объектов и плюсы позволяют это сделать.

Почему вы не перестали пить коньяк по утрам?

Почему в C++ каждый проект пишет свой аллокатор?

Хороший аллокатор для нынешней архитектуре объектов никто не разработает.

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

То бишь списки для: 1, 2, 4, 8, 16, ... ,блоков данных.

Безусловно такой подход много лучше чем использования памяти по типу «куча мала».

Почему в C++ каждый проект пишет свой аллокатор?

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

Потому что могут.

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

Свои аллокаторы имеют только старые и крупные проекты.

А до появления pmr с аллокаторами в плюсах творилось нечто странное. Как следствие людям приходилось писать своё, это своё расползлось по проекту и сейчас с него слезть практически невозможно. Ну и разумеется, любой быстрый аллокатор будет чудовищно медленным в другом сценарии использования. Алгоритм может быть либо очень быстрым, но только в одном сценарии использования, либо везде не очень медленным (ну или всегда плохим, конечно). Собственно последние и попадают в стандартную библиотеку и т.п.

Короче всё как со строками, только с аллокаторами.

Люди даже не могут придумать универсальный класс для работы со строками

Ну почему же? Вот в Qt вполне себе универсальный класс для работы со строками.

Комментарий про коньяк по утрам уже был? Был, вижу, это хорошо.

Нет, в заголовке 4.2, свой аллокатор пишет не каждый проект, а только те, которые уткнулись в неоптимальность стандартного. Зачем — выше примерно объяснили.

За 25 лет писания проектов на плюсах ни разу не писал свой аллокатор. От коллег видел один раз, но это неточно.

Я для AVR из интереса делал, когда решил попробовать C++ вместо C.

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

Но почему тогда не сделали какой-нибудь стандартизированный быстрый аллокатор?

jemalloc например много кто пользуется, вполне себе стандартизированная вещь

Индустрия удивляет!

Хотя бы разработали оптимальные алгоритмы для работы с строками.
Ведь то, что ныне имеем - ЛАБА.

Да и архитектура Unicode ведь «не очень».

Я на обычных сях писал свои функции для работы с памятью вместо malloc и free. Просто так, ради понимания.

jemalloc например много кто пользуется,

Хороший проект.

Свои менеджеры памяти иногда пишутся конечно, но у нас они очень специфические и никто их в STL не сует. Я бы это аллокатором не назвал…

Которые работали с уже выделенным malloc большим куском?

Нет, зачем. Которые делали ту же работу, но только упрощенную.

Дык а память они откуда брали? Интересно, я на таком уровне никогда не работал.

Или это просто эмуляция была?

Дык а память они откуда брали?

Ну, можно в самом начале, бахнуть статический массив. И потом оттуда указатели возвращать. Как вариант.

Дык а память они откуда брали?

mmap()

Разве для большого куска нужен менеджер? Мегаструктуру фигачишь и всё

Статический массив будет маленький.

x22

mmap()

Почти те же яйца что и malloc, только в профиль?

DumLemming

Мегаструктуру фигачишь и всё

на стеке или в глобальной памяти? Так там или с опциями надо морочится, или кусок будет совсем небольшой.

В глобальной. Рядом с main. И ни одного указателя внутри

демонстрировали графики, которые показывали, как эти аллокаторы обходят по скорости другие аллокаторы

https://github.com/mjansson/rpmalloc-benchmark 🤫

Помнится, когда Firefox перешёл на jemalloc, мем про наглую рыжую и толстую морду, жрущую RAM исчез и Firefox с jemalloc действительно ощутимо меньше стал кушать.

Память выделяет ядро. Его можно попросить об этом системными вызовами. А вот о чем именно попросить, тут уже надо рассказывать.

Если подробнее, то рассказ нужно начать с ассемблера. Не очень глубоко. Вы кодили когда-нибудь на ассемблере? Помните из каких секций, сегментов состоит программа? Помните такой сегмент данных?

Так вот, когда программа загружена в память, то место куда она загружена – это и есть сегмент данных, на х86. Примерно сразу после вашего кода – этот сегмент данных заканчивается и начинается стек. Т.е. здесь проходит граница сегмента данных и стека. Собственно, это все. А где же куча?

Стек спускается сверху вниз. И до границы дата-сегмента данные в стеке могут никогда не дойти. Там очень много. 4 гигабайта – полное пространство, а на стек это минус размер дата-сегмента т.е. минус ваш код пока что.

Значит, можно подвинуть границу стека вверх. От него не убудет. Тем самым мы увеличим дата-сегмент. Вот собственно этим и занимается ядро. Вот об этом можно его попросить.

Окей, подвинули мы границу. У нас теперь есть пространство после нашего кода. Вот это и есть та самая куча. И выделение в ней куска на самом деле сводится к разметке Т.е. маллок должен так вести учет этого свободного пространства, чтобы достаточно быстро находить «свободное» место нужного размера для ваших нужд.

Понятно?

Вы кодили когда-нибудь на ассемблере?

Нет, но про типы памяти помню конечно.

Понятно?

Да, спасибо большое!

Во-первых, далеко не каждый проект. Выделение памяти далеко не всегда узкое место. А преждевременная оптимизация плохо.

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

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

Короче, сильно зависит от задачи. И в общем случае свой аллокатор не пишут, только в частном.

Ну это в традиционном unix.

Вроде в linux сейчас делают mmap - просто ядро выделяет в виртуальной памяти сколько-то страниц и мапит их в адресное пространство процесса

Хорошо, но без основ всё равно никуда. Тут надо еще разобраться из чего состоит адресное пространство процесса и куда ядро мапит эти страницы. И может ли быть это пространство больше 4 гигабайт сейчас суммарно.

Стек спускается сверху вниз.

Или расширяется снизу вверх?

может ли быть это пространство больше 4 гигабайт сейчас суммарно.

может, мы так делаем.

Формальная граница всегда внизу. А там уж ядро может мухлевать по-своему. Это не запрещено.

Т.е. важно понимать, что обещанное пространство не значит реальное. То, что процессу на старте обещано 4 гига – это не значит, что прям реально дали. Не означает, что адреса после дата-сегмента реально соответствуют каким-то страницам в памяти. Хотя казалось бы это стек.

Понятно, что ядро знает сколько данных лежит в стеке и не станет выделять на него честные страницы прям до формальной границы. Это не зачем. Когда понадобятся – выделит, если сможет.

Формальная граница всегда внизу.

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

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

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

С тредами что делать будем?

Безжалостно модерировать!

Какие сложности?

Каждому нужен свой стек.

Если знаешь что-то насчет этого – так пиши прямо. Зачем все эти ухмылки, ужимки?

Если знаешь что-то насчет этого

Пару вещей слышал когда-то…

Зачем все эти ухмылки, ужимки?

Просто подкидываю пищу для размышлений, чтобы не было «а стек мы задвинем в самый конец адресного пространства». Кстати, а где оно в 64битах?

Вряд ли можно объять необъятное. Можно еще и разные архитектуры вспомнить. Особенно какие-нибудь экзотические, где вообще все не так.

Еще, кстати, забыты динамические библиотеки, которые тоже мапятся куда-то туда. Куда?

Так что, обо всех нюансах не упомнишь. Да и мы тут не книгу пишем.

О, когда этот момент настанет - ты поймёшь :)

Но почему тогда не сделали какой-нибудь стандартизированный быстрый аллокатор?

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

Если случай не общий, то на какой-то функционал стандартного аллокатора можно забить, или можно поменять какую-то переменную которая в стандартном захардкожена.

Потому что в разных ситуациях разные аллокаторы оказываются эффективнее. Например - есть у тебя постоянный поток короткоживущих объектов, то делать на каждый чих malloc/free дорого. Проще сообразить arena allocator, ну или object pool по ситуации.

Ну и если NUMA начинается - там мрак и содомия.

На контроллерах можно провернуть трюк и заставить стек и кучу расти от середины к краям. В случае overflow - вылет в аналог segfault. Но свои минусы, да.