Comments 15
The default memory manager
The debug memory manager
The Quick Pool memory manager
Ясно, что когда нужно что-то специфическое, можно изобрести свой аллокатор.
Например, арену для кучи локальных вычислений, которую всю целиком после получения результата можно деаллоцировать.
Или сотню 10-гиговых блоков для сотни потоков, исходя из того, что со сплошным куском адресов работать проще, чем постоянно проверять границы (и при этом знать, что всей сотне в среднем вряд ли понадобится больше 100м фактически занятой памяти).
А вот ко всем кастомным аллокаторам, которые реализуют более-менее стандартный алгоритм, завсегда главный вопрос: "Где бенчи? Я хочу бенчей! Бенчи где?"
Потому что если банальный malloc/new из коробки оказывается ничуть не хуже по оверхеду, но при этом вдруг существенно быстрее — в чём смысл велосипеда?
(возьмите small objects allocator из книжки Александреску. Прогоните бенчи на современной ОС с её свежими либами. И — о ужас! Книжка бесполезна...)
malloc — да, максимально общего. Но при этом он не консервативный, как стек TCP, а вполне воспринимает лучшие из техник. Поэтому — если "кастомный алгоритм" чуть сложнее, чем тупо двигать вверх/вниз указатель вершины стека на шаги одинакового размера, то написать бенч сравнения с malloc более, чем стОит. Результат очень часто вызывает "гнев-неприятие-торг-смирение".
Да, и там в статье — я не увидел графиков.
Те прямые линии об измерении времени на выделение блоков размером строго 4к в зависимости от их количества — ну, извините, это не бенчи, а просто какие-то картинки.
(а в каком порядке блоки выделялись? А освобождались? А все вместе толпой выделялись, или последовательно? А сразу все, или рандомно? А если блок 2К? А если кучу случайных? — ничего такого нет). В конце там есть упоминание, что неплохо бы ещё бенчей добавить, но… Вижу, последний раз существенно проект обновлялся 4 года назад.
Я приводил ссылку на описание Quick Pool менеджера памяти на AS/400. Там выделяется сразу несколько пулов (до 64-х пулов) с ячейками разного размера (размер ячейки кратен 16-ти байтим — квант выделения памяти).
Допустим, запросили пулы с размерами 16,32,64,128 байт. Если хотим выделить 20 байт — возьмет ячейку из пула с размером 32. 50 байт — из пула с размером 64 байт и так далее… Плюсом можно указать символы, которыми заполняется выделяемая ячейка при выделении и про освобождении. Плюс есть функция вывода отчета (для ее активации нужно включить сбор статистики), которая в любой момент выдает количество выделенных и освобожденных ячеек по каждому пулу. Весьма удобно для диагностики как использования памяти, так и наличия утечек — на выходе из программы выводишь отчет и смотришь чтобы количество выделенных ячеек совпадало с количеством освобожденных.
Ну вот я на Александреску тоже ссылался. Аллокатор маленьких объектов. Тоже куча пулов. Тоже разумное обоснование и даже оптимизация для наиболее типичных паттернов использования в реальной программе. И документация подробная (и разумная). И реализация есть, бери да пользуйся. Тоже пулы для объектов разного размера; всё заточено на минимальный оверхед по памяти и вычислениям.
Всё круто, взял, запилил… А потом запустил бенч сравнения с malloc, и по его итогам выкинул. Потому что да, всё круто, стройно, разумно, понятно… Но оказалось, что в 2018-м "чёрный ящик" malloc, прямо из коробки работает в разы быстрее. Как именно — не вникал. Но просто за прошедшие годы разработчики что-то сделали. Может, взяли туже loci и эту часть добавили прямо в либу. Может придумали что-то ещё лучше (всё же книжке уже 18 лет, а мысль не стоит на месте). Но факт именно в том, что придумывание нынче своего аллокатора требует очень веских причин. Как упражнение для мозга студентов — да. Как что-то очень специфическое, типа кастомной арены для коллективного владения — возможно. Но "просто так", чтоб был общего назначения, и при этом оказался лучше системного — хммм..
Во-вторых — годами улучшаемую систему просто так сходу обогнать непросто. Но — это не значит невозможно. Например, была у меня задача выделения небольших временных объектов разного размера. Так вот я сделал многопоточный(!) аллокатор, амортизированная скорость выделения/освобождения которого — это как раз смещение атомарного указателя (там как бы многостраничный линейный аллокатор). Ясное дело, что это быстрее даже чем пул. Да, если использовать его для не очень временных объектов — будет дикая фрагментация, но для той конкретной ситуации он оказался сильно лучше malloc'а.
Ну и в-третьих — не стоит забывать, что бенчмарки и реальный код — это не одно и то же. Тот аллокатор, который я описывал — сделал бенчмарк, который вызывает его постоянно из нескольких потоков, и получил существенное отставание от malloc'а (ну ясное дело, один atomic counter на всех). Казалось бы, надо делать thread-local выделение — только вот в реальном коде мне ведь не нужно выделять память постоянно, это лишь одна из операций. Так что такая реализация работает вполне нормально.
Ну и да — практически во все современные malloc'и давно завезли массивы пулов для маленьких объектов, аналогичные Александреску и Quick Pool из AS/400.
у меня задача выделения небольших временных объектов разного размера
Это автоматически делает задачу специфичной. Можно ещё добавить специфичности, смоделировав, как именно (как часто, в каком порядке и т.д.) будет использоваться аллокатор. Многие подводные камни "общего" решения сами по себе отпадают со специфичностью.
сделал бенчмарк, который вызывает его постоянно из нескольких потоков, и получил существенное отставание от malloc'а
Если реальный юзкейс такой же — я бы уже задумался и начал бы склоняться в сторону стандартного средства. А если просто бенчмарк ради бенчмарка, при этом в реальной программе всё будет не так — ну, только что ради любопытства. Чтобы (с досадой) убедиться, что не получилась вдруг "серебряная пуля" на все случаи лучше стандартной.
Под специфичную задачу (известный размер, время жизни, порядок использования и т.д.) можно и заморочиться. При этом ещё если и бенч иметь реальный (например, прогон на дампе реальных данных в "полностью снаряжённом состоянии"), то прямо все предпосылки есть заняться.
Особенно, если реальный прогон показал, что работа с памятью в общем времени занимает существенную часть, а не какие-нибудь сотые доли процента.
Можно конечно самому изобретать алгоритмы аллокации, но можно ввести свободные внешние гиперпараметры программы. Далее путем запуска программы с разными параметрами и путем перебора этих параметров выбрать оптимальные. Так делают например в машинном обучении.
например если в аллокаторе не указан propagate_on_container_swap как true_type
alloc<int> a1{...};
std::vector<int, alloc<int>> vec1{a1};
alloc<int> a2{...};
std::vector<int, alloc<int>> vec2{a2};
std::swap(a1, a2); // UBи отдельный гемор если нужно передавать аллокатор «в глубь» контейнера
std::vector<std::set<int>>c 17го стандарта лучше смотреть в сторону en.cppreference.com/w/cpp/memory/polymorphic_allocator
Аллокаторы памяти