Пользовательские распределители кучи

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

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

Программирование игр (по крайней мере, в тех играх, которые амбициозны по отношению к аппаратному обеспечению) иногда оказывается промежуточным: вы можете использовать динамическое выделение, но при этом достаточно памяти и мягких ограничений в реальном времени, которые нельзя рассматривать как распределитель как черный ящик не говоря уже о сборке мусора, поэтому вы должны использовать пользовательские распределители. Это одна из причин, почему C ++ все еще широко используется в игровой индустрии; это позволяет вам делать такие вещи, как http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html

Какие еще домены находятся на этой промежуточной территории? Где помимо игр интенсивно используются пользовательские распределители?

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

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

Чтобы привести несколько примеров ... в моей первой компании я работал над пакетом Historian, программным обеспечением, отвечающим за сбор / хранение / архивирование данных управления процессом (например, завод, атомная электростанция или нефтеперерабатывающий завод с 10 миллионами датчиков, мы будем хранить эти данные). Каждый раз, когда мы анализировали любые узкие места в производительности, которые мешали Historian обрабатывать больше данных, большую часть времени проблема заключалась в том, как обрабатывается память. Мы проделали большую работу, чтобы убедиться, что malloc / free не были вызваны, если они не были абсолютно необходимы.

На моей нынешней работе я работаю над видеомагнитофоном для видеонаблюдения и пакетом анализа. При 30 кадрах в секунду каждый канал получает видеокадр каждые 33 миллисекунды. На оборудовании, которое мы продаем, мы можем легко записать 100 каналов видео. Так что это еще один случай, чтобы убедиться, что в критическом пути (сетевой вызов => компоненты захвата => программное обеспечение для управления записывающим устройством => компоненты хранения => диск) нет динамического выделения памяти. У нас есть специальный распределитель кадров, который содержит блоки буферов фиксированного размера и использует LIFO для повторного использования ранее выделенных буферов. Если вам требуется 600 КБ хранилища, вы можете получить буфер 1024 КБ, который занимает пустое место, но поскольку он специально предназначен для нашего использования, где каждое выделение очень короткое, он работает очень хорошо, потому что используется буфер,

В описанных мной типах приложений (перемещение большого количества данных из A в B и обработка большого количества клиентских запросов) переход в кучу и обратно является основным источником узких мест производительности ЦП. Сокращение фрагментации кучи до минимума является вторичным преимуществом, однако, насколько я могу судить, большинство современных ОС уже реализуют кучи с низкой фрагментацией (как минимум, я знаю, что Windows это делает, и я надеюсь, что и другие тоже). Лично за 12+ лет работы в таких средах я часто сталкивался с проблемами использования процессора, связанными с кучей, хотя ни разу не видел систему, которая действительно страдала от фрагментированной кучи.

Обработка видео, VFX, операционные системы и т. Д. Часто люди злоупотребляют ими, хотя. Структура данных и распределитель не должны быть разделены для достижения эффективного распределения.

Например, он вносит много дополнительных сложностей, чтобы разделить эффективное распределение узлов дерева в октрее от самого октри и полагаться на внешний распределитель. Совсем не обязательно нарушать SRP, чтобы объединить эти две проблемы и возложить на октре ответственность за одновременное выделение нескольких узлов одновременно, поскольку это не увеличивает количество причин для изменения. Фактически, это может уменьшить его.

В C ++, например, один из запаздывающих побочных эффектов , имеющие стандартные контейнеров полагаться на внешнем распределителе сделавшим связаны структуры , как std::mapи std::listсчитаются практически бесполезны в C ++ сообщества, так как они бенчмаркинг их противыstd::allocatorв то время как эти структуры данных выделяют один узел за раз. Конечно, в этом случае ваши связанные структуры будут работать плохо, но все могло бы сложиться иначе, если бы эффективное распределение узлов для связанных структур считалось ответственностью структуры данных, а не распределителя. Они могут по-прежнему использовать пользовательское распределение по другим причинам, таким как отслеживание / профилирование памяти, но использование распределителя для повышения эффективности связанных структур при одновременном распределении узлов делает их все по умолчанию крайне неэффективными, что было бы хорошо, если бы он шел с известным предупреждением о том, что связанные структуры теперь нуждаются в специальном распределителе, таком как свободный список, чтобы быть достаточно эффективными и избегать пропусков кэша влево и вправо. Гораздо более практичным, возможно, было что-то вродеstd::list<T, BlockSize, Alloc>где BlockSizeуказывает количество смежных узлов, выделяемых за один раз для свободного списка (указание 1 фактически приведет к тому, std::listчто происходит сейчас).

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

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

Где помимо игр интенсивно используются пользовательские распределители?

facebook

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