Boost.Pool

Назначение учебника в популяризации применения библиотеки Boost вообще (полная документация к библиотеке) и Boost::Pool в частности.

Введение

Что такое Pool?

Boost.Pool представляет собой очень быстрый алгоритм выделения памяти, быстродействие которого достигается за счет ограничения области применения, т.е. потерей универсальности. Для более подробной информации об идеях, на которых базируется Pool, смотрите Идеи, лежащие в основе Pool и Хранилище с простым разбиением (Simple Segregated Storage)).

Зачем нужен Pool?

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

Когда нужен Pool?

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

Какой аллокатор лучше всего?

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

Если для вас важна производительность, применяйте fast_pool_allocator при использовании таких контейнеров как std::list, и используйте pool_allocator при работе с std::vector.

Как пользоваться Pool?

Смотрите раздел Интерфейсные классы Boost Pool, который демонстрирует различные интерфейсы Pool, предоставляемые библиотекой.

Структура библиотеки и зависимости

Форвард-декларации всех доступных символов библиотеки находятся в заголовочном файле, включаемым с помощью
#include <boost/pool/poolfwd.hpp>

Библиотека использует макросы с префиксом BOOST_POOL_. Исключениями из этого правила являются стражи заголовочных файлов (the include file guards), которые представляю собой (для файла xxx.hpp) BOOST_xxx_HPP. Все символы, предоставляемые библиотекой, определены в пространстве имен boost::. Символы, используемые реализацией библиотеки находятся в пространстве имен boost::details::pool.
Заголовочные файлы, используемые реализацией находятся в поддиректории /detail/.

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

Установка

Библиотека Boost.Pool состоит только из заголовочных файлов. Это означает, что не нужно собирать какие-либо .lib, .dll, или .so файлы; просто добавьте директорию Boost в пути к заголовочным файлам вашего компилятора.

Сборка тестовых программ

Осуществляется с помощью jamfile.v2, который запускается обычным способом, например: boost\libs\pool\test> bjam -a >pool_test.log

Интерфейсные классы Boost Pool — Какие классы существуют и когда их использовать.

Введение

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

Терминология и соглашения

Object или Singleton

Вы можете использовать Boost.Pool в виде Object или как Singleton. При использовании в виде Object вы каждый Pool создаете в виде отдельного индивидуального объекта, который может быть явно создан или уничтожен в любой удобный для вас момент. При этом уничтожение такого Pool неявно освобождает всю ранее выделенную память.
При использовании Boost.Pool в виде Singleton вы создаете каждый Pool в виде статического объекта. При этом созданием и удалением такого Boost.Pool вы не управляете - он создается перед началом программы и удаляется после ее завершения. Boost.Pool, основанные на применении Singleton могут быть разделяемыми (shared), что неявно подразумевает потокобезопасность (implies thread-safety). Системная память, выделенная объектом Boost.Pool в виде Singleton при необходимости может быть освобождена до завершения программы с помощью release_memory или purge_memory.

Нехватка памяти (Out-of-memory): Исключения или возврат Null

Некоторые интерфейсы Pool используют исключения при нехватке памяти, другие просто возвращают 0. В общем случае, где это не требуется стандартом, интерфейсы Pool всегда предпочитают возвращать 0 вместо использования исключения.

Сортировать или не сортировать

Упорядоченный pool поддерживает свой внутренний список свободных блоков упорядоченным по адресам каждого свободного блока — это наиболее эффективный способ, если вы выделяете память для массива объектов. Однако, освобождение объекта может иметь сложность O(N) от текущего числа свободных блоков, что может быть запредельно дорогим в некоторых ситуациях.
Неупорядоченный pool не поддерживает список свободных блоков упорядоченным в какой-либо форме, как результат выделение и освобождение одиночного объекта очень быстрое, но выделение памяти для массива может быть медленным (отдельно нужно отметить, что Boost.Pool просто может не знать, что он содержит достаточно свободной памяти для выполнения запроса на выделение и без необходимости запросит (у системы) дополнительную память).

Интерфейсы Pool

