Динамическое распределение памяти является фундаментальной частью большинства компьютерных систем с 1960 года.1

Каждый использует динамическое распределение памяти. Если вы когда-либо называли malloc или new, то вы использовали динамическое распределение памяти. Большинство программистов склонны рассматривать кучу как& #8220;магический мешок& #8221;: Мы просим его о памяти, и он волшебным образом создает что-то для нас. Иногда мы сталкиваемся с проблемами, потому что куча не волшебная.

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

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

Dynamic memory allocation is often inefficient

Из-за усложнения динамического распределения памяти, он часто неэффективен с точки зрения времени и / или пространства. Большинство алгоритмов распределения памяти хранят некоторую форму информации с каждым блоком памяти, размером блока или некоторой реляционной информацией, такой как его положение во внутреннем дереве или структуре списка. Для такихполей заголовкаобычно используется одно машинное слово в блоке, который используется программой. Очевидным недостатком является то, что небольшие объекты динамически распределяются. Например, если инты были динамически распределены, то алгоритм автоматически зарезервирует пространство для полей заголовка, и мы в конечном итоге потеряем 50% памяти. Конечно, это наихудший сценарий. Однако более современные программы используют небольшие объекты на куче, что делает эту проблему все более очевидной. Уилсон и др. АЛ. утверждают, что средняя сумма накладных расходов на память составляет от десяти до двадцати процентов2. Накладные расходы на память будут расти, поскольку все больше программ используют более мелкие объекты. Именно накладные расходы на память приближают программы к виртуальному пределу.

В более крупных системах накладные расходы на память не так велики, как проблема (по сравнению с количеством времени, которое потребуется для работы вокруг нее), и поэтому часто игнорируются. Тем не менее, существуют ситуации, когда многие распределения и/или распределения меньших объектов происходят в рамках алгоритма с критичным временем, и в этих ситуациях система распределения памяти часто слишком медленна.

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

Простое сегрегированное хранилище является основной идеей библиотеки Boost Pool. Simple Segregated Storage — самый простой и, вероятно, самый быстрый алгоритм распределения памяти. Он начинается с разделения блока памяти на куски фиксированного размера. То, откуда происходит блок, не важно до момента реализации. Бассейн — это объект, который использует простое сегрегированное хранилище таким образом. Для иллюстрации:

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

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

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

Простое сегрегированное хранение также очень быстрое. В простейшем случае выделение памяти — это просто удаление первой части из свободного списка, операция O(1). В случае, когда свободный список пуст, другой блок может быть приобретен и разделен, что приведет к амортизированному времени O(1). Распределение памяти может быть таким же простым, как добавление этого фрагмента в переднюю часть свободного списка, операция O(1). Однако для более сложного использования Simple Segregated Storage может потребоваться отсортированный бесплатный список, который делает распределение сделок O(N).

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

Terminology

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

Overview

Каждый пул имеет один бесплатный список, который может распространяться на несколько блоков памяти. Таким образом, Бассейн также имеет связанный список выделенных блоков памяти. Каждый блок памяти по умолчанию выделяется с помощью<new[]>, и все блоки памяти освобождаются от разрушения. Именно использование<new[]>позволяет нам гарантировать выравнивание.

Proof of Concept: Guaranteeing Alignment

Каждый блок памяти выделяется как тип POD (в частности, массив символов) через<operator new[]>. Пусть<POD_size>будет число выделенных знаков.

Predicate 1: Arrays may not have padding

Это следует из следующей цитаты:

[5.3.3/2] (Выражения::Унитарные выражения::Sizeof)... При применении к массиву результатом является общее количество байтов в массиве. Это означает, что размер массива n элементов в n раз больше размера элемента.

Поэтому массивы не могут содержать набивку, хотя элементы внутри массивов могут содержать набивку.

Predicate 2: Any block of memory allocated as an array of characters through operator new[] (hereafter referred to as the block) is properly aligned for any object of that size or smaller

Это следует из следующего:

Consider: imaginary object type Element of a size which is a multiple of some actual object size; assume sizeof(Element) > POD_size

Обратите внимание, что объект такого размера может существовать. Одним из объектов такого размера является массив «фактических» объектов.

Обратите внимание, что блок правильно выровнен для элемента. Это следует из предикат 2.

Corollary 1: The block is properly aligned for an array of Elements

Это следует из предикатов 1 и 2 и следующей цитаты:

[3.9/9] (Основные понятия::Типы)«Тип объекта — это (возможно, cv-квалифицированный) тип, который не является типом функции, не является эталонным типом и не является пустотным типом».

