Чего не хватает / неоптимально в этой реализации memcpy?

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

__forceinline   //因为通常Size已知，内联后编译器可以优化掉大部分无用代码
void* myMemcpy(char* Dst, const char* Src, size_t Size)
{
        void* start = Dst;
        for ( ; Size >= sizeof(__m256i); Size -= sizeof(__m256i) )
        {
                __m256i ymm = _mm256_loadu_si256(((const __m256i* &)Src)++);
                _mm256_storeu_si256(((__m256i* &)Dst)++, ymm);
        }

#define CPY_1B *((uint8_t * &)Dst)++ = *((const uint8_t * &)Src)++
#define CPY_2B *((uint16_t* &)Dst)++ = *((const uint16_t* &)Src)++
#define CPY_4B *((uint32_t* &)Dst)++ = *((const uint32_t* &)Src)++
#if defined _M_X64 || defined _M_IA64 || defined __amd64
#define CPY_8B *((uint64_t* &)Dst)++ = *((const uint64_t* &)Src)++
#else
#define CPY_8B _mm_storel_epi64((__m128i *)Dst, _mm_loadu_si128((const __m128i *)Src)), ++(const uint64_t* &)Src, ++(uint64_t* &)Dst
#endif
#define CPY16B _mm_storeu_si128((__m128i *)Dst, _mm_loadu_si128((const __m128i *)Src)), ++(const __m128i* &)Src, ++(__m128i* &)Dst

    switch (Size) {
    case 0x00:                                                      break;
    case 0x01:      CPY_1B;                                         break;
    case 0x02:              CPY_2B;                                 break;
    case 0x03:      CPY_1B; CPY_2B;                                 break;
    case 0x04:                      CPY_4B;                         break;
    case 0x05:      CPY_1B;         CPY_4B;                         break;
    case 0x06:              CPY_2B; CPY_4B;                         break;
    case 0x07:      CPY_1B; CPY_2B; CPY_4B;                         break;
    case 0x08:                              CPY_8B;                 break;
    case 0x09:      CPY_1B;                 CPY_8B;                 break;
    case 0x0A:              CPY_2B;         CPY_8B;                 break;
    case 0x0B:      CPY_1B; CPY_2B;         CPY_8B;                 break;
    case 0x0C:                      CPY_4B; CPY_8B;                 break;
    case 0x0D:      CPY_1B;         CPY_4B; CPY_8B;                 break;
    case 0x0E:              CPY_2B; CPY_4B; CPY_8B;                 break;
    case 0x0F:      CPY_1B; CPY_2B; CPY_4B; CPY_8B;                 break;
    case 0x10:                                      CPY16B;         break;
    case 0x11:      CPY_1B;                         CPY16B;         break;
    case 0x12:              CPY_2B;                 CPY16B;         break;
    case 0x13:      CPY_1B; CPY_2B;                 CPY16B;         break;
    case 0x14:                      CPY_4B;         CPY16B;         break;
    case 0x15:      CPY_1B;         CPY_4B;         CPY16B;         break;
    case 0x16:              CPY_2B; CPY_4B;         CPY16B;         break;
    case 0x17:      CPY_1B; CPY_2B; CPY_4B;         CPY16B;         break;
    case 0x18:                              CPY_8B; CPY16B;         break;
    case 0x19:      CPY_1B;                 CPY_8B; CPY16B;         break;
    case 0x1A:              CPY_2B;         CPY_8B; CPY16B;         break;
    case 0x1B:      CPY_1B; CPY_2B;         CPY_8B; CPY16B;         break;
    case 0x1C:                      CPY_4B; CPY_8B; CPY16B;         break;
    case 0x1D:      CPY_1B;         CPY_4B; CPY_8B; CPY16B;         break;
    case 0x1E:              CPY_2B; CPY_4B; CPY_8B; CPY16B;         break;
    case 0x1F:      CPY_1B; CPY_2B; CPY_4B; CPY_8B; CPY16B;         break;
    }
#undef CPY_1B
#undef CPY_2B
#undef CPY_4B
#undef CPY_8B
#undef CPY16B
        return start;
}

Комментарий переводится как "Размер обычно известен, поскольку компилятор может оптимизировать встроенный код наиболее бесполезно".

Я хотел бы улучшить, если возможно, эту реализацию, но, возможно, не так много улучшений. Я вижу, что он использует SSE/AVX для больших кусков памяти, а затем вместо цикла по последним < 32 байтам выполняется эквивалент развертывания вручную с некоторыми изменениями. Итак, вот мои вопросы:

  • Зачем развертывать цикл для последних нескольких байтов, но не частично развертывать первый (и теперь единственный) цикл?
  • Как насчет вопросов выравнивания? Разве они не важны? Должен ли я по-разному обрабатывать первые несколько байтов вплоть до некоторого кванта выравнивания, а затем выполнять 256-битные операции для выровненных последовательностей байтов? И если да, то как определить соответствующий квант выравнивания?
  • Что является наиболее важной отсутствующей функцией в этой реализации (если есть)?

