Циклы malloc cpu

Какова стоимость malloc(), с точки зрения циклов процессора? (Vista/OS, последняя версия gcc, самый высокий уровень оптимизации,...)

В принципе, я реализую сложную структуру DAG (похожую на связанный список) состоящий из 16B (менее распространенных) и 20B узлов (более общий).

Иногда мне придется удалить некоторые узлы, а затем добавить некоторые. Но, вместо того, чтобы всегда использовать malloc() и free(), я могу просто переместить ненужных узлов до конца моей структуры данных, а затем обновить по мере продолжения моего алгоритма. Если доступен бесплатный node, я обновить поля; если нет, мне придется выделить новый.

Проблема заключается в том, что у меня может быть только один бесплатный node доступный при наличии для ввода, например, 20 узлов данных. Это означает:

Я проверю наличие бесплатного node
Проверка будет успешной, и бесплатный node будет обновлен
Я буду проверять наличие node еще 19 раз
Все проверки будут терпеть неудачу, и malloc() будет вызываться каждый раз

Вопрос: Это действительно стоит? Должен ли я просто malloc() и free(), как обычно, или стоит ли хранить свободные узлы в конце списка, и продолжайте проверять, даже если он обычно терпит неудачу и приведет к malloc() в любом случае?

Более конкретно,

Какова стоимость процессора для malloc()??

Ответ 1

Неважно, что это стоит? Действительно?

Истинный ответ: "Это зависит".

Это зависит от множества вещей

Что еще делает ОС в это время
Насколько фрагментированная память стала
скорость памяти и процессора на клиентском ПК
и т.д.

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

Если это не самый критически важный бит кода, просто сделайте самый простой и простейший для реализации и поддержки.

"Мы должны забыть о небольшой эффективности, скажем, около 97% времени: преждевременная оптимизация - это корень всего зла", Дональд Кнут

Ответ 2

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

Поскольку ваши размеры node относительно невелики, вы должны всегда учитывать распределение большего размера, возможно, 10 или более размеров node для каждого размещения и набивание лишних в неиспользуемый пул. Таким образом, вы будете нести распределение неопределенно реже. Но что более важно, вы уменьшите количество фрагментации памяти, вызванное множеством мелких распределений.

Кстати, я не рассматриваю такого рода проектные соображения "Преждевременная оптимизация", так как вы не ищете оправдания для введения тупых дизайнерских характеристик без уважительной причины. Структуры данных, которые могут вырасти до произвольного размера и сохраняются для произвольной продолжительности, требуют немного предусмотрительности.

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

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

Ответ 3

Действительно ли это стоит?

Вам нужно будет измерить, чтобы знать, период.

Ответ 4

Если память никогда не освобождается, malloc() будет работать довольно быстро. Если много блоков памяти используются и освобождаются, malloc() может стать довольно медленным. Детали того, насколько быстро или медленнее это будет для любого заданного шаблона использования, сильно зависят от реализации, а иногда только немного меньше на фазе Луны.

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

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

Ответ 5

В дополнение к тому, что подчеркивается @rikh, если вы хотите сверхбыстрое выделение памяти, один из методов состоит в том, чтобы предварительно выделить блоки, размер которых вам нужен (их много).

Я написал пользовательских менеджеров памяти, у которых есть предварительно выделенные списки блоков разных размеров.

Кроме того, вы можете также включить схему проверки границ памяти в блоки, которыми вы управляете.

Ответ 6

Возможно, вы захотите посмотреть на объединенные распределители; AT & T vmalloc пакет предоставляет объединенный распределитель, например.

Ответ 7

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

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

По этой причине я бы избегал высокочастотного использования malloc и free и добавлял дополнительную сложность фрилиста.

Ответ 8

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

Ответ 9

Запрос на стоимость одного malloc - неправильный вопрос.

Обычными факторами снижения производительности являются:

Размер рабочего набора (сколько байтов вы "касаетесь" в течение, например, секунды)
Фрагментация памяти (сколько времени занимает malloc, чтобы найти подходящий блок, и насколько это увеличит размер рабочего набора)

Из моего опыта, когда вам нужно ожидать многих узлов такого размера ( > ~ 100K... Миллионы), все это имеет значение.

Custom Allocator
Конечно, если вы можете настроить свой алгоритм на использование меньше памяти или меньше узлов, сделайте это. Тем не менее, вместо того, чтобы позволить затраты на перенос проблемы протекать в ваше решение, изолируйте его в пользовательском распределителе.

Самый простой выбор для этого - перегрузка нового для вашего класса, это означает, что ваш код решения не будет затронут.

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

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

Однако решающим фактором между ними обычно является локальность ссылки. Если вы можете что-то сделать, чтобы увеличить это, вы можете выиграть большое время.

Ответ 10

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

Вы задали нам вопрос, который не имеет смысла. Какой процессор? Какая скорость? Какая архитектура? Malloc - это функция C. О какой реализации стандартных подпрограмм кучи вы говорите? Один в Microsoft Visual C/С++? Тот, который поставляется с стандартными библиотеками GNU (stdlibc) в Linux/Unix/Posix?

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