(В частности, типы массивов являются типами объектов.)

Corollary 2: For any pointer p and integer i, if p is properly aligned for the type it points to, then p + i (when well-defined) is properly aligned for that type; in other words, if an array is properly aligned, then each element in that array is properly aligned

Нет цитат из Стандарта, чтобы непосредственно поддержать этот аргумент, но он соответствует общей концепции значения «выравнивания».

Следует отметить, что условия для<p +i>, которые должны быть четко определены, изложены в [5.7/5]. Мы не цитируем это здесь, но только заметим, что это четко определено, если<p>и<p+ i>оба указывают на один и тот же массив.

Let: sizeof(Element) be the least common multiple of sizes of several actual objects (T1, T2, T3, ...)

Let: block be a pointer to the memory block, pe be (Element *) block, and pn be (Tn *) block

Corollary 3: For each integer i, such that pe + i is well-defined, then for each n, there exists some integer jn such that pn + jn is well-defined and refers to the same memory address as pe + i

Это следует естественно, поскольку блок памяти представляет собой массив Элементов, и для каждого n,<sizeof(Element)%sizeof(Tn) ==0;>таким образом, граница каждого элемента в массиве Элементов также является границей каждого элемента в каждом массиве Tn.

Theorem: For each integer i, such that pe + i is well-defined, that address (pe + i) is properly aligned for each type Tn

Так как<pe+ i>хорошо определено, то по следствию 3<pn+ jn>хорошо определено. Он правильно выровнен из Предиката 2 и Следствий 1 и 2.

Use of the Theorem

Вышеприведенное доказательство охватывает требования к выравниванию для вырезания кусков из блока. В реализации используются фактические размеры объектов:

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

Таким образом,<alloc_size>определяется как самый большой из вышеперечисленных размеров, округленный до множества из всех трех размеров. Это гарантирует выравнивание при условии, что все выравнивания являются полномочиями двух: что-то, что кажется верным на всех известных платформах.

A Look at the Memory Block

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

Каждая из этих секций может содержать прокладку по мере необходимости, чтобы гарантировать выравнивание для каждой из следующих секций. Размер первой секции<number_of_chunks* lcm(requested_size, sizeof(void*),sizeof(size_type));>, размер второй секции<lcm(sizeof(void*), sizeof(size_type);>и размер третьей секции<sizeof(size_type)>.

Вот пример блока памяти, где<requested_size ==sizeof(void*) ==sizeof(size_type)==4>:

Чтобы показать визуальный пример возможной прокладки, вот пример блока памяти, где<requested_size==8and sizeof(void*)==sizeof(size_type)==4>

Introduction

<simple_segregated_storage.hpp>предоставляет класс шаблонов simple_segregated_storage, который контролирует доступ к свободному списку фрагментов памяти.

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

Synopsis

template <typename SizeType = std::size_t>
class simple_segregated_storage
{
  private:
    simple_segregated_storage(const simple_segregated_storage &);
    void operator=(const simple_segregated_storage &);
  public:
    typedef SizeType size_type;
    simple_segregated_storage();
    ~simple_segregated_storage();
    static void * segregate(void * block,
        size_type nsz, size_type npartition_sz,
        void * end = 0);
    void add_block(void * block,
        size_type nsz, size_type npartition_sz);
    void add_ordered_block(void * block,
        size_type nsz, size_type npartition_sz);
    bool empty() const;
    void * malloc();
    void free(void * chunk);
    void ordered_free(void * chunk);
    void * malloc_n(size_type n, size_type partition_sz);
    void free_n(void * chunks, size_type n,
        size_type partition_sz);
    void ordered_free_n(void * chunks, size_type n,
        size_type partition_sz);
};

Semantics

Объект типа<simple_segregated_storage<SizeType>>пуст, если его свободный список пуст. Если он не пустой, то заказывается, если заказывается его бесплатный список. Свободный список упорядочен, если повторные вызовы<malloc()>приведут к постоянно увеличивающейся последовательности значений, как определено<std::less<void*>>. Функция-член сохраняет порядок, если свободный список сохраняет свою ориентацию порядка (то есть упорядоченный свободный список все еще упорядочен после вызова функции-члена).

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

В следующей таблицеUserAllocatorявляется типом User Allocator,блокявляется значением типа char *, аnявляется значением типа. UserAllocator::size_type

В этой библиотеке представлены два класса UserAllocator:<default_user_allocator_new_delete>и<default_user_allocator_malloc_free>. Значение по умолчанию для параметра шаблона UserAllocator всегда<default_user_allocator_new_delete>.