Особенности / принципы, упомянутые в ответах до сих пор

  • Вам следует __restrict__ ваши параметры. (@Chux)
  • Пропускная способность памяти является ограничивающим фактором; сравните вашу реализацию с этим.(@Zboson)
  • Для небольших массивов вы можете ожидать приблизиться к пропускной способности памяти; для больших массивов - не так много. (@Zboson)
  • Несколько потоков (может быть | есть) необходимы для насыщения пропускной способности памяти. (@Zboson)
  • Вероятно, разумно по-разному оптимизировать копии больших и малых размеров. (@Zboson)
  • (Выравнивание важно? Не указано явно!)
  • Компилятор должен быть более четко осведомлен о "очевидных фактах", которые он может использовать для оптимизации (например, тот факт, что Size < 32 после первого цикла). (@Chux)
  • Существуют аргументы для развертывания ваших вызовов SSE/AVX (@BenJackson, здесь) и аргументы против этого (@PaulR)
  • невременные передачи (с помощью которых вы говорите процессору, что он не нужен для кэширования целевого местоположения) должны быть полезны для копирования больших буферов. (@Zboson)
Источник

4 ответа

Решение

Я изучал измерение пропускной способности памяти для процессоров Intel с различными операциями, и одна из них memcpy, Я сделал это на Core2, Ivy Bridge и Haswell. Я сделал большинство моих тестов, используя C/C++ со встроенными функциями (см. Код ниже - но в настоящее время я переписываю свои тесты в сборке).

Написать свой эффективный memcpy Для работы важно знать, какая абсолютная лучшая пропускная способность возможна. Эта полоса пропускания является функцией размера массивов, которые будут скопированы, и, следовательно, эффективной memcpy Функция должна по-разному оптимизироваться для маленьких и больших (и, возможно, между). Для простоты я оптимизировал работу с маленькими массивами по 8192 байта и большими массивами по 1 ГБ.

Для небольших массивов максимальная пропускная способность чтения и записи для каждого ядра составляет:

Core2-Ivy Bridge             32 bytes/cycle
Haswell                      64 bytes/cycle

Это ориентир, который вы должны стремиться к маленьким массивам. Для моих тестов я предполагаю, что массивы выровнены до 64 байтов и что размер массива кратен 8*sizeof(float)*unroll_factor, Вот мой ток memcpy результаты размером 8192 байта (Ubuntu 14.04, GCC 4.9, EGLIBC 2.19):

                             GB/s     efficiency
    Core2 (p9600@2.66 GHz)  
        builtin               35.2    41.3%
        eglibc                39.2    46.0%
        asmlib:               76.0    89.3%
        copy_unroll1:         39.1    46.0%
        copy_unroll8:         73.6    86.5%
    Ivy Bridge (E5-1620@3.6 GHz)                        
        builtin              102.2    88.7%
        eglibc:              107.0    92.9%
        asmlib:              107.6    93.4%
        copy_unroll1:        106.9    92.8%
        copy_unroll8:        111.3    96.6%
    Haswell (i5-4250U@1.3 GHz)
        builtin:              68.4    82.2%     
        eglibc:               39.7    47.7%
        asmlib:               73.2    87.6%
        copy_unroll1:         39.6    47.6%
        copy_unroll8:         81.9    98.4%

asmlib это ассмлиб Агнера Фога. copy_unroll1 а также copy_unroll8 функции определены ниже.

Из этой таблицы видно, что встроенный в GCC memcpy не работает на Core2 и что memcpy в EGLIBC плохо работает на Core2 или Haswell. Я недавно проверил головную версию GLIBC, и на Haswell производительность была намного лучше. Во всех случаях раскрутка дает лучший результат.

void copy_unroll1(const float *x, float *y, const int n) {
    for(int i=0; i<n/JUMP; i++) {
        VECNF().LOAD(&x[JUMP*(i+0)]).STORE(&y[JUMP*(i+0)]);
    }
}

