Разрешено ли компиляторам оптимизировать realloc?

Я столкнулся с ситуацией, когда было бы полезно оптимизировать ненужные вызовы для realloc. Тем не менее, похоже, что ни Clang, ни GCC не делают этого (Compiler Explorer (godbolt.org)) - хотя я вижу оптимизацию, выполняемую с помощью нескольких вызовов malloc.

Пример:

void *myfunc() {
    void *data;
    data = malloc(100);
    data = realloc(data, 200);
    return data;
}

Я ожидал, что он будет оптимизирован для чего-то вроде следующего:

void *myfunc() {
    return malloc(200);
}

Почему ни Clang, ни GCC не оптимизируют это? - Им не разрешено это делать?

Ответ 1

Разве им не разрешено это делать?

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

Если осталось 150 байтов выделяемой памяти,
data = malloc(100); data = realloc(data, 200); возвращает NULL с 100 байтами, израсходованными (и утекшими), и 50 остаются.

data = malloc(200); Возвращает NULL с 0 использованными байтами (ни один не просочился) и 150 остаются.

Различные функциональные возможности в этом узком случае могут помешать оптимизации.

Разрешено ли компиляторам оптимизировать realloc?

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

Успешный malloc(n);... realloc(p, 2*n) malloc(n);... realloc(p, 2*n) отличается от malloc(2*n); когда ... возможно, установил часть памяти.

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

Ответ 2

Компилятор, который объединяет свои собственные автономные версии malloc/calloc/free/realloc, может законно выполнить указанную оптимизацию, если авторы считают, что это стоило усилий. Компилятор, который связывает цепочки с внешними функциями, все же может выполнить такую оптимизацию, если он задокументирует, что он не рассматривает точную последовательность вызовов таких функций как наблюдаемый побочный эффект, но такая обработка может быть немного более ненадежной.

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

void *p1 = malloc(2000000000);
void *p2 = malloc(2);
free(p1);
p2 = realloc(p2, 2000000000);

система может не иметь 2000000000 байт для p2, пока не будет освобожден p1. Если бы это было изменить код на:

void *p1 = malloc(2000000000);
void *p2 = malloc(2000000000);
free(p1);

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

void *malloc(size_t size) { return 0; }
void *calloc(size_t size, size_t count) { return 0; }
void free(void *p) {  }
void *realloc(void *p, size_t size) { return 0; }

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

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

Ответ 3

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

Поэтому вопрос в том, является ли realloc() чистой функцией или нет.

В проекте стандартного комитета C11 N1570 говорится о функции realloc:

7.22.3.5 Функция realloc... 2. Функция realloc освобождает старый объект, на который указывает ptr, и возвращает указатель на новый объект, размер которого определяется размером. Содержимое нового объекта должно быть таким же, как и у старого объекта до освобождения, до меньшего из нового и старого размеров. Любые байты в новом объекте, превышающие размер старого объекта, имеют неопределенные значения.

Возвращает 4. Функция realloc возвращает указатель на новый объект (который может иметь то же значение, что и указатель на старый объект), или нулевой указатель, если новый объект не может быть выделен.

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

Это означает, что realloc() нельзя считать чистой функцией, и компилятор не может оптимизировать многочисленные вызовы к ней.

Ответ 4

Но вы не проверяете возвращаемое значение первого malloc(), которое затем используете во втором realloc(). С тем же успехом это может быть NULL.

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

Тогда есть еще один возможный сценарий. Во FreeBSD раньше была realloc() которая в основном была malloc + memcpy + освобождала старый указатель.

Предположим, что от свободной памяти осталось всего 230 байтов. В этой реализации ptr = malloc(100) за которым следует realloc(ptr, 200), потерпит неудачу, но один malloc(200) завершится успешно.

Ответ 5

Насколько я понимаю, такая оптимизация может быть запрещена (особенно для случая -indeed unlikely-, когда malloc успешен, но следующий realloc терпит неудачу).

Можно предположить, что malloc и realloc всегда выполняются успешно (это противоречит стандарту C11, n1570; посмотрите также мою реализацию шутки для malloc). В этой гипотезе (не так строго, но некоторые системы Linux имеют чрезмерную нагрузку на память, чтобы создать иллюзию), если вы используете GCC, вы можете написать свой собственный плагин GCC для такой оптимизации.

Я не уверен, что стоит потратить несколько недель или месяцев на кодирование такого плагина GCC (на практике вы, вероятно, захотите, чтобы он иногда обрабатывал некоторый код между malloc и realloc, и тогда это не так просто, так как вам нужно охарактеризовать и определить, какой такой промежуточный код является приемлемым), но этот выбор остается за вами.