Аллокаторы в C++. Или свой распределитель памяти.

Введение

"Allocator" - переводится как "распределитель" - попросту говоря аллокатор - это действующая по определённой логике высокоуровневая прослойка между запросами памяти под динамические объекты и стандартными сервисами выделения памяти (new/malloc или другими (например запросами напрямую к ядру о.с.)), конечно же прослойка берет на себя и вопросы управлением отдачей уже ненужной памяти назад. По другому можно сказать - что аллокатор это реализация стратегии управления памятью.

Использование аллокаторов позволяет добиться существенного повышения производительности в работе с динамическими объектами (особенно с объектами-контейнерами). Если в коде много работы по созданию/уничтожению динамических объектов, и нет никакой стратегии управления памятью, а только использование стандартных сервисов new/malloc - то весьма вероятно, что не смотря на то, что программа написанна на Си++ (или даже чистом Си) - она окажется более медленной чем схожая программа написанная на Java или C#.

Естественно что епархия аллокаторов - в основном объекты-контейнеры, т.к. именно там остро проявляется необходимость в некоторой стратегии, но так же можно использовать и для одиночных динамических объектов, на протяжении всего времени жизни программы размещая эти объекты в заранее выделенном бассейне "pool" памяти. Кстати обычно pool переводят как пул, но бассейн вроде звучит - так что бассейне памяти. Так же обычно pool аллокаторы - понятие, применяемое к определенной категории аллокаторов, работающих с объектами одного размера (такой тип будет описан ниже). Использование стратегии будет не выгодно по памяти, но очень выгодно по времени выполнения.

Фрагментация памяти

При этом если предполагается использование программы в режиме 24x7, в аллокаторе должно быть предусмотрен тот или иной способ борьбы с фрагментацией памяти. Например в pool аллокаторах дефрагментация не страшна, в аллокаторах для разноразмерных объектов нужно применять различные ухищрения, или же по простому, в определенное время полностью освобождать выделенное и выделять заново (это самое простое), более сложные способы борьбы с фрагметацией, достаточно сложно реализовать так, чтобы они не ухудшали производительность, по сравнению с полной переаллокацией. Кстати фрагментация памяти возможна и не только внутри памяти, управляемой аллокатором, но и в куче процесса. Дело в том что new это обертка над malloc, а malloc в свою очередь обертка над запросами к ядру операционной системы по выделению памяти. Ядро ос само следит за фрагментацией физической памяти, и когда нужно производит дефрагментацию, используя для этого разные алгоритмы, в Unix чаще всего применяется "аллокатор Макьюсика-Карлеса" (Mckusick-Karels Allocator). Процессу же ядро предоставляет область виртуальной памяти, адреса из которой транслируются, по известным лишь ядру связям на адреса физической памяти. Т.е. в момент работы процесса значение, хранимое, с точки зрения процесса в одном и том же адресе, может плавать по физическим ячейкам памяти.

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

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

Java и C# vs C++

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

Например в Java, все строки неизменны, при append(там этот метод называется иначе, но мы говорим на языке Си++), например, результатом будет не измененная строка, вызвавшая append - а копия строки. Из-за такого решения Java программы активно работающие со строками - разрастаются в ОЗУ до неприличия, но зато значительно меньшая потребность в аллокациях/деаллокациях делают Java строки быстрее чем использованные "из коробки"std::string. Впрочем если перейти с обычного использования Си++ на эффективное - то уже std::string будет быстрее Java строк, причем не потребляя до неприличия много памяти.

* - Возможно кто-то прочитав о славящихся низким быстродействием Java и C# впадёт в когнитивный диссонанс, ведь интернет ему говорил другое. Но нужно не доверять а проверять. И прежде всего если в бенчмарке заявляется о том что Java или C# быстрее - посмотреть адрес сайта - если это Оракл в первом случае, и Майкрософт во втором, ну вы понимаете... Маркетинг, реклама, все дела. Если же это не официальный сайт - нужно посмотреть на стилистику, обычно автору тяжело скрыть свой субъективизм и цель, показать лучше тот язык, который ему нравится. Возможно в моём тексте тоже просматривается субъективизм, но тем не менее честные эксперименты и прямые сслыки, уверен превращают этот субъективизм в объективизм.

