Убедительные примеры пользовательских распределителей C++?

Как я упоминал здесь, я видел, что пользовательский распределитель STL Intel TBB значительно улучшился. производительность многопоточного приложения, просто изменив один

std::vector<T>

to

std::vector<T,tbb::scalable_allocator<T> >

(это быстрый и удобный способ переключения распределителя на использование отличных выделенных потоком куч TBB; см. .1.71.8289&rep=rep1&type=pdf" rel="noreferrer">стр. 7 в этом документе)

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

EASTL — библиотека стандартных шаблонов Electronic Arts

Я работаю над распределителем mmap, который позволяет векторам использовать память из файла с отображением памяти. Цель состоит в том, чтобы векторы, использующие хранилище, находились непосредственно в виртуальной памяти и отображались с помощью mmap. Наша проблема состоит в том, чтобы улучшить чтение действительно больших файлов (> 10 ГБ) в память без накладных расходов на копирование, поэтому мне нужен этот специальный распределитель.

Пока у меня есть скелет пользовательского распределителя (который происходит от std::allocator), я думаю, что это хорошая отправная точка для написания собственных распределителей. Не стесняйтесь использовать этот фрагмент кода как хотите:

#include <memory>
#include <stdio.h>

namespace mmap_allocator_namespace
{
        // See StackOverflow replies to this answer for important commentary about inheriting from std::allocator before replicating this code.
        template <typename T>
        class mmap_allocator: public std::allocator<T>
        {
public:
                typedef size_t size_type;
                typedef T* pointer;
                typedef const T* const_pointer;

                template<typename _Tp1>
                struct rebind
                {
                        typedef mmap_allocator<_Tp1> other;
                };

                pointer allocate(size_type n, const void *hint=0)
                {
                        fprintf(stderr, "Alloc %d bytes.\n", n*sizeof(T));
                        return std::allocator<T>::allocate(n, hint);
                }

                void deallocate(pointer p, size_type n)
                {
                        fprintf(stderr, "Dealloc %d bytes (%p).\n", n*sizeof(T), p);
                        return std::allocator<T>::deallocate(p, n);
                }

                mmap_allocator() throw(): std::allocator<T>() { fprintf(stderr, "Hello allocator!\n"); }
                mmap_allocator(const mmap_allocator &a) throw(): std::allocator<T>(a) { }
                template <class U>                    
                mmap_allocator(const mmap_allocator<U> &a) throw(): std::allocator<T>(a) { }
                ~mmap_allocator() throw() { }
        };
}

Чтобы использовать это, объявите контейнер STL следующим образом:

using namespace std;
using namespace mmap_allocator_namespace;

vector<int, mmap_allocator<int> > int_vec(1024, 0, mmap_allocator<int>());

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

Обновление: распределитель отображения памяти теперь доступен по адресу https://github.com/johannesthoma/mmap_allocator и LGPL. Не стесняйтесь использовать его для своих проектов.

Я работаю с механизмом хранения MySQL, который использует С++ для своего кода. Мы используем специальный распределитель для использования системы памяти MySQL, а не конкурируем с MySQL за память. Это позволяет нам убедиться, что мы используем память так, как пользователь настроил MySQL, а не «дополнительно».

Может быть полезно использовать настраиваемые распределители для использования пула памяти вместо кучи. Это один из многих примеров.

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

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

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

1. посредством пользовательского распределения среда выполнения ускорителя или драйвер уведомляются о блоке памяти
2. кроме того, операционная система может убедиться, что выделенный блок памяти заблокирован по страницам (некоторые называют это закрепленной памятью), то есть подсистема виртуальной памяти операционной системы не может перемещать или удалять страница внутри или из памяти
3. если 1. и 2. удерживаются и запрашивается передача данных между блоком памяти с блокировкой страницы и ускорителем, среда выполнения может напрямую обращаться к данным в основной памяти, поскольку она знает, где они находятся, и может быть уверена, что операционная система этого не сделала. переместить / удалить его
4. это экономит одну копию памяти, которая произошла бы с памятью, которая была выделена без блокировки страниц: данные должны быть скопированы в основную память в промежуточную область с блокировкой страниц, откуда с помощью ускорителя можно инициализировать передачу данных (через DMA )

Я не писал код на C++ с настраиваемым распределителем STL, но могу представить веб-сервер, написанный на C++, который использует настраиваемый распределитель для автоматического удаления временных данных, необходимых для ответа на HTTP-запрос. Пользовательский распределитель может освободить все временные данные сразу после создания ответа.

Другой возможный вариант использования пользовательского распределителя (который я использовал) — это написание модульного теста, чтобы доказать, что поведение функции не зависит от какой-либо части ее ввода. Пользовательский распределитель может заполнить область памяти любым шаблоном.

Здесь я использую пользовательские распределители; можно даже сказать, что это было сделано для обхода другого пользовательского управления динамической памятью.

Предыстория: у нас есть перегрузки для malloc, calloc, free и различные варианты операторов new и delete, и компоновщик с радостью заставляет STL использовать их для нас. Это позволяет нам делать такие вещи, как автоматическое объединение небольших объектов, обнаружение утечек, заполнение аллоков, свободное заполнение, выделение отступов с помощью часовых, выравнивание строк кэша для определенных аллоков и отложенное освобождение.

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

Решение: напишите собственный распределитель, который использует расширенную кучу, и используйте его только во внутренних компонентах архитектуры отслеживания утечек памяти... Все остальное по умолчанию соответствует обычным перегрузкам new/delete, которые выполняют отслеживание утечек. Это позволяет избежать самого отслеживания трекера (а также обеспечивает дополнительную функциональность упаковки, мы знаем размер узлов трекера).

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

Я использую специальный распределитель для подсчета количества выделений/освобождений в одной части моей программы и измерения того, сколько времени это занимает. Этого можно добиться и другими способами, но этот способ мне очень удобен. Особенно полезно то, что я могу использовать пользовательский распределитель только для подмножества моих контейнеров.

Одна важная ситуация: при написании кода, который должен работать за пределами модуля (EXE/DLL), важно, чтобы ваши выделения и удаления происходили только в одном модуле.

Где я столкнулся с этим, так это в архитектуре плагинов в Windows. Очень важно, например, если вы передаете std::string через границу DLL, любое перераспределение строки происходит из кучи, из которой она возникла, а НЕ из кучи в DLL, которая может быть другой*.

*На самом деле это сложнее, так как если вы динамически связываетесь с CRT, это может работать в любом случае. Но если каждая библиотека DLL имеет статическую ссылку на CRT, вы попадаете в мир боли, где постоянно возникают фантомные ошибки выделения.

Обязательная ссылка на доклад Андрея Александреску на CppCon 2015 о распределителях:

https://www.youtube.com/watch?v=LIb3L4vKZ7U

Приятно то, что просто придумывая их, вы начинаете думать о том, как бы вы их использовали :-)

