«но лил аби, почему мы не можем просто положиться на новое????»
Введение
Некоторое время назад на Reddit я был вовлечен в горячую дискуссию о важности написания собственных распределителей памяти. Теперь имейте в виду, что вам не нужно побеждать tcmalloc, jmalloc или распределители Дуга Ли. Просто знайте, насколько хороша работа под капотом и расплывчатая реализация. В любом случае, мы обсуждали хороший «проект C++ для начинающих», и я порекомендовал первоначальным авторам спроектировать и написать собственный распределитель памяти, чтобы они могли начать думать о программировании с точки зрения эффективности кэширования и производительности. По мере того, как мы начинаем достигать физических пределов закона Мура, наши компьютеры становятся ненамного быстрее, чем предыдущие поколения. Теперь, чтобы получить выигрыш в скорости вычислений, мы должны обратить внимание на другие области оптимизации.
Что такое распределитель памяти?
Распределители памяти позволяют нам разделить огромный блок системной памяти на меньшие куски памяти. По сути, это означает, что мы можем разбить еще более мелкие фрагменты памяти и определить какую-то структуру данных и алгоритм, который управляет этими меньшими фрагментами памяти. Но какова цель выполнения всей этой работы только для выделения памяти? С помощью настраиваемых распределителей памяти мы повышаем эффективность использования памяти, ограничивая объем фрагментации памяти, а также сокращаем накладные расходы, возникающие при выполнении новых вызовов. У нас также есть увеличение производительности и более эффективное использование кеша (меньший промах кеша) за счет лучшей пространственной локальности (причудливый разговор о том, что связанные объекты находятся близко друг к другу в памяти) похожих объектов. Пользовательские распределители памяти используются в разработке игр и программировании встроенных систем.
Проектирование распределителя памяти
Теперь, когда мы рассмотрели, что такое распределитель памяти и цель его создания, давайте посмотрим, как мы можем спроектировать распределитель памяти. В представлении высокого уровня распределитель памяти может быть определен двумя разными частями: интерфейсом и данными. структура, которая управляет блоками памяти.
Простая реализация интерфейса распределителя памяти может выглядеть так:
Любой пользовательский распределитель, который мы создаем для конкретной задачи, должен наследоваться от этого базового класса и реализовывать эти функции. В нашей функции-конструкторе мы вызываем malloc и резервируем буфер памяти для последующего использования. В функцию Allocate мы передаем размер памяти, которую хотим «выделить», и выравнивание, затем находим доступный кусок памяти и возвращаем выровненный указатель на него. В функции Free мы передаем указатель на созданный объект и «освобождаем» его. Чтобы управлять набором фрагментов памяти, которые мы «распределяем», мы применяем некоторую структуру данных и алгоритм для основных операций, таких как: вставка фрагментов, удаление фрагментов и поиск определенного фрагмента. Важно выбрать правильную структуру данных и алгоритм, поскольку они могут сильно повлиять на производительность.
Давайте посмотрим на некоторые распределители.
Линейный распределитель
Линейный аллокатор — один из самых простых аллокаторов, которые вы можете сделать. Идея этого распределителя заключается в распределении памяти в линейном порядке. Каждый последующий вызов функции Allocate будет перемещать указатель смещения вперед на запрошенную сумму. Указатель смещения начинается с начала буфера. Преимущество этого буфера заключается в том, что выделенные объекты хранятся ближе друг к другу, так что они оказываются в одной и той же строке кэша. Для этого типа распределителя функция Free не освобождает отдельные фрагменты, а стирается весь буфер памяти.
Распределитель стека
Распределитель стека похож на линейный распределитель, но мы можем освобождать фрагменты памяти, только если . Сохраняя указатель смещения на начало буфера, мы линейно перемещаем его каждый раз, когда вызываем функцию Allocate и присоединяем тег к началу фрагмента памяти. Тег — это объект, который дает некоторую информацию о фрагменте памяти. В этом теге мы отмечаем размер чанка. Функция Free может освобождать фрагменты памяти только в том случае, если они находятся на вершине стека.
Распределитель пула
Распределитель пула берет весь буфер памяти и разбивает его на части одинакового размера. Каждый фрагмент содержит тег с флагом (🔥), если блок свободен или нет. Функция Выделить ищет свободный блок, затем помечает его как используемый и возвращает указатель на него. Функция Free берет входящий фрагмент и помечает его как свободный.
Распределитель бесплатных списков
Распределитель Free List управляет списком свободных блоков и выделенных блоков. Функция Выделить ищет свободный блок нужного размера или блок большего размера для разделения. При выборе правильного блока функция возвращает указатель на выделенный блок. Функция Free берет кусок памяти и добавляет его обратно в список свободных блоков, если возможно, он объединяется с одним из других свободных блоков.
Вы можете улучшить производительность распределителя свободных списков, используя красно-черное дерево в качестве внутренней структуры данных; мы достигаем наихудшей временной сложности O (log n).
Заключение
Ознакомьтесь с моим репозиторием Github для полной реализации этих распределителей.
