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

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

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

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

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

Спасибо, dragonwrenn

Ответы

Ответ 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/