Сколько накладных расходов вносят вызовы realloc?

Question

Я использую realloc в каждой итерации цикла for, который повторяется более 10000 раз.

Это хорошая практика?Вызовет ли realloc ошибку, если ее вызывали много раз?

Answer 1

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

Зачастую лучше выполнить дополнительный цикл только для определения требований к хранилищу.

Я бы не сказал, что realloc - это запрет, но это тоже не очень хорошая практика.

Answer 2

Я недавно наткнулся на этот вопрос, и хотя он довольно старый, я чувствую, что информация не совсем точна.

Относительно дополнительного цикла для определения необходимого количества байтов памяти,

Использование дополнительного цикла не всегда или даже часто лучше. Что входит в предопределение, сколько памяти необходимо? Это может привести к дополнительным затратам и нежелательности ввода-вывода.

Что касается использования realloc в целом,

Семейство функций alloc (malloc, calloc, realloc и free) очень эффективно. Базовая система выделения выделяет большой кусок из ОС, а затем передает части пользователю по запросу. Последовательные вызовы realloc почти наверняка просто добавят дополнительное пространство к текущей ячейке памяти.

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

Answer 3

В дополнение к тому, что было сказано ранее, необходимо учесть еще несколько моментов:

Производительность realloc(<X-sized-buf>, X + inc) зависит от двух вещей:

1. скорость malloc(N + inc)который обычно уменьшается до O(N) с размером выделенного блока
2. со скоростью memcpy(newbuf, oldbuf, N), которая также O(N) с размером блока

Это означает, что для небольшие приращения, но большие существующие блоки, производительность realloc() составляет O(N^2) по отношению к размеру существующего блока данных.Подумайте, пузырьковая сортировка против быстрой сортировки ...

Это сравнительно дешево, если вы начнете с небольшого блока, но значительно накажет вас, если блок, который будет перераспределен, большой.Чтобы смягчить, вы должны убедиться, что inc равно не мало относительно существующего размера;Перераспределение на постоянную величину - это рецепт проблем с производительностью.

Кроме того, даже если вы увеличиваете с большим шагом (скажем, масштабируйте новый размер до 150% от старого), есть скачок использования памяти от перераспределения большого буфера;во время копирования существующего содержимого вы используете вдвое больше памяти.Последовательность:

addr = malloc(N);
addr = realloc(addr, N + inc);

поэтому терпит неудачу (намного) раньше, чем:

addr[0] = malloc(N);
addr[1] = malloc(inc);

Существуют структуры данных, которым не требуется realloc() для роста;связанные списки, списки пропусков, деревья интервалов - все они могут добавлять данные без необходимости копировать существующих данных.C ++ vector<> растет таким образом, он начинается с массива для начального размера и продолжает , добавляя , если вы его увеличите, но он не будет realloc() (т.е. копировать).Попробуйте реализовать (или использовать уже существующую реализацию) нечто подобное.

Answer 4

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

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

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

Answer 5

В С:

При правильном использовании, с realloc все в порядке. Тем не менее, легко использовать его неправильно. См. Написание твердого кода для подробного обсуждения всех способов испортить вызов realloc и дополнительных сложностей, которые это может вызвать при отладке.

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

В C ++:

Вам, вероятно, следует избегать realloc (а также malloc и free). По возможности используйте контейнерный класс из стандартной библиотеки (например, std :: vector). Они хорошо протестированы и оптимизированы и избавляют вас от многих домашних деталей, связанных с правильным управлением памятью (например, работа с исключениями).

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

Answer 6

Вы должны перераспределить на размеры, которые являются степенью 2. Эта политика используется stl и хороша из-за способа управления памятью.Realloc не завершается с ошибкой, за исключением случаев, когда вам не хватает памяти (и вы получите NULL), но вы скопируете ваши существующие (старые) данные в новом месте, и это может быть проблемой производительности.

Answer 7

, если вы используете realloc () - один и тот же буфер в цикле, я не вижу проблем, если у вас достаточно памяти для ужаса запросов дополнительной памяти:)

обычно realloc () расширяет / уменьшает существующее выделенное пространство, с которым вы работаете, и возвращает вам тот же указатель; если это не удается сделать на месте, то задействуются копия и бесплатная, поэтому в этом случае realloc () становится дорогостоящим; и вы также получите новый указатель:)