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

У меня два вопроса.

  1. Делать realloc()и memcpy()копировать записи в массиве другим способом быстрее, чем просто повторять каждый элемент O(N)? Если ответ «да», то как вы думаете, в чем его сложность?

  2. Если выделенный размер меньше исходного размера, realloc()копирует ли записи в другое место или просто оставляет их, поскольку они уменьшают размер массива?

12.12.2008 13:43:13
8 ОТВЕТОВ
РЕШЕНИЕ

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. «В нескольких реализациях выделения, уменьшение размера блока иногда требует его копирования»

19
2.04.2014 17:40:43
Спасибо. Обновил ссылку.
Sean 2.04.2014 17:43:13
  1. Нет абсолютно никакого способа скопировать N элементов быстрее, чем O (N). Тем не менее, он может копировать несколько элементов одновременно или использовать специальные инструкции процессора - так что это может быть быстрее, чем вы могли бы сделать это самостоятельно.
  2. Не знаю точно, но я бы предположил, что память полностью перераспределена. Это самое безопасное предположение, и оно в любом случае, вероятно, зависит от реализации.
5
12.12.2008 14:02:16
  1. Производительность memcpyне может быть лучше, чем O (N), но ее можно оптимизировать, чтобы она превосходила ручное копирование; например, он может скопировать 4 байта за то время, которое требуется для копирования 1 байта. Многие memcpyреализации написаны на ассемблере с использованием оптимизированных инструкций, которые могут копировать несколько элементов за раз, что обычно быстрее, чем копирование данных по одному байту за раз.

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

5
12.12.2008 14:18:22
  1. Можно предположить, что memcpy может быть написан так, что он будет перемещать большое количество бит вокруг. Например, можно полностью скопировать данные, используя инструкции SSE, если это выгодно.

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

2
17.12.2008 19:35:38

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

malloc.c

memcpy.c

То, как я это читаю, дает ответы:

  1. O (N) --- нет способа скопировать предметы лучше, чем линейное время.
  2. Иногда большие объекты будут копироваться, когда realloc () используется для их сжатия.
0
27.12.2008 02:21:34

Давайте немного подробнее рассмотрим memcpyи, пока мы это делаем, обозначение «большой О» или Ландау.

Во-первых, биг-о. Как я уже говорил в другом месте, стоит вспомнить определение большого O, которое заключается в том, что некоторая функция g (n) называется O (f (n)), когда существует постоянная k, для которой g (n)кф (н) . То, что делает константа, позволяет вам игнорировать мелкие детали в пользу важной части. Как уже отмечалось, 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) микро- инструкции под прикрытием. Что отличается между ними является константа к ; потому что микрокод намного быстрее, и поскольку в инструкциях всего три шага декодирования, он значительно быстрее простой версии, но он все равно O (n) - просто константа меньше.

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

18
28.03.2014 21:05:16

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

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

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

Программа установки регистрируется с адресами src / trg и числом int, и все - и все.

0
27.12.2008 05:51:37

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

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

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

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

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

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

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

0
18.02.2012 03:26:08