Dlaczego memcpy () i memmove () są szybsze niż przyrosty wskaźnika?

92

Kopiuję N bajtów z pSrcdo pDest. Można to zrobić w jednej pętli:

for (int i = 0; i < N; i++)
    *pDest++ = *pSrc++

Dlaczego jest to wolniejsze niż memcpylub memmove? Jakich sztuczek używają, aby to przyspieszyć?

c++  c  loops 
— wędrowiec
źródło
2
Twoja pętla kopiuje tylko jedną lokalizację. Myślę, że chciałeś w jakiś sposób zwiększyć wskaźniki.
— Mysticial
13
Albo możesz to dla nich naprawić, tak jak ja. A tak przy okazji, żaden prawdziwy programista C nie liczy od 1do N, zawsze jest od 0do N-1:-)
— paxdiablo
6
@paxdiablo: Jeśli przeglądasz tablice, to jasne. Ale jest wiele przypadków, w których pętla od 1 do N jest w porządku. Zależy od tego, co robisz z danymi - jeśli na przykład wyświetlasz użytkownikowi listę numerowaną zaczynającą się od 1, to rozpoczęcie od 1 prawdopodobnie ma większy sens. W każdym razie ignoruje większy problem, który jest używany intjako licznik, gdy size_tzamiast tego należy użyć typu bez znaku, takiego jak .
— Billy ONeal
2
@paxdiablo Można również liczyć od N do 1. Na niektórych procesorach, które wyeliminują jedną instrukcję porównania, ponieważ dekrementacja ustawi odpowiedni bit dla instrukcji rozgałęzienia, gdy osiągnie zero.
— onemasse
6
Myślę, że przesłanka tego pytania jest fałszywa. Nowoczesne kompilatory przekonwertują to na memcpylub memmove(w zależności od tego, czy mogą stwierdzić, czy wskaźniki mogą aliasować).
— David Schwartz,

Odpowiedzi:

120

Ponieważ memcpy używa wskaźników do słów zamiast wskaźników do bajtów, również implementacje memcpy są często pisane za pomocą instrukcji SIMD, co umożliwia tasowanie 128 bitów na raz.

Instrukcje SIMD to instrukcje montażu, które mogą wykonywać tę samą operację na każdym elemencie w wektorze o długości do 16 bajtów. Obejmuje to instrukcje dotyczące ładowania i przechowywania.

— onemasse
źródło
15
Kiedy włączysz GCC do -O3, użyje SIMD dla pętli, przynajmniej jeśli zna pDesti pSrcnie zna aliasu.
— Dietrich Epp
Obecnie pracuję na Xeon Phi z 64-bajtową (512-bitową) kartą SIMD, więc te „do 16 bajtów” sprawiają, że się uśmiecham. Ponadto musisz określić docelowy procesor, aby SIMD był włączony, na przykład za pomocą -march = native.
— yakoudbz
Może powinienem zmienić swoją odpowiedź. :)
— onemasse
Jest to bardzo nieaktualne, nawet w momencie publikacji. Wektory AVX na x86 (dostarczone w 2011) mają długość 32 bajtów, a AVX-512 - 64 bajty. Istnieją architektury z wektorami 1024-bitowymi lub 2048-bitowymi, a nawet ze zmienną szerokością wektorów, takich jak ARM SVE
— phuclv
@phuclv Chociaż instrukcje mogły być wtedy dostępne, czy masz jakieś dowody na to, że memcpy ich używa? Biblioteki zwykle potrzebują trochę czasu, aby nadrobić zaległości, a najnowsze, które mogę znaleźć, używają SSSE3 i są znacznie nowsze niż z 2011 roku.
— Pete Kirkham
81

Procedury kopiowania pamięci mogą być znacznie bardziej skomplikowane i szybsze niż zwykłe kopiowanie pamięci za pomocą wskaźników, takich jak:

void simple_memory_copy(void* dst, void* src, unsigned int bytes)
{
  unsigned char* b_dst = (unsigned char*)dst;
  unsigned char* b_src = (unsigned char*)src;
  for (int i = 0; i < bytes; ++i)
    *b_dst++ = *b_src++;
}

Improvements

Pierwszym ulepszeniem, jakie można wprowadzić, jest wyrównanie jednego ze wskaźników na granicy słowa (przez słowo mam na myśli natywny rozmiar liczby całkowitej, zwykle 32 bity / 4 bajty, ale może to być 64 bity / 8 bajtów na nowszych architekturach) i użycie ruchu / kopiuj instrukcje. Wymaga to używania bajtu do kopiowania bajtu, dopóki wskaźnik nie zostanie wyrównany.