Дальше будет много воды, которая уже никак не связана с темой аллокаторов, но решил поделиться, то что между тегом <вода> - можно пропустить.

<вода================================>
Рассмотрим конкретные примеры вранья:

Oracle. Плохо то что из-за раскрученности этот материал будет в топе поиска от Гугл. В итоге огромное покрытие дезинформацией. Ну ведь очень крутая и именитая контора, типа следит за своими словами. Но это бизнес. В результате на бенче от оракла джава практически везде побеждает, лишь в некоторых тестах незначительно отстаёт. На самом деле всё не так, и хорошо знающие язык Си++ увидят то что в коде тестов Оракл подыгрывает себе, причем в наглую, делая неоптимальный код в лоб или же и того хуже, выбирая более медленные методы или вызовы лишних (для решения задачи) функций - в данном случае, предполагаю, намеренно. А вот правдивая статья с теми же тестами, но с убранными препонами, бережно расстановленными Ораклом (которую очень тяжело найти в гугле, ведь это не корпорация с мировым именем, а какой-то польский сайтик).

Вот тут уже правильный результат (график - секунды)

Рис.1. Java vs C++ Benchmark.
Небольшие замечания - хеш2, здесь Си++ проиграл, т.к. статья писалась до появления 11го стандарта, в 11м же используется более совершенная хешфункция и в данном тесте, в современных условиях ++ обгоняет Java, не поленился проверить это на своем компьютере.

К плюсу Javа можно отнести скорость вызова методов. Но и тут стоит сказать что в тестах для Си++ использовались виртуальные методы. Если бы использовались не виртуальные - Си++ был бы в разы быстрее. Виртуальные же они потому что, по умолчанию, все методы в Джава виртуальны, поэтому и в ++ для равенства условий они тоже виртуальны. Почему в Джава виртуальные методы вызываются быстрее? Потому что в Си++ для вызова виртуального метода нужно перейти по нескольким указателям в случайное место памяти + сделать накрутку/раскрутку стека. Среда исполнения Джава - тоже накручивает стек, но это делает среда, так же за счет своей высокоуровневости она может производить некоторые оптимизации - например часто вызываемые методы переместить ближе по адресам (про оптимизацию - это мои догадки), чего не может быть в статически компилируемой программе. Пожалуй это единственное где не компилируемые в бинарный код языки могут быть быстрее. Так же некоторые оптимизации могут сократить время рекурсивных вызовов, но и современные Си++ и Си компиляторы научились делать рекурсивный стек вызовов очень быстрым, настолько - что быстрее вряд ли кто есть.

Что касается C#, лично не запускал, но судя по нормальным источникам (и еще один), так же проигрывает C++, но меньше чем Java.

Вывод Если где-либо описано сравнение языков - прежде всего нужно, убедиться что в источнике нет субъективизма. Косвенно из этого следует - что источник не должен быть Oracle или Microsoft, т.к. они естественно будут выставлять свои продукты как лучшее из лучших. За Си++ не стоят корпорации, и о нём не нужно писать, что это самый супер-пупер язык, потому что это дефакто и так всем известно, что именно этот язык является самым поппулярным после Си, когда дело переходит из процедурного в объектно ориентированное программирование. У кого-то опять диссонанс, ведь везде трубят что Java. Ну конечно же Java, ведь любой школьник, кому не лень пишет что-то для андроида, и выкладывает это на гитхаб, предполагаю оттуда и льется львинная доля статистики. Если же взглянуть на серьезные проекты - то картина иная.

Ну и самое главное - в бенчах обязательно должны быть ссылки на исходники тестов. Напоследок подтемки пара ссылок:
Очень полный бенчмарк, правда немного не свежий.
А здесь всегда свежие результаты, очень часто и stackoverflow вопрошающих про производительность отправляют именно на этот ресурс.
</вода================================>

Стратегия и общепринятый интерфейс аллокатора

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

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

Если речь касается стандартных контейнеров, то ускорить работу с памятью можно не обязательно реализуя свой аллокатор в виде специального класса. В простых случаях будет достаточно воспользоваться методом reserve. Этого вполне хватит чтобы обогнать по производительности строки Java. Но знать наперед максимально необходимый размер сложно, особенно когда строковых объектов предполагается много и в разных местах прогараммы. Тут не обойтись без реализации специального класса.

