Полиморфные аллокаторы C++17

    Уже совсем скоро в OTUS стартует новый поток курса «C++ Developer. Professional». В преддверии старта курса наш эксперт Александр Ключев подготовил интересный материал про полиморфные аллокаторы. Передаем слово Александру:





    В данной статье, хотелось бы показать простые примеры работы с компонентами из нэймспэйса pmr и основные идеи лежащие в основе полиморфных аллокаторов.

    Основная идея полиморфных аллокаторов, введенных в c++17, — в улучшении стандартных аллокаторов, реализованных на основе статического полиморфизма или иными словами темплейтов. Их гораздо проще использовать, чем стандартные аллокаторы, кроме того, они позволяют сохранять тип контейнера при использовании разных аллокаторов и, следовательно, менять аллокаторы в рантайме.

    Если вы хотите std::vector с определенным аллокатором памяти, можно задействовать Allocator параметр шаблона:

    auto my_vector = std::vector<int, my_allocator>();


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

    auto my_vector = std::vector<int, my_allocator>();
    auto my_vector2 = std::vector<int, other_allocator>();
    auto vec = my_vector; // ok
    vec = my_vector2; // error

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

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

    Специфические типы данных, используемые новым аллокатором, находятся в нэймспэйсе std::pmr. Там же находятся темплейтные специализации стандартных контейнеров, которые умеют работать с полиморфным аллокатором.

    Одной из основных проблем на текущий момент остается несовместимость новых версий контейнеров из std::pmr с аналогами из std.

    Основные компоненты std::pmr:


    • std::pmr::memory_resource — абстрактный класс, реализация которого в конечном счете отвечают за работу с памятью.
    • Содержит следующий интерфейс:
      • virtual void* do_allocate(std::size_t bytes, std::size_t alignment),
      • virtual void do_deallocate(void* p, std::size_t bytes, std::size_t alignment)
      • virtual bool do_is_equal(const std::pmr::memory_resource& other) const noexcept.
    • std::pmr::polymorphic_allocator — имплементация стандартного аллокатора, использует указатель на memory_resource для работы с памятью.
    • new_delete_resource() и null_memory_resource() используются для работы с «глобальной» памятью
    • Набор готовых пулов памяти:
      • synchronized_pool_resource
      • unsynchronized_pool_resource
      • monotonic_buffer_resource
    • Специализации стандартных контейнеров с полиморфным аллокатором, std::pmr::vector, std::pmr::string, std::pmr::map и тд. Каждая специализация определена в том же заголовочном файле, что и соответствующий контейнер.
    • Набор готовых memory_resource:
      • memory_resource* new_delete_resource() Свободная функция, возвращает указатель на memory_resource, который использует глобальные операторы new и delete выделения памяти.
      • memory_resource* null_memory_resource()
        Свободная функция возвращает указатель на memory_resource, который бросает исключение std::bad_alloc на каждую попытку аллокации.
        Может быть полезен для того, чтобы гарантировать, что объекты не выделяют память в куче или для тестовых целей.


    • class synchronized_pool_resource : public std::pmr::memory_resource
      Потокобезопасная имплементация memory_resource общего назначения состоит из набора пулов с разными размерами блоков памяти.
      Каждый пул представляет из себя набор из кусков памяти одного размера.
    • class unsynchronized_pool_resource : public std::pmr::memory_resource
      Однопоточная версия synchronized_pool_resource.
    • class monotonic_buffer_resource : public std::pmr::memory_resource
      Однопоточный, быстрый, memory_resource специального назначения берет память из заранее выделенного буфера, но не освобождает его, т.е может только расти.

    Пример использования monotonic_buffer_resource и pmr::vector:

    #include <iostream>
    #include <memory_resource>   // pmr core types
    #include <vector>        	// pmr::vector
    #include <string>        	// pmr::string
     
    int main() {
    	char buffer[64] = {}; // a small buffer on the stack
    	std::fill_n(std::begin(buffer), std::size(buffer) - 1, '_');
    	std::cout << buffer << '\n';
     
    	std::pmr::monotonic_buffer_resource pool{std::data(buffer), std::size(buffer)};
     
    	std::pmr::vector<char> vec{ &pool };
    	for (char ch = 'a'; ch <= 'z'; ++ch)
        	vec.push_back(ch);
     
    	std::cout << buffer << '\n';
    }

    Вывод программы:

    
    _______________________________________________________________
    aababcdabcdefghabcdefghijklmnopabcdefghijklmnopqrstuvwxyz______
    

    В приведенном примере мы использовали monotonic_buffer_resource, инициализированный с помощью буфера выделенного на стеке. С помощью указателя на этот буфер мы легко можем вывести содержимое памяти.

    Вектор берет память из пула, что работает очень быстро, так как он на стеке, если память заканчивается, он запрашивает ее с помощью глобального оператора new. Пример демонстрирует реаллокации вектора при попытке вставить большее чем зарезервировано число элементов. При этом monotonic_buffer не освобождают старую память, а только растет.

    Можно, конечно, вызвать reserve() для вектора, чтобы минимизировать реаллокации, но цель примера именно в том чтобы продемонстрировать, как меняется monotonic_buffer_resource при расширении контейнера.

    Хранение pmr::string


    Что если мы хотим хранить строки в pmr::vector?

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

    Если вы хотите воспользоваться этой возможностью, нужно использовать std::pmr::string вместо std::string.

    Рассмотрим пример с заранее выделенным на стеке буфером, который мы передадим в качестве memory_resource для std::pmr::vector std::pmr::string:

    #include <iostream>
    #include <memory_resource>   // pmr core types
    #include <vector>        	// pmr::vector
    #include <string>        	// pmr::string
     
    int main() {
    	std::cout << "sizeof(std::string): " << sizeof(std::string) << '\n';
    	std::cout << "sizeof(std::pmr::string): " << sizeof(std::pmr::string) << '\n';
     
    	char buffer[256] = {}; // a small buffer on the stack
    	std::fill_n(std::begin(buffer), std::size(buffer) - 1, '_');
     
    	const auto BufferPrinter = [](std::string_view buf, std::string_view title) {
        	std::cout << title << ":\n";
        	for (auto& ch : buf) {
            	std::cout << (ch >= ' ' ? ch : '#');
        	}
        	std::cout << '\n';
    	};
     
    	BufferPrinter(buffer, "zeroed buffer");
     
    	std::pmr::monotonic_buffer_resource pool{std::data(buffer), std::size(buffer)};
    	std::pmr::vector<std::pmr::string> vec{ &pool };
    	vec.reserve(5);
     
    	vec.push_back("Hello World");
    	vec.push_back("One Two Three");
    	BufferPrinter(std::string_view(buffer, std::size(buffer)), "after two short strings");
     
    	vec.emplace_back("This is a longer string");
    	BufferPrinter(std::string_view(buffer, std::size(buffer)), "after longer string strings");
     
    	vec.push_back("Four Five Six");
    	BufferPrinter(std::string_view(buffer, std::size(buffer)), "after the last string");   
    }

    Вывод программы:

    sizeof(std::string): 32
    sizeof(std::pmr::string): 40
    zeroed buffer:
    _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
    after two short strings:
    #m######n#############Hello World######m#####@n#############One Two Three###_______________________________________________________________________________________________________________________________________________________________________________#
    after longer string strings:
    #m######n#############Hello World######m#####@n#############One Two Three####m######n#####################________________________________________________________________________________________This is a longer string#_______________________________#
    after the last string:
    #m######n#############Hello World######m#####@n#############One Two Three####m######n#####################________#m######n#############Four Five Six###________________________________________This is a longer string#_______________________________#

    Основные моменты, на которые нужно обратить внимание в данном примере:

    • Размер pmr::string больше чем std::string. Связано этот с тем, что добавляется указатель на memory_resource;
    • Мы резервируем вектор под 5 элементов, поэтому при добавлении 4х реаллокаций не происходит.
    • Первые 2 строки достаточно короткие для блока памяти вектора, поэтому дополнительного выделения памяти не происходит.
    • Третья строка более длинная и для потребовался отдельный кусок памяти внутри нашего буфера, в векторе при этом сохраняется только указатель на этот блок.
    • Как можно видеть из вывода, строка «This is a longer string» расположена почти в самом конце буфера.
    • Когда мы вставляем еще одну короткую строку, она попадает снова в блока памяти вектора

    Для сравнения проделаем такой же эксперимент с std::string вместо std::pmr::string

    sizeof(std::string): 32
    sizeof(std::pmr::string): 40
    zeroed buffer:
    _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
    after two short strings:
    ###w###########Hello World########w###########One Two Three###_______________________________________________________________________________________________________________________________________________________________________________________________#
    new 24
    after longer string strings:
    ###w###########Hello World########w###########One Two Three###0#######################_______________________________________________________________________________________________________________________________________________________________________#
    after the last string:
    ###w###########Hello World########w###########One Two Three###0#######################________@##w###########Four Five Six###_______________________________________________________________________________________________________________________________#


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

    Еще раз про расширение вектора:


    Упоминалось, что когда память в пуле заканчивается, аллокатор запрашивает ее с помощью оператора new().

    На самом деле это не совсем так — память запрашивается у memory_resource, возвращаемого с помощью свободной функции
    std::pmr::memory_resource* get_default_resource()
    По умолчанию эта функция возвращает
    std::pmr::new_delete_resource(), который в свою очередь выделяет память с помощью оператора new(), но может быть заменен с помощью функции
    std::pmr::memory_resource* set_default_resource(std::pmr::memory_resource* r)

    Итак, давайте рассмотрим пример, когда get_default_resource возвращает значение по умолчанию.

    Нужно иметь в виду, что методы do_allocate() и do_deallocate() используют аргумент «выравнивания», поэтому нам понадобится С++17 версия new() c поддержкой выравнивания:

    void* lastAllocatedPtr = nullptr;
    size_t lastSize = 0;
     
    void* operator new(std::size_t size, std::align_val_t align) {
    #if defined(_WIN32) || defined(__CYGWIN__)
    	auto ptr = _aligned_malloc(size, static_cast<std::size_t>(align));
    #else
    	auto ptr = aligned_alloc(static_cast<std::size_t>(align), size);
    #endif
     
    	if (!ptr)
        	throw std::bad_alloc{};
     
    	std::cout << "new: " << size << ", align: "
              	<< static_cast<std::size_t>(align)
      	        << ", ptr: " << ptr << '\n';
     
    	lastAllocatedPtr = ptr;
    	lastSize = size;
     
    	return ptr;
    }

    Теперь давайте вернемся к рассмотрению основного примера:

    constexpr auto buf_size = 32;
    uint16_t buffer[buf_size] = {}; // a small buffer on the stack
    std::fill_n(std::begin(buffer), std::size(buffer) - 1, 0);
     
    std::pmr::monotonic_buffer_resource pool{std::data(buffer), std::size(buffer)*sizeof(uint16_t)};
     
    std::pmr::vector<uint16_t> vec{ &pool };
     
    for (int i = 1; i <= 20; ++i)
    	vec.push_back(i);
     
    for (int i = 0; i < buf_size; ++i)
    	std::cout <<  buffer[i] << " ";
     
    std::cout << std::endl;
     
    auto* bufTemp = (uint16_t *)lastAllocatedPtr;
     
    for (unsigned i = 0; i < lastSize; ++i)
    	std::cout << bufTemp[i] << " ";

    Программа пытается положить 20 чисел в вектор, но учитывая, что вектор только растет, нам нужно места больше чем в зарезервированном буфере с 32 записями.

    Поэтому в какой-то момент аллокатор запросит память через get_default_resource, что в свою очередь приведет к вызову глобального new().

    Вывод программы:

    new: 128, align: 16, ptr: 0xc73b20
    1 1 2 1 2 3 4 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 132 0 0 0 0 0 0 0 144 0 0 0 65 0 0 0 16080 199 0 0 16176 199 0 0 16176 199 0 0 15344 199 0 0 15472 199 0 0 15472 199 0 0 0 0 0 0 145 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

    Судя по выводу в консоль выделенного буфера хватает только для 16 элементов, и когда мы вставляем число 17, происходит новая аллокация 128 байт с помощью оператора new().

    На 3й строчке мы видим блок памяти аллоцированный с помощью оператора new().

    Приведенный выше пример с переопределением оператора new() вряд ли подойдет для продуктового решения.

    К счастью, нам никто не мешает сделать свою реализацию интерфейса memory_resource.

    Все что нам нужно при этом –

    • унаследоваться от std::pmr::memory_resource
    • Реализовать методы:
      • do_allocate()
      • do_deallocate()
      • do_is_equal()
    • Передать нашу реализацию memory_resource контейнерам.

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


    Читать ещё


    OTUS. Онлайн-образование
    Цифровые навыки от ведущих экспертов

    Комментарии 2

      0
      Полиморфные аллокаторы интересны для оптимизаций выделения памяти «на куче». Например, через них можно сделать аллокации в арене (как protobuf arena) и очистить всю память разом, освободив арену.

      Один момент, который смущает — это хранение указателя на аллокатор в каждом объекте. Для контейнеров такой overhead может быть незаметен, а вот для строк — это плюс одна треть к размеру объекта. Вот думаю, можно ли провести оптимизация: хранить указатель на аллокатор в статической области памяти (thread_local). И перед работой с контейнером назначать этот указатель на необходимый аллокатор. Есть ли у кого подобный опыт?
        0
        А разве старый тип std::basic_string не хранил аллокатор, который был указан в шаблоне?
        Плюс с размером там не все так однозначно — в некоторых реализациях делают буфер прямо в самой переменной, чтобы короткие строки не ходили за памятью в кучу.
        И вообще всегда можно было взять старый тип и специализировать его типом аллокатора, который как раз и ходит в thread storage, чтобы получить инстанс алокатора для текущего треда.

      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

      Самое читаемое