Важность заполнения в динамическом распределении памяти

Question

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

Помогает ли это также локальность в моей программе и как она помогает?

Должен ли я заполнить весь блок форматом, скажем, кратным 4 или 8 байтам, или я должен дополнить свой блок, исключая верхний и нижний колонтитулы.

Забыл упомянуть, что это реализация C, использующаяUnistd в Linux.

Answer 1

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

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

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

Возможно, даже будет разумной идеей заполнить памятьвыделение для полных строк кэша (64 байта на X86-64, если я не сильно ошибаюсь), но это не является обязательным требованием.

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

Answer 2

Я читал, что это как-то уменьшает фрагментацию, но я не совсем понимаю, почему это так.

Это правильно. И это работает, потому что он устанавливает минимальный размер выделений. Допустим, вы добавляете отступы, чтобы каждый блок занимал не менее 1 КБ. Это означает, что никогда не будет ситуации, когда вы освобождаете часть памяти и что выделенное после этого выделение не будет вписываться в эту вновь освобожденную память, пока новое выделение не превышает 1 КБ.

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

Короче говоря, заполнение уменьшает фрагментацию, но требует больше памяти.

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

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

Помогает ли это также локальность в моей программе и как она помогает?

Это сложнее,Это может идти обоими путями и зависит от программ, использующих кучу. Но мое внутреннее чувство говорит, что заполнение, вероятно, уменьшит местность. В таком случае это может повлиять на производительность из-за пропадания кэша.