Dlaczego memmove jest szybsze niż memcpy?

89

Badam punkty aktywne wydajności w aplikacji, która spędza 50% czasu w memmove (3). Aplikacja wstawia miliony 4-bajtowych liczb całkowitych do posortowanych tablic i używa memmove do przesunięcia danych „w prawo” w celu zwolnienia miejsca na wstawioną wartość.

Spodziewałem się, że kopiowanie pamięci będzie niezwykle szybkie i byłem zaskoczony, że tak dużo czasu spędzam w memmove. Ale wtedy wpadłem na pomysł, że memmove jest powolne, ponieważ porusza nakładające się regiony, które muszą być realizowane w ciasnej pętli, zamiast kopiować duże strony pamięci. Napisałem mały mikrobenchmark, aby dowiedzieć się, czy istnieje różnica w wydajności między memcpy i memmove, spodziewając się, że memcpy wygra bez wątpienia.

Przeprowadziłem benchmark na dwóch maszynach (core i5, core i7) i zobaczyłem, że memmove jest w rzeczywistości szybszy niż memcpy, na starszym rdzeniu i7 nawet prawie dwa razy szybciej! Teraz szukam wyjaśnień.

Oto mój punkt odniesienia. Kopiuje 100 MB za pomocą memcpy, a następnie przesuwa się około 100 MB za pomocą memmove; źródło i miejsce docelowe nakładają się. Próbuje się różnych „odległości” dla źródła i celu. Każdy test jest wykonywany 10 razy, średni czas jest drukowany.

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

Oto wyniki dla Core i5 (Linux 3.5.0-54-generic # 81 ~ exact1-Ubuntu SMP x86_64 GNU / Linux, gcc to 4.6.3 (Ubuntu / Linaro 4.6.3-1ubuntu5). Liczba w nawiasach to odległość (wielkość przerwy) między źródłem a celem:

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 jest implementowany jako zoptymalizowany kod asemblera SSE, kopiujący od tyłu do przodu. Używa wstępnego pobierania sprzętowego do załadowania danych do pamięci podręcznej i kopiuje 128 bajtów do rejestrów XMM, a następnie przechowuje je w miejscu docelowym.

( memcpy-ssse3-back.S , wiersze 1650 i następne)

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)

Dlaczego memmove jest szybsze niż memcpy? Spodziewałbym się, że memcpy skopiuje strony pamięci, co powinno być znacznie szybsze niż zapętlanie. W najgorszym przypadku spodziewałbym się, że memcpy będzie tak samo szybkie jak memmove.

PS: Wiem, że w moim kodzie nie mogę zamienić memmove na memcpy. Wiem, że przykładowy kod łączy C i C ++. To pytanie jest naprawdę tylko do celów akademickich.

AKTUALIZACJA 1

Przeprowadziłem kilka odmian testów w oparciu o różne odpowiedzi.

  1. Przy dwukrotnym uruchomieniu memcpy drugi bieg jest szybszy niż pierwszy.
  2. Kiedy "dotykasz" bufora docelowego memcpy ( memset(b2, 0, BUFFERSIZE...)), to pierwsze uruchomienie memcpy jest również szybsze.
  3. memcpy jest wciąż trochę wolniejszy niż memmove.

Oto wyniki:

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

Mój wniosek: na podstawie komentarza @Oliver Charlesworth, system operacyjny musi zatwierdzić pamięć fizyczną, gdy tylko bufor docelowy memcpy zostanie uzyskany po raz pierwszy (jeśli ktoś wie, jak to „udowodnić”, dodaj odpowiedź! ). Ponadto, jak powiedział @Mats Petersson, memmove jest bardziej przyjazny dla pamięci podręcznej niż memcpy.

Dzięki za wszystkie świetne odpowiedzi i komentarze!

