void * memcpy ( void * destination, const void * source, size_t num );
Казалось бы, что там сложного? А о реализациях этой функции можно написать целую историю.
Когда я смотрю на окно своего любимого рабочего инструмента — профилировщика Vtune XE, очень часто вижу, что он в очередной раз обнаружил, что значительное время потратилось на копирование памяти. Так и обычно и написано: clock ticks spent in libgcc/[g]libc/kernel memcpy — XX%.
Наверное, поэтому memcpy часто переписывался, например в lkml частенько появляются подобные треды. (Больше реализаций, скорее всего, есть только у сортировок). Казалось бы, в отличие от сортировки, где есть много вариантов и алгоритмов с копированием памяти все просто. На самом деле, даже если говорить о корректности, а не производительности, возможны варианты. (В подтверждение тому — обсуждение эпического бага с участием Линуса Торвальдса и Ульриха Дреппера).
Еще во времена 8086, то есть тридцать четыре года назад, внутри реализации memcpy был следующий код:
mov [E]SI, src
mov [E]DI, ptr_dst
mov [E]CX, len
rep movsb
(все проверки и т.д. здесь и далее опущены для простоты)
Что же изменилось с тех пор? Под катом ассемблерный код и ни одной картинки.
В классической работе Агнера Фога Optimizing Assembly есть хорошее (но не очень подробное) объяснение большинства аспектов производительности memcpy.
В середине 90-х программисты обнаружили, что, несмотря на то, что новые инструкции не всегда ускоряют интернет, использовать расширенные SIMD регистры можно, чтобы копировать память быстрее, чем это делает REP MOVS.
Сначала в качестве промежуточного хранилища использовались MMx регистры, потом XMM. Забегая вперед скажу, что до YMM не дошло.
movups XMM[0-4], [src] (x4, полная кэш линия)
movups [dst], XMM[0-4]
Потом добавились разные комбинации из [не]выровненного чтения, [выравнивания], и [не]выровненной записи в память, в лучшем случае(SSE4.1) получалось что-то вроде
mov[nt]dqa XMM2, [src+i*2]
mov[nt]dqa XMM1, [src+i*2+1]
movdqa XMM1, XMM0
movdqa XMM0, XMM3
palignr XMM3, XMM2, shift
palignr XMM2, XMM1, shift
mov[nt]dqa [dst+i*2], XMM2
mov[nt]dqa [dst+i*2+1], XMM3
Небольшая сложность в том, что инструкция выравнивания существует только с immediate последним операндом (shift), из-за этого код хорошо так раздувается (см. glibc). Кстати, начиная с архитектуры «Nehalem», невыровненый доступ в память, с которым борется вышеприведенный код, больше не является важнейшей причиной тормозов, хотя и не бесплатен.
Таким образом появилось несколько реализаций memcpy, каждая из которых работала быстрее на одних процессорах, но медленнее на остальных. Через какой-то время несколько вариантов и код, который выбирает, который из них вызывать, пробрались в glibc. Наверное, среды CLR и JVM тоже умеют выбирать эффективную реализацию System.arraycopy на лету. В отличие от glibc в ядро такой SSE код просто так не впендюрить. Там все еще интереснее, надо сохранять SIMD регистры, а дело это не такое быстрое. Что в Linux, что в Windows.
А недавно вдруг раз, и все вернулось на круги своя. (Может быть, для того, чтобы не заставлять переписывать memcpy на AVX?) Для последних процессоров классическая реализация memcpy снова самая быстрая. Так что если кто-то проспал 34 года, самое время вытащить старый код, и победно посмотреть на коллег, которые переписывали memcpy последовательно на MMX, SSE2, SSE3, SSE4.1.
Кстати, чтобы было еще интереснее тестировать производительность копирования (особенно в контексте реального софта), на нее могут влиять еще non temporal чтение и запись, ограничения скорости доступа к памяти, эффекты, связанные с общим кэшем последнего уровня, и промахи по DTLB.
Выводы.
1. Писать очередную реализацию теперь бесполезно, std::memcpy останется эффективной, используя rep movs.
2. Для изучения истории вопроса и изучения производительности на старых платформах, см. эту статью и Agner Fog.
3. На Атоме, других X86 платформах и старых (до Нехалема) процессорах rep mov все еще медленный.
Upd:
Как неоднократно просили в комментах, прогнал простую микробенчмарку с memcpy пары килобайт со всеми комбинациями выравнивания в цикле.
Цифра — во сколько раз самый продвинутый SSE4.1 код быстрее, чем std::memcpy, реализованный через rep movs
Bulldozer — 1.22x (спасибо stepmex за данные)
Penryn — 1.6x
Nehalem — 1.5x
Sandy Bridge — 1.008x
Этот бенчмарк не особенно точный, в реальном софте играют роль многие другие факторы, которые я вкраце перечислил выше.
Казалось бы, что там сложного? А о реализациях этой функции можно написать целую историю.
Когда я смотрю на окно своего любимого рабочего инструмента — профилировщика Vtune XE, очень часто вижу, что он в очередной раз обнаружил, что значительное время потратилось на копирование памяти. Так и обычно и написано: clock ticks spent in libgcc/[g]libc/kernel memcpy — XX%.
Наверное, поэтому memcpy часто переписывался, например в lkml частенько появляются подобные треды. (Больше реализаций, скорее всего, есть только у сортировок). Казалось бы, в отличие от сортировки, где есть много вариантов и алгоритмов с копированием памяти все просто. На самом деле, даже если говорить о корректности, а не производительности, возможны варианты. (В подтверждение тому — обсуждение эпического бага с участием Линуса Торвальдса и Ульриха Дреппера).
Еще во времена 8086, то есть тридцать четыре года назад, внутри реализации memcpy был следующий код:
mov [E]SI, src
mov [E]DI, ptr_dst
mov [E]CX, len
rep movsb
(все проверки и т.д. здесь и далее опущены для простоты)
Что же изменилось с тех пор? Под катом ассемблерный код и ни одной картинки.
В классической работе Агнера Фога Optimizing Assembly есть хорошее (но не очень подробное) объяснение большинства аспектов производительности memcpy.
В середине 90-х программисты обнаружили, что, несмотря на то, что новые инструкции не всегда ускоряют интернет, использовать расширенные SIMD регистры можно, чтобы копировать память быстрее, чем это делает REP MOVS.
Сначала в качестве промежуточного хранилища использовались MMx регистры, потом XMM. Забегая вперед скажу, что до YMM не дошло.
movups XMM[0-4], [src] (x4, полная кэш линия)
movups [dst], XMM[0-4]
Потом добавились разные комбинации из [не]выровненного чтения, [выравнивания], и [не]выровненной записи в память, в лучшем случае(SSE4.1) получалось что-то вроде
mov[nt]dqa XMM2, [src+i*2]
mov[nt]dqa XMM1, [src+i*2+1]
movdqa XMM1, XMM0
movdqa XMM0, XMM3
palignr XMM3, XMM2, shift
palignr XMM2, XMM1, shift
mov[nt]dqa [dst+i*2], XMM2
mov[nt]dqa [dst+i*2+1], XMM3
Небольшая сложность в том, что инструкция выравнивания существует только с immediate последним операндом (shift), из-за этого код хорошо так раздувается (см. glibc). Кстати, начиная с архитектуры «Nehalem», невыровненый доступ в память, с которым борется вышеприведенный код, больше не является важнейшей причиной тормозов, хотя и не бесплатен.
Таким образом появилось несколько реализаций memcpy, каждая из которых работала быстрее на одних процессорах, но медленнее на остальных. Через какой-то время несколько вариантов и код, который выбирает, который из них вызывать, пробрались в glibc. Наверное, среды CLR и JVM тоже умеют выбирать эффективную реализацию System.arraycopy на лету. В отличие от glibc в ядро такой SSE код просто так не впендюрить. Там все еще интереснее, надо сохранять SIMD регистры, а дело это не такое быстрое. Что в Linux, что в Windows.
А недавно вдруг раз, и все вернулось на круги своя. (Может быть, для того, чтобы не заставлять переписывать memcpy на AVX?) Для последних процессоров классическая реализация memcpy снова самая быстрая. Так что если кто-то проспал 34 года, самое время вытащить старый код, и победно посмотреть на коллег, которые переписывали memcpy последовательно на MMX, SSE2, SSE3, SSE4.1.
Кстати, чтобы было еще интереснее тестировать производительность копирования (особенно в контексте реального софта), на нее могут влиять еще non temporal чтение и запись, ограничения скорости доступа к памяти, эффекты, связанные с общим кэшем последнего уровня, и промахи по DTLB.
Выводы.
1. Писать очередную реализацию теперь бесполезно, std::memcpy останется эффективной, используя rep movs.
2. Для изучения истории вопроса и изучения производительности на старых платформах, см. эту статью и Agner Fog.
3. На Атоме, других X86 платформах и старых (до Нехалема) процессорах rep mov все еще медленный.
Upd:
Как неоднократно просили в комментах, прогнал простую микробенчмарку с memcpy пары килобайт со всеми комбинациями выравнивания в цикле.
Цифра — во сколько раз самый продвинутый SSE4.1 код быстрее, чем std::memcpy, реализованный через rep movs
Bulldozer — 1.22x (спасибо stepmex за данные)
Penryn — 1.6x
Nehalem — 1.5x
Sandy Bridge — 1.008x
Этот бенчмарк не особенно точный, в реальном софте играют роль многие другие факторы, которые я вкраце перечислил выше.