А так как этот класс планируется использовать для размещения стандартных контейнеров, то он должен следовать определенным соглашениям STL. А именно должен обязательно содержать такие методы:

T* allocate( std::size_t n ); - выделяет память.
void deallocate( T* p, std::size_t n ) - освобождает или помечает свободной память.
void construct( U* p, Args&&... args ) - конструирует объект по адресу.
void destroy( U* p ) - уничтожает объект по адресу.

А так же пару внешних операторов == и !=.
Так же есть, необязательный метод получения максимально возможного количества единиц хранения нужного типа. На словах слишком мудрёно. Проще показать код:

  1. size_type max_size() noexcept { return size_t(-1) / sizeof(_Tp) };

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

  1. // данный класс выделяет новую память из кучи
  2. // и помечает ненужные блоки памяти как свободные
  3. // возврат памяти обратно ОС не происходит
  4. class Arena
  5. {
  6. public:
  7. Arena() = default;
  8. ~Arena()
  9. {
  10. assert(m_allocations == 0);
  11. }
  12.  
  13. void* allocate(std::size_t n)
  14. {
  15. if (n > m_available)
  16. {
  17. m_chunks.emplace_back(100500);
  18. m_available = m_chunks.back().size();
  19. m_memory = &m_chunks.back().front();
  20. }
  21.  
  22. auto mem = m_memory;
  23. m_available -= n;
  24. m_memory += n;
  25. ++m_allocations;
  26. return mem;
  27. }
  28.  
  29. // фрагметация при удалении не учитывается
  30. void deallocate(void* p, std::size_t n) {
  31. --m_allocations;
  32. auto mem = (unsigned char*)p;
  33.  
  34. // освобожденная память будет доступна для использования,
  35. // только тогда, когда освобождаемый блок - граничит
  36. // со свободной памятью.
  37. if (mem + n == m_memory)
  38. {
  39. m_memory = mem;
  40. m_available += n;
  41. }
  42. }
  43.  
  44. private:
  45. std::deque<std::vector<unsigned char>> m_chunks;
  46. std::size_t m_available = 0;
  47. unsigned char* m_memory = nullptr;
  48. int m_allocations = 0;
  49. };
  50.  
  51. template <class T>
  52. struct ArenaAllocator
  53. {
  54. // данный синоним должен быть в классе ArenaAllocator для инстанцирования от ArenaAllocator класса
  55. // std::allocator_traits, причем его инстанция будет находиться в отношении композиции в ArenaAllocator :)
  56. using value_type = T;
  57.  
  58. // не нужный синоним, но оставил его, т.к. он был в первоисточнике
  59. using Traits = std::allocator_traits<ArenaAllocator<T>>;
  60.  
  61. // конструкторы по умолчанию и копирования обязательно должны быть для совместимости с STL
  62. ArenaAllocator() = default;
  63. template<class U> ArenaAllocator(const ArenaAllocator<U>& other) : m_arena(other.m_arena) { }
  64. // а это уже вольная реализация
  65. explicit ArenaAllocator(Arena& arena): m_arena(&arena) { }
  66. ~ArenaAllocator() { }
  67.  
  68. // libstdc++ требует следующие определения
  69. using size_type = typename std::allocator<T>::size_type;
  70. using difference_type = typename std::allocator<T>::difference_type;
  71. using pointer = typename std::allocator<T>::pointer;
  72. using const_pointer = typename std::allocator<T>::const_pointer;
  73. using reference = typename std::allocator<T>::reference;
  74. using const_reference = typename std::allocator<T>::const_reference;
  75.  
  76.  
  77. // описанные ниже методы и внеклассовые операторы сравнения - требуются для работы с аллокатором
  78. // стандартных контейнеров
  79. T* allocate(std::size_t n) { return (T*)m_arena->allocate(n * sizeof(T)); }
  80. void deallocate(T* p, std::size_t n) { m_arena->deallocate(p, n * sizeof(T)); }
  81.  
  82. // вызовет размещающий new и передаст конструктору объекта столько параметров, сколько необходимо.
  83. template<class U, class... Args> void construct(U* p, Args&&... args) { std::allocator<T>().construct(p, std::forward<Args>(args)...); }
  84. // обёртка, которая вызывае p->~U()
  85. template<class U> void destroy(U* p) { std::allocator<T>().destroy(p); }
  86.  
  87. // Современные реализациях STL требуеют наличие такой структуры
  88. // как обёртки аналогичной traits технике.
  89. template<class U> struct rebind { using other = ArenaAllocator<U>; };
  90.  
  91. Arena* m_arena = nullptr;
  92. };
  93.  
  94. template<class T, class U> bool operator==(const ArenaAllocator<T>& lhs, const ArenaAllocator<U>& rhs) { return lhs.m_arena == rhs.m_arena; }
  95. template<class T, class U> bool operator!=(const ArenaAllocator<T>& lhs, const ArenaAllocator<U>& rhs) { return !(lhs == rhs); }

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

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