c++ c performance memory cruppstahl
źródło
1
Spojrzałeś na kod memmove, czy spojrzałeś również na kod memcpy?
Oliver Charlesworth,
8
Spodziewałem się, że kopiowanie pamięci będzie niezwykle szybkie - tylko wtedy, gdy pamięć jest w pamięci podręcznej L1. Gdy dane nie mieszczą się w pamięci podręcznej, wydajność kopiowania spada.
Maxim Egorushkin
1
A tak przy okazji, skopiowałeś tylko jedną gałąź memmove. Ta gałąź nie obsługuje przenoszenia, gdy źródło nakłada się na miejsce docelowe, a miejsce docelowe znajduje się pod niższymi adresami.
Maxim Egorushkin
2
Nie miałem czasu na dostęp do maszyny z Linuksem, więc nie mogę jeszcze przetestować tej teorii. Ale inne możliwe wytłumaczenie jest przesadne ; Twoja memcpypętla jest pierwszym, do którego b2uzyskuje się dostęp do zawartości , dlatego system operacyjny musi na bieżąco wykorzystywać pamięć fizyczną.
Oliver Charlesworth,
2
PS: Jeśli jest to wąskie gardło, ponownie rozważyłbym podejście. Co powiesz na umieszczenie wartości w liście lub strukturze drzewa (np. Drzewo binarne), a następnie wczytanie ich na końcu do tablicy. Węzły w takim podejściu byłyby doskonałym kandydatem do alokacji puli. Są dodawane tylko do końca, kiedy są masowo wydawane. Jest to szczególnie ważne, jeśli wiesz, ile będziesz potrzebować na początku. Biblioteki dodatkowe mają alokator puli.
Persixty,

Odpowiedzi:

57

Twoje memmovewywołania tasują pamięć o 2 do 128 bajtów, podczas gdy memcpyźródło i cel są zupełnie inne. W jakiś sposób to tłumaczy różnicę w wydajności: jeśli skopiujesz w to samo miejsce, zobaczysz, że memcpyprawdopodobnie skończy się to odrobinę szybciej, np. Na 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

Prawie nic w tym nie ma - nie ma dowodów na to, że odpisywanie na już błędną stronę pamięci ma duży wpływ, a na pewno nie widzimy skrócenia czasu o połowę ... ale pokazuje, że nie ma nic złego w memcpyniepotrzebnym spowolnieniu w porównaniu z jabłkami -dla-jabłek.

Tony Delroy
źródło
Spodziewałbym się, że pamięci podręczne procesora nie powodują różnicy, ponieważ moje bufory są znacznie większe niż pamięci podręczne.
cruppstahl
2
Ale każdy wymaga tej samej całkowitej liczby dostępów do pamięci głównej, prawda? (Tj. 100 MB odczytu i 100 MB zapisu). Wzorzec pamięci podręcznej tego nie obejdzie. Tak więc jedynym sposobem, aby jeden mógł być wolniejszy od drugiego, jest to, że niektóre rzeczy muszą być czytane / zapisywane z / do pamięci więcej niż raz.
Oliver Charlesworth,
2
@Tony D - Mój wniosek był taki, aby zapytać ludzi, którzy są mądrzejsi ode mnie;)
cruppstahl
1
Co się stanie, jeśli skopiujesz w to samo miejsce, ale memcpynajpierw zrobisz to ponownie?
Oliver Charlesworth,
1
@OliverCharlesworth: pierwsze uruchomienie testowe zawsze przynosi znaczące trafienie, ale wykonanie dwóch testów memcpy: memcpy 0,0688002 0,0583162 | memmove 0,0577443 0,05862 0,0601029 ... patrz ideone.com/8EEAcA
Tony Delroy
25

Kiedy używasz memcpy, zapisy muszą iść do pamięci podręcznej. Kiedy używasz memmovegdzie podczas kopiowania małego kroku do przodu, pamięć, którą kopiujesz, będzie już w buforze (ponieważ została odczytana 2, 4, 16 lub 128 bajtów „wstecz”). Spróbuj zrobić, memmovegdzie miejsce docelowe ma kilka megabajtów (> 4 * rozmiar pamięci podręcznej) i podejrzewam (ale nie chce mi się to przetestować), że uzyskasz podobne wyniki.

Gwarantuję, że WSZYSTKO dotyczy utrzymania pamięci podręcznej podczas wykonywania dużych operacji na pamięci.

