Почему memmove быстрее, чем memcpy?

90

Я исследую «горячие точки» производительности в приложении, которое 50% времени проводит в memmove (3). Приложение вставляет миллионы 4-байтовых целых чисел в отсортированные массивы и использует memmove для смещения данных «вправо», чтобы освободить место для вставленного значения.

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

Я провел тест на двух машинах (Core i5, Core i7) и увидел, что memmove на самом деле быстрее, чем memcpy, а на более старом Core i7 даже почти в два раза быстрее! Сейчас ищу объяснения.

Вот мой тест. Он копирует 100 МБ с помощью memcpy, а затем перемещает около 100 МБ с помощью memmove; источник и место назначения перекрываются. Испытываются различные «расстояния» для источника и назначения. Каждый тест запускается 10 раз, печатается среднее время.

https://gist.github.com/cruppstahl/78a57cdf937bca3d062c

Вот результаты на Core i5 (Linux 3.5.0-54-generic # 81 ~ точный1-Ubuntu SMP x86_64 GNU / Linux, gcc 4.6.3 (Ubuntu / Linaro 4.6.3-1ubuntu5). Число в скобках расстояние (размер разрыва) между источником и местом назначения:

memcpy        0.0140074
memmove (002) 0.0106168
memmove (004) 0.01065
memmove (008) 0.0107917
memmove (016) 0.0107319
memmove (032) 0.0106724
memmove (064) 0.0106821
memmove (128) 0.0110633

Memmove реализован как оптимизированный для SSE ассемблерный код, копирующий от корки до корки. Он использует аппаратную предварительную выборку для загрузки данных в кеш и копирует 128 байтов в регистры XMM, а затем сохраняет их в месте назначения.

( memcpy-ssse3-back.S , строки 1650 и далее)

L(gobble_ll_loop):
    prefetchnta -0x1c0(%rsi)
    prefetchnta -0x280(%rsi)
    prefetchnta -0x1c0(%rdi)
    prefetchnta -0x280(%rdi)
    sub $0x80, %rdx
    movdqu  -0x10(%rsi), %xmm1
    movdqu  -0x20(%rsi), %xmm2
    movdqu  -0x30(%rsi), %xmm3
    movdqu  -0x40(%rsi), %xmm4
    movdqu  -0x50(%rsi), %xmm5
    movdqu  -0x60(%rsi), %xmm6
    movdqu  -0x70(%rsi), %xmm7
    movdqu  -0x80(%rsi), %xmm8
    movdqa  %xmm1, -0x10(%rdi)
    movdqa  %xmm2, -0x20(%rdi)
    movdqa  %xmm3, -0x30(%rdi)
    movdqa  %xmm4, -0x40(%rdi)
    movdqa  %xmm5, -0x50(%rdi)
    movdqa  %xmm6, -0x60(%rdi)
    movdqa  %xmm7, -0x70(%rdi)
    movdqa  %xmm8, -0x80(%rdi)
    lea -0x80(%rsi), %rsi
    lea -0x80(%rdi), %rdi
    jae L(gobble_ll_loop)

Почему memmove быстрее, чем memcpy? Я ожидал, что memcpy будет копировать страницы памяти, что должно быть намного быстрее, чем цикл. В худшем случае я ожидал бы, что memcpy будет работать так же быстро, как memmove.

PS: Я знаю, что не могу заменить memmove на memcpy в своем коде. Я знаю, что в примере кода смешаны C и C ++. Этот вопрос действительно чисто академический.

ОБНОВЛЕНИЕ 1

Я провел несколько вариантов тестов, основанных на разных ответах.

  1. Если memcpy запускается дважды, второй запуск выполняется быстрее, чем первый.
  2. Если "коснуться" целевого буфера memcpy ( memset(b2, 0, BUFFERSIZE...)), то первый запуск memcpy также будет быстрее.
  3. memcpy по-прежнему немного медленнее, чем memmove.

Вот результаты:

memcpy        0.0118526
memcpy        0.0119105
memmove (002) 0.0108151
memmove (004) 0.0107122
memmove (008) 0.0107262
memmove (016) 0.0108555
memmove (032) 0.0107171
memmove (064) 0.0106437
memmove (128) 0.0106648

Мой вывод: на основе комментария @Oliver Charlesworth, операционная система должна выделить физическую память, как только целевой буфер memcpy будет доступен в первый раз (если кто-то знает, как «доказать» это, то добавьте ответ! ). Кроме того, как сказал @Mats Petersson, memmove более дружественен к кешу, чем memcpy.

Спасибо за отличные ответы и комментарии!

c++ c performance memory Cruppstahl
источник
2
Вы смотрели код memmove, вы также смотрели код memcpy?
Оливер Чарльзуорт,
9
Я ожидал, что копирование памяти будет чрезвычайно быстрым - только когда память находится в кэше L1. Когда данные не помещаются в кеши, производительность копирования снижается.
Максим Егорушкин
1
Кстати, вы скопировали только одну ветку memmove. Эта ветвь не может обрабатывать перемещение, когда источник перекрывает пункт назначения, а пункт назначения находится по более низким адресам.
Максим Егорушкин
2
У меня не было времени получить доступ к машине с Linux, поэтому я пока не могу проверить эту теорию. Но другое возможное объяснение - чрезмерная приверженность ; ваш memcpyцикл - это первый b2доступ к содержимому , поэтому ОС должна выделять для него физическую память по ходу.
Оливер Чарльзуорт,
2
PS: Если это узкое место, я бы пересмотрел подход. Как насчет помещения значений в список или древовидную структуру (например, двоичное дерево), а затем считывание их в массив в конце. Узлы при таком подходе были бы отличным кандидатом для распределения пула. Они добавляются только до конца, когда выпускаются массово. Это особенно верно, если вы знаете, сколько вам понадобится с самого начала. Библиотеки повышения имеют распределитель пула.
Персиксти,

Ответы:

58

Ваши memmoveвызовы перетасовывают память от 2 до 128 байтов, в то время как ваш memcpyисточник и адресат совершенно разные. Каким-то образом memcpyэто объясняет разницу в производительности: если вы скопируете в то же место, вы увидите, что в конечном итоге, возможно, немного быстрее, например, на ideone.com :

memmove (002) 0.0610362
memmove (004) 0.0554264
memmove (008) 0.0575859
memmove (016) 0.057326
memmove (032) 0.0583542
memmove (064) 0.0561934
memmove (128) 0.0549391
memcpy 0.0537919

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

Тони Делрой
источник
Я ожидал, что кеши ЦП не вызывают разницы, потому что мои буферы намного больше, чем кеши.
cruppstahl
2
Но для каждого из них требуется одинаковое общее количество обращений к основной памяти, верно? (Т.е. 100 МБ на чтение и 100 МБ на запись). Шаблон кеширования этого не обходит. Таким образом, единственный способ, которым один может быть медленнее другого, - это если некоторые данные должны быть прочитаны / записаны из / в память более одного раза.
Оливер Чарльзуорт,
2
@Tony D - Я решил спросить людей, которые умнее меня;)
cruppstahl
1
Кроме того, что произойдет, если вы скопируете в то же место, но сделаете memcpyсначала снова?
Оливер Чарльзуорт,
1
@OliverCharlesworth: первый запуск теста всегда требует значительных усилий, но выполняется два теста memcpy: memcpy 0,0688002 0,0583162 | memmove 0,0577443 0,05862 0,0601029 ... см. ideone.com/8EEAcA
Тони Делрой,
27