void copy_unroll8(const float *x, float *y, const int n) {
for(int i=0; i<n/JUMP; i+=8) {
    VECNF().LOAD(&x[JUMP*(i+0)]).STORE(&y[JUMP*(i+0)]);
    VECNF().LOAD(&x[JUMP*(i+1)]).STORE(&y[JUMP*(i+1)]);
    VECNF().LOAD(&x[JUMP*(i+2)]).STORE(&y[JUMP*(i+2)]);
    VECNF().LOAD(&x[JUMP*(i+3)]).STORE(&y[JUMP*(i+3)]);
    VECNF().LOAD(&x[JUMP*(i+4)]).STORE(&y[JUMP*(i+4)]);
    VECNF().LOAD(&x[JUMP*(i+5)]).STORE(&y[JUMP*(i+5)]);
    VECNF().LOAD(&x[JUMP*(i+6)]).STORE(&y[JUMP*(i+6)]);
    VECNF().LOAD(&x[JUMP*(i+7)]).STORE(&y[JUMP*(i+7)]);
}

}

куда VECNF().LOAD является _mm_load_ps() для SSE или _mm256_load_ps() для AVX, VECNF().STORE является _mm_store_ps() для SSE или _mm256_store_ps() для AVX и JUMP 4 для SSE или 8 для AVX.

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

void copy_stream(const float *x, float *y, const int n) {
    #pragma omp parallel for        
    for(int i=0; i<n/JUMP; i++) {
        VECNF v = VECNF().load_a(&x[JUMP*i]);
        stream(&y[JUMP*i], v);
    }
}

куда stream является _mm_stream_ps() для SSE или _mm256_stream_ps() для AVX

Вот memcpy результаты на моем E5-1620@3,6 ГГц с четырьмя потоками на 1 ГБ с максимальной пропускной способностью основной памяти 51,2 ГБ / с.

                         GB/s     efficiency
    eglibc:              23.6     46%
    asmlib:              36.7     72%
    copy_stream:         36.7     72%

Еще раз EGLIBC работает плохо. Это потому, что он не использует временные хранилища.

Я модифицировал eglibc а также asmlibmemcpy функции для параллельного запуска

void COPY(const float * __restrict x, float * __restrict y, const int n) {
    #pragma omp parallel
    {
        size_t my_start, my_size;
        int id = omp_get_thread_num();
        int num = omp_get_num_threads();
        my_start = (id*n)/num;
        my_size = ((id+1)*n)/num - my_start;
        memcpy(y+my_start, x+my_start, sizeof(float)*my_size);
    }
}

Генерал memcpy Функция должна учитывать массивы, которые не выровнены по 64 байтам (или даже по 32 или 16 байтам) и размер которых не кратен 32 байтам или коэффициенту развертывания. Кроме того, необходимо принять решение о том, когда использовать временные магазины. Общее правило - использовать временные хранилища только для размеров, превышающих половину самого большого уровня кэша (обычно L3). Но эти тезисы являются деталями "второго порядка", которые, я думаю, следует рассмотреть после оптимизации для идеальных случаев, больших и малых. Нет особого смысла беспокоиться о корректировке смещения или неидеальных кратных размеров, если идеальный случай также работает плохо.

Обновить

Основываясь на комментариях Стивена Кэнона, я узнал, что на Ivy Bridge и Haswell более эффективно использовать rep movsb чем movntdqa (не временная инструкция хранения). Intel называет это расширенным представителем movsb (ERMSB). Это описано в руководствах по оптимизации Intel в разделе 3.7.6 Расширенные операции REP MOVSB ​​и STOSB (ERMSB).

Кроме того, в разделе " Оптимизация подпрограмм Agner Fog" в руководстве по сборке в разделе 17.9 "Перемещение блоков данных (все процессоры)" он пишет:

"Существует несколько способов перемещения больших блоков данных. Наиболее распространенными являются следующие:

  1. REP MOVS инструкция.
  2. Если данные выровнены: чтение и запись в цикле с наибольшим доступным размером регистра.
  3. Если размер постоянен: встроенные инструкции перемещения.
  4. Если данные выровнены неправильно: сначала переместите столько байтов, сколько требуется для выравнивания места назначения. Затем читайте unaligned и пишите выровненный в цикле с наибольшим доступным размером регистра.
  5. Если данные выровнены неправильно: считайте выровненным, сдвиньте, чтобы компенсировать смещение, и выровняйте запись.
  6. Если размер данных слишком велик для кэширования, используйте невременные записи, чтобы обойти кеш. Сдвиг, чтобы компенсировать смещение, если это необходимо. "

Генерал memcpy Следует рассмотреть каждый из этих пунктов. Кроме того, с Ivy Bridge и Haswell кажется, что точка 1 лучше, чем точка 6 для больших массивов. Различные технологии необходимы для Intel и AMD и для каждой итерации технологии. Я думаю, что ясно, что написание собственного общего эффективного memcpy Функция может быть довольно сложной. Но в особых случаях, на которые я смотрел, мне уже удалось добиться большего успеха, чем в GCC. memcpy или в EGLIBC, поэтому предположение, что вы не можете добиться большего успеха, чем стандартные библиотеки, неверно.

