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

Я копирую N байтов из pSrcв pDest. Это можно сделать за один цикл:

for (int i = 0; i < N; i++)
    *pDest++ = *pSrc++

Почему это медленнее, чем memcpyили memmove? Какие уловки они используют, чтобы его ускорить?

Поскольку memcpy использует указатели слов вместо указателей байтов, также реализации memcpy часто записываются с инструкциями SIMD, которые позволяют перетасовывать 128 бит за раз.

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

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

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++;
}

Улучшения

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

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 * Для быстрого копирования оптимизируйте общий случай, когда оба указателя
    00027 * и длина выровнены по словам, вместо этого копируется по одному
    00028 * побайтно. В противном случае копируйте байтами.

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

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

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

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

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

Обратите внимание, есть аналогичные оптимизации, которые можно сделать и для поиска байтов в буфере. strchr()и друзья часто будут быстрее, чем эквивалент, брошенный вами вручную. Это особенно верно для .NET и Java . Например, в .NET встроенная String.IndexOf()функция намного быстрее, чем даже строковый поиск Бойера – Мура , поскольку в ней используются описанные выше методы оптимизации.

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

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

Я не знаю, используется ли он на самом деле в каких-либо реальных реализациях 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поскольку оно намеренно не увеличивает toуказатель. Он реализует несколько иную операцию: запись в регистр с отображением в память. См. Статью в Википедии для подробностей.

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

Ответы великов, но если вы все еще хотите осуществить быстрые memcpyсебя, есть интересный блог о быстром тетсре, Fast тетсра в 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 (Не повторяйте другие). Кроме того, библиотечные процедуры с меньшей вероятностью ошибаются, чем ваша собственная реализация.

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

Вы можете посмотреть на реализацию memset, memcpy и memmove в MacOS.

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

Реализации C memset, memcpy и memmove - это всего лишь переход к этому фиксированному месту.

Реализации используют различный код в зависимости от выравнивания источника и назначения для memcpy и memmove. Очевидно, они используют все доступные векторные возможности. Они также используют варианты без кеширования при копировании больших объемов данных и имеют инструкции по минимизации ожидания таблиц страниц. Это не просто код ассемблера, это код ассемблера, написанный кем-то, кто очень хорошо знает архитектуру каждого процессора.

Intel также добавила инструкции ассемблера, которые могут ускорить строковые операции. Например, с инструкцией для поддержки strstr, которая выполняет сравнение 256 байт за один цикл.