• pool
• Object_pool
• Singleton_pool
• pool_allocator

pool

Интерфейсный класс pool  реализует собой подход с применением Object, возвращающий Null при нехватке памяти. pool является быстрым аллокатором и гарантирует правильное выравнивание все выделенных блоков памяти (chunks). Заголовочный файл pool.hpp предоставляет два UserAllocator класса и  шаблонный класс pool, которые расширяют и обобщают фреймворк  Simple Segregated Storage . Для дополнительной информации о других интерфейсах, основанных на pool, смотрите  Pool Interfaces.
Синопсис
Существует два UserAllocator класса. Оба находятся в  pool.hpp.
По умолчанию, параметром шаблона UserAllocator всегда является  default_user_allocator_new_delete.

struct default_user_allocator_new_delete
{
  typedef std::size_t size_type;
  typedef std::ptrdiff_t difference_type;

  static char * malloc(const size_type bytes)
  { return new (std::nothrow) char[bytes]; }
  static void free(char * const block)
  { delete [] block; }
};

struct default_user_allocator_malloc_free
{
  typedef std::size_t size_type;
  typedef std::ptrdiff_t difference_type;

  static char * malloc(const size_type bytes)
  { return reinterpret_cast<char *>(std::malloc(bytes)); }
  static void free(char * const block)
  { std::free(block); }
};

template <typename UserAllocator = default_user_allocator_new_delete>
class pool
{
  private:
    pool(const pool &);
    void operator=(const pool &);

  public:
    typedef UserAllocator user_allocator;
    typedef typename UserAllocator::size_type size_type;
    typedef typename UserAllocator::difference_type difference_type;

    explicit pool(size_type requested_size);
    ~pool();

    bool release_memory();
    bool purge_memory();

    bool is_from(void * chunk) const;
    size_type get_requested_size() const;

    void * malloc();
    void * ordered_malloc();
    void * ordered_malloc(size_type n);

    void free(void * chunk);
    void ordered_free(void * chunk);
    void free(void * chunks, size_type n);
    void ordered_free(void * chunks, size_type n);
};

Например:
void func()
{
  boost::pool<> p(sizeof(int));
  for (int i = 0; i < 10000; ++i)
  {
    int * const t = p.malloc();
    ... // Делаем что-либо с t; не тратим время на вызов free().
  }
} // при завершении функции, p уничтожается, и вся выделенная под int память неявно освобождается.

Object_pool

Интерфейс  template class object_pool  также является интерфейсом Object Usage, возвращающим Null при нехватке памяти, но при этом знающим тип объекта, для которого выделяется память. При вызове деструктора object_pool , будет произведен вызов деструкта для всех раннее размещенных объектов. object_pool.hpp предоставляет шаблон, который может быть использован для быстрого и эффективного выделения памяти, а также обеспечивает автоматический вызов деструктора для неудаленных (non-deallocated) объектов. Для дополнительной информации о других интерфейсах на основе pool смотрите Pool Interfaces.

Синопсис

template <typename ElementType, typename UserAllocator = default_user_allocator_new_delete>
class object_pool
{
  private:
    object_pool(const object_pool &);
    void operator=(const object_pool &);

  public:
    typedef ElementType element_type;
    typedef UserAllocator user_allocator;
    typedef typename pool<UserAllocator>::size_type size_type;
    typedef typename pool<UserAllocator>::difference_type difference_type;

    object_pool();
    ~object_pool();

    element_type * malloc();
    void free(element_type * p);
    bool is_from(element_type * p) const;

    element_type * construct();
    // other construct() functions
    void destroy(element_type * p);
};

Параметры шаблона:
ElementType
Тип объекта для которого выделяется/освобождается память. Деструктор объекта не должен выбрасывать исключения.
UserAllocator
Определяет метод, используемый Pool для выделения системной памяти. По умолчанию это default_user_allocator_new_delete.
Подробнее смотрите __UserAllocator .

Пример: 