Источник

На этот вопрос нельзя ответить точно без некоторых дополнительных деталей, таких как:

  • Какова целевая платформа (архитектура ЦП, в большинстве случаев, но конфигурация памяти также играет роль)?
  • Каково распределение и предсказуемость 1 длины копий (и, в меньшей степени, распределение и предсказуемость выравниваний)?
  • Будет ли когда-нибудь статически известен размер копии во время компиляции?

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

Заявление о переключении на 32 корпуса

Оператор переключения из 32 случаев - это симпатичный способ обработки конечных байтов от 0 до 31 и, вероятно, очень хороший результат - но он может работать плохо в реальном мире из-за двух факторов.

Размер кода

Один только этот оператор switch занимает несколько сотен байтов кода для тела в дополнение к 32-элементному. Стоимость этого не будет отображаться в целевом ориентире memcpy на полноразмерном процессоре, потому что все по-прежнему вписывается в самый быстрый уровень кэша: но в реальном мире вы выполняете и другой код, и возникает конкуренция за кэш-память uop и кэш-память данных и инструкций L1.

То, что многие инструкции могут занимать полностью 20% от эффективного размера вашего UOP-кэша 3, а промахи UOP-кэша (и соответствующие циклы перехода из кэш-памяти в устаревший кодер) могут легко уничтожить небольшое преимущество, предоставляемое этим сложным переключателем.

Вдобавок к этому коммутатору требуется таблица поиска с 256 байтами из 32 записей для целей перехода 4. Если вы когда-нибудь пропустите DRAM в этом поиске, вы говорите о штрафе в 150+ циклов: сколько не пропущенных дел вам нужно, чтобы сделать switch Стоит ли, учитывая, что это, вероятно, экономит несколько или максимум два? Опять же, это не будет отображаться в микробенчмарке.

Для чего это стоит, это memcpy не является чем-то необычным: такой "исчерпывающий перечень дел" встречается даже в оптимизированных библиотеках. Я могу сделать вывод, что либо их разработка была в основном основана на микробенчмарках, либо она все еще стоит большого кусочка кода общего назначения, несмотря на недостатки. Тем не менее, безусловно, есть сценарии (давление инструкций и / или кеша данных), где это неоптимально.

Прогнозирование отрасли

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

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

Эта проблема особенно коварна, потому что она может причинить вам больший вред в реальной жизни именно в тех ситуациях, когда микробенчмарк показывает switch быть лучшим: короткие длины. Для очень длинных длин поведение на завершающих 31 байтах не очень важно, так как в нем преобладает массовая копия. Для коротких длин switch это очень важно (действительно, для копий размером 31 байт или меньше это все, что выполняется)!

Для этих коротких длин предсказуемый ряд длин работает очень хорошо для switch поскольку косвенный скачок в основном бесплатный. В частности, типичный memcpy бенчмарк "охватывает" серию длин, многократно используя одну и ту же длину для каждого суб-теста, чтобы сообщить результаты для удобного построения графиков "время против длины". switch отлично подходит для этих тестов, часто сообщая о результатах, таких как 2 или 3 цикла, для небольшой длины в несколько байтов.

В реальном мире ваши длины могут быть небольшими, но непредсказуемыми. В этом случае косвенная ветвь будет часто неверно предсказывать 5 с штрафом ~20 циклов на современных процессорах. По сравнению с лучшим случаем пары циклов это на порядок хуже. Таким образом, стеклянная челюсть здесь может быть очень серьезной (то есть, поведение switch в этом типичном случае может быть на порядок хуже, чем в лучшем случае, в то время как при больших длинах вы обычно рассматриваете разницу в 50% для разных стратегий).

Решения

Итак, как вы можете сделать лучше, чем выше, по крайней мере, в условиях, когда switch разваливается?

Используйте устройство Даффа

Одно из решений проблемы размера кода состоит в том, чтобы объединить случаи коммутатора вместе, стиль устройства Даффа.

Например, собранный код для случаев длины 1, 3 и 7 выглядит так:

Длина 1

    movzx   edx, BYTE PTR [rsi]
    mov     BYTE PTR [rcx], dl
    ret

Длина 3

    movzx   edx, BYTE PTR [rsi]
    mov     BYTE PTR [rcx], dl
    movzx   edx, WORD PTR [rsi+1]
    mov     WORD PTR [rcx+1], dx

