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

Ответ 1

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

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

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

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

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

Ответ 4

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

Ответ 5

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

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