Об истории реализаций memcpy и их производительности
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
Этот бенчмарк не особенно точный, в реальном софте играют роль многие другие факторы, которые я вкраце перечислил выше.
memcpy , wmemcpy
Копирует байты между буферами. Доступны более безопасные версии этих функций; см. раздел , wmemcpy_s .
Синтаксис
Параметры
src
Буфер, из которого происходит копирование.
count
Число копируемых символов.
Возвращаемое значение
Комментарии
memcpy копирует count байт из src в dest ; wmemcpy копирует count расширенных символов (двухбайтовых). При перекрытии исходного и конечного буферов поведение memcpy не определено. Используйте memmove для обработки перекрывающихся областей.
Убедитесь в том, что буфер назначения равен или превосходит по размеру исходный буфер. Дополнительные сведения см. в разделе Как избежать переполнения буфера.
Так как большое количество переполнений буфера и, таким образом, потенциальные эксплойты безопасности, были заблокированы для неправильного использования memcpy , эта функция перечислена между «запрещенными» функциями жизненного цикла разработки безопасности (SDL). Вы можете заметить, что некоторые библиотечные классы VC++ по-прежнему используют memcpy . Более того, можно заметить, что оптимизирующий компилятор VC++ иногда также вызывает функцию memcpy . Язык Visual C++ разрабатывался в соответствии с требованиями SDL, поэтому использование этой запрещенной функции тщательно анализировалось. В случае использования в библиотеке вызовы были тщательно изучены на предмет того, не могут ли они вызвать переполнение буфера. В случае с компилятором некоторые шаблоны кода были признаны идентичными шаблону memcpy и поэтому заменены на вызов функции. В таких случаях использование функции memcpy не менее безопасно, чем использование исходных инструкций, поэтому вызов функции memcpy , оптимизированной в плане производительности, является более предпочтительным. Точно так же, как использование «безнадежных» функций CRT ’ не гарантирует безопасность (они просто затрудняют их ненадежность), использование «запрещенных» функций не ’ гарантирует опасности (они просто потребовали более тщательной проверки безопасности).
поскольку memcpy использование VC++ компилятором и библиотеками настолько тщательно изучены, эти вызовы разрешены в коде, который в противном случае соответствует SDL. memcpy вызовы, представленные в исходном коде приложения, соответствуют SDL только в том случае, если они были проверены экспертами по безопасности.
memcpy Функции и wmemcpy являются устаревшими только в том случае, если константа _CRT_SECURE_DEPRECATE_MEMORY определена перед оператором include, как показано в примере ниже:
Memcpy
void *memcpy(void *dst, const void *src, size_t n); , где:
- dst — адрес буфера назначения
- srс — адрес источника
- n — количество , иначе данные могут быть скопированы неправильно, например таким образом:
после копирования буфер dst содержит данные отличные от исходных, т.к. они были разрушены в процессе копирования:
Что получится на самом деле, зависит от реализации функции (пример относится к одной из реализации приведенных ниже).
Для правильного копирования перекрывающихся областей нужно использовать функцию string.h .
Алгоритм работы и реализации
memcpy() копирует содержимое src в буфер dst, например, так:
Но данный пример будет работать медленнее чем любая практическая реализация, по причине того что они оптимизированы:
- не используют индексы, как в примере
- перемещают за один цикл не один байт, а блок равный Пример использования