Одним из примеров того, как я их использовал, была работа со встроенными системами с очень ограниченными ресурсами. Допустим, у вас есть 2 КБ свободной оперативной памяти, и ваша программа должна использовать часть этой памяти. Вам нужно хранить, скажем, 4-5 последовательностей где-то вне стека, и, кроме того, вам нужен очень точный доступ к тому, где эти вещи хранятся, это ситуация, когда вы можете написать свой собственный распределитель. Реализации по умолчанию могут фрагментировать память, это может быть неприемлемо, если у вас недостаточно памяти и вы не можете перезапустить программу.

Один проект, над которым я работал, заключался в использовании AVR-GCC на некоторых маломощных чипах. Нам нужно было хранить 8 последовательностей переменной длины, но с известным максимумом. реализация стандартной библиотеки управления памятью представляет собой тонкую оболочку вокруг malloc/free, который отслеживает, где размещать элементы, добавляя перед каждым выделенным блоком памяти указатель на конец этого выделенного участка памяти. При выделении новой части памяти стандартный распределитель должен пройтись по каждой из частей памяти, чтобы найти следующий доступный блок, в котором будет соответствовать запрошенный размер памяти. На настольной платформе это было бы очень быстро для этих нескольких элементов, но вы должны иметь в виду, что некоторые из этих микроконтроллеров очень медленные и примитивные по сравнению с ними. Кроме того, проблема фрагментации памяти была серьезной проблемой, и у нас действительно не было другого выбора, кроме как использовать другой подход.

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

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

