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

176

Какие есть веские причины отказаться std::allocatorот нестандартного решения? Сталкивались ли вы с ситуациями, когда это было абсолютно необходимо для корректности, производительности, масштабируемости и т. Д.? Какие-нибудь действительно умные примеры?

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

Naaff
источник

Ответы:

121

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

std::vector<T>

в

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

(это быстрый и удобный способ переключения распределителя на использование изящных кучи частных потоков TBB; см. стр. 7 в этом документе )

timday
источник
3
Спасибо за эту вторую ссылку. Использование распределителей для реализации кучи частных потоков очень разумно. Мне нравится, что это хороший пример того, где пользовательские распределители имеют явное преимущество в сценарии, который не ограничен в ресурсах (встраивание или консоль).
Нааф
7
Первоначальная ссылка больше не существует, но у CiteSeer есть файл PDF: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.8289
Арто Бендикен,
1
Я должен спросить: вы можете надежно переместить такой вектор в другой поток? (Наверное, нет)
Sellibitze
@sellibitze: Поскольку векторами манипулировали из задач TBB и повторно использовали в нескольких параллельных операциях, и нет никакой гарантии, какой рабочий поток TBB будет выполнять задачи, я пришел к выводу, что он работает просто отлично. Хотя обратите внимание, что были некоторые исторические проблемы с компонентами освобождения TBB, созданными в одном потоке в другом потоке (по-видимому, классическая проблема с частными кучами потоков и шаблонами распределения и выделения ресурсов между производителями и потребителями. TBB утверждает, что это средство выделения позволяет избежать этих проблем, но я видел иначе . Может быть исправлено в более новых версиях.)
Timday
@ArtoBendiken: ссылка на скачивание по вашей ссылке недействительна.
einpoklum
81

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

EASTL - Стандартная библиотека шаблонов Electronic Arts

Grumbel
источник
14
+1 для ссылки на EASTL: «Среди разработчиков игр самая фундаментальная слабость [STL] - это дизайн распределителя std, и именно эта слабость была основным фактором, способствующим созданию EASTL».
Нааф
65

Я работаю над mmap-allocator, который позволяет векторам использовать память из отображенного в памяти файла. Цель состоит в том, чтобы векторы, использующие хранилище, находящиеся непосредственно в виртуальной памяти, отображались с помощью 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. Не стесняйтесь использовать его для своих проектов.

Johannes Thoma
источник
17
Проще говоря, наследование от std :: allocator не совсем идиоматический способ написания распределителей. Вместо этого вы должны взглянуть на allocator_traits, который позволяет вам предоставить минимум функций, а класс traits предоставит все остальное. Обратите внимание, что STL всегда использует ваш распределитель через allocator_traits, а не напрямую, поэтому вам не нужно обращаться к allocator_traits самостоятельно. Нет особого стимула извлекать из std :: allocator (хотя этот код может быть полезной отправной точкой независимо от этого).
Нир Фридман
25

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

Томас Джонс-Лоу
источник
21

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

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

Мартин Кот
источник
3
Или когда этот пул памяти используется совместно.
Энтони
9

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

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

PTS
источник
5
Кажется, что первый пример - это работа деструктора, а не распределителя.
Майкл Дорст
2
Если вы беспокоитесь о своей программе в зависимости от начального содержимого памяти из кучи, быстрый (то есть за ночь!) Запуск в valgrind позволит вам узнать, так или иначе.
cdyson37
3
@anthropomorphic: деструктор и пользовательский распределитель будут работать вместе, сначала будет выполняться деструктор, затем удаление пользовательского распределителя, который еще не вызовет free (...), но будет вызван free (...) позже, когда обслуживание закончилось. Это может быть быстрее, чем распределитель по умолчанию и уменьшить фрагментацию адресного пространства.
оч
8

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

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

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

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

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

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

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

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

Leander
источник
5

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

Йорген Фог
источник
4

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

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

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

Стивен
источник
Если вы передаете объекты через границы DLL, вы должны использовать параметр Многопоточная (Debug) DLL (/ MD (d)) для обеих сторон. C ++ не был разработан с поддержкой модулей. В качестве альтернативы вы можете скрыть все за интерфейсами COM и использовать CoTaskMemAlloc. Это лучший способ использовать интерфейсы плагинов, которые не привязаны к конкретному компилятору, STL или поставщику.
gast128
Правило старых парней таково: не делай этого. Не используйте типы STL в DLL API. И не передавайте ответственность за освобождение динамической памяти через границы API DLL. Не существует C ++ ABI - поэтому, если вы рассматриваете каждую DLL как API C, вы избегаете целого класса потенциальных проблем. На счет "c ++ beauty", конечно. Или, как предполагает другой комментарий: используйте COM. Просто C ++ - плохая идея.
BitTickler
3

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

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

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

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

shuttle87
источник
3

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

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

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

einpoklum
источник
2

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

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

Тед
источник
2

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

никто особенный
источник
1

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

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

Фрактальная Множественность
источник
1

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

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