struct X { ... }; // деструктор с побочным эффектом.
void func()
{
  boost::object_pool<X> p;
  for (int i = 0; i < 10000; ++i)
  {
    X * const t = p.malloc();
    ... // Делаем что-либо с t; не тратим время на вызов free().
  }
} при завершении функции, p уничтожается, и вся выделенная под Х объекты память неявно освобождается..

Singleton_pool

Интерфейс singleton_pool в singleton_pool.hpp построен с применением Singleton и возвращает NULL при нехватке памяти. Идентичен интерфейсу pool за исключением того, что использует Singleton вместо Object.
Синопсис

template <typename Tag, unsigned RequestedSize,
    typename UserAllocator = default_user_allocator_new_delete>
struct singleton_pool
{
  public:
    typedef Tag tag;
    typedef UserAllocator user_allocator;
    typedef typename pool<UserAllocator>::size_type size_type;
    typedef typename pool<UserAllocator>::difference_type difference_type;

    static const unsigned requested_size = RequestedSize;

  private:
    static pool<size_type> p; // только для примера, реальное объявление p более сложное

    singleton_pool();

  public:
    static bool is_from(void * ptr);

    static void * malloc();
    static void * ordered_malloc();
    static void * ordered_malloc(size_type n);

    static void free(void * ptr);
    static void ordered_free(void * ptr);
    static void free(void * ptr, std::size_t n);
    static void ordered_free(void * ptr, size_type n);

    static bool release_memory();
    static bool purge_memory();
};

Примечание
Внутренний pool p  используемый статическими функциями в singleton_pool  в действительности объявлен другим способом, поэтому:

• является потокобезопасным (thread-safe) если только один поток (thread) выполняется до начала функции  main()  и после ее окончания. Все статические функции singleton_pool синхронизируют свой доступ к  p.
• гарантируется, что конструирование объекта будет завершено перед его первым использованием, поэтому простой статический объект приведенный в синопсисе является некорректной реализацией. Чтобы гарантировать данную возможность, реальная реализация выполнена значительно более сложной.

Обратите внимание, что существуют различные внутренние pool p для различных сочетаний параметров шаблона, включая специализации зависящие от реализации.

Параметры шаблона

Tag позволяет сосуществовать различным неограниченным наборам singleton pools (different unbounded sets of singleton pools). Например, аллокатор интерфейса pool использует два класса Tag для гарантии, что два различных типа аллокатора никогда не будут совместно использовать один и тот же внутренний pool.
В действительности Tag никогда не используется  singleton_pool.

RequestedSize Размер блока памяти выделяемой из системы для данного pool. Передается как параметр конструктора внутренней реализации pool. Должен быть больше чем 0.

UserAllocator Определяет метод, который внутренняя реализация pool будет использовать для выделения памяти из системы. Подробнее см. User Allocators.

Пример: 

struct MyPoolTag { };
typedef boost::singleton_pool<MyPoolTag, sizeof(int)> my_pool;
void func()
{
  for (int i = 0; i < 10000; ++i)
  {
    int * const t = my_pool::malloc();
    ... // Делаем что-либо с t; не тратим время на вызов free().
  }
  // Явно освобождаем выделенную память.
  my_pool::purge_memory();
}

pool_allocator

Интерфейсный класс  pool_allocator  реализует подход с использованием Singleton и Exceptions. Он построен на основе интерфейсного класса singleton_pool и является совместимым со стандартным аллокатором (для использования в контейнерах, например).

Введение
pool_alloc.hpp
Предлагает два шаблонных типа для быстрого и эффективного выделения памяти. Оба типа удовлетворяют требованиям к стандартному аллокатору [20.1.5] и дополнительным требованиям в [20.1.5/4] и, таким образом, могут быть использованы со стандартными или пользовательскими контейнерами.
Для подробной информации о других интерфейсных классах, основанных на pool, смотрите Интерфейсные классы Pool.

Синопсис

struct pool_allocator_tag { };
template <typename T,
    typename UserAllocator = default_user_allocator_new_delete>
class pool_allocator
{
  public:
    typedef UserAllocator user_allocator;
    typedef T value_type;
    typedef value_type * pointer;
    typedef const value_type * const_pointer;
    typedef value_type & reference;
    typedef const value_type & const_reference;
    typedef typename pool<UserAllocator>::size_type size_type;
    typedef typename pool<UserAllcoator>::difference_type difference_type;