Для разделяемой памяти жизненно важно, чтобы не только заголовок контейнера, но и содержащиеся в нем данные хранились в разделяемой памяти.

Распределитель Boost::Interprocess — хороший пример. Однако, как вы можете прочитать здесь этого всего недостаточно, чтобы сделать все контейнеры STL совместимыми с разделяемой памятью (из-за разных смещений отображения в разных процессах указатели могут "сломаться").

Некоторое время назад я нашел это решение очень полезным для себя: Быстрый распределитель C++11 для контейнеров STL . Это немного ускоряет контейнеры STL на VS2017 (~5x), а также на GCC (~7x). Это распределитель специального назначения, основанный на пуле памяти. Его можно использовать с контейнерами STL только благодаря механизму, который вы запрашиваете.

Я лично использую Loki::Allocator/SmallObject для оптимизации использования памяти для небольших объектов — он показывает хорошую эффективность и удовлетворительную производительность, если вам приходится работать с небольшим количеством очень маленьких объектов (от 1 до 256 байт). Это может быть примерно в 30 раз эффективнее, чем стандартное выделение нового/удаления C++, если мы говорим о выделении умеренного количества небольших объектов разных размеров. Кроме того, существует специальное для VC решение под названием «QuickHeap», которое обеспечивает максимально возможную производительность (операции выделения и освобождения просто считывают и записывают адрес выделяемого/возвращаемого в кучу блока, соответственно, в 99,(9)% случаев. — зависит от настроек и инициализации), но за счет заметных накладных расходов — ему нужно два указателя на экстент и один дополнительный для каждого нового блока памяти. Это максимально быстрое решение для работы с огромным (10 000++) количеством создаваемых и удаляемых объектов, если вам не нужно большое разнообразие размеров объектов (для каждого размера объекта создается отдельный пул, от 1 до 1023 байт). в текущей реализации, поэтому затраты на инициализацию могут преуменьшить общее повышение производительности, но можно пойти дальше и выделить/освободить некоторые фиктивные объекты до того, как приложение войдет в критические для производительности этапы).

Проблема со стандартной реализацией new/delete в C++ заключается в том, что обычно это просто оболочка для выделения C malloc/free, и она хорошо работает для больших блоков памяти, например 1024+ байт. Он имеет заметные накладные расходы с точки зрения производительности, а иногда и дополнительную память, используемую для отображения. Таким образом, в большинстве случаев пользовательские распределители реализуются таким образом, чтобы максимизировать производительность и/или минимизировать объем дополнительной памяти, необходимой для выделения небольших (≤1024 байт) объектов.

В графическом моделировании я видел специальные распределители, используемые для

1. Ограничения выравнивания, которые std::allocator не поддерживали напрямую.
2. Сведение к минимуму фрагментации за счет использования отдельных пулов для краткосрочных (только этот кадр) и долгосрочных выделений.

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

template <class T>
class allocator
{
public:
    using value_type    = T;

    allocator() noexcept {}
    template <class U> allocator(allocator<U> const&) noexcept {}

    value_type*  // Use pointer if pointer is not a value_type*
    allocate(std::size_t n)
    {
        return static_cast<value_type*>(::operator new (n*sizeof(value_type)));
    }

    void
    deallocate(value_type* p, std::size_t) noexcept  // Use pointer if pointer is not a value_type*
    {
        OPENSSL_cleanse(p, n);
        ::operator delete(p);
    }
};
template <class T, class U>
bool
operator==(allocator<T> const&, allocator<U> const&) noexcept
{
    return true;
}
template <class T, class U>
bool
operator!=(allocator<T> const& x, allocator<U> const& y) noexcept
{
    return !(x == y);
}

Рекомендовать использовать шаблон распределителя от Hinnant: https://howardhinnant.github.io/allocator_boilerplate.html )