Как реализовать кучу памяти

Question

Не был точно уверен, как сформулировать заголовок, но вопрос таков:

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

Я считаю, что JVM делает именно это, поддерживая свой собственный раздел памяти и затем выделяя объектыИсходя из этого.

Мой вопрос: как бы на самом деле это реализовать?

Спасибо, dragonwrenn

Answer 1

Большинство компиляторов C и C ++ уже предоставляют диспетчер динамической памяти как часть стандартной библиотеки, поэтому вам вообще не нужно ничего делать, чтобы избежать попадания в ОС при каждом запросе.

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

Если вы хотите написать свой собственныйменеджер кучи как учебное упражнение, вот основные вещи, которые ему нужно сделать:

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

Answer 2

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

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

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

Answer 3

Вот классический распределитель и один из лучших для не многопоточного использования:

http://g.oswego.edu/dl/html/malloc.html

Вы можете многому научиться, прочитав объяснение его конструкции.

С учетом вышесказанного, если ваша программа не имеет действительно необычных шаблонов распределения, вероятно, очень плохая идея написать свой собственный распределитель или использовать собственный.Особенно если вы пытаетесь заменить систему malloc, вы рискуете получить всевозможные ошибки и проблемы совместимости из разных библиотек (или функций стандартных библиотек), связанные с «неправильной версией malloc».

Если вам нужно специализированное распределение только для нескольких конкретных задач, это можно сделать без замены malloc.Я бы порекомендовал поискать GNU obstack и пулы объектов для объектов фиксированного размера.Они охватывают большинство случаев, когда специализированное распределение может иметь реальную практическую полезность.

Answer 4

В IBM developerWorks есть хорошая статья об управлении памятью с подробным разделом ресурсов для дальнейшего чтения: Управление внутренней памятью .

В Википедии есть и хорошая информация: C динамическое выделение памяти , Управление памятью .

Answer 5

1. Да, куча stdlib и куча / виртуальная память ОС довольно хлопотны.Вызовы ОС действительно медленные, а stdlib быстрее, но все еще имеет некоторые «ненужные» блокировки и проверки и добавляет значительные накладные расходы к выделенным блокам (т.е. некоторая память используется для управления, в дополнение к тому, что вы выделяете).
2. Во многих случаях можно полностью избежать динамического размещения, используя вместо этого статические структуры.Например, иногда лучше (безопаснее и т. Д.) Определить статический буфер размером 64 КБ для имени файла Unicode, чем определять указатель / std: string и динамически выделять его.
3. Когда программе необходимо выделить много экземпляровта же структура, намного быстрее выделять большие блоки памяти и затем просто сохранять экземпляры там (последовательно или с помощью связанного списка свободных узлов) - для этого в C ++ есть «новое размещение».
4. Во многих случаяхпри работе с объектами переменного размера набор возможных размеров на самом деле очень ограничен (например, что-то вроде 4 + 2 * (1..256)), поэтому можно использовать несколько пулов типа [3] без необходимостисобирать мусор, заполнять пробелы и т. д.
5. Обычный распределитель для конкретной задачи обычно намного быстрее, чем один (ие) из стандартной библиотеки, и даже быстрее, чем оптимизированные по скорости, но слишком универсальные реализации.
6. Современные процессоры / ОС поддерживают «большие страницы», которые могут значительно повысить скорость доступа к памяти при явной работе сih большие блоки - см. http://7 -max.com /