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

StackOverflow https://stackoverflow.com/questions/362760

  •  21-08-2019
  •  | 
  •  

Вопрос

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

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

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

Это было полезно?

Решение

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

Другие советы

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

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

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

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

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

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

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

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

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

    malloc.c

    memcpy.c

    Судя по тому, как я это прочитаю, ответы будут следующими:

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

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

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

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

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

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

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

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

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

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

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

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

    Лицензировано под: CC-BY-SA с атрибуция
    Не связан с StackOverflow
    scroll top