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

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

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

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

Вот мой бенчмарк. Он копирует 100 мб с memcpy, а затем перемещает около 100 мб с memmove; источник и место назначения перекрываются. Различные "расстояния" для источника и назначения. Каждый тест выполняется 10 раз, средний время печатается.

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

Вот результаты на Core i5 (Linux 3.5.0-54-generiС# 81 ~ exact1-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 ff)

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 и С++. Этот вопрос действительно просто для академических целей.

ОБНОВЛЕНИЕ 1

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

При первом запуске memcpy второй запуск выполняется быстрее, чем первый.
Когда "касание" целевого буфера memcpy (memset(b2, 0, BUFFERSIZE...)), то первый запуск memcpy также выполняется быстрее.
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.

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

Ответ 1

Ваши вызовы 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 излишне медленнее при сравнении яблок для яблок.

Ответ 2

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

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

Ответ 3

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

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

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

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

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

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

Ответ 4

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

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

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