Код, на котором основана эта статья, находится в стадии разработки, с различными коммитами на рассмотрении в теме «Аллокатор». Обратите внимание, что в коде используются различные функции C++17.
Несколько месяцев назад разработчики Qt Company работали над исправлением того, как QHostInfo отправляет результаты вызывающей стороне, что привело к небольшой оптимизации того, как выделяется память для аргументов в QMetaCallEvent. Разработчики используют объекты этого типа в соединениях сигнал/слот с очередями, и некоторое время, проведенное в этом коде, напомнило, что в Qt есть схема размещения довольно маленьких, недолговечных объектов в куче, а также в производительности критического пути кода.
Поэтому они стали задаваться вопросом, можно ли разместить экземпляры QEvent из выделенного пула памяти, используя специальный аллокатор.
Немного статистики
Повторная реализация QEvent::operator new(size_t)и использование QHash в качестве структуры данных гистограммы показывает, что большинство экземпляров QEvent в небольшом приложении Qt имеют размер всего 24 байта:
using HistogramHash = QHash<size_t, int>;
Q_GLOBAL_STATIC(HistogramHash, histogram);
void *QEvent::operator new(std::size_t size) noexcept
{
++(*histogram())[size];
qDebug() << "QEvent:" << *histogram();
return ::operator new(size);
}
Делая то же самое для QObject, получаем более широкий разброс, но и здесь большинство экземпляров невелики. 16 байт являются наиболее распространенным размером.
Это не удивительно. Экземпляр QObject имеет таблицу виртуальных функций и d-указатель на QObjectPrivate, где находятся все реальные данные. Подклассы QObject используют подклассы QObjectPrivate для своих личных данных и передают эти частные экземпляры в QObject для хранения.
Таким образом, экземпляры QEvent и QObject довольно малы, и даже приложение выделяет их целую кучу. Насколько сложно было бы реализовать аллокатор (распределитель) памяти, оптимизированный для этих вариантов использования?
Аллокатор общего назначения против специализированных
По умолчанию global C++ operator new выделяет память с помощью malloc(). malloc() - это аллокатор общего назначения, который должен хорошо работать для всех размеров, от нескольких байтов до нескольких гигабайт, поэтому для каждого выделения у него есть немного накладных расходов на ведение бухгалтерского учета. Существуют различные реализации malloc(), и некоторые из них действительно потрясающе оптимизируют распределение небольших объектов и другие частые случаи использования. Тем не менее, они все еще являются аллокаторами общего назначения, поэтому им приходится принимать решения во время выполнения, которые, возможно, не придется принимать специализированному распределителю.
Специализированные аллокаторы обычно используются в ситуациях, когда структуры данных должны распределяться очень динамично, а создание и уничтожение данных должны быть высокопроизводительными. Прикладная область, в которой небольшие недолговечные объекты часто создаются и разрушаются, являются играми: снаряды в шутере от первого лица - один из примеров. Другие домены - это графы сцен в движках рендеринга, парсеры, которые создают AST, хеш-таблицы. Во всех этих случаях часто заранее известно, какое распределение памяти потребуется, также разработчики очень хотели бы сократить несколько циклов ЦП.
Другая причина, по которой пользовательский аллокатор может быть ценным, заключается в том, что некоторые платформы, не поставляются с блоком управления памятью. Как недавно было объявлено, Qt теперь работает на микроконтроллерах, и эти устройства часто не имеют MMU. В таких средах фрагментация памяти в результате частых небольших выделений может быстро стать серьезной проблемой.
За счет предварительного распределения памяти и управления этим пулом способом, оптимизированным для соответствующих шаблонов использования, специализированный аллокатор может защитить много служебных данных и циклических обращений ядра. Проблемы фрагментации памяти будут, по крайней мере, ограничены этим пулом памяти и с меньшей вероятностью будут влиять на всю систему.
Основные структуры данных
Аллокатор пулов Qt должен дать быстрое распределение и освобождение для разных объектов, но обычно небольших размеров, о которых известно во время компиляции. Аллокатор должен работать с пулом памяти, достаточно большим, чтобы требовать только очень редких обращений к ядру. Распределения и освобождения должны быть возможны в случайном порядке.
Быстрая структура данных для управления свободными порциями памяти без лишних затрат - это стек на месте: предварительно выделенная страница памяти делится на порции одинакового размера, каждая в узле, которая указывает на предыдущую порцию. Для выделенных узлов не нужно знать предыдущий узел, поэтому можно использовать объединение и весь блок для пользовательских данных. Выделения извлекают узел из стека, освобождение перемещает узел обратно в стек.
template<size_t ChunkSize>
class PoolAllocator
{
struct Page
{
char memory[4096];
};
union Node
{
Node *previous;
char chunk[ChunkSize];
};
public:
PoolAllocator()
{
initPage(&m_page);
}
void *allocate(size_t size)
{
Q_ASSERT(size <= ChunkSize);
if (!stack)
return nullptr;
Node *top = stack;
stack = stack->previous;
return top->chunk;
}
void free(void *ptr)
{
Node *top = static_cast<Node*>(ptr);
top->previous = stack;
stack = top;
}
private:
void initPage(Page *page)
{
Node *newStack = reinterpret_cast<Node*>(page->memory);
newStack->previous = stack;
const size_t numChunks = sizeof(Page) / sizeof(Node);
for (size_t i = 0; i < numChunks - 1; ++i, ++newStack)
newStack[1].previous = newStack;
stack = newStack;
}
Node *stack = nullptr;
Page m_page;
};
Это дает O(1) сложность для распределения и освобождения, и практически 100% эффективности памяти. Все, что нужно сохранить аллокатору - это указатель на вершину стека (для страницы памяти 4K это означает 8 байтов служебной информации в 64-битной системе. Это очень хорошо!) Но пока аллокатор Qt может работать только с фиксированным объемом памяти.
Вместо того, чтобы ограничиваться одной страницей памяти и возвращать nullptr, когда она израсходована, можно было бы выделить другую страницу и добавить куски в стек. Таким образом, пул памяти может увеличиваться настолько, насколько это необходимо, и не нужно будет беспокоиться о том, чтобы сделать пул памяти достаточно большим во время компиляции. По-прежнему возможно будет размещать более ста 40-битных объектов на одной странице памяти размером 4 КБ, и, когда нужно будет расти, достаточно сделать одно обращение к ядру. Однако теперь необходимо поддерживать вектор указателей на страницах памяти, чтобы можно было освобождать страницы при разрушении аллокатора.
template<size_t ChunkSize>
class PoolAllocator
{
struct Page
{
char memory[4096];
};
union Node
{
Node *previous;
char chunk[ChunkSize];
};
public:
PoolAllocator()
{
}
~PoolAllocator()
{
for (auto page : pages)
::free(page);
}
void *allocate(size_t size)
{
Q_ASSERT(size <= ChunkSize);
if (!stack && !grow())
return nullptr;
Node *top = stack;
stack = stack->previous;
return top->chunk;
}
void free(void *ptr)
{
Node *top = static_cast<Node*>(ptr);
top->previous = stack;
stack = top;
}
private:
bool grow()
{
Page *newPage = static_cast<Page*>(::malloc(sizeof(Page)));
if (!newPage)
return false;
initPage(newPage);
pages.append(newPage);
return true;
}
void initPage(Page *page)
{
Node *newStack = reinterpret_cast<Node*>(page->memory);
newStack->previous = stack;
const size_t numChunks = sizeof(Page) / sizeof(Node);
for (size_t i = 0; i < numChunks - 1; ++i, ++newStack)
newStack[1].previous = newStack;
stack = newStack;
}
Node *stack = nullptr;
QVector<Page*> pages;
};
Теперь аллокатор может увеличиваться по одной странице за раз до необходимого размера.
Бенчмаркинг
Имеется основной аллокатор пулов, как класс шаблона, созданный с использованием размера фрагмента данных. Это позволяет компилятору генерировать очень эффективный код. Как это быстро на самом деле? Тривиальный бенчмарк просто распределяет и освобождает память в цикле. Необходимо оптимизировать работу с небольшими объектами, поэтому нужно сравнить скорость для 16, 32 и 64 байтов памяти, выделить 100, 200 и 400 блоков за раз, а затем освободить эти блоки в два цикла, освободив сначала нечетные, а затем четные индексы. Чтобы получить достаточно стабильные и сопоставимые результаты запускаем 250000 итераций.
void *pointers[allocations];
QBENCHMARK {
for (int i = 0; i < 250000; ++i) {
for (int j = 0; j < allocations; ++j)
pointers[j] = ::malloc(allocSize);
for (int j = 0; j < allocations; j += 2)
::free(pointers[j]);
for (int j = 1; j < allocations; j += 2)
::free(pointers[j]);
}
}
Аллокаторы, которые сравниваются, являются реализациями malloc по умолчанию на настольных платформах - macOS 10.14 (платформа разработчика), Windows 10 с VC ++17 и система malloc в Linux (Ubuntu 18.04, которая использует ptmalloc2). В Linux также сравнивались Google tcmalloc, Microsoft mimalloc и jemalloc из FreeBSD и Firefox. Тривиально использовать эти аллокаторы вместо malloc () из glibc в Linux, где они могут быть просто LD_PRELOAD.
$ LD_PRELOAD=LD_PRELOAD=/usr/local/lib/libtcmalloc.so ./tst_bench_allocator
Эти результаты довольно многообещающие:
Все аллокаторы имеют достаточно стабильное поведение для этого теста. Размер выделенного блока едва ли имеет значение, а удвоение количества выделений занимает вдвое больше времени.
Учитывая простоту реализации, не удивительно, что специализированный аллокатор пулов Qt превосходит даже самые быстрые аллокаторы общего назначения в 3 раза по сравнению с mimalloc и в 70 раз по сравнению с системным malloc в macOS 10.14.
Многопоточные модели
Один из вариантов использования, для которого разработчики Qt хотят спроектировать аллокатор - это выделения QEvent в целом и выделения QMetaCallEvent в частности. QEvents могут быть созданы из нескольких потоков, поэтому аллокатор должен быть потокобезопасным. Более того, QMetaCallEvent используется для передачи сигналов/слотов между потоками, и события обычно можно публиковать на объектах в разных потоках. Таким образом, поток, который выделяет, не обязательно будет потоком, который освобождает объект, и поток, который выделен, мог даже прерваться до того, как объект был обработан и удален в принимающем потоке.
Но, безусловно, будут случаи, когда клиентский код может гарантировать, что тот же поток, который выделяет память, является также потоком, который освобождает эту память, или, когда все происходит в одном потоке (например, работа с графом сцены). В идеале возможно сделать оптимизированную реализацию для каждой из этих ситуаций, не дублируя весь код.
Блокировки
Варианты создания потокового аллокатора безопасны, если ввести блокировку или использовать реализацию стека без блокировок, используя атомарные инструкции. Атомная реализация сделает саму реализацию стека свободной от блокировки, но это не поможет нам расти, когда исчерпаем стек. С мьютексом, однако, конкуренция за просмотр будет очень высокой, если несколько потоков пытаются выделить и освободить память.
Можно уменьшить конфликт блокировок, выделяя фрагмент данных из свободного стека, но возвращая фрагмент в другой стек «бэклога». Затем можно использовать другой мьютекс для защиты бэклога, когда заканчиваются свободные фрагменты данных, возможно поменяться местами в бэклоге. Для этой операции нужно держать оба мьютекса.
void *allocate()
{
auto stack_guard = lock_stack();
// try to adopt backlog
if (!stack) {
auto backlog_guard = lock_backlog();
stack = backlog;
backlog = nullptr;
}
if (!stack && !grow())
return nullptr;
Node *top = stack;
stack = stack->previous;
return top->chunk;
}
void free(void *ptr)
{
auto guard = lock_backlog();
Node *top = static_cast<Node*>(ptr);
top->previous = backlog;
backlog = top;
}
Это немного помогает, но выполнение данного теста с несколькими потоками быстро показывает, что одно это не может быть успешной стратегией.
Arenas
Более сложной архитектурой было бы, если каждый поток работал на своей собственной «arena». Каждый поток должен иметь свой собственный пул памяти для работы, поэтому будут некоторые накладные расходы. Можно использовать переменную thread_local для специфичной для потока arena. Время жизни arena связано с временем жизни потока с помощью std::unique_ptr.
private:
struct Arena
{
void push(void *ptr);
void *pop();
void grow();
void initPage();
QVector<page*> pages;
Node *stack = nullptr;
};
inline thread_local static std::unique_ptr<Arena> current_thread;
Arena *arena()
{
Arena *a = current_thread.get();
if (!a) {
a = new Arena;
current_thread.reset(a);
}
return a;
}
public:
void *allocate(size_t size)
{
Q_ASSERT(size <= ChunkSize);
Node *node = return arena()->pop();
return node ? node->chunk : nullptr;
}
void free(void *ptr)
{
Node *node = static_cast<Node*>(ptr);
arena()->push(node);
}
И пока клиентский код может гарантировать, что память освобождается тем же потоком, который ее выделил, не нужно использовать какие-либо блокировки для синхронизации операций в стеке арены.
Если объединить два подхода, то получим аллокатор, в котором каждый поток извлекает фрагменты из своей собственной arena без какой-либо блокировки. Потоки, освобождающие память, пришедшую из arena другого потока, будут выталкивать куски в стек невыполненной работы исходной arena, поэтому они конкурируют только с другими такими же освобождающими потоками за необходимую блокировку. Когда стек исчерпан, бэклог меняется, но тогда распределяющий поток также должен будет конкурировать за блокировку. Однако нужно иметь возможность отобразить часть памяти, которую клиентский код передает в free() на правильную arena, так как больше нет возможности просто использовать указатель arena thread_local, иначе получим освобождающий поток, принимающий всю память из распределяющих потоков. Наличие указателя на arena для каждого фрагмента памяти в стеке было бы одним из вариантов, но вносит немало затрат на распределение ресурсов. Необходимость записать 8 байт для фрагмента размером 40 байт означает, что при этом тратится 20% памяти.
Вместо этого можно использовать тот факт, что страницы памяти, которые выделяют с помощью mmap(), всегда имеют 4K байтовое выравнивание. В адресе страницы, выделенной с помощью mmap (или VirtualAlloc в Windows), нижние 12 бит (4096 = 2^12) всегда будут равны нулю, то есть 0x123456789abcd000. Адреса фрагментов данных на странице будут иметь одинаковые верхние 52 бита, поэтому возможно применить простую битовую маску к адресу фрагмента данных, и получить адрес страницы. Затем можно сделать так, чтобы страница памяти содержала указатель на arena, которой она принадлежит, поэтому нужно будет жертвовать только 8 байтами для каждой страницы 4K.
pivate:
struct Page
{
char memory[4096 - sizeof(Arena*)];
Arena *arena;
static Page *fromNode(Node *node)
{
return reinterpret_cast<Page*>(uintptr_t(node) & ~(sizeof(Page) - 1));
}
};
struct Arena
{
bool grow()
{
void *ptr = ::mmap(NULL, sizeof(Page), PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
Q_ASSERT_X(!(uintptr_t(ptr) % sizeof(Page)),
"PoolAllocator", "Page Alignment Error!");
if (!ptr)
return false;
Page *newPage = static_cast<Page*>(ptr);
initPage(newPage);
newPage->arena = this;
pages.append(newPage);
return true;
}
};
public:
void *allocate(size_t size)
{
Q_ASSERT(size <= ChunkSize);
Node *node = arena()->pop();
return node ? node->chunk : nullptr;
}
void free(void *ptr)
{
Node *node = static_cast<Node*>(ptr);
Arena *arena = Page::fromNode(node)->arena;
arena->push(node);
}
Дополнительную сложность добавляет возможность того, что поток выделения завершается, пока объекты с его arena еще живы. Для этого нужно отделить время жизни пула памяти от arena (которая посредством хранилища thread_local связана с временем жизни потока). Аллокатор может позаботиться о таких устаревших пулах памяти. Будущие потоки примут их.
Чтобы реализовать это, нужно выяснить, есть ли еще выделенная память. Структура же данных ничего не знает о выделенной памяти, только о свободной памяти. Итак, самый быстрый способ проверить - это перебрать весь стек и посчитать, сколько у имеется узлов. Если узлов меньше, чем умещается на всех выделенных страницах, память все еще используется.
Сравнение моделей потоков
Итак, теперь есть четыре модели многопоточности, с различными компромиссами в отношении производительности, накладных расходов памяти и параллелизма.
• Однопоточный (single-threaded), как тривиальный случай с одной arena и без блокировок.
• Модель общего пула (shared pool model), в которой все потоки работают на одной arena с двумя блокировками.
• Модель с несколькими пулами (multi-pool model), где каждый поток должен оставаться в пределах своей собственной arena и не нуждается в каких-либо блокировках.
• Наконец, многопоточная модель (multi-threaded model), в которой потоки выделяются из своей собственной arena, но память может быть освобождена любым потоком, и потоки могут завершаться, пока память, выделенная из их arena, все еще используется.
У первых трех моделей будет много вариантов использования, но для случая QEvent понадобится многопоточная модель.
Выполнение предыдущего теста с использованием этих различных реализаций, но без использования потоков, позволяет измерить чистые накладные расходы, которые представляют различные стратегии:
Кажется, что дополнительный код, необходимый для реализации стратегии arena, вносит очень мало накладных расходов. Модель общего пула, с другой стороны, не будет иметь большого преимущества по сравнению с простым использованием malloc, хотя она все еще может быть полезной при рассмотрении фрагментации памяти.
Многопоточный бенчмаркинг
Сравнительный анализ аллокаторов в реалистичном, многопоточном сценарии не прост. Даже система malloc работает очень быстро, поэтому выполнение чего-либо нетривиального, помимо выделения и освобождения памяти в тесте, затрудняет измерение реального воздействия аллокатора. Однако, если память только выделяем и освобождаем, то влияние конкуренции за блокировку в аллокаторах становится сильно преувеличенным. С другой стороны, разработчикам, возможно, придется использовать примитивы синхронизации, такие, как мьютексы или условия ожидания, для моделирования потока данных в реалистичных сценариях производителя/потребителя (например, когда Qt использует QMetaCallEvent для соединений сигнала/слота, пересекающих потоки). Это будет скрывать влияние блокировок в аллокаторе.
Тем не менее, относительные числа должны дать некоторое представление о том, насколько эффективен аллокатор Qt, который значительно быстрее, чем другие, находящиеся в состоянии стресса, с большой вероятностью окажет некоторое положительное влияние на производительность реального приложения. Основываясь на наблюдении из первого теста, что все аллокаторы имеют одинаковые характеристики производительности, независимо от того, насколько велики объекты. Теперь просто запускаем один тест для 16-байтовых объектов, но с таким количеством потоков, сколько у нас процессоров.
Используемая здесь модель потоков - это полная многопоточная реализация, в которой аллокатор Qt по-прежнему превосходит самую быструю альтернативу общего назначения в 2,5 раза, а система malloc по умолчанию соответствует коэффициенту не менее 7.
В следующей статье рассмотрим методы тестирования и отладки памяти. Покажем, как можно использовать идеи, разработанные до сих пор, при распределении объектов разных размеров. И, может быть, узнаем, как можно освободить пустые страницы.