Длина 7

    movzx   edx, BYTE PTR [rsi]
    mov     BYTE PTR [rcx], dl
    movzx   edx, WORD PTR [rsi+1]
    mov     WORD PTR [rcx+1], dx
    mov     edx, DWORD PTR [rsi+3]
    mov     DWORD PTR [rcx+3], edx
    ret

Это может быть объединено в один случай с различными переходами:

    len7:
    mov     edx, DWORD PTR [rsi-6]
    mov     DWORD PTR [rcx-6], edx
    len3:
    movzx   edx, WORD PTR [rsi-2]
    mov     WORD PTR [rcx-2], dx
    len1:
    movzx   edx, BYTE PTR [rsi]
    mov     BYTE PTR [rcx], dl
    ret

Этикетки ничего не стоят, и они объединяют дела вместе и удаляют два из 3 ret инструкции. Обратите внимание, что основой для rsi а также rcx здесь изменились: они указывают на последний байт для копирования из / в, а не на первый. Это изменение бесплатно или очень дешево в зависимости от кода перед переходом.

Вы можете расширить это для более длинных длин (например, вы можете прикрепить длины 15 и 31 к цепочке выше) и использовать другие цепочки для недостающих длин. Полное упражнение оставлено читателю. Вероятно, вы можете получить только 50% уменьшение размера при таком подходе, и гораздо лучше, если вы объедините его с чем-то еще, чтобы уменьшить размеры от 16 до 31.