void aligned_memory_copy(void* dst, void* src, unsigned int bytes)
{
  unsigned char* b_dst = (unsigned char*)dst;
  unsigned char* b_src = (unsigned char*)src;

  // Copy bytes to align source pointer
  while ((b_src & 0x3) != 0)
  {
    *b_dst++ = *b_src++;
    bytes--;
  }

  unsigned int* w_dst = (unsigned int*)b_dst;
  unsigned int* w_src = (unsigned int*)b_src;
  while (bytes >= 4)
  {
    *w_dst++ = *w_src++;
    bytes -= 4;
  }

  // Copy trailing bytes
  if (bytes > 0)
  {
    b_dst = (unsigned char*)w_dst;
    b_src = (unsigned char*)w_src;
    while (bytes > 0)
    {
      *b_dst++ = *b_src++;
      bytes--;
    }
  }
}

Różne architektury będą działać inaczej w zależności od tego, czy wskaźnik źródłowy lub docelowy jest odpowiednio wyrównany. Na przykład na procesorze XScale uzyskałem lepszą wydajność, wyrównując wskaźnik docelowy zamiast wskaźnika źródłowego.

Aby jeszcze bardziej poprawić wydajność, można wykonać pewne rozwijanie pętli, dzięki czemu więcej rejestrów procesora jest ładowanych danymi, a to oznacza, że ​​instrukcje ładowania / przechowywania mogą być przeplatane, a ich opóźnienie może być ukryte przez dodatkowe instrukcje (takie jak zliczanie pętli itp.). Korzyści, jakie to przynosi, różnią się znacznie w zależności od procesora, ponieważ opóźnienia instrukcji ładowania / przechowywania mogą być zupełnie inne.

Na tym etapie kod kończy się napisaniem w asemblerze, a nie w C (lub C ++), ponieważ musisz ręcznie umieścić instrukcje ładowania i przechowywania, aby uzyskać maksymalne korzyści z ukrywania opóźnień i przepustowości.

Generalnie cała linia danych pamięci podręcznej powinna być skopiowana w jednej iteracji rozwiniętej pętli.

Co prowadzi mnie do następnego ulepszenia, dodania pobierania wstępnego. Są to specjalne instrukcje, które mówią systemowi pamięci podręcznej procesora, aby załadował określone części pamięci do swojej pamięci podręcznej. Ponieważ między wydaniem instrukcji a wypełnieniem linii pamięci podręcznej występuje opóźnienie, instrukcje należy umieścić w taki sposób, aby dane były dostępne w momencie, gdy mają być skopiowane, a nie wcześniej / później.

Oznacza to umieszczenie instrukcji pobierania wstępnego na początku funkcji, a także wewnątrz głównej pętli kopiowania. Z instrukcjami pobierania wstępnego w środku pętli kopiowania, które pobierają dane, które zostaną skopiowane w czasie kilku iteracji.

Nie pamiętam, ale może być również korzystne pobranie z wyprzedzeniem adresów docelowych i źródłowych.

Czynniki

Główne czynniki wpływające na szybkość kopiowania pamięci to:

  • Opóźnienie między procesorem, jego pamięcią podręczną i pamięcią główną.
  • Rozmiar i struktura linii pamięci podręcznej procesora.
  • Instrukcje przenoszenia / kopiowania pamięci procesora (opóźnienie, przepustowość, rozmiar rejestru itp.).

Więc jeśli chcesz napisać wydajną i szybką procedurę radzenia sobie z pamięcią, musisz dużo wiedzieć o procesorze i architekturze, dla której piszesz. Wystarczy powiedzieć, że jeśli nie piszesz na jakiejś wbudowanej platformie, znacznie łatwiej byłoby po prostu użyć wbudowanych procedur kopiowania pamięci.

