Wydajność: tablice vs wskaźniki
[[3]}dostęp do pamięci przez wskaźniki jest uważany za bardziej wydajny niż dostęp do pamięci przez tablicę. Uczę się C, a powyższe jest podane w K & R. konkretnie mówią
Każda operacja, która może być osiągnięta przez zapisanie tablicy, może być również wykonywana za pomocą wskaźników. Wersja wskaźnika będzie ogólnie szybsza
Stworzyłem poniższy kod używając visual C++.(Mój to procesor 686. Wyłączyłem wszystkie optymalizacje.)
int a[10], *p = a, temp;
void foo()
{
temp = a[0];
temp = *p;
}
Ku mojemu zdziwieniu I zobacz, że dostęp do pamięci przez wskaźnik zabiera 3 Instrukcje do dwóch pobranych przez dostęp do pamięci przez tablicę. Poniżej znajduje się odpowiedni kod.
; 5 : temp = a[0];
mov eax, DWORD PTR _a
mov DWORD PTR _temp, eax
; 6 : temp = *p;
mov eax, DWORD PTR _p
mov ecx, DWORD PTR [eax]
mov DWORD PTR _temp, ecx
Jak wskazuje wiele odpowiedzi i komentarzy, użyłem stałej czasowej kompilacji jako indeksu tablicy, dzięki czemu prawdopodobnie łatwiej jest uzyskać dostęp przez tablicę. Poniżej znajduje się kod złożenia ze zmienną jako indeks. Mam teraz taką samą liczbę instrukcji dla dostęp przez wskaźnik i tablice. Moje szersze pytania nadal są dobre. Dostęp do pamięci przez wskaźnik nie jest bardziej wydajny.
; 7 : temp = a[i];
mov eax, DWORD PTR _i
mov ecx, DWORD PTR _a[eax*4]
mov DWORD PTR _temp, ecx
; 8 :
; 9 :
; 10 : temp = *p;
mov eax, DWORD PTR _p
mov ecx, DWORD PTR [eax]
mov DWORD PTR _temp, ecx
13 answers
[24]}dostęp do pamięci przez wskaźniki jest uważany za bardziej wydajny niż dostęp do pamięci przez tablicę.
To mogło być prawdą w przeszłości, kiedy Kompilatory były stosunkowo głupimi bestiami. Wystarczy spojrzeć na Część kodu wyjściowego gcc w trybach wysokiej optymalizacji, aby wiedzieć, że nie jest to już prawda. Część tego kodu jest bardzo trudna do zrozumienia, ale gdy już to zrobisz, jego blask jest oczywisty.
Porządny kompilator wygeneruje ten sam kod dla wskaźnika dostęp i dostęp do tablicy i prawdopodobnie nie powinieneś martwić się o ten poziom wydajności. Ludzie piszący Kompilatory wiedzą znacznie więcej o swoich architekturach docelowych niż my zwykli śmiertelnicy. Podczas optymalizacji kodu skoncentruj się bardziej na poziomie makr (wybór algorytmu itd.) i zaufaj twórcom narzędzi, którzy wykonają swoją pracę.
W rzeczywistości jestem zaskoczony, że kompilator nie zoptymalizował całego
temp = a[0];
Linia nie istnieje, ponieważ temp jest nadpisana w następny wiersz o innej wartości i {[7] } nie jest w żaden sposób oznaczony volatile.
Pamiętam miejski mit z dawno temu o benchmarku dla najnowszego kompilatora Vax Fortran (pokazującego mój wiek tutaj), który przewyższył swoich konkurentów o kilka rzędów wielkości.
Okazuje się, że kompilator zorientował się, że wynik z obliczeń benchmarkowych nie został nigdzie wykorzystany, więc zoptymalizował całą pętlę obliczeń w zapomnienie. Stąd znaczna poprawa przebiegu speed.
Update: powodem, dla którego zoptymalizowany kod jest bardziej wydajny w twoim konkretnym przypadku, jest sposób, w jaki znajdujesz lokalizację. a będzie w ustalonym miejscu ustalonym w czasie połączenia / ładowania, a odniesienie do niego zostanie ustalone w tym samym czasie. Więc a[0] lub rzeczywiście {[11] } będzie w ustalonym miejscu.
I p z tego samego powodu również będzie w ustalonym miejscu. ale *p (zawartość p) jest zmienna i dlatego będzie miał dodatkowe wyszukiwanie zaangażowane, aby znaleźć poprawną lokalizację pamięci.
Prawdopodobnie przekonasz się, że ustawienie kolejnej zmiennej x na 0 (Nie const) i użycie a[x] również wprowadziłoby dodatkowe obliczenia.
W jednym z twoich komentarzy stwierdzasz:
Wykonanie zgodnie z sugestiami zaowocowało 3 instrukcjami dostępu do pamięci przez tablice (fetch index, fetch value of array element, store in temp). Ale nadal nie jestem w stanie dostrzec skuteczności. :-(
Moja odpowiedź na to jest to, że bardzo prawdopodobne nie będzie zobaczyć skuteczność w użyciu wskaźników. Nowoczesne Kompilatory są bardziej niż do zadania dowiedzieć się, że operacje tablicowe i operacje pointer mogą być przekształcone w ten sam podstawowy kod maszynowy.
W rzeczywistości, bez włączonej optymalizacji, kod wskaźnika może być mniej efektywny . Rozważmy następujące tłumaczenia:
int *pa, i, a[10];
for (i = 0; i < 10; i++)
a[i] = 100;
/*
movl $0, -16(%ebp) ; this is i, init to 0
L2:
cmpl $9, -16(%ebp) ; from 0 to 9
jg L3
movl -16(%ebp), %eax ; load i into register
movl $100, -72(%ebp,%eax,4) ; store 100 based on array/i
leal -16(%ebp), %eax ; get address of i
incl (%eax) ; increment
jmp L2 ; and loop
L3:
*/
for (pa = a; pa < a + 10; pa++)
*pa = 100;
/*
leal -72(%ebp), %eax
movl %eax, -12(%ebp) ; this is pa, init to &a[0]
L5:
leal -72(%ebp), %eax
addl $40, %eax
cmpl -12(%ebp), %eax ; is pa at &(a[10])
jbe L6 ; yes, stop
movl -12(%ebp), %eax ; get pa
movl $100, (%eax) ; store 100
leal -12(%ebp), %eax ; get pa
addl $4, (%eax) ; add 4 (sizeof int)
jmp L5 ; loop around
L6:
*/
Z tego przykładu widać, że wskaźnik przykład jest dłuższy, a niepotrzebnie tak . Ładuje pa do %eax wiele razy, bez zmiany i rzeczywiście zmienia %eax między pa i &(a[10]). Domyślna optymalizacja jest tutaj w zasadzie żadna.
xorl %eax, %eax
L5:
movl $100, %edx
movl %edx, -56(%ebp,%eax,4)
incl %eax
cmpl $9, %eax
jle L5
Dla wersji tablicy oraz:
leal -56(%ebp), %eax
leal -16(%ebp), %edx
jmp L14
L16:
movl $100, (%eax)
addl $4, %eax
L14:
cmpl %eax, %edx
ja L16
Dla wersji pointera.
Nie zamierzam robić analizy cykli zegarowych tutaj (ponieważ to za dużo pracy i jestem zasadniczo leniwy), ale zwrócę uwagę na jedną rzecz. Nie ma wielkiej różnicy w kodzie obu wersji pod względem instrukcji asemblera, a biorąc pod uwagę szybkość, z jaką działają współczesne Procesory, nie zauważysz różnicy, chyba że wykonasz {42]}miliardy {43]} tych operacji. Zawsze wolę pisać kod dla czytelności i martwić się tylko o wydajność, jeśli stanie się to problemem.
Na marginesie, to stwierdzenie, do którego się odwołujesz:
5.3 Tablice: wersja ze wskaźnikiem będzie na ogół szybsza, ale przynajmniej dla niewtajemniczonych, nieco trudniejsza do opanowania od razu.
Pochodzi z najwcześniejszych wersji K & R, w tym mojej starożytnej z 1978 roku, gdzie funkcje są nadal napisane:
getint(pn)
int *pn;
{
...
}
Kompilatory przebyły strasznie długą drogę od tamtego czasu.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-11-11 04:59:12
Jeśli programujesz platformy wbudowane, szybko dowiadujesz się, że metoda wskaźnika jest o wiele szybsza niż użycie indeksu.
struct bar a[10], *p;
void foo()
{
int i;
// slow loop
for (i = 0; i < 10; ++i)
printf( a[i].value);
// faster loop
for (p = a; p < &a[10]; ++p)
printf( p->value);
}
Wolna pętla musi obliczyć a + (i * sizeof(struct bar)) za każdym razem przez, podczas gdy druga musi dodać sizeof (struct bar) do p za każdym razem przez. Operacja multiply wykorzystuje więcej cykli zegara niż add na wielu procesorach.
Naprawdę zaczynasz dostrzegać ulepszenia, jeśli wielokrotnie odwoływasz się do[i] wewnątrz pętli. Niektóre Kompilatory nie buforują tego adresu, więc może on być wielokrotnie przeliczany wewnątrz pętli.
Spróbuj zaktualizować swoją próbkę, aby użyć struktury i odwołać się do wielu elementów.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-02-21 15:49:24
W pierwszym przypadku kompilator zna bezpośrednio adres tablicy (która jest również adresem pierwszego elementu) i uzyskuje do niej dostęp. W drugim przypadku zna adres wskaźnika i odczytuje jego wartość, która wskazuje na to miejsce pamięci. To właściwie jedna dodatkowa opcja, więc prawdopodobnie jest wolniejsza.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-02-21 12:00:28
Prędkość uzyskuje się przede wszystkim w pętlach. Kiedy używasz tablicy, używasz licznika, który zwiększasz. Aby obliczyć pozycję, system mnoży ten licznik o rozmiar elementu tablicy, a następnie doda adres pierwszego elementu, który otrzyma adres. W przypadku wskaźników, wszystko, co musisz zrobić, aby przejść do następnego elementu, to zwiększyć bieżący wskaźnik o rozmiar elementu, aby uzyskać następny, zakładając, że wszystkie elementy są obok siebie w pamięci.
Pointer arytmetyka zajmuje więc nieco mniej obliczeń podczas wykonywania pętli. Ponadto, posiadanie wskaźników do prawego elementu jest szybsze niż użycie indeksu w tablicy.
Współczesny rozwój powoli pozbywa się jednak wielu operacji pointerowych. Procesory są coraz szybsze, a tablice są łatwiejsze w zarządzaniu niż wskaźniki. Ponadto tablice mają tendencję do zmniejszania ilości błędów w kodzie. Tablica umożliwia sprawdzanie indeksów, upewniając się, że nie masz dostępu do danych poza tablicą.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-02-21 12:19:51
Jak powiedział paxdiablo, każdy nowy kompilator uczyni je bardzo podobnymi.
Co więcej, widziałem sytuacje, w których tablica była szybsza niż wskaźniki. Było to na procesorze DSP, który wykorzystuje operacje wektorowe.
W tym przypadku używanie tablic było podobne do używania wskaźników restrict . Ponieważ używając dwóch tablic kompilator-w domyśle - wie, że nie wskazują na to samo miejsce. Ale jeśli masz do czynienia ze wskaźnikiem 2, kompilator może pomyśleć, że wskazują na to samo miejsce i będzie pomiń podszewkę rury.
Na przykład:
int a[10],b[10],c[10];
int *pa=a, *pb=b, *pc=c;
int i;
// fill a and b.
fill_arrays(a,b);
// set c[i] = a[i]+b[i];
for (i = 0; i<10; i++)
{
c[i] = a[i] + b[i];
}
// set *pc++ = *pa++ + *pb++;
for (i = 0; i<10; i++)
{
*pc++ = *pa++ + *pb++;
}
W przypadku 1 kompilator z łatwością dokona dodawania a i b oraz zapisania wartości do c.
W przypadku 2 kompilator nie nadpisuje a lub b podczas zapisywania do C.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-02-21 12:21:08
Wskaźniki w naturalny sposób wyrażają proste zmienne indukcyjne, podczas gdy indeksy dolne z natury wymagają bardziej wyrafinowanych optymalizacji kompilatora
W wielu przypadkach samo użycie subscripted expression wymaga dodania dodatkowej warstwy do problemu. Pętla, która zwiększa indeks dolny i może być traktowana jako maszyna stanowa, a wyrażenie a [i] technicznie wymaga, za każdym razem, gdy jest używane, aby i być pomnożone razy rozmiar każdego elementu i dodany do adresu bazowego.
W celu przekształcenia wzorca dostępu w wskaźnik, kompilator musi przeanalizować całą pętlę i stwierdzić, że, powiedzmy, każdy element jest dostępny. Następnie kompilator może zastąpić wiele przypadków pomnożenia indeksu dolnego przez Rozmiar elementu prostym przyrostem poprzedniej wartości pętli. Proces ten łączy w sobie optymalizacje zwane wspólna eliminacja podwyrażeń oraz indukcja zmienna redukcja siły.
Podczas pisania ze wskaźnikami, cały proces optymalizacji nie jest konieczny, ponieważ programista zwykle przechodzi przez tablicę, aby zacząć.
Czasami kompilator może dokonać optymalizacji, a czasami nie. w ostatnich latach coraz częściej można mieć pod ręką zaawansowany kompilator, więc kod oparty na wskaźnikach jest nie zawsze szybszy .
Ponieważ arrrays zwykle muszą być przyległe, inny zaletą wskaźników jest tworzenie przyrostowo przydzielanych struktur kompozytowych.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-02-22 01:58:02
Jest to bardzo stare pytanie i zostało już udzielone, jako takie nie muszę odpowiadać! Jednak nie zauważyłem prostej odpowiedzi, więc ją udzielam.
Odpowiedź: dostęp pośredni (pointer / array) "może" dodać jedną dodatkową instrukcję do załadowania adresu (bazowego), ale wszystkie dostępy po nim (elementy w przypadku array / Member w przypadku pointer to struct) powinny być tylko jedną instrukcją, ponieważ jest to zwykłe dodanie przesunięcia do adresu (bazowego), który jest już załadowany. Tak więc w sposób będzie tak dobry, jak bezpośredni dostęp. Jako takie, w większości przypadków dostęp przez tablicę / wskaźnik jest równoważny, a dostęp do elementów jest równie dobry jak bezpośredni dostęp do zmiennej.
Ex. jeśli posiadam tablicę (lub wskaźnik) z 10 elementami lub strukturę z 10 członkami (dostęp do niej poprzez wskaźnik do struktury) i uzyskuję dostęp do elementu/elementu, jedna możliwa dodatkowa instrukcja jest wymagana tylko raz na początku. Dostęp do wszystkich elementów / członków to powinna być tylko jedna instrukcja.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-08-02 21:53:06
Dostajesz tu dobre odpowiedzi na swoje pytanie, ale skoro się uczysz, warto podkreślić, że efektywność na tym poziomie jest rzadko zauważalna.
Kiedy dostrajasz program dla maksymalnej wydajności, powinieneś poświęcić przynajmniej tyle uwagi znajdowaniu i naprawianiu większych problemów w strukturze programu. Po ich usunięciu optymalizacje niskiego poziomu mogą jeszcze bardziej zmienić.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 12:34:37
Wskaźniki były szybsze od tablic. Na pewno z powrotem, gdy język C został zaprojektowany wskaźniki były dość szybsze. Ale w dzisiejszych czasach optymalizatory mogą zwykle lepiej optymalizować tablice niż w przypadku wskaźników, ponieważ tablice są bardziej ograniczone.
Zestawy instrukcji nowoczesnych procesorów zostały również zaprojektowane w celu optymalizacji dostępu do macierzy.
Więc najważniejsze jest to, że tablice są często szybsze w dzisiejszych czasach, zwłaszcza gdy są używane w pętlach z indeksem zmienne.
Oczywiście nadal chcesz używać wskaźników do takich rzeczy jak listy połączone, ale stara optymalizacja czasu przechodzenia wskaźnika przez tablicę zamiast używania zmiennej indeksowej jest teraz prawdopodobnie optymalizacją dis.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-02-21 21:37:35
"wersja wskaźnika będzie w ogóle szybsza" oznacza, że w większości przypadków kompilator może łatwiej wygenerować bardziej wydajny kod mający wskaźnik (który musi być po prostu dereferowany) niż mający tablicę i indeks dolny (co oznacza, że kompilator musi przesunąć adres Od początku tablicy). Jednak w przypadku nowoczesnych procesorów i kompilatorów optymalizujących dostęp do tablicy w typowym przypadku nie jest wolniejszy niż dostęp do wskaźnika.
Konkretnie w Twoim przypadku, trzeba włączyć optymalizację, aby uzyskać ten sam wynik.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-02-21 12:04:48
Ponieważ 0 jest definiowane jako stała, a[0] jest również stałą, a kompilator wie, gdzie jest w czasie kompilacji. W" normalnym " przypadku kompilator musiałby obliczyć adres elementu z bazy + offset (przy czym offset jest skalowany zgodnie z rozmiarem elementu).
OTOH, P jest zmienną, a indirection wymaga dodatkowego ruchu.
Ogólnie rzecz biorąc, indeks tablicy jest wewnętrznie obsługiwany jako arytmetyka wskaźnika, więc nie jestem pewien, czy widzę punkt, że K & R był staram się.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-02-21 12:05:03
Ponieważ większość ludzi udzieliła już szczegółowych odpowiedzi, podam intuicyjny przykład. Jeśli używasz tablicy i wskaźnika w większej skali, wydajność używania wskaźnika będzie bardziej znacząca. Na przykład, jeśli chcesz posortować duży, długi zestaw danych int, sortując go na kilka podzbiorów, a następnie scalić je.
long int * testData = calloc(N, sizeof(long int));
Dla codziennych maszyn 8G ram w 2017 r. możemy ustawić N na tak duże, jak 400000000, co oznacza, że będziesz używał mniej więcej 1,5 g pamięci dla tych oryginalnych danych gotowi. A jeśli używasz MPI, możesz szybko oddzielić swoje dane za pomocą
MPI_Scatterv(testData, partitionLength, partitionIndex, MPI_LONG, MPI_IN_PLACE, N/number_of_thread, MPI_LONG, 0, MPI_COMM_WORLD);
Możesz po prostu traktować paritionLength jako wskaźnik, który przechowuje N/number_of_thread jako długość dla każdej identycznej części, i traktować partitionIndex jako wskaźnik, który przechowuje N/number_of_threads w indeksie increamently . Załóżmy, że masz 4-rdzeniowy procesor i oddzielasz zadanie tylko w 4 wątkach. MPI na pewno wykona pracę w szybkim sensie przez referencje. Ale jeśli używasz tablicy, ta procedura musi uruchomić wskaźnik arytmetyka na tablicy, aby najpierw znaleźć punkt partycji. Co nie jest tak bezpośrednie jak wskaźnik. Ponadto, podczas scalania partycjonowanego zestawu danych, możesz użyć K-way merge do przyspieszenia. Potrzebujesz przestrzeni tymczasowej do przechowywania czterech posortowanych zestawów danych. Tutaj, jeśli używasz wskaźnika, musisz tylko przechowywać 4 adresy. Jeśli jednak użyjesz tablicy, będzie ona przechowywać 4 całe tablice podrzędne, co nie jest efektywne. Czasami, jeśli nie używasz MPI_Barrier, aby upewnić się, że twój program jest bezpieczny dla wątków, MPI może nawet narzekać że Twoja implementacja pamięci jest zła. Mam maszynę 32G do sortowania 400000000 długich wartości na 8 wątkach metodą array i metodą pointer, mam odpowiednio 11.054980 s i 13.182739 s. A jeśli zwiększę rozmiar do 1000000000, mój program sortujący nie zostanie pomyślnie uruchomiony, jeśli używam tablicy. Dlatego wiele osób używa wskaźników dla każdej struktury danych z wyjątkiem skalarów w C.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-04 17:02:34
Jestem trochę zaskoczony dyskusją ptr szybszą niż tablica, gdzie dowód na to, że tak nie jest, podaje początkowo kod asm z Abhijith.
Mov eax, dord ptr _a; / / Wczytaj bezpośrednio wartość z adresu _a
Vs
Mov eax, dword ptr _p; / / załaduj adres / wartość p do eax
I
Mov ecx, dword ptr [eax]; / / użyj załadowanego adresu, aby uzyskać dostęp do wartości i umieścić w ecx
An array reprezentuje stały adres, więc cpu może uzyskać do niego bezpośredni dostęp, a nie w przypadku ptr, aby cpu mógł uzyskać dostęp do wartości, musi być ona zdereferowana!
Druga partia kodu nie jest comareable, ponieważ offset tablicy musi być kalulowany, aby to zrobić dla ptr, potrzebujesz co najmniej 1/2 więcej instrukcji!
Wszystko, co kompilator może wywnioskować w czasie kompilacji (stałe adresy, offsety itp.) jest kluczem do wykonania kodu. Porównywanie kodu iteracyjnego i przypisywanie do vars:
Array:
; 2791: tmp = buf_ai[ l];
mov eax, DWORD PTR _l$[ebp]
mov ecx, DWORD PTR _buf_ai$[ebp+eax*4]
mov DWORD PTR _tmp$[ebp], ecx
Vs
PTR
; 2796: tmp2 = * p;
mov eax, DWORD PTR _p$[ebp]
mov ecx, DWORD PTR [eax]
mov DWORD PTR _tmp2$[ebp], ecx
Plus
; 2801: ++P;
mov eax, DWORD PTR _p$[ebp]
add eax, 4
mov DWORD PTR _p$[ebp], eax
To po prostu dla PTR załaduj adres pierwszy niż użyj go w porównaniu do tablicy użyj adresu i uzyskaj wartość jednocześnie!
Pozdrawiam
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-06-06 11:12:44