Этот подход помогает только с размером кода (и, возможно, с размером таблицы переходов, если вы уменьшите размер, как описано в 4, и получите меньше 256 байт, разрешив таблицу поиска размером в байт. Он ничего не делает для предсказуемости.

Перекрывающиеся магазины

Одна хитрость, которая помогает как для размера кода, так и для предсказуемости, заключается в использовании перекрывающихся хранилищ. То есть, memcpy от 8 до 15 байтов могут быть выполнены без ветвления с двумя 8-байтовыми хранилищами, причем второе хранилище частично перекрывает первое. Например, чтобы скопировать 11 байтов, вы должны сделать 8-байтовую копию в относительной позиции 0 а также 11 - 8 == 3, Некоторые байты в середине будут "скопированы дважды", но на практике это нормально, поскольку 8-байтовая копия имеет ту же скорость, что и 1, 2 или 4-байтовая копия.

Код C выглядит так:

  if (Size >= 8) {
    *((uint64_t*)Dst) = *((const uint64_t*)Src);
    size_t offset = Size & 0x7;
    *(uint64_t *)(Dst + offset) = *(const uint64_t *)(Src + offset);
  }

... и соответствующая сборка не проблемная

    cmp     rdx, 7
    jbe     .L8
    mov     rcx, QWORD PTR [rsi]
    and     edx, 7
    mov     QWORD PTR [rdi], rcx
    mov     rcx, QWORD PTR [rsi+rdx]
    mov     QWORD PTR [rdi+rdx], rcx

В частности, обратите внимание, что вы получаете ровно два груза, два магазина и один and (в добавок к cmp а также jmp чье существование зависит от того, как вы организуете окружающий код). Это уже связано или лучше, чем большинство сгенерированных компилятором подходов для 8-15 байтов, которые могут использовать до 4 пар загрузки / хранения.

Старые процессоры подвергались некоторому штрафу за такие "пересекающиеся магазины", но более новые архитектуры (по крайней мере, в последнее десятилетие) справляются с ними без штрафа 6. Это имеет два основных преимущества:

  1. Поведение свободно от ветвей для разных размеров. По сути, это квантует ветвление так, что многие значения выбирают один и тот же путь. Все размеры от 8 до 15 (или от 8 до 16, если хотите) выбирают один и тот же путь и не подвергаются давлению неверного прогноза.

  2. По крайней мере 8 или 9 разных случаев из switch подразделяются на единичный случай с долей общего размера кода.

Этот подход может быть объединен с switch подход, но с использованием только нескольких случаев, или он может быть расширен до более крупных размеров с условными перемещениями, которые могут сделать, например, все перемещения от 8 до 31 байта без ветвей.

То, что сработает лучше всего, зависит от распределения по филиалам, но в целом эта "перекрывающаяся" техника работает очень хорошо.

центровка

Существующий код не касается выравнивания.

На самом деле, это, вообще говоря, не является законным или C или C++, так как char * указатели просто приводятся к более крупным типам и разыменовываются, что недопустимо - хотя на практике он генерирует коды, которые работают на современных компиляторах x86 (но на самом деле не работает на платформе с более строгими требованиями к выравниванию).

Кроме того, часто лучше обращаться с выравниванием специально. Есть три основных случая:

  1. Источник и пункт назначения уже выровнены. Даже оригинальный алгоритм будет хорошо работать здесь.
  2. Источник и пункт назначения относительно выровнены, но абсолютно не выровнены. То есть есть значение A это может быть добавлено и к источнику и к месту назначения так, чтобы оба были выровнены.
  3. Источник и пункт назначения полностью выровнены (т. Е. Фактически не выровнены, а case (2) не применяется).

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

Это также, вероятно, работает плохо в случае (3), так как в общем случае в случае полностью выровненного положения вы можете выбрать либо выравнивание места назначения или источника, а затем продолжить "полулинирование".

Штрафы за выравнивание со временем уменьшались, и на самых последних чипах они скромны для кода общего назначения, но все же могут быть серьезными для кода с большим количеством загрузок и хранилищ. Для больших копий это, вероятно, не имеет большого значения, поскольку в конечном итоге пропускная способность DRAM будет ограничена, но для меньших копий смещение может снизить пропускную способность на 50% и более.

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

Нет раскатывания

Код не развернут и компиляторы развернуты на разные суммы по умолчанию. Понятно, что это неоптимально, поскольку среди двух компиляторов с разными стратегиями развертывания лучше всего будет один.

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

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

Известные размеры

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

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

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

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

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

1 Обратите внимание, что здесь я делаю различие между "распределением" размеров - например, вы можете сказать "равномерно распределенный между 8 и 24 байтами" - и "предсказуемостью" фактической последовательности размеров (например, имеют ли размеры предсказуемый образец)? Вопрос о предсказуемости несколько тонкий, поскольку он зависит от реализации, поскольку, как описано выше, некоторые реализации по своей природе более предсказуемы.

2 В частности, ~750 байт инструкций в clang и ~600 байт в gcc только для тела, поверх таблицы поиска с 256-байтовым переходом для тела коммутатора, в котором было 180 - 250 инструкций (gcc а также clang соответственно). Годболт ссылка.

3 В основном 200 слитных операций из эффективного кэш-памяти размером 1000 команд. В то время как последние x86 имели размер кэша UOP около 1500 моп, вы не можете использовать все это вне предельно выделенного заполнения вашей кодовой базы из-за ограничительных правил назначения кода в кэш.

4 Варианты переключения имеют разную скомпилированную длину, поэтому переход не может быть рассчитан напрямую. Для чего бы это ни стоило, это можно было бы сделать по-другому: они могли бы использовать 16 -битное значение в таблице поиска за счет того, чтобы не использовать источник памяти для jmp, сокращая его размер на 75%.

5 В отличие от условного предсказания ветвления, который имеет типичный прогноз предсказания наихудшего случая ~50% (для совершенно случайных ветвей), трудно предсказуемое косвенное ветвление может легко приблизиться к 100%, так как вы не подбрасываете монету, вы выбирая для почти бесконечного набора целей отрасли. Это происходит в реальном мире: если memcpy используется для копирования небольших строк с длинами, равномерно распределенными между 0 и 30, switch код будет неверно предсказан в ~97% случаев.

6 Конечно, могут быть штрафы за смещение магазинов, но они также, как правило, небольшие и становятся меньше.

7 Например, memcpy в стек, после чего могут быть полностью исключены некоторые манипуляции, а копия в другом месте, непосредственно перемещая исходные данные в их окончательное местоположение. Даже такие вещи, как malloc с последующим memcpy может быть полностью устранено.

Источник

Использование преимуществ ERMSB

Также рассмотрите возможность использования REP MOVSB ​​для больших блоков.

Как вы знаете, начиная с первого процессора Pentium, выпущенного в 1993 году, Intel стала выполнять простые команды быстрее, а сложные команды (например, REP MOVSB) медленнее. Таким образом, REP MOVSB ​​стал очень медленным, и больше не было причин его использовать. В 2013 году Intel решила вернуться к REP MOVSB. Если процессор имеет бит CPUID ERMSB (Enhanced REP MOVSB), то команды REP MOVSB ​​выполняются иначе, чем на более старых процессорах, и должны быть быстрыми. На практике это быстро только для больших блоков, 256 байтов и больше, и только при соблюдении определенных условий:

  • адреса источника и назначения должны быть выровнены по 16-байтовой границе;
  • исходный регион не должен перекрываться с регионом назначения;
  • длина должна быть кратна 64, чтобы обеспечить более высокую производительность;
  • направление должно быть вперед (CLD).

См. Руководство Intel по оптимизации, раздел 3.7.6 Расширенные операции REP MOVSB ​​и STOSB (ERMSB) http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf

Intel рекомендует использовать AVX для блоков размером менее 2048 байт. Для более крупных блоков Intel рекомендует использовать REP MOVSB. Это связано с высокими начальными затратами на запуск REP MOVSB ​​(около 35 циклов).

Я провел тесты скорости, и для блоков размером более 2048 байт производительность REP MOVSB ​​непобедима. Однако для блоков размером менее 256 байт REP MOVSB ​​очень медленный, даже медленнее, чем обычный MOV RAX, в цикле.

Обратите внимание, что ERMSB влияет только на MOVSB, а не на MOVSD (MOVSQ), поэтому MOVSB ​​немного быстрее, чем MOVSD (MOVSQ).

Таким образом, вы можете использовать AVX для вашей реализации memcpy(), и если блок больше 2048 байт и все условия выполнены, то вызвать REP MOVSB ​​- так что ваша реализация memcpy() будет непревзойденной.

Использование преимуществ механизма выполнения вне заказа

Вы также можете прочитать о механизме выполнения вне очереди в "Справочном руководстве по оптимизации архитектур Intel® 64 и IA-32" http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf раздел 2.1.2, и воспользоваться его преимуществами.

Например, в серии процессоров Intel SkyLake (выпущенной в 2015 году) он имеет:

  • 4 исполнительных блока для Арифметико-логического блока (ALU) (добавьте и, cmp или, test, xor, movzx, movsx, mov, (v) movdqu, (v) movdqa, (v) movap *, (v) movup),
  • 3 исполнительных блока для Vector ALU ( (v)pand, (v)por, (v)pxor, (v)movq, (v)movq, (v)movap*, (v)movup*, (v) и p*, (v)orp*, (v)paddb/w/d/q, (v)blendv*, (v)blendp*, (v)pblendd)

Таким образом, мы можем занимать вышеупомянутые блоки (3+4) параллельно, если будем использовать только регистровые операции. Мы не можем использовать 3 + 4 инструкции параллельно для копирования памяти. Мы можем одновременно использовать максимум две 32-байтовые инструкции для загрузки из памяти и одну 32-байтовую инструкцию для хранения из памяти, даже если мы работаем с кешем уровня 1.

Пожалуйста, обратитесь к руководству Intel снова, чтобы понять, как сделать самую быструю реализацию memcpy: http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf

Раздел 2.2.2 (Механизм выхода из строя микроархитектуры Haswelll): "Планировщик контролирует отправку микроопераций на порты диспетчеризации. Существует восемь портов диспетчеризации для поддержки ядра выполнения вне очереди. Четыре из восьми портов предоставлены ресурсы для выполнения вычислительных операций. Остальные 4 порта поддерживают операции с памятью до двух 256-битных операций загрузки и одной 256-битной операции сохранения в цикле."

Раздел 2.2.4 (Подсистема кэша и памяти) содержит следующее примечание: "Кэш данных первого уровня поддерживает две микрооперации загрузки в каждом цикле; каждая микрооперация может извлекать до 32 байтов данных".

Раздел 2.2.4.1 (Улучшения операций загрузки и сохранения) содержит следующую информацию: Кэш данных L1 может обрабатывать две 256-битные (32 байта) операции загрузки и одну 256-битную (32 байта) операции хранения в каждом цикле. Унифицированный L2 может обслуживать одну строку кэша (64 байта) каждый цикл. Кроме того, имеется 72 буфера загрузки и 42 буфера хранилища, доступных для поддержки выполнения микроопераций в полете.

Другие разделы (2.3 и т. Д., Посвященные Sandy Bridge и другим микроархитектурам) в основном повторяют приведенную выше информацию.

Раздел 2.3.4 ("Ядро исполнения") дает дополнительные сведения.

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

  • Порт 0: ALU, Shift, Mul, STTNI, Int-Div, 128b-Mov, Blend, 256b-Mov
  • Порт 1: ALU, Fast LEA, Медленный LEA, MUL, Shuf, Blend, 128bMov, Add, CVT
  • Порт 2 и Порт 3: Load_Addr, Store_addr
  • Порт 4: Store_data
  • Порт 5: ALU, Shift, Branch, Fast LEA, Shuf, Blend, 128b-Mov, 256b-Mov

Раздел 2.3.5.1 (Обзор операций загрузки и хранения) также может быть полезен для понимания того, как сделать быстрое копирование памяти, а также раздел 2.4.4.1 (Загрузка и хранение).

Для других процессорных архитектур это опять-таки - два блока загрузки и один блок хранения. Таблица 2-4 (Параметры кэша микроархитектуры Skylake) содержит следующую информацию:

Пиковая пропускная способность (байт / цикл):

  • Кэш данных первого уровня: 96 байт (загрузка 2x32B + хранилище 1*32B)
  • Кэш второго уровня: 64 байта
  • Кэш третьего уровня: 32 байта.

Я также провел тесты скорости на моем процессоре Intel Core i5 6600 (Skylake, 14 нм, выпущен в сентябре 2015 г.) с памятью DDR4, и это подтвердило теорию. Например, мой тест показал, что использование общих 64-битных регистров для копирования в память, даже параллельное использование многих регистров, снижает производительность. Кроме того, достаточно использовать только два XMM-регистра - добавление третьего не повышает производительность.

Если ваш ЦП имеет бит AVX CPUID, вы можете воспользоваться большими 256-битными (32-байтовыми) регистрами YMM для копирования памяти, чтобы занять две единицы полной загрузки. Впервые поддержка AVX была представлена ​​Intel с процессорами Sandy Bridge, которые поступили в продажу в первом квартале 2011 года, а затем AMD - с процессором Bulldozer, выпущенным в третьем квартале 2011 года.

// first cycle  
vmovdqa ymm0, ymmword ptr [rcx+0]      // load 1st 32-byte part using first load unit
vmovdqa ymm1, ymmword ptr [rcx+20h]    // load 2nd 32-byte part using second load unit

// second cycle
vmovdqa ymmword ptr [rdx+0], ymm0      // store 1st 32-byte part using the single store unit

// third cycle
vmovdqa ymmword ptr [rdx+20h], ymm1    ; store 2nd 32-byte part - using the single store unit (this instruction will require a separate cycle since there is only one store unit, and we cannot do two stores in a single cycle)

add ecx, 40h // these instructions will be used by a different unit since they don't invoke load or store, so they won't require a new cycle
add edx, 40h

Кроме того, есть преимущество в скорости, если вы развернете этот код как минимум 8 раз. Как я писал ранее, добавление большего количества регистров помимо ymm0 и ymm1 не увеличивает производительность, потому что есть только две единицы загрузки и одна единица хранения. Добавление таких циклов, как "dec r9 jnz @@again", снижает производительность, а простое "add ecx/edx" - нет.

Наконец, если ваш процессор имеет расширение AVX-512, вы можете использовать 512-битные (64-байтовые) регистры для копирования памяти:

vmovdqu64   zmm0, [rcx+0]           ; load 1st 64-byte part
vmovdqu64   zmm1, [rcx+40h]         ; load 2nd 64-byte part 

vmovdqu64   [rdx+0], zmm0           ; store 1st 64-byte part
vmovdqu64   [rdx+40h], zmm1         ; store 2nd 64-byte part 

add     rcx, 80h
add     rdx, 80h

AVX-512 поддерживается следующими процессорами: Xeon Phi x200, выпущен в 2016 году; Процессоры Skylake EP/EX Xeon "Purley" (Xeon E5-26xx V5) (H2 2017); Процессоры Cannonlake (H2 2017), процессоры Skylake-X - Core i9-7×××X, i7-7×××X, i5-7×××X - выпущены в июне 2017 года.

Обратите внимание, что память должна быть выровнена по размеру регистров, которые вы используете. Если это не так, пожалуйста, используйте "невыровненные" инструкции: vmovdqu и moveups.

Источник

Во-первых, основной цикл использует невыровненные векторные загрузки / сохранения AVX для копирования 32 байтов за раз, пока не останется < 32 байтов для копирования:

    for ( ; Size >= sizeof(__m256i); Size -= sizeof(__m256i) )
    {
        __m256i ymm = _mm256_loadu_si256(((const __m256i* &)Src)++);
        _mm256_storeu_si256(((__m256i* &)Dst)++, ymm);
    }

Затем последний оператор switch обрабатывает оставшиеся 0..31 байта настолько эффективным способом, насколько это возможно, используя комбинацию 8/4/2/1 байтовых копий в зависимости от ситуации. Обратите внимание, что это не развернутый цикл - это просто 32 различных оптимизированных пути кода, которые обрабатывают остаточные байты с использованием минимального количества загрузок и хранилищ.

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

  • большинство компиляторов будут автоматически развертывать небольшие циклы (в зависимости от размера цикла и параметров оптимизации)
  • чрезмерное развертывание может вызвать выпадение небольших циклов из кэша LSD (обычно только 28 декодированных мопов)
  • на современных процессорах Core iX вы можете выполнить только две одновременные загрузки / сохранения до остановки [*]
  • как правило, даже такой не развернутый цикл AVX, как этот, может насыщать доступную полосу пропускания DRAM [*]

[*] обратите внимание, что два последних комментария выше применимы к случаям, когда источник и / или адресат не находятся в кэше (т.е. запись / чтение в / из DRAM), и, следовательно, задержка загрузки / сохранения высока.

Источник
Другие вопросы по тегам