Когда вы используете memcpy, записи должны идти в кеш. Когда вы используете memmovewhere при копировании на небольшой шаг вперед, память, которую вы копируете, уже будет в кэше (потому что она была прочитана на 2, 4, 16 или 128 байтов «назад»). Попробуйте сделать, memmoveгде место назначения составляет несколько мегабайт (> 4 * размер кеша), и я подозреваю (но не могу потрудиться проверить), что вы получите аналогичные результаты.

Я гарантирую, что ВСЕ касается обслуживания кеша при выполнении больших операций с памятью.

Матс Петерссон
источник
+1 Я думаю, по причинам, о которых вы упомянули, обратный цикл memmove более дружелюбен к кешу, чем memcpy. Однако я обнаружил, что при двойном запуске теста memcpy второй запуск выполняется так же быстро, как и memmove. Почему? Буферы настолько велики, что второй запуск memcpy должен быть таким же неэффективным (с точки зрения кеширования), как и первый запуск. Так что, похоже, здесь есть дополнительные факторы, которые вызывают снижение производительности.
cruppstahl
3
При правильных обстоятельствах секунда memcpyбудет заметно быстрее просто потому, что TLB предварительно заполнен. Кроме того, секунде memcpyне нужно будет очищать кеш от вещей, от которых вам может потребоваться "избавиться" (грязные строки кэша "плохи" для производительности во многих отношениях. Чтобы сказать наверняка, однако, вам нужно запустите что-то вроде "perf" и попробуйте такие вещи, как промахи в кэше, промахи TLB и т. д.
Матс Петерссон
16

Исторически memmove и memcopy - это одна и та же функция. Они работали одинаково и имели одинаковую реализацию. Затем стало понятно, что memcopy не нужно (и часто не было) определять для обработки перекрывающихся областей каким-либо определенным образом.

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

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

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

Изменить: О, и последнее; перемещение большого количества содержимого памяти ОЧЕНЬ медленно. Я предполагаю, что ваше приложение будет работать быстрее с чем-то вроде простой реализации B-Tree для обработки ваших целых чисел. (О, ты, хорошо)

Edit2: Подводя итог моему расширению в комментариях: микробенчмарк - это проблема здесь, он не измеряет то, что вы думаете. Задачи, которые передаются memcpy и memmove, значительно отличаются друг от друга. Если задача, переданная memcpy, повторяется несколько раз с memmove или memcpy, конечные результаты не будут зависеть от того, какую функцию сдвига памяти вы используете, ЕСЛИ области не перекрываются.

user3710044
источник
Но в этом суть - я тестирую то, что на самом деле делаю. Этот вопрос касается интерпретации результатов теста, которые противоречат тому, что вы утверждаете - что memcpy быстрее для неперекрывающихся регионов.
cruppstahl
Мое приложение - b-tree! Всякий раз, когда целые числа вставляются в листовой узел, для освобождения места вызывается memmove. Я работаю над движком базы данных.
cruppstahl
1
Вы используете микро-тест, и у вас даже нет memcopy и memmove для сдвига одних и тех же данных. Точные места в памяти, в которых находятся копируемые данные, имеют значение для кэширования и количества циклов обращения к памяти, которое должен совершить ЦП.
user3710044
Хотя этот ответ правильный, он на самом деле не объясняет, почему он медленнее в этом случае, он по сути говорит: «Он медленнее, потому что в некоторых случаях он может быть медленнее».
Оливер Чарльзуорт,
Я говорю, что при тех же обстоятельствах, включая тот же макет памяти для копирования / перемещения, тесты БУДУТ одинаковыми, потому что реализации одинаковы. Проблема в микробенчмарке.
user3710044
2

«memcpy более эффективен, чем memmove». В вашем случае вы, скорее всего, не делаете то же самое, пока выполняете две функции.

В общем, ИСПОЛЬЗУЙТЕ memmove только в случае необходимости. ИСПОЛЬЗУЙТЕ его, когда есть очень большая вероятность того, что исходный и целевой регионы пересекаются.

Ссылка: https://www.youtube.com/watch?v=Yr1YnOVG-4g Д-р Джерри Кейн, (Стэнфордская вводная лекция по системам - 7) Время: 36:00

Эхсан
источник