Почему memcpy() и memmove () быстрее, чем приращения указателя?

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

void simple_memory_copy(void* dst, void* src, unsigned int bytes)
{
  unsigned char* b_dst = (unsigned char*)dst;
  unsigned char* b_src = (unsigned char*)src;
  for (int i = 0; i < bytes; ++i)
    *b_dst++ = *b_src++;
}

улучшение

void aligned_memory_copy(void* dst, void* src, unsigned int bytes)
{
  unsigned char* b_dst = (unsigned char*)dst;
  unsigned char* b_src = (unsigned char*)src;

  // Copy bytes to align source pointer
  while ((b_src & 0x3) != 0)
  {
    *b_dst++ = *b_src++;
    bytes--;
  }

  unsigned int* w_dst = (unsigned int*)b_dst;
  unsigned int* w_src = (unsigned int*)b_src;
  while (bytes >= 4)
  {
    *w_dst++ = *w_src++;
    bytes -= 4;
  }

  // Copy trailing bytes
  if (bytes > 0)
  {
    b_dst = (unsigned char*)w_dst;
    b_src = (unsigned char*)w_src;
    while (bytes > 0)
    {
      *b_dst++ = *b_src++;
      bytes--;
    }
  }
}

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

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

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

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

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

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

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

факторы

основные факторы, влияющие на скорость копирования памяти являются:

• задержка между процессором, его кэшем и основной памятью.
• размер и структура строк кэша процессора.
• инструкции по перемещению/копированию памяти процессора (задержка, пропускная способность, размер регистра и т. д.).

memcpy может копировать более одного байта одновременно в зависимости от архитектуры компьютера. Большинство современных компьютеров могут работать с 32 битами и более в одной инструкции процессора.

С одним из примеров реализации:

    00026          * For speedy copying, optimize the common case where both pointers
    00027          * and the length are word-aligned, and copy word-at-a-time instead
    00028          * of byte-at-a-time. Otherwise, copy by bytes.

вы можете реализовать memcpy() используя любой из следующих методов, некоторые зависят от вашей архитектуры для повышения производительности, и все они будут намного быстрее, чем ваш код:

1. используйте большие единицы измерения, такие как 32-разрядные слова вместо байтов. Вы также можете (или, возможно, придется) иметь дело с выравниванием здесь. Вы не можете читать / писать 32-разрядное слово в нечетное место памяти, например, на некоторых платформах, а на других платформах вы платите огромную производительность штраф. Чтобы исправить это, адрес должен быть единицей, кратной 4. Вы можете взять это до 64-бит для 64-битных процессоров, или даже выше, используя SIMD (одна инструкция, несколько данных) инструкции ( MMX,SSE и т. д.)

2. вы можете использовать специальные инструкции CPU, которые ваш компилятор не сможет оптимизировать из C. Например, на 80386 вы можете использовать инструкцию префикса "rep" + инструкцию "movsb" для перемещения N байтов, продиктованных поместив N в регистр счетчика. Хорошие компиляторы просто сделают это за вас, но вы можете быть на платформе, которой не хватает хорошего компилятора. Обратите внимание, что пример имеет тенденцию быть плохой демонстрацией скорости, но в сочетании с инструкциями alignment + large unit он может быть быстрее, чем в основном все остальное на определенных процессорах.

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

например,http://www.agner.org/optimize/#asmlib имеет memcpy реализация, которая превосходит большинство там (на очень малую сумму). Если Вы читаете исходный код, он будет заполнен тоннами встроенного кода сборки, который снимает все вышеперечисленные три метода, выбирая, какой из этих методов основан на том, на каком процессоре вы работаете.

обратите внимание, там аналогичные оптимизации, которые могут быть сделаны для поиска байтов в буфере тоже. strchr() и друзья будут часто быстрее, чем ваш ручной прокат эквивалента. Это особенно верно для.NET и Java. Например, в .NET, встроенный String.IndexOf() гораздо быстрее, чем даже a Boyer-Moore string search, потому что он использует вышеуказанные методы оптимизации.

короткий ответ:

• кэш заполнения
• передача wordsize вместо байтовых, где это возможно
• SIMD magic

Как и другие говорят, memcpy копирует больше, чем 1-байтовые куски. Копирование в слова размера кусков гораздо быстрее. Однако большинство реализаций делают это на шаг дальше и запускают несколько инструкций MOV (word) перед циклом. Преимущество копирования, скажем, 8 блоков слов в цикле заключается в том, что сам цикл является дорогостоящим. Этот метод уменьшает количество условных ветвей в 8 раз, оптимизируя копирование для гигантских блоков.

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

С Википедия:

send(to, from, count)
register short *to, *from;
register count;
{
        register n = (count + 7) / 8;
        switch(count % 8) {
        case 0:      do {     *to = *from++;
        case 7:              *to = *from++;
        case 6:              *to = *from++;
        case 5:              *to = *from++;
        case 4:              *to = *from++;
        case 3:              *to = *from++;
        case 2:              *to = *from++;
        case 1:              *to = *from++;
                } while(--n > 0);
        }
}

обратите внимание, что выше не memcpy так как он намеренно не увеличивает

ответы отличные, но если вы все еще хотите реализовать быстрый memcpy вы сами, есть интересный пост в блоге о fast memcpy, быстрый memcpy в C.

void *memcpy(void* dest, const void* src, size_t count)
{
    char* dst8 = (char*)dest;
    char* src8 = (char*)src;

    if (count & 1) {
        dst8[0] = src8[0];
        dst8 += 1;
        src8 += 1;
    }

    count /= 2;
    while (count--) {
        dst8[0] = src8[0];
        dst8[1] = src8[1];

        dst8 += 2;
        src8 += 2;
    }
    return dest;
}

даже, это может быть лучше с оптимизацией доступа к памяти.

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

учитывая выбор, используйте библиотечные процедуры, а не сворачивать свой собственный. Это вариация DRY, которую я называю DRO (не повторяйте других). Кроме того, библиотечные процедуры менее вероятны, чем ваша собственная реализация.

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