Но если же программист решил пользоваться выделениями аллокатора в не контейнерах

  1. char * vals1 = arena_allocator.allocate(256);
  2. char * vals2 = arena_allocator.allocate(256);
  3. char * vals3 = arena_allocator.allocate(256);
  4. ...
  5. arena_allocator.deallocate(vals1,256);
  6. arena_allocator.deallocate(vals2,256);
  7. arena_allocator.deallocate(vals3,256);

То в данном случае блок памяти будет присоединен к свободным только от vals3, остальные блоки перестанут быть доступны. Понятно, что если такое ручное добавление и очищение будет в конце всех автоматических переменных - то ни один блок из автоматических переменных не будет очищен, т.к. условие mem + n == m_memory "поплывёт".

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

Такая утечка происходит в самом примере от автора.

  1. a_vector<X> v_x(42, arena_allocator);
  2. a_vector<a_string> v_str({s_empty, s_123}, arena_allocator);
  3. a_vector<a_string> v_str_copy(v_str, arena_allocator);
  4. a_deque<int> d_int({1, 2, 3}, arena_allocator);
  5. a_list<int> l_int({1, 2, 3}, arena_allocator); // отсюда поплывёт.
  6. a_set<int> s_int({1, 2, 3}, std::less<int>{}, arena_allocator);
  7. a_map<a_string, int> m_str_int(arena_allocator);
  8. a_unordered_set<int> us_int(arena_allocator);

Почему поплывёт? Рассмотрим например строку из того же примера

  1. a_vector<int> v_int({1, 2, 3}, arena_allocator);

Если вставить в метод Allocator::allocate вывод в поток запрашиваемого размера (n), а ниже определения v_int вывести в поток размер (в элементах) вектора - v_int.size() - то увидим что произошла всего одна аллокация, необходимая для записи 3 элементов вектора 3*(sizeof(int)).

Схожее конструирование std::list даст то, что не для группы разом, а для каждого элемента будет вызван метод Allocator::allocate. Причем для каждого элемента в 64битной среде будет выделено 2*sizeof(pointer)+выравнивание+sizeof(int). Таким образом, если у нас 3 элемента в списке - то будет 3 запроса. Да, в итоге Арена защитит от обращения к выделению новой памяти процессу и просто выдаст заранее выделенный блок (тут всё хорошо). Но суть в том, что в виду свойств классических структур данных работа с вектором и листом будет проходить так:

std::vector
1. аллокация происходит единым блоком, для всего множества элеметов
2. начиная от первого до последнего происходит конструирование объектов.
при вызове деструктора вектора:
1. начиная от первого до последнего происходит уничтожение объектов.
2. деаллокация происходит единым блоком.

Поэтому вектор ничего не нарушает в работе данной реализации Арены.

std::list
1. запрос на аллокацию происходит для каждого отдельного элеметна
2. сразу же после аллокации идет вызов конструирования объекта и так от первого до последнего
при вызове деструктора списка:
1. начиная от первого до последнего происходит одновременный вызов деструктора (из destroy) и освобождения блока (deallocate).

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

