Как я могу реализовать функцию быстрого копирования, такую ​​как memcpy ()?

Question

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

void *my_memcpy(void *dest, const void *src, size_t n) {
    uint64_t *d = dest;
    const uint64_t *s = src;
    n /= sizeof(uint64_t);

    while (n--)
        *d++ = *s++;

    return dest;
}

, что, насколько я понимаю (поправьте меня, если я ошибаюсь), может нарушить строгое предположение о псевдонимах и вызвать неопределенное поведение.Для простоты предположим, что n, а также выравнивание и размер src и dest кратны 8.

Если my_memcpy действительно может вызвать неопределенное поведение, я хочу знать, как memcpy удается копировать несколько байтов одновременно, не нарушая предположения компилятора.Пример любой работающей реализации для x64 может помочь.

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

Answer 1

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

Фактические быстрые реализации почти всегда используют ассемблер и специальныеintrinsics (например, glibc с SSSE3 ), но другие реализации libc могут реализовать его в C (например, musl ).

Answer 2

Портативно, вы должны копировать на основе выравнивания, что не обязательно uint64_t. Теоретически, вы должны использовать uint_fast8_t, но на практике это, по-видимому, 1 байт большого размера, 1 байт выровнен в большинстве систем. Если мобильность не требуется, вы можете придерживаться uint64_t.

---

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

size_t prealign = (uintptr_t)src % _Alignof(uint64_t);
if(prealign != 0)
{
  // copy bytes up to next aligned address
}

То же самое для пункта назначения и то же самое для конца данных.

---

что, насколько я понимаю (поправьте меня, если я ошибаюсь), может нарушить строгое предположение о псевдонимах и привести к неопределенному поведению.

Правильно. Таким образом, чтобы скопировать чанки uint64_t, вы должны либо написать код на встроенном ассемблере, либо отключить строгий псевдоним нестандартным способом при компиляции, например gcc -fno-strict-aliasing.

.

"Настоящая" библиотека memcpy рассматривается компилятором как особый случай, как и многие другие подобные библиотечные функции. memcpy(&foo, &bar, sizeof(int)); будет, например, переведен в одну mov инструкцию, встроенную в код вызывающего абонента, без вызова memcpy вообще.

---

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

Забавно, когда я пишу следующую наивную функцию копирования:

#include <stdint.h>
#include <stddef.h>

void foocpy (void* dst, const void* src, size_t n)
{
  uint8_t* u8_dst = dst;
  const uint8_t* u8_src = src;

  for(size_t i=0; i<n; i++)
  {
    u8_dst[i] = u8_src[i];
  }
}

Затем компилятор дает мне тонну довольно неэффективного машинного кода. Но если я просто добавлю restrict к обоим указателям, все функции будут заменены следующим:

foocpy:
        test    rdx, rdx
        je      .L1
        jmp     memcpy
.L1:
        ret

Это еще раз показывает, что встроенный memcpy рассматривается компилятором как особая снежинка.

Answer 3

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

Код C может быть непереносимым . [акцент на оригинале] Несмотря на то, что он стремился дать программистам возможность писать действительно переносимые программы, Комитет C89 не хотел заставлять программистов писать портативно, чтобы исключить использование C в качестве «ассемблера высокого уровня»: возможность писать машинный код является одной из сильных сторон языка C. Именно этот принцип в значительной степени мотивирует проведение различия между строго соответствующей программой и соответствующей программой (§4).

Оптимизация по частям требует использования популярного расширения, почти все реализации которого могут быть настроены для поддержки. Использование флага -fno-strict-aliasing для включения этого расширения в gcc и clang может привести к низкой производительности, если в коде не используется квалификатор restrict, когда это необходимо, но это следует винить в неправильном использовании restrict. Сокращение производительности -fno-strict-aliasing является небольшим в коде, который правильно использует restrict, в то время как отказ от использования restrict часто приводит к значительному снижению производительности даже без -fno-strict-aliasing.

Answer 4

Цтеннер уже подробно изложены самые важные моменты.

Но я добавлю это: если вы пишете код на C, а ваш компилятор умнее вас, он заметит, что вы написали плохую версию memcpy, и заменит ее вызовомфактический встроенный memcpy.Например, это:

#include <stdlib.h>

void *mymemcpy(void *restrict dest, const void * restrict src, size_t n) {
   char *csrc = (char *)src; 
   char *cdest = (char *)dest; 

   for (size_t i=0; i<n; i++) 
       cdest[i] = csrc[i]; 

   return dest;
}

Скомпилируйте с GCC 9.1 , и полученная сборка будет

mymemcpy:
        test    rdx, rdx
        je      .L7
        sub     rsp, 8
        call    memcpy
        add     rsp, 8
        ret
.L7:
        mov     rax, rdi
        ret

Это, если вы не пытаетесь быть слишком умным...