циклы CPU malloc
Какова стоимость malloc (), с точки зрения циклов ЦП? (Vista/ОС, последняя версия gcc, самого высокого уровня оптимизации...)
В основном я реализую сложную структуру DAG (подобный связанному списку) состоявший из некоторых 16B (менее распространенный) и 20B (более распространенные) узлы.
Иногда, я должен буду удалить некоторые узлы и затем добавить некоторых. Но, вместо того, чтобы всегда использовать malloc () и свободный (), я могу просто переместить ненужные узлы в конец своей структуры данных и затем обновить поля, в то время как мой алгоритм продолжается. Если свободный узел будет доступен, то я обновлю поля; в противном случае я должен буду выделить новый.
Проблема, я мог бы иметь только один свободный узел в наличии, имея необходимость ввести, например, 20 ценности узлов данных. Это означает:
- Я проверю на доступный бесплатно узел
- Проверка успешно выполнится, и что свободный узел будет обновлен
- Я проверю на доступный узел еще 19 раз
- Все проверки перестанут работать, и malloc () назовут каждый раз
Вопрос: это действительно стоит того? Должен я просто malloc () и свободный (), как обычно, или действительно ли это стоит того, чтобы сохранить некоторые свободные узлы доступными в конце списка и продолжать проверять, перестанет ли это обычно работать и приводить к malloc () так или иначе?
Более конкретно,
Какова стоимость ЦП malloc ()??
10 ответов
Имеет ли значение, сколько он стоит? Правда?
Правильный ответ - «это зависит от обстоятельств».
Это зависит от множества вещей
- Что еще делает ОС в то время
- Как фрагментированная память стала
- скорость памяти и процессора на клиентском ПК
- и т. Д.
Если этот код чрезвычайно критичен к производительности, они учитывают все , что вы можете, и выработают лучший шаблон для вашего случая использования.
Если это не самый критичный для производительности фрагмент кода, просто сделайте то, что наиболее понятно и проще всего реализовать и поддерживать .
«Мы должны забыть о небольшой эффективности, скажем, примерно в 97% случаев: преждевременная оптимизация - корень всех зол», Дональд Кнут
Стоит ли оно того?
Чтобы узнать, нужно измерить, и точка.
Если память никогда не освобождается, malloc () будет работать довольно быстро. Если используется и освобождается много блоков памяти, функция malloc () может работать довольно медленно. Детали того, насколько быстро или медленно он будет для любого данного шаблона использования, сильно зависят от реализации, а иногда лишь немного менее сильно от фазы луны.
В некоторых случаях, особенно во встроенных системах, использование памяти будет строго соответствовать шаблону LIFO. В этом случае может быть полезно просто захватить всю память, которую можно использовать (во встроенных системах это часто можно сделать во время компоновки), и сохранить указатель на начало этой области и конец выделенного пространства ( который изначально является началом области). Чтобы выделить n байтов, просто скопируйте указатель конца выделенного пространства, добавьте n к оригиналу и верните скопированное значение.Чтобы освободить фрагмент и все, что после него выделено, скопируйте адрес фрагмента в указатель на конец выделенного пространства.
Обратите внимание, что этот подход имеет нулевые накладные расходы на каждый блок, и что как выделение, так и освобождение очень дешевы. Ограничение LIFO может быть проблемой, но если большая часть использования - это LIFO, и кто-то явно знает все, что необходимо сохранить после «развертки», можно будет переместить все, что необходимо сохранить после «развертки», в начало выделяемого пространства и поместите указатель после перемещенного материала.
Вы можете изучить объединенные распределители памяти; Пакет AT&T vmalloc , например, предоставляет объединенный распределитель.
Стоит выяснить, каков минимальный размер выделяемого блока в вашей целевой ОС. Возможно, вам будет лучше использовать malloc () в блоках 4K и использовать их в качестве неиспользуемого пула.
Кучи, особенно для выделения небольших объемов памяти, часто структурируются в виде связного списка, где каждая ячейка кучи указывает на следующую. При выделении памяти распределитель проходит по куче, пока не найдет ячейку, достаточно большую для требуемого выделения. По мере того, как память становится все более фрагментированной, приходится обходить все большее и большее количество ячеек. Хотя была проделана большая работа по минимизации времени выделения, лучше избегать этой проблемы.
Хорошей идеей может быть выделение большого блока и разделение его на несколько элементов списка. Это, вероятно, означает, что у вас будет меньше промахов кэша при обходе связанного списка.
По этой причине я бы избегал частого использования malloc и free и добавления дополнительной сложности в виде freelist.
Любой совет выше, который призывает вас попробовать какую-то конкретную технику, неверен. Совет выше, который советует вам избегать преждевременной оптимизации (действительно очень важный принцип), правильный.
Вы задали нам вопрос, который не имеет смысла. Какой процессор? Какая скорость? Какая архитектура? Malloc - это функция языка Си. О какой реализации стандартных процедур работы с кучей вы говорите? О той, которая есть в Microsoft Visual C/C++? О той, которая поставляется со стандартными библиотеками GNU (stdlibc) в Linux/Unix/Posix?
Вы не измерили производительность и не сказали нам, какова производительность под нагрузкой, вы не сказали нам, что написали модульные тесты для нагрузочного тестирования. Вы делаете начальный дизайн и "думаете о том, сколько циклов" одновременно? Потому что это просто глупо.
Запрашивать стоимость одного malloc - неправильный вопрос.
Обычные факторы снижения производительности:
- Размер рабочего набора (сколько байтов вы «касаетесь», например, за секунду)
- Фрагментация памяти (сколько времени требуется malloc, чтобы найти подходящий блок, и как Это значительно увеличит размер рабочего набора)
По моему опыту, когда вы должны ожидать много узлов такого размера (> ~ 100K ... миллионов), эти вещи имеют значение.
Пользовательский распределитель
Конечно, если вы можете настроить свой алгоритм на использование меньшего объема памяти или узлов, сделайте это. Однако вместо того, чтобы позволить проблеме стоимости распределения просочиться в ваше решение, изолируйте ее в настраиваемом распределителе.
Самым простым выбором для этого будет перегрузка new для вашего класса, это означает, что это не повлияет на код вашего решения.
Какой распределитель немного зависит от требований алгоритма. Для частого выделения и освобождения блоков одинакового размера каноническим выбором является пул фиксированного размера .
Распределитель арены может работать даже лучше, если у вас много выделений и очень мало удалений (т.е. вы можете себе позволить не освобождать освобожденную память).
Однако решающим фактором между ними обычно является местонахождение ссылки. Если есть что-то, что вы можете сделать, чтобы увеличить это, вы можете выиграть по-крупному.
malloc () не имеет фиксированной стоимости с точки зрения задержки из-за множества возможных состояний, с которыми диспетчер памяти должен иметь дело для выполнения вашего запроса.
Поскольку размеры ваших узлов относительно малы, вам следует всегда думать о выделении некоторого большего размера, возможно, 10 или более размеров узлов на одно выделение, и вставлять дополнительные в неиспользуемый пул. Таким образом, вы будете реже сталкиваться с неопределенным распределением. Но что еще более важно, вы уменьшите количество фрагментации памяти, вызванной таким большим количеством крошечных выделений.
Между прочим, я не считаю такое соображение дизайна «преждевременной оптимизацией», поскольку вы не ищете предлога для введения тупых характеристик дизайна без уважительной причины. Структуры данных, которые могут увеличиваться до произвольного размера и сохраняться в течение произвольного времени, требуют некоторой предусмотрительности.
В частности, поскольку структуры данных имеют тенденцию находить свой путь к незапланированному использованию позже и часто другими разработчиками, важно найти разумный баланс с точки зрения ясности и ожидаемого поведения.
Напишите вашу структуру правильно с вашими собственными функциями распределения и освобождения. Реализуйте их отдельно.Изначально сделайте для них просто malloc и освободите один узел, чтобы упростить отладку. Позже вы можете переработать их с помощью более изящных алгоритмов, как того требуют ваши потребности.
В дополнение к тому, что подчеркнул @rikh, если вам нужно сверхбыстрое выделение памяти, один из способов - предварительно выделить блоки нужного вам размера (их много).
Я написал собственные менеджеры памяти, в которых есть заранее выделенные списки блоков разного размера.
Кроме того, вы также можете включить схему проверки границ памяти в блоки, которыми вы управляете.