Что же остальные (ассоциативные) контейнеры из примера? Ведь они тоже работают подобно листу - в них невозможно выделить и уничтожить память для всех включаемых данных одним блоком (вообще конечно можно для конструктора, но не имеет смысла, исходя из определений этих классических структур). Главная разница же в том, что в std::set и std::map, в отличие от std::list, где память освобождается строго прямо порядку выделения, память освобождается строго в обратном порядке выделения - поэтому здесь всё хорошо для рассматриваемой реализации.

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

И в заключении обсуждения реализации из статьи - приведу забавную закономерность (она не имеет никакого отношения ни к чему здесь, просто если такое помнить, будет лучше, мне :) )

  1. class X {
  2. public:
  3. X():array(new char[1024]){}
  4. ~X(){ delete [] array; }
  5. // для формы вызова #1 обязательно наличие конструктора копирования,
  6. // иначе, из-за штатного произойдет double free corruption
  7. X(const X& rhs)
  8. {
  9. if (array) delete [] array;
  10. array = new char[1024];
  11. memcpy(this->array, rhs.array, 1024);
  12. }
  13. private:
  14. char * array;
  15. };
  16. ...
  17. // #1
  18. a_vector<X> v_x(42, X(), arena_allocator);
  19.  
  20. // #2 для такой формы, конструктор копирования не обязателен,
  21. // т.к. для объектов будет вызываться умолчальный конструктор.
  22. a_vector<X> v_x2(42, arena_allocator);

код целиком можно посмотреть здесь.