    template <typename U>
    struct rebind
    { typedef pool_allocator<U, UserAllocator> other; };

  public:
    pool_allocator();
    pool_allocator(const pool_allocator &);
    // The following is not explicit, mimicking std::allocator [20.4.1]
    template <typename U>
    pool_allocator(const pool_allocator<U, UserAllocator> &);
    pool_allocator & operator=(const pool_allocator &);
    ~pool_allocator();

    static pointer address(reference r);
    static const_pointer address(const_reference s);
    static size_type max_size();
    static void construct(pointer ptr, const value_type & t);
    static void destroy(pointer ptr);

    bool operator==(const pool_allocator &) const;
    bool operator!=(const pool_allocator &) const;

    static pointer allocate(size_type n);
    static pointer allocate(size_type n, pointer);
    static void deallocate(pointer ptr, size_type n);
};

struct fast_pool_allocator_tag { };

template <typename T
    typename UserAllocator = default_user_allocator_new_delete>
class fast_pool_allocator
{
  public:
    typedef UserAllocator user_allocator;
    typedef T value_type;
    typedef value_type * pointer;
    typedef const value_type * const_pointer;
    typedef value_type & reference;
    typedef const value_type & const_reference;
    typedef typename pool<UserAllocator>::size_type size_type;
    typedef typename pool<UserAllocator>::difference_type difference_type;

    template <typename U>
    struct rebind
    { typedef fast_pool_allocator<U, UserAllocator> other; };

  public:
    fast_pool_allocator();
    fast_pool_allocator(const fast_pool_allocator &);
    // The following is not explicit, mimicking std::allocator [20.4.1]
    template <typename U>
    fast_pool_allocator(const fast_pool_allocator<U, UserAllocator> &);
    fast_pool_allocator & operator=(const fast_pool_allocator &);
    ~fast_pool_allocator();

    static pointer address(reference r);
    static const_pointer address(const_reference s);
    static size_type max_size();
    static void construct(pointer ptr, const value_type & t);
    static void destroy(pointer ptr);

    bool operator==(const fast_pool_allocator &) const;
    bool operator!=(const fast_pool_allocator &) const;

    static pointer allocate(size_type n);
    static pointer allocate(size_type n, pointer);
    static void deallocate(pointer ptr, size_type n);

    static pointer allocate();
    static void deallocate(pointer ptr);
};

Параметры шаблона

T первый параметр шаблона представляет собой тип объекта, для которого выделяется/освобождается память.
UserAllocator определяет метод, используемый внутренней реализацией для выделения памяти из системы. Подробнее смотрите User Allocators.
Пример:

void func()
{
  std::vector<int, boost::pool_allocator<int> > v;
  for (int i = 0; i < 10000; ++i)
    v.push_back(13);
} // Завершение функции НЕ освобождает ранее выделенную память (потому что Singleton создается до
  // начала выполнения программы и уничтожается перед выходом из программы)
  // Вы должны вызвать 
  //  boost::singleton_pool<boost::pool_allocator_tag, sizeof(int)>::release_memory();
  // чтобы принудительно освободить системную память

Подробнее о Pool

Идеи, лежащие в основе pool

Динамическое выделение памяти

