Perfomance -потребление realloc()

Question

Мне интересно, сколько производительности действительно realloc() действительно стоит: я делаю это довольно часто, чтобы расширить доступную область памяти на один элемент (= конкретная структура). Есть - благодаря MMU - такой realloc() просто расширение зарезервированной области памяти или есть полное копирование всех данных, которые можно себе представить при некоторых условиях?

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

Answer 1

поведение действительно зависит от реализации. Но все пытаются минимизировать затраты на перемещение памяти. Потому что перемещение очень дорого для производительности. Это напрямую влияет на кеш. У меня нет номеров, но это очень дорогостоящая операция.
Например, в случае переселения, если среда выполнения сталкивается с двумя вариантами перемещения памяти или расширения зарезервированной в настоящее время, она выбирает последнюю.
Но это не так просто, как я сказал. Он также должен учитывать фрагментацию памяти.
Таким образом, существует несколько компромиссов, удовлетворяющих требованиям.
В случае vector, о котором вы упомянули, они используют другую схему. Если vector имеет m байт в резерве и ему нужны дополнительные байты n, среда выполнения будет выделять 2 * (n+m), чтобы свести к минимуму возможность будущего перемещения. Если вы превысите новый размер, в следующий раз он будет использовать коэффициент 4 вместо 2; и так далее. Цифры, о которых я упоминал, не являются реальными.
Я не очень понимаю, что другие дают вам более конкретную информацию.

Answer 2

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

MMU не имеет к этому никакого отношения, потому что стоимость переназначения страниц памяти, выделяющих выделение, не окупается, пока вы не нажмете более двух страниц. Это основано на исследованиях, которые я прочитал 15 лет назад, и с тех пор копирование памяти стало быстрее, а управление памятью стало более дорогостоящим из-за систем MP. Это было также для схем с нулевой копией внутри ядра, без передачи служебных данных syscall, что является значительным и замедляет работу здесь. Это также потребовало бы, чтобы ваше распределение было идеально выровнено и разбросано, что еще больше снизило полезность реализации realloc таким образом.

В лучшем случае realloc может избежать копирования данных, если фрагмент памяти, который он расширил, не выделяется. Если realloc - единственное, что вам может принести ваше приложение, но как только вы выделите немного фрагментации или других вещей, вам не повезло. Всегда предполагайте, что realloc равен malloc(new_size); memcpy(new, old, old_size); free(old);.

Хорошая практика при работе с размерами массивов с realloc - отслеживать, сколько элементов у вас есть в массиве и иметь отдельную емкость. Увеличьте емкость и realloc только тогда, когда количество элементов попадает в емкость. Увеличьте емкость на 1.5x на каждом realloc (большинство людей делают 2x, это часто рекомендуется в литературе, но исследования показывают, что 2x вызывает очень плохие проблемы фрагментации памяти, а 1.5x почти так же эффективен и намного приятнее для памяти).Что-то вроде этого:

if (a->sz == a->cap) { 
    size_t ncap = a->cap ? a->cap + a->cap/2 : INITIAL_CAP; 
    void *n = realloc(a->a, ncap * sizeof(*a->a)); 
    if (n == NULL) 
     deal_with_the_error(); 
    a->a = n; 
    a->cap = ncap; 
} 
a->a[a->sz++] = new_element; 

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

Answer 3

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

This как я рассказываю, какая часть времени тратит.

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