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

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ć?

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.

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.

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.

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.

Krótka odpowiedź:

• wypełnienie pamięci podręcznej
• Jeśli to możliwe, transfery w rozmiarze wyrazy zamiast bajtów
• Magia SIMD

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.

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.

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.

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.

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.