Динамическое выделение памяти является фундаментальной частью большинства компьютерных систем примерно с начала шестидесятых годов 20 века. 1
Динамическое выделение памяти используют все. Если вы хоть раз вызывали malloc или new, значит вы тоже использовали динамическое выделение памяти. Большинство программистов склонны рассматривать кучу как абстрактный черный ящик: мы просим у нее память, и она как-то там (не важно как) создает ее для нас. Но иногда у нас возникают проблемы, потому что куча — вовсе не черный ящик и на самом деле иногда важно, откуда куча берет память.
Во-первых, куча не бесконечна. Даже на больших системах (т. е. не встраиваемых) с огромным количеством виртуальной памяти существует предел. Все знают о физическом пределе памяти, но существует более тонкий, «виртуальный» предел, предел, после которого ваша программа (или система в целом) замедляется из-за использования виртуальной памяти. Ваша программа намного ближе к данному виртуальному пределу, чем к физическому, особенно на многозадачных системах. Поэтому, когда вы запускаете программу на большой системе, неплохо, если ваша программа использует самый минимум ресурсов и освобождает их как можно быстрее. Если же вы запускаете программу на встраиваемой системе, обычно у вас вообще нет памяти разбрасываться и нужно тщательно контролировать ее расход.
Во-вторых, куча имеет сложное внутреннее устройство. Она выполняет запросы на выделение различных типов памяти, разного размера и должна делать это быстро. Обычный подход к управлению памятью заключается в разбиении памяти на порции и хранении информации о данных порциях в виде упорядоченного по размеру дерева или списка. Добавьте сюда такие параметры как расположение в глобальной/локальной памяти (locality), расчетное время жизни (estimating life time) и куча станет очень сложной. Настолько сложной, что просто не существует исчерпывающего ответа как лучше всего динамически выделять память. Диаграмма ниже иллюстрирует работу большинства менеджеров памяти: для каждого блока памяти (chunck) они используют часть памяти для хранения внутреннего дерева или списка. Даже когда блок памяти выделен программе, менеджер памяти вынужден хранить часть информации о нем — обычно это размер. Тогда при освобождении блока памяти менеджер легко может определить его размер.

Динамическое выделение памяти часто неэффективно

Благодаря своей сложности динамическое выделение памяти зачастую оказывается неэффективным в плане быстродействия или расхода памяти. Большинство алгоритмов динамического выделения памяти хранят некоторую информацию о каждом блоке памяти, будь то размер этого блока или какая-либо другая информация вроде позиции данного блока во внутреннем дереве или списке (хранящих информацию о всех блокам памяти). Обычно такое поле в заголовке блока памяти занимает до одного машинного слова. Явный недостаток такого подхода проявляется при динамическом выделении маленьких объектов. Например, если выделять память под переменные типа int, такой алгоритм выделит памяти в два раза больше, чем нужно для хранения самих переменных - одно машинное слово под int и еще одно машинное слово под под заголовок, что приведет к 50% росту расхода памяти. Конечно, это самый худший случай, но современные программы все чаще работают с небольшими объектам в куче и это делает проблему все более острой. Вильсон (Wilson) и другие утверждают, что перерасход памяти в среднем составляет от 10 до 12 процентов a reference has to be here. Перерасход возрастает по мере того, как все больше программ используют маленькие объекты, что делает программы ближе к виртуальному лимиту памяти.

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

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

Хранилище с простым разбиением (Simple Segregated Storage)

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

ссылки нет и в оригинале, сорри

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

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

Также хранилище с простым разбиением является чрезвычайно быстрым. В простейшем случае, выделение памяти представляет собой удаление первого свободного блока из списка свободных блоков, что имеет сложность O(1). Если список свободных блоков пуст (т.е. в Pool закончилась предварительно выделенная системой память), другой блок памяти должен быть выделен системой и разбит на блоки фиксированного размера. В этом случае сложность составит в среднем O(1). Освобождение памяти может быть таким же простым как вставка в начало списка со сложностью O(1). Однако более сложные варианты применения хранилища с простым разбиением могут потребовать применения сортированного списка свободных блоков, в этом случае сложность освобождения памяти составляет O(N).

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

Гарантированное выравнивание - Как мы гарантируем выравниваение переносимым способом (Guaranteeing Alignment - How we guarantee alignment portably.)

Терминология

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

Обзор

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

Доказательство концепции: Гарантированное выравнивание(Proof of Concept: Guaranteeing Alignment)

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

Утверждение 1: Массив не может иметь заполнения(padding).

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

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

Поэтому, массивы не могут содержать заполнение, но элементы массивов могут.

Утверждение 2: Любой блок памяти, выделенный как массив символов с помощью оператора new[] (здесь и далее - блок), имеет правильное выравнивание для любого объекта такого же или меньшего размера.

