Как работают realloc и memcpy?

Ответ 1

1 - Нет. Они копируют блок за раз. См. http://www.embedded.com/design/configurable-systems/4024961/Optimizing-Memcpy-improves-speed для довольно хорошего анализа.

2 - Это зависит от реализации. См. http://www.gnu.org/software/libtool/manual/libc/Changing-Block-Size.html для подробностей glibc. "В нескольких реализациях выделения, делая блок меньшим, иногда требуется копировать его"

Ответ 2

Давайте немного поглядим на memcpy и, пока мы на нем, на обозначениях "большой O" или Ландау.

Во-первых, большой-O. Как я уже говорил в другом месте, стоит вспомнить определение большой O, а именно, что некоторая функция g (n) называется O (f (n)), когда существует константа k, для которой g (n) & le; кф (п). То, что делает константа, позволяет игнорировать небольшие детали в пользу важной части. Как отмечалось всеми, memcpy из n байтов будет O (n) в большинстве любых нормальных архитектур, потому что независимо от того, что вы должны переместить эти n байтов, по одному фрагменту за раз. Итак, первая наивная реализация memcpy в C может быть записана

unsigned char *
memcpy(unsigned char * s1, unsigned char * s2, long size){
    long ix;
    for(ix=0; ix < size; ix++)
        s1[ix] = s2[ix];
    return s1;
}

Это на самом деле O (n), и вы можете задаться вопросом, почему мы даже беспокоимся о библиотечной программе. однако дело о функциях libc заключается в том, что они являются местом, где записываются утилиты, специфичные для платформы; если вы хотите оптимизировать архитектуру, это одно из мест, где вы можете это сделать. Таким образом, в зависимости от архитектуры могут быть более эффективные варианты реализации; например, в архитектуре IBM 360 существует инструкция MOVL, которая перемещает данные в виде больших фрагментов с использованием очень высоко оптимизированного микрокода. Таким образом, вместо этого цикла реализация memcpy на 360 может выглядеть примерно так:

LR 3,S1      LOAD S1 ADDR in Register 3
LR 4,S2      
MOVL 3,4,SIZE

(Нет гарантий, что в точности верный код 360, кстати, он будет служить для иллюстрации.) Эта реализация выглядит, как если бы не делать n шагов вокруг цикла, как это делал код C, он просто выполняет 3 команды.

Однако на самом деле происходит то, что он выполняет O (n) микрокоманды под обложками. Какая разница между ними - константа k; потому что микрокод работает намного быстрее, и поскольку на инструкциях есть только три этапа декодирования, это значительно быстрее, чем наивная версия, но все же O (n) - это просто константа меньше.

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

Ответ 3

• Абсолютно невозможно скопировать N элементов быстрее, чем O (N). Тем не менее, он может копировать сразу несколько элементов или использовать специальные инструкции процессора, поэтому он может быть быстрее, чем вы могли бы сделать это самостоятельно.
• Я не знаю точно, но я бы предположил, что память полностью перераспределена. Это самое безопасное предположение, и это, вероятно, зависит от реализации.

Ответ 4

• Производительность memcpy не может быть лучше, чем O (N), но ее можно оптимизировать, чтобы она превосходила ручное копирование; например, он может копировать 4 байта за время, затрачиваемое на копирование 1 байта. Многие реализации memcpy записываются в сборку с использованием оптимизированных инструкций, которые могут копировать несколько элементов за раз, что обычно быстрее, чем копирование данных по одному байту за раз.

• Я не совсем понимаю этот вопрос, если вы используете realloc для уменьшения размера памяти, и он преуспевает (возвращает не-NULL), новое местоположение будет содержать те же данные, что и старое местоположение вверх к размеру нового запроса. Если местоположение памяти было изменено в результате вызова realloc (не обычное при уменьшении размера), содержимое будет скопировано, иначе копирование не должно происходить, поскольку память не была перемещена.

Ответ 5

• Можно предположить, что memcpy можно записать так, чтобы он перемещал большое количество бит. например Полностью можно скопировать данные с помощью инструкций SSE, если это выгодно.

Как и все сказанное, оно не будет быстрее, чем O (n), но системы памяти часто имеют предпочтительный размер блока, а также можно, например, записать размер строки кэша за раз.

Ответ 6

Предполагая, что вы говорите о glibc, и поскольку ваши вопросы зависят от реализации, вероятно, лучше всего проверить источник:

malloc.c

memcpy.c

Как я его читал, ответы были бы следующими:

• O (N) --- нет способа скопировать элементы лучше, чем линейное.
• Иногда большие файлы будут скопированы, если для их сокращения используется realloc().

Ответ 7

В x86 есть специальные инструкции для сканирования и сопоставления байта/слова в блоке памяти, а также для копирования блока памяти (это CPC CISC). Многие компиляторы C, которые реализуют встроенный язык ассемблера и прагму, чтобы сделать вложение целых функций, в течение многих лет использовали это в своих библиотечных функциях.

Те, которые используются для копирования mem, - movsb/movsw в комбинации с командой rep.

CMPS/MOVS/SCAS/STOS
REP, REPE, REPNE, REPNZ, REPZ

Настройки регистров с адресами src/trg и int count и от вас.

Ответ 8

Некоторые важные моменты, связанные с realloc (проверка на dev С++): void * realloc (void * ptr, size_t size);

• Функция realloc() должна изменять размер объекта памяти, на который указывает ptr, до размера, указанного размером.

• Содержимое объекта остается неизменным до меньшего размера нового и старого размера.

• Если новый размер больше, содержимое вновь выделенной части объекта не указано.

• Если размер равен 0, а ptr не является нулевым указателем, объект, на который указывает, освобождается.

• Если ptr является нулевым указателем, realloc() должен быть эквивалентен malloc() для указанного размера.

• Если ptr не соответствует указателю, возвращенному ранее calloc(), malloc() или realloc(), или если пространство ранее было освобождено вызовом free() или realloc(), поведение undefined.