Mats Petersson
źródło
+1 Myślę, że z powodów, o których wspomniałeś, memmove zapętlony wstecz jest bardziej przyjazny dla pamięci podręcznej niż memcpy. Jednak odkryłem, że podczas dwukrotnego uruchamiania testu memcpy drugie uruchomienie jest tak szybkie, jak memmove. Czemu? Bufory są tak duże, że drugie uruchomienie memcpy powinno być równie nieefektywne (pod względem pamięci podręcznej), jak pierwsze uruchomienie. Wydaje się więc, że są tutaj dodatkowe czynniki, które powodują spadek wydajności.
cruppstahl
3
W odpowiednich okolicznościach sekunda memcpybędzie znacznie szybsza, ponieważ TLB jest wstępnie wypełniona. Również sekunda memcpynie będzie musiała opróżniać pamięci podręcznej rzeczy, których możesz potrzebować „pozbyć się” (brudne wiersze pamięci podręcznej są „złe” pod względem wydajności na wiele sposobów. Aby jednak być pewnym, musisz uruchom coś takiego jak „perf” i wypróbuj rzeczy, takie jak chybienia w pamięci podręcznej, chybienia w TLB itp.
Mats Petersson,
15

Historycznie rzecz biorąc, memmove i memcopy pełnią tę samą funkcję. Działali w ten sam sposób i mieli taką samą implementację. Wtedy zdano sobie sprawę, że memcopy nie musi być (i często nie było) definiowane, aby obsługiwać nakładające się obszary w jakikolwiek szczególny sposób.

Efektem końcowym jest to, że memmove została zdefiniowana do obsługi nakładających się regionów w określony sposób, nawet jeśli ma to wpływ na wydajność. Memcopy ma używać najlepszego dostępnego algorytmu dla nienakładających się regionów. Implementacje są zwykle prawie identyczne.

Problem, z którym się spotkałeś, polega na tym, że istnieje tak wiele odmian sprzętu x86, że nie można powiedzieć, która metoda przesuwania pamięci będzie najszybsza. I nawet jeśli myślisz, że w jednej sytuacji masz wynik, coś tak prostego, jak inny „krok” w układzie pamięci, może spowodować znacznie inną wydajność pamięci podręcznej.

Możesz albo porównać to, co faktycznie robisz, albo zignorować problem i polegać na testach porównawczych wykonanych dla biblioteki C.

Edycja: Och, i ostatnia rzecz; przesuwanie zawartości pamięci jest BARDZO powolne. Domyślam się, że Twoja aplikacja działałaby szybciej z czymś w rodzaju prostej implementacji B-Tree do obsługi liczb całkowitych. (Oh jesteś, okej)

Edit2: Podsumowując moje rozwinięcie w komentarzach: Problemem jest tutaj mikroznak, nie mierzy tego, co myślisz. Zadania przydzielone memcpy i memmove znacznie się od siebie różnią. Jeśli zadanie powierzone memcpy zostanie powtórzone kilka razy z memmove lub memcpy, końcowe rezultaty nie będą zależeć od tego, której funkcji zmiany pamięci użyjesz, chyba że regiony się pokrywają.

user3710044
źródło
Ale o to chodzi - sprawdzam, co właściwie robię. To pytanie dotyczy interpretacji wyników testu porównawczego, które są sprzeczne z tym, co twierdzisz - że memcpy jest szybsze dla regionów, które nie pokrywają się.
cruppstahl
Moja aplikacja to b-tree! Za każdym razem, gdy do węzła-liścia wstawiane są liczby całkowite, wywoływana jest funkcja memmove, aby zwolnić miejsce. Pracuję na silniku bazy danych.
cruppstahl
1
Używasz mikro testu porównawczego i nie masz nawet memcopy i memmove przesunąć tych samych danych. Dokładne lokalizacje w pamięci, w których znajdują się dane, z którymi się radzisz, mają wpływ na buforowanie i liczbę rund do pamięci, które procesor musi wykonać.
user3710044
Chociaż ta odpowiedź jest poprawna, w rzeczywistości nie wyjaśnia, dlaczego jest wolniejsza w tym przypadku, zasadniczo mówi „jest wolniejsza, ponieważ w niektórych przypadkach może być wolniejsza”.
Oliver Charlesworth,
Mówię, że dla tych samych okoliczności, w tym tego samego układu pamięci do kopiowania / przenoszenia, benchmarki BĘDĄ takie same, ponieważ implementacje są takie same. Problem tkwi w mikroznakach.
user3710044
2

„memcpy jest bardziej wydajne niż memmove”. W twoim przypadku najprawdopodobniej nie robisz dokładnie tego samego podczas uruchamiania dwóch funkcji.

Ogólnie rzecz biorąc, UŻYWAJ memmove tylko wtedy, gdy musisz. UŻYWAJ go, gdy istnieje bardzo rozsądna szansa, że ​​region źródłowy i docelowy pokrywają się.

Źródła : https://www.youtube.com/watch?v=Yr1YnOVG-4g Dr. Jerry Cain, (wykład Stanford Intro Systems - 7) Godz .: 36:00

Ehsan
źródło