Что отсутствует / не оптимально в этой реализации 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; } 

Комментарий переводится как «Размер обычно известен как компилятор может оптимизировать код inline из самых бесполезных».

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

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

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

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

Я изучал пропускную способность памяти для процессоров 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 ([email protected] 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 ([email protected] 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 ([email protected] 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 является asmlib Fog . Функции copy_unroll1 и copy_unroll8 определены ниже.

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

 void copy_unroll1(const float *x, float *y, const int n) { for(int i=0; i 

}

Где 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.

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

 void copy_stream(const float *x, float *y, const int n) { #pragma omp parallel for for(int i=0; i 

Где stream _mm_stream_ps() для SSE или _mm256_stream_ps() для AVX

Вот результаты memcpy на моем [email protected] ГГц с четырьмя streamами для 1 ГБ с максимальной пропускной способностью основной памяти 51,2 ГБ / с .

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

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

Я modfied функции eglibc и asmlib memcpy для параллельной работы

 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 называет это расширенным rep movsb (ERMSB) . Это описано в руководствах по оптимизации Intel в разделе 3.7.6 Расширенные операции REP MOVSB ​​и STOSB (ERMSB) .

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

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

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

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

Во-первых, основной цикл использует неравновесные векторные нагрузки / хранилища 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 декодированных μops)
  • на текущих процессорах Core iX вы можете выпускать только две параллельные нагрузки / хранилища до того, как вы остановитесь [*]
  • обычно даже не развернутый цикл AVX, подобный этому, может насыщать доступную пропускную способность DRAM [*]

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

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

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

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

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

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

Размер кода

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

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

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

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

Отраслевое предсказание

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

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

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

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

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

Решения

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

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

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

Например, собранный код для длин 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 

Этикетки не стоят ничего, и они объединяют случаи вместе и удаляют два из трех инструкций 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); } 

… и соответствующая assembly не является проблематичной:

  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 includeся в один случай с долей от общего размера кода.

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

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

центровка

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

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

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

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

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

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

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

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

Нет разворачивания

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

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

Кроме того, разворачивание часто можно комбинировать с помощью «intro» нашего «outro» кода, делая лучшую работу, чем мог бы сделать компилятор.

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

Основная причина, по которой трудно превзойти «встроенную» процедуру 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 соответственно). Ссылка Godbolt.

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

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

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

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

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

Taking Benefits of The ERMSB

Please also consider using REP MOVSB for larger blocks.

As you know, since first Pentium CPU produced in 1993, Intel began to make simple commands faster and complex commands (like REP MOVSB) slower. So, REP MOVSB became very slow, and there was no more reason to use it. In 2013, Intel decided to revisit REP MOVSB. If the CPU has CPUID ERMSB (Enhanced REP MOVSB) bit, then REP MOVSB commands are executed differently than on older processors, and are supposed to be fast. On practice, it is only fast for large blocks, 256 bytes and larger, and only when certain conditions are met:

  • both the source and destination addresses have to be aligned to a 16-Byte boundary;
  • the source region should not overlap with the destination region;
  • the length has to be a multiple of 64 to produce higher performance;
  • the direction has to be forward (CLD).

See the Intel Manual on Optimization, section 3.7.6 Enhanced REP MOVSB and STOSB operation (ERMSB) http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf

Intel recommends using AVX for blocks smaller than 2048 bytes. For the larger blocks, Intel recommends using REP MOVSB. This is because high initial startup costs of REP MOVSB (about 35 cycles).

I have done speed tests, and for the blocks of than 2048 bytes and higher, the performance of REP MOVSB is unbeatable. However, for blocks smaller than 256 bytes, REP MOVSB is very slow, even slower than plain MOV RAX back and forth in a loop.

Please not that ERMSB only affects MOVSB, not MOVSD (MOVSQ), so MOVSB is little bit faster than MOVSD (MOVSQ).

So, you can use AVX for your memcpy() implementation, and if the block is larger than 2048 bytes and all the conditions are met, then call REP MOVSB – so your memcpy() implementation will be unbeatable.

Taking Benefits of The Out-of-Order Execution Engine

You can also read about The Out-of-Order Execution Engine in the “Intel® 64 and IA-32 Architectures Optimization Reference Manual” http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf section the 2.1.2, and take benefits of it.

For example, in Intel SkyLake processor series (launched in 2015), it has:

  • 4 execution units for the Arithmetic logic unit (ALU) (add, and, cmp, or, test, xor, movzx, movsx, mov, (v)movdqu, (v)movdqa, (v)movap*, (v)movup),
  • 3 execution units for Vector ALU ( (v)pand, (v)por, (v)pxor, (v)movq, (v)movq, (v)movap*, (v)movup*, (v)andp*, (v)orp*, (v)paddb/w/d/q, (v)blendv*, (v)blendp*, (v)pblendd)

So we can occupy above units (3+4) in parallel if we use register-only operations. We cannot use 3+4 instructions in parallel for memory copy. We can use simultaneously maximum of up to two 32-bytes instructions to load from memory and one 32-bytes instructions to store from memory, and even if we are working with Level-1 cache.

Please see the Intel manual again to understand on how to do the fastest memcpy implementation: http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf

Section 2.2.2 (The Out-of-Order Engine of the Haswelll microarchitecture): “The Scheduler controls the dispatch of micro-ops onto the dispatch ports. There are eight dispatch ports to support the out-of-order execution core. Four of the eight ports provided execution resources for computational operations. The other 4 ports support memory operations of up to two 256-bit load and one 256-bit store operation in a cycle.”

Section 2.2.4 (Cache and Memory Subsystem) has the following note: “First level data cache supports two load micro-ops each cycle; each micro-op can fetch up to 32-bytes of data.”

Section 2.2.4.1 (Load and Store Operation Enhancements) has the following information: The L1 data cache can handle two 256-bit (32 bytes) load and one 256-bit (32 bytes) store operations each cycle. The unified L2 can service one cache line (64 bytes) each cycle. Additionally, there are 72 load buffers and 42 store buffers available to support micro-ops execution in-flight.

The other sections (2.3 and so on, dedicated to Sandy Bridge and other microarchitectures) basically reiterate the above information.

The section 2.3.4 (The Execution Core) gives additional details.

The scheduler can dispatch up to six micro-ops every cycle, one on each port. The following table summarizes which operations can be dispatched on which port.

  • Port 0: ALU, Shift, Mul, STTNI, Int-Div, 128b-Mov, Blend, 256b-Mov
  • Port 1: ALU, Fast LEA, Slow LEA, MUL, Shuf, Blend, 128bMov, Add, CVT
  • Port 2 & Port 3: Load_Addr, Store_addr
  • Port 4: Store_data
  • Port 5: ALU, Shift, Branch, Fast LEA, Shuf, Blend, 128b-Mov, 256b-Mov

The section 2.3.5.1 (Load and Store Operation Overview) may also be useful to understand on how to make fast memory copy, as well as the section 2.4.4.1 (Loads and Stores).

For the other processor architectures, it is again – two load units and one store unit. Table 2-4 (Cache Parameters of the Skylake Microarchitecture) has the following information:

Peak Bandwidth (bytes/cyc):

  • First Level Data Cache: 96 bytes (2x32B Load + 1*32B Store)
  • Second Level Cache: 64 bytes
  • Third Level Cache: 32 bytes.

I have also done speed tests on my Intel Core i5 6600 CPU (Skylake, 14nm, released in September 2015) with DDR4 memory, and this has confirmed the teory. For example, my test have shown that using generic 64-bit registers for memory copy, even many registers in parallel, degrades performance. Also, using just 2 XMM registers is enough – adding the 3rd doesn’t add performance.

If your CPU has AVX CPUID bit, you may take benefits of the large, 256-bit (32 byte) YMM registers to copy memory, to occupy two full load units. The AVX support was first introduced by Intel with the Sandy Bridge processors, shipping in Q1 2011 and later on by AMD with the Bulldozer processor shipping in Q3 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 

Also, there is speed benefit if you loop-unroll this code at least 8 times. As I wrote before, adding more registers besides ymm0 and ymm1 doesn’t increase performance, because there are just two load units and one store unit. Adding loops like “dec r9 jnz @@again” degrades the performance, but simple “add ecx/edx” does not.

Finally, if your CPU has AVX-512 extension, you can use 512-bit (64-byte) registers to copy memory:

 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 is supported by the following processors: Xeon Phi x200, released in 2016; Skylake EP/EX Xeon “Purley” (Xeon E5-26xx V5) processors (H2 2017); Cannonlake processors (H2 2017), Skylake-X processors – Core i9-7×××X, i7-7×××X, i5-7×××X – released on June 2017.

Please note that the memory have to be aligned on the size of the registers that you are using. If it is not, please use “unaligned” instructions: vmovdqu and moveups.

  • Что каждый программист должен знать о памяти?
  • Какие оптимизаторы предотвращают «volatile» в C ++?
  • Предоставляет ли компилятор возможность оптимизировать распределение памяти кучи?
  • Использует ли Interlocked.CompareExchange барьер памяти?
  • Оказывание программы для конвейера в процессорах Intel Sandybridge
  • Оптимизация Hyperparameter для глубоких обучающих структур с использованием байесовской оптимизации
  • Какие, если есть, компиляторы C ++ выполняют оптимизацию хвостовой рекурсии?
  • Что быстрее? SELECT SQL_CALC_FOUND_ROWS FROM `table` или SELECT COUNT (*)
  • флаг оптимизации gcc -O3 делает код медленнее, чем -O2
  • Когда компиляторы встроены в код C ++?
  • Действительно ли ADD 1 быстрее INC? x86
  • Давайте будем гением компьютера.