Вернёмся к рассмотрению стандартного аллокатора из STL.

  1. template <class T> class allocator
  2. {
  3. public:
  4. typedef T value_type;
  5. typedef size_t size_type;
  6. typedef ptrdiff_t difference_type;
  7. typedef value_type* pointer;
  8. typedef const value_type* const_pointer
  9. typedef value_type* reference;
  10. typedef const value_type* const_reference;
  11.  
  12. typedef size_t size_type;
  13.  
  14. // Выделяем память для _Count элементов
  15. // типа value_type
  16. pointer allocate(size_type _Count)
  17. {
  18. void *_Ptr = 0;
  19.  
  20. // Если ничего не запросили, то ничего и не делаем
  21. if (_Count == 0)
  22. ;
  23. else if ( ((size_t)(-1) / sizeof (value_type) < _Count)
  24. || (_Ptr = ::operator new(_Count * sizeof (value_type))) == 0 )
  25. {
  26. throw bad_alloc(); // Выделение памяти не удалось
  27. }
  28. return ((pointer)_Ptr);
  29. }
  30.  
  31. void deallocate(pointer _Ptr, size_type)
  32. {
  33. ::operator delete(_Ptr); // Освобождение памяти
  34. }
  35.  
  36. // А вот и те методы, к которым обращалась, упомянутая
  37. // выше Arena
  38. template<typename _Up, typename... _Args>
  39. void construct ( _Up* __p, _Args&&... __args )
  40. { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
  41.  
  42. template<typename _Up>
  43. void destroy(_Up* __p) { __p->~_Up(); }
  44.  
  45. size_type max_size() noexcept { return size_t(-1) / sizeof(_Tp) };
  46.  
  47. // Есть и другие методы, но они не так интересны, подробнее можно
  48. // посмотреть например здесь /usr/include/c++/4.9/ext/new_allocator.h
  49. };

Кстати рекомендую прочесть эту статью (зеркало) статью, в ней описывается стандартный аллокатор, и то как эффективно работать с контейнерами, на примере std::vector.

В статье есть небольшая опечатка:

  1. if (max_size() - _Capacity / 2 < _Capacity) ----имелось ввиду---> if (max_size() - _Capacity / 2 > _Capacity)

Заключение раздела

  • Все стандартные контейнеры по-умолчанию используют std::allocator, по сути являющийся обёрткой над new/delete.
  • Простейшим способом значительно ускорить работу стандартных контейнеров является выделение огромных блоков памяти в классе-аллокаторе (выделить заранее не всегда возможно (например не известен итоговый размер для reserve или же reserve вообще нет в данном контейнере)).
  • Класс аллокатор должен быть снабжен указанным выше интерфейсом (нужными методами) для работы в сочетании со стандартными контейнерами (если же это не предполагается, то итерфейс - вольный).
  • Существуют различные техники, от простейшей (что мы рассмотрели выше) до более сложных, которые рассмотрим ниже. Аллокатор может являться сложной системой с несколькими стратегиями внутри себя, например, для маллых объектов можно выделять память на стеке (или же использовать автоматический массив переменной длинны) - что в разы ускорит и само выделение, и избавит от необходимости финального возвращения участка памяти в операционную систему.

Продвинутые техники

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

Разбирать будем аллокатор, реализация которого частично приведена в этой статье. Интересен так же подход, в примерах выше аллокатор включается в шаблонные классы в отношении композиции, в статье же от него наследуются. Сути это не меняет, кроме того что описанный в статье с хабра аллокатор - уникальный для каждого объекта, а первый рассмотренный, может быть как уникальным, так и общим (рассматривался общий). Так же в статье описываются Microsoft методы работы с Windows виртуальной памятью, как отобразить это в мир Unix - описано здесь.

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

  1. inline size_t align(size_t x, size_t a) { return ((x-1) | (a-1)) + 1; }

Она использует свойство логичекого Или:

7 ...0111 7 ...00111
3 ...0011 15 ...01111
7 ...0111 15 ...01111

Т.е. для любого входящего параметра (размер которых есть четные числа какой-то из степеней 2-ки ), если сократить на единицу будет представлено в битах только единицами. А тут битовая OR действует на подобие (a>b)?a:b. Единицу же возвращают вконце. В итоге для всех типов, размер которых меньше размера указателя - будет вычислено выравнивание по размеру указателя (а это очень важно, и мы поймем почему - ниже), а для типов, размер которых больше указателя - будет вычислено выравнивание по размеру этого типа. Т.е. такой простой вычислительной функцией соблюдается известное требование к выравниванию составных типов.

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

Класс реализующий бассейн выглядит так:

  1. #define PAGESIZE 65536
  2. template <size_t PageSize = PAGESIZE>
  3. class PagePool
  4. {
  5. public:
  6. // архитектурно зависимая чать кода, инкапсулирована в функции
  7. // _Alloc и _Free
  8. void* GetPage()
  9. {
  10. void* page = _Alloc(PageSize);
  11. pages.push_back(page);
  12. return page;
  13. }
  14.  
  15. ~PagePool()
  16. {
  17. for (vector<void*>::iterator i = pages.begin(); i != pages.end(); ++i)
  18. {
  19. _Free(*i, PAGESIZE);
  20. }
  21. }
  22. private:
  23. vector<void*> pages;
  24. };

В нём всё просто, перейдем к его клиенту, классцу BlockPool, своего рода - управляющего бассейном.

  1. template <class T, size_t PageSize = PAGESIZE, size_t Alignment = sizeof(void*)>
  2. class BlockPool: public PagePool<PageSize>
  3. {
  4. public:
  5. BlockPool(): head(nullptr)
  6. {
  7. BlockSize = align(sizeof(T), Alignment);
  8. count = PageSize / BlockSize;
  9. }
  10.  
  11. void* AllocBlock()
  12. {
  13. if (!head) FormatNewPage();
  14. void* tmp = head;
  15. head = *(void**)head;
  16. return tmp;
  17. }
  18.  
  19. void FreeBlock(void* tmp)
  20. {
  21. *(void**)tmp = head;
  22. head = tmp;
  23. }
  24.  
  25. private:
  26. void FormatNewPage()
  27. {
  28. void* tmp = GetPage();
  29. head = tmp;
  30. for (size_t i = 0; i < count-1; i++)
  31. {
  32. void* next = (char*)tmp + BlockSize;
  33. *(void**)tmp = next;
  34. tmp = next;
  35. }
  36. *(void**)tmp = NULL;
  37. }
  38.  
  39. size_t BlockSize;
  40. size_t count;
  41. void* head;
  42. using PagePool<PageSize>::GetPage;
  43. };

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

Рассмотрим как это работает подробно.

FormatNewPage

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

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

  1. void* next = (char*)tmp + BlockSize;

Далее идут возможно самые необычный строчки данной статьи

  1. // так идёт преобразование типа к указателю на указатель, а потом разыменование. А зачем?
  2. // Затем, что после такого разыменования, сюда *(void**)tmp= - можно будет записать адрес
  3. // но не в указатель tmp - а в область памяти, на которую он указывает. Understand? Ok ahead.
  4. *(void**)tmp = next;
  5. // ну а тут всё просто, переназначаем указатель tmp указывать на начало блока в который можно
  6. // записать значение следующего элемента типа инсатнцирования аллокатора.
  7. tmp = next;

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

AllocBlock

До распределения в области памяти будут храниться адреса смежных блоков, в формате нетипового укзателя (void*).

Во время запроса на выделение - голова переместиться через присвоение самой себе но через механизм преобразования типов
head = *(void**)head, описанный выше т.е. адрес возьмется из блока памяти на который указывает head. Таким образом значение указателя head будет указавать на следующий_нужный адрес.

Адрес же, на который до этого указывал head отдаётся клиенту аллокатора. В данном случае клиент - это конструктор односвязного списка, конструрующй объект типа Node. Компилятор на место вызова BlockAlloc::operator new подставит вызов конструктора в возвращенный методом адрес.

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

Во время же освобождения памяти, сначала вызовется деструктор (вызов которого компилятор вставил автоматически, перед BlockAlloc::operator delete, для Node он окажется деструктром по-умолчанию, т.е. ничего не делающим), затем вызовется метод FreeBlock, который в переданный ему адрес (где в данный момент хранится уничтожаемый объект) запишет адрес "первого" свободного блока. А переменную, указующую на этот адрес, переназначит на адрес, в котором только что был объект, но уже адрес бывшей головы. Undertand?

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

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

Класс самого аллокатора

  1. template<class T> class BlockAlloc
  2. {
  3. public:
  4. static void* operator new(size_t s)
  5. {
  6. if (s != sizeof(T))
  7. {
  8. return ::operator new(s);
  9. }
  10. return pool.AllocBlock();
  11. }
  12.  
  13. static void operator delete(void* m, size_t s)
  14. {
  15. if (s != sizeof(T))
  16. {
  17. ::operator delete(m);
  18. } else if (m != NULL)
  19. {
  20. pool.FreeBlock(m);
  21. }
  22. }
  23.  
  24. private:
  25. static BlockPool<T> pool;
  26. };
  27. template<class T> BlockPool<T> BlockAlloc<T>::pool;

Здесь нет ничего примечательного, кроме возможно момента с проверкой размеров. А так же с не так часто встречаемой формой оператора delete, в которую компилятор автоматически подставляет размер (взятый из типа объекта-указателя), кстати можно было бы использовать и обычную форму delete(void*), но тогда мы бы лишились возможности сверить размер блока с размером типа.

Дело в том что память форматируется под конкретный размер. Если от Node будет сделан класс наследник, то он унаследует и аллокатор, и если класс наследник будет иметь иной размер - то стратегия реализованная в аллокаторе уже не применима, и он переключается в режим обычных разовых выделений. К наследникам же так же можно "примешать" аллокатор, в таком случае в наследнике аллокатор базового класса перекроется аллокатором производного.

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

Композиция единственного объекта_аллокатора в классе_контейнере, была бы предпочтительнее. Для адаптации данного аллокатора к композиции можно - пулы_векторы хранить в словаре, в итоге получим контейнер пулов аллокатора. BlockSize же будет ключем данного словаря, а пул_вектор и "голову" потребуется инкапсулирвать в структуру, экземпляры которой будут служить значениями словаря.

Отнаследуя класс элемента списка, активируем применение аллокатора.

  1. template <typename T> struct Node: public BlockAlloc<Node<T> >
  2. {
  3. T value;
  4. Node * next;
  5. Node (const T&);
  6. };

Здесь - полный листинг аллокатора.

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

Сам класс аллокатора получился достоточно прост и не требует комментариев

  1. template<size_t PageSize = PAGESIZE, size_t Alignment = sizeof(void*)>
  2. class PointerBumpAllocator
  3. {
  4. public:
  5. PointerBumpAllocator() : _free(0) { }
  6.  
  7. void* AllocBlock(size_t block)
  8. {
  9. // todo: lock(this)
  10. block = align(block, Alignment);
  11. if (block > _free)
  12. {
  13. _free = align(block, PageSize);
  14. head = GetPage(_free);
  15. }
  16. void* tmp = head;
  17. head = (char*)head + block;
  18. _free -= block;
  19. return tmp;
  20. }
  21.  
  22. ~PointerBumpAllocator()
  23. {
  24. for (vector<void*>::iterator i = pages.begin(); i != pages.end(); ++i)
  25. {
  26. _Free(*i, PAGESIZE);
  27. }
  28. }
  29.  
  30. private:
  31. void* GetPage(size_t size)
  32. {
  33. void* page = _Alloc(PageSize);
  34. pages.push_back(page);
  35. return page;
  36. }
  37.  
  38. vector<void*> pages;
  39. void* head;
  40. size_t _free;
  41. };
  42. typedef PointerBumpAllocator<> DefaultAllocator;

Для использования аллокатора применяется такой адаптер "примесь" - т.е. класс, от которого нужно наследоваться для пользования аллокатором.

  1. template<class T, class A = DefaultAllocator>
  2. struct AllocAdaptor
  3. {
  4. static void* operator new(size_t s, A& allocator) // 1
  5. {
  6. return allocator.AllocBlock(s);
  7. }
  8.  
  9. static void* operator new(size_t s, A* allocator) // 2
  10. {
  11. return allocator->AllocBlock(s);
  12. }
  13.  
  14. static void operator delete(void*, size_t) { }
  15. static void operator delete(void*, A*) { }
  16. static void operator delete(void*, A&) { }
  17. private:
  18. static void* operator new(size_t s);
  19. };

Подклассы, должны наследоваться от адаптера:

  1. class XMLTagGPS : AllocAdaptor<XMLTagGPS>
  2. {
  3. ...
  4. };

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

Собственно для этого в адаптере и определены перегрузки:

  1. /*создание подобъектов в контейнере*/
  2.  
  3. // будет использована перегрузка 1, в случае композиции, внутри подтипа
  4. XMLTagGPS* node = new(allocator) XMLTagGPS(lat,lon);
  5. // в случае когда аллокатор - родительский класс контейнера, будет использована 2-я перегрузка
  6. XMLTagGPS* node = new(this) XMLTagGPS(lat,lon);

Можно было обойтись без перегрузок:

  1. // Передача производного объекта по ссылке на базовый
  2. XMLTagGPS* node = new(*this) XMLTagGPS(lat,lon);

Но с перегрузками, красивее - тут больше вопрос стилистики кода.

operator delete компилятор выберет самый первый из унаследованных из адаптера методов. Остальные два, опеределяют пользовательскую форму placement delete, для защиты от удаления (согласно выбранной стратегии).

Так же вместо обращений к перегрузкам операторов new, в основном_классе_контейнере можно воспользоваться паттерном "фабрика":

  1. тело_фабрики
  2. {
  3. ...
  4. XMLTagGPS* factoryMethod() { return new(alocator) XMLTagGPS(arg1, arg2); }
  5. }

Интересно многообразие форм placement new (например 11 и 19) и placement delete (например 13 и 25 - вообще может быть переданно множетво аргуметов, очень удобно).

В этой заметке уже рассматривалась простейшая перегрузка placement new.

Вот она

  1. static void * operator new (std::size_t, void *p) { return p; }

Такая реализация просто вернет переданный адрес, и далее в строкеnew(c) A() компилятор просто вызовет конструктор по этому адресу.

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

Заключение

Мы рассмотрели базовую теорию аллокаторов, следовать которой имеет смысл в приложениях интенсивно работающих с созданием/уничтожением объектов в куче, или же не так интенсивно, но в режиме 24х7. Существует множество разннобразных стратегий выделения памяти, от простых до сложных, в статье, из которой взяты последние два примера в комментариях описываются источники, откуда можно набраться идей стратегий ещё. В прочем, хорошо описанных готовых реализаций мощных стратегий довольно мало, видимо в виду сложности темы, это своего рода интеллектуальная собственность.

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

Комментарии

Аватар пользователя Илья Лесной

Менеджер памяти TCMalloc от google

Аватар пользователя Илья Лесной

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