— Daemin
źródło
Nowoczesne procesory wykryją liniowy wzorzec dostępu do pamięci i samodzielnie rozpoczną wstępne pobieranie. Spodziewam się, że instrukcje pobierania wstępnego nie zrobią z tego powodu dużej różnicy.
— maksymalnie
@maxy Na kilku architekturach, w których zaimplementowałem procedury kopiowania pamięci, dodanie pobierania wstępnego pomogło wymiernie. Chociaż może być prawdą, że układy Intel / AMD obecnej generacji są wstępnie pobierane z wyprzedzeniem, istnieje wiele starszych układów i innych architektur, które tego nie robią.
— Daemin
czy ktoś może wyjaśnić "(b_src & 0x3)! = 0"? Nie rozumiem tego, a także - nie skompiluje się (zgłasza błąd: nieprawidłowy operator do binarnego &: unsigned char i int);
— Maverick Meerkat
„(b_src & 0x3)! = 0” sprawdza, czy najniższe 2 bity są różne od 0. Czyli wskaźnik źródła jest wyrównany do wielokrotności 4 bajtów, czy nie. Twój błąd kompilacji występuje, ponieważ traktuje 0x3 jako bajt, a nie in, możesz to naprawić za pomocą 0x00000003 lub 0x3i (myślę).
— Daemin
b_src & 0x3nie skompiluje się, ponieważ nie możesz wykonywać arytmetyki bitowej na typach wskaźników. Musisz rzucić go jako (u)intptr_tpierwszy
— phuclv
18

memcpymoże kopiować więcej niż jeden bajt na raz, w zależności od architektury komputera. Większość nowoczesnych komputerów może pracować z 32 bitami lub więcej w jednej instrukcji procesora.

Z jednej przykładowej realizacji :

    00026 * W celu szybkiego kopiowania zoptymalizuj typowy przypadek, w którym oba wskaźniki
    00027 *, a długość jest wyrównana do słowa, a zamiast tego kopiuj słowo w czasie
    00028 * bajtów na raz. W przeciwnym razie skopiuj bajty.
— Mark Byers
źródło
8
Na 386 (na przykład), który nie miał wbudowanej pamięci podręcznej, zrobiło to ogromną różnicę. W przypadku większości nowoczesnych procesorów odczyty i zapisy będą odbywać się po jednej linii pamięci podręcznej na raz, a szyna do pamięci będzie zwykle wąskim gardłem, więc spodziewaj się poprawy o kilka procent, a nie nawet czterokrotnie.
— Jerry Coffin
2
Myślę, że powinieneś być nieco bardziej dosadny, kiedy mówisz „ze źródła”. Jasne, to jest „źródło” na niektórych architekturach, ale na pewno nie jest na, powiedzmy, BSD lub Windowsie. (Do diabła, nawet między systemami GNU często jest duża różnica w tej funkcji)
— Billy ONeal
@Billy ONeal: +1 absolutnie tak ... jest więcej niż jeden sposób na oskórowanie kota. To był tylko jeden przykład. Naprawiony! Dzięki za konstruktywny komentarz.
— Mark Byers
7

Możesz zaimplementować memcpy()za pomocą dowolnej z następujących technik, niektóre zależne od Twojej architektury w celu zwiększenia wydajności, i wszystkie będą znacznie szybsze niż Twój kod:

  1. Użyj większych jednostek, takich jak słowa 32-bitowe zamiast bajtów. Możesz również (lub być może będziesz musiał) zająć się tutaj wyrównaniem. Nie możesz czytać / pisać 32-bitowego słowa w dziwnej lokalizacji pamięci, na przykład na niektórych platformach, a na innych platformach płacisz ogromną karę za wydajność. Aby to naprawić, adres musi być jednostką podzielną przez 4. Możesz przyjąć do 64 bitów dla 64-bitowych procesorów lub nawet więcej, używając instrukcji SIMD (pojedyncza instrukcja, wiele danych) ( MMX , SSE itp.)

  2. Możesz użyć specjalnych instrukcji procesora, których kompilator może nie być w stanie zoptymalizować z C. Na przykład w 80386 możesz użyć instrukcji prefiksu "rep" + instrukcji "movsb", aby przenieść N bajtów podyktowane przez umieszczenie N w liczbie zarejestrować. Dobre kompilatory zrobią to za Ciebie, ale możesz być na platformie, której brakuje dobrego kompilatora. Zauważ, że ten przykład wydaje się być złą demonstracją szybkości, ale w połączeniu z wyrównaniem + większymi instrukcjami jednostkowymi może być szybszy niż większość innych elementów na niektórych procesorach.

  3. Rozwijanie pętli - gałęzie mogą być dość drogie na niektórych procesorach, więc rozwijanie pętli może zmniejszyć liczbę gałęzi. Jest to również dobra technika łączenia instrukcji SIMD i jednostek o bardzo dużych rozmiarach.