Вытекает из:

• [3.7.3.1/2] (Основные концепции::Продолжительность хранения::Продолжительность динамического хранения::Функции выделения) "... Возвращаемый указатель должен быть подходящим образом выравнен таким образом, чтобы мог быть преобразован в указатель на любой объект завершенного типа и затем использован для доступа к объекту или массиву в выделенном хранилище ..."
  
• [5.3.4/10] (Выражения::Унарные выражения::New) "... Для массивов типов char и unsigned char разница между результатом new-выражения и адресом, возвращаемым функцией выделения должна быть целым, кратным наиболее строгим требованиям к выравниванию (3.9) объекта любого типа, чей размер не превышает размер создаваемого массива. [Примечание: В следствии того, что ожидается, что функции выделения возвращают указатели на хранилище, имеющее необходимое выравнивание для объектов любого типа, это ограничение потерь памяти при выделении массивов разрешает использование распространенной идиомы выделения символьных массивов, которые используются для размещения объектов других типов.]"

Возьмем воображаемый объект типа Element, размер которого кратен размеру какого-либо настоящего объекта; принимаем, что sizeof(Element) > POD_size

Обратите внимание, что существование объекта такого размера допустимо. Один объект такого размера представляет собой массив "настоящих" объектов.

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

Заключение 1: Блок правильно выравнен для массива из Elements

Это следует из Утверждений 1 и 2, и следующей цитаты:

[3.9/9] (Основные концепции::Типы) "Объектный тип является (возможно cv-qualified) типом, не являющимся функциональным типом, ссылочным типом, или типом void."

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

Заключение 2: Для любого указателя p и целого i, если p правильно выравнен в соответствии с типом, на который он указывает, то p + i (при правильном определении) также правильно выравнено для этого типа; другими словами, если массив имеет правильное выравнивание, то каждый элемент в этом массиве имеет правильное выравнивание

Нет цитат из Стандарта прямо подтверждающих данное утверждение, но это соответствует общей концепции понятия "выравнивание".

Обратите внимание, что условие для p + i быть правильно определенным (be well-defined) обозначено в [5.7/5]. Мы не цитируем это здесь, а только обращаем внимание на то, что (p + i) является правильно определенным если p и p + i оба указывают в один и тот же массив или на следующий элемент за массивом(?) (both point into or one past the same array).

Пусть: sizeof(Element) является наименьшим общим множителем размеров нескольких реальных объектов (T1, T2, T3, ...)

Пусть: блок будет указателем на блок памяти, pe будет(Element *) блоком, и pn будет (Tn *) блок

Заключение 3: Для каждого целого i, такого что pe + i является правильно определенным, тогда для каждого n, существует целое jn такое что pn + jn является правильно определенным и ссылается на тот же адрес памяти что и pe + i

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

Теорема: Для каждого целого i, такого что pe + i является правильно определенным, адрес (pe + i) является правильно выравненным для каждого типа Tn

Так как pe + i правильно определено, тогда в соответствии с Заключением 3, pn + jn также правильно определено и имеет правильно выравнивание в соответствии с Утверждением 2 и Заключениями 1 and 2.

Применение Теоремы

Доказательство выше покрывает всю область требований к выравниванию для выделения памяти. Реализация использует следующие размеры объекта:

Запрошенный размер объекта (requested_size); это размер памяти запрошенный пользователем void* (указатель на void); нужен для размещения списка свободных блоков size_type; мы храним размер следующего блока в каждом блоке Также каждый блок содержит указатель на следующий блок; он хранится как указатель на void и приводится к нужному типу при необходимости, для упрощения требований к выравниванию.

Следовательно, alloc_size является наибольшим размеров из указанных выше, округленный, чтобы бы быть кратным всех трем размерам. Это гарантирует выравнивание при условии, что выравнивание является степень двух, что выполняется на всех известных платформах.

Взгляд на блок памяти

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

Каждая из этих частей может содержать заполнение для гарантирования правильного выравнивания каждой из этих частей. Размер первой части равен 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 == 8 и sizeof(void *) == sizeof(size_type) == 4