Na przykład http://www.agner.org/optimize/#asmlib ma memcpyimplementację, która bije najwięcej (o bardzo niewielką ilość). Jeśli przeczytasz kod źródłowy, będzie on pełen ton wbudowanego kodu asemblera, który wyciąga wszystkie powyższe trzy techniki, wybierając, która z tych technik opiera się na tym, na jakim procesorze pracujesz.

Zauważ, że istnieją podobne optymalizacje, które można wprowadzić do wyszukiwania bajtów w buforze. strchr()a przyjaciele często będą szybciej niż Twój odpowiednik wyrzucony z ręki. Jest to szczególnie prawdziwe w przypadku .NET i Java . Na przykład w .NET funkcja wbudowana String.IndexOf()jest znacznie szybsza niż nawet wyszukiwanie ciągów Boyera-Moore'a , ponieważ wykorzystuje powyższe techniki optymalizacji.

— Danny Dulai
źródło
1
Ta sama mgła Agner, z którą się łączysz, również wysuwa teorię, że rozwijanie pętli jest szkodliwe dla nowoczesnych procesorów .
Większość dzisiejszych procesorów ma dobre przewidywanie rozgałęzień, co powinno negować korzyści płynące z rozwijania pętli w typowych przypadkach. Dobry kompilator optymalizujący może nadal czasami go używać.
— thomasrutter
5

Krótka odpowiedź:

  • wypełnienie pamięci podręcznej
  • Jeśli to możliwe, transfery w rozmiarze wyrazy zamiast bajtów
  • Magia SIMD
— moshbear
źródło
4

Nie wiem, czy jest faktycznie używane w jakichkolwiek rzeczywistych implementacjach memcpy, ale myślę, że urządzenie Duffa zasługuje na wzmiankę tutaj.

Z Wikipedii :

send(to, from, count)
register short *to, *from;
register count;
{
        register n = (count + 7) / 8;
        switch(count % 8) {
        case 0:      do {     *to = *from++;
        case 7:              *to = *from++;
        case 6:              *to = *from++;
        case 5:              *to = *from++;
        case 4:              *to = *from++;
        case 3:              *to = *from++;
        case 2:              *to = *from++;
        case 1:              *to = *from++;
                } while(--n > 0);
        }
}

Zauważ, że powyższe nie jest a, memcpyponieważ celowo nie zwiększa towskaźnika. Implementuje nieco inną operację: zapis do rejestru mapowanego w pamięci. Szczegółowe informacje można znaleźć w artykule w Wikipedii.

— NPE
źródło
Urządzenie Duffa, lub po prostu mechanizm początkowego skoku, jest dobrym zastosowaniem do skopiowania pierwszych 1..3 (lub 1..7) bajtów, tak aby wskaźniki były wyrównane do ładniejszej granicy, gdzie można zastosować większe instrukcje przenoszenia pamięci.
— Daemin
@MarkByers: Kod ilustruje nieco inną operację ( *toodwołuje się do rejestru mapowanego w pamięci i celowo nie jest zwiększany - zobacz artykuł powiązany). Jak pomyślałem, jasno powiedziałem, moja odpowiedź nie jest próbą zapewnienia skutecznej memcpy, po prostu wspomina o dość ciekawej technice.
— NPE
@Daemin Zgoda, jak powiedziałeś, możesz pominąć do {} while (), a przełącznik zostanie przetłumaczony na tablicę skoków przez kompilator. Bardzo przydatne, gdy chcesz zadbać o pozostałe dane. Należy wspomnieć o ostrzeżeniu dotyczącym urządzenia Duffa, najwyraźniej na nowszych architekturach (nowsza x86), przewidywanie rozgałęzień jest tak wydajne, że urządzenie Duffa jest w rzeczywistości wolniejsze niż prosta pętla.
— onemasse
1
O nie… nie urządzenie Duffa. Nie używaj urządzenia Duffa. Proszę. Użyj PGO i pozwól, że kompilator wykona dla ciebie rozwijanie pętli tam, gdzie ma to sens.
— Billy ONeal
Nie, urządzenie Duffa zdecydowanie nie jest używane w żadnej nowoczesnej implementacji.
— gnasher729
3

Jak inni mówią, kopie memcpy większe niż 1-bajtowe fragmenty. Kopiowanie fragmentów wielkości słowa jest znacznie szybsze. Jednak większość implementacji idzie o krok dalej i uruchamia kilka instrukcji MOV (słowo) przed zapętleniem. Zaletą kopiowania, powiedzmy, 8 bloków słów na pętlę jest to, że sama pętla jest kosztowna. Ta technika zmniejsza liczbę gałęzi warunkowych o współczynnik 8, optymalizując kopię dla gigantycznych bloków.

— VoidStar
źródło
1
Nie sądzę, żeby to była prawda. Możesz rozwinąć pętlę, ale nie możesz skopiować w jednej instrukcji więcej danych niż adresowalnych naraz w architekturze docelowej. Poza tym rozwijanie pętli
— wiąże się z dodatkowymi kosztami
@Billy ONeal: Nie sądzę, że to miało na myśli VoidStar. Mając kilka kolejnych instrukcji ruchu zmniejsza się narzut liczenia jednostek.
— wallyk
@Billy ONeal: Nie rozumiesz. Jedno słowo na raz to jak MOV, JMP, MOV, JMP, itd. Gdzie można zrobić MOV MOV MOV MOV JMP. Pisałem już mempcy i testowałem wiele sposobów na zrobienie tego;)
— VoidStar
@wallyk: Być może. Ale mówi „skopiuj jeszcze większe fragmenty” - co nie jest tak naprawdę możliwe. Jeśli ma na myśli rozwijanie pętli, to powinien powiedzieć „większość implementacji idzie o krok dalej i rozwija pętlę”. Odpowiedź, tak jak napisano, jest w najlepszym przypadku myląca, w najgorszym przypadku błędna.
— Billy ONeal
@VoidStar: Zgoda - teraz jest lepiej. +1.
— Billy ONeal
2

Odpowiedzi są świetne, ale jeśli nadal chcesz realizować szybki memcpysiebie, tam jest ciekawym blogu o szybkim memcpy, szybkiego memcpy w C .

void *memcpy(void* dest, const void* src, size_t count)
{
    char* dst8 = (char*)dest;
    char* src8 = (char*)src;

    if (count & 1) {
        dst8[0] = src8[0];
        dst8 += 1;
        src8 += 1;
    }

    count /= 2;
    while (count--) {
        dst8[0] = src8[0];
        dst8[1] = src8[1];

        dst8 += 2;
        src8 += 2;
    }
    return dest;
}

Nawet może być lepiej dzięki optymalizacji dostępu do pamięci.

— masoud
źródło
1

Ponieważ podobnie jak wiele procedur bibliotecznych został zoptymalizowany pod kątem architektury, na której pracujesz. Inni opublikowali różne techniki, których można użyć.

Mając wybór, używaj procedur bibliotecznych zamiast tworzyć własne. Jest to odmiana DRY, którą nazywam DRO (Don't Repeat Others). Ponadto procedury biblioteczne są mniej prawdopodobne niż Twoja własna implementacja.

Widziałem, jak programy sprawdzające dostęp do pamięci narzekały na odczyty poza zakresem w pamięci lub buforach ciągów, które nie były wielokrotnością rozmiaru słowa. Wynika to z zastosowanej optymalizacji.

— BillThor
źródło
0

Możesz przyjrzeć się implementacji memset, memcpy i memmove w systemie MacOS.

Podczas rozruchu system operacyjny określa, na którym procesorze działa. Ma wbudowany specjalnie zoptymalizowany kod dla każdego obsługiwanego procesora, a podczas rozruchu przechowuje instrukcję jmp we właściwym kodzie w stałej lokalizacji tylko do odczytu / tylko.

Implementacje memset, memcpy i memmove w C to tylko skok do tej stałej lokalizacji.

Implementacje używają innego kodu w zależności od wyrównania źródła i przeznaczenia memcpy i memmove. Oczywiście używają wszystkich dostępnych możliwości wektorów. Używają również wariantów bez buforowania podczas kopiowania dużych ilości danych i mają instrukcje, aby zminimalizować oczekiwania na tabele stron. To nie tylko kod asemblera, to kod asemblera napisany przez kogoś z bardzo dobrą znajomością każdej architektury procesora.

Intel dodał również instrukcje asemblera, które mogą przyspieszyć operacje na łańcuchach. Na przykład z instrukcją obsługi strstr, która wykonuje porównania 256 bajtów w jednym cyklu.

— gnasher729
źródło
Wersja memset / memcpy / memmove firmy Apple o otwartym kodzie źródłowym to tylko wersja ogólna, która będzie znacznie wolniejsza niż wersja rzeczywista korzystająca z SIMD
— phuclv
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.