Wskaźniki - wcale nie szybsze

Question

Witam, przerabiam aktualnie kurs pana Mirosława o C++. Doszedłem do wskaźników. Mówi on tam, że są one szybsze i na dowód pisze program, w którym pokazana jest różnica między użyciem tablicy z i bez wskaźników. Rzeczywiście, pokazuje czarno na białym, że różnica, mała bo mała, ale jest. U mnie jednak to wskaźniki są wolniejsze.

Pomyślałem, że to jakiś błąd w kodzie. Ściągnąłem kod z bloga, ale wszystko się zgadza i po odpaleniu programu to samo, wersja ze wskaźnikiem wykonuje się wolniej. O co tutaj może chodzić?

Answer 1

Który to odcinek? Spojrzę sobie na kod. :)

Comments

https://www.youtube.com/watch?v=0DQl74alJzw

Odc 10, C++

Około 13:55 ten przykład się zaczyna

---

Z całym szacunkiem dla pana Mirosława, ale przykład jest nietrafiony. Mechanizm indeksowania tablic w C++ opiera się właśnie na wskaźnikach.
Dostęp do elementu tablicy przez operator indeksowania to nic innego, jak wzięcie wskaźnika na jej zerowy element i przesunięcie o żądaną liczbę. Tutaj optymalizacja mija się z celem. Poza tym testowanie należy wykonywać kilku(nasto)krotnie, żeby wyniki były wiarygodne.
U mnie, na 32-bitowym systemie, wyniki są takie, że druga pętla zawsze wykonuje się szybciej... Niezależnie od tego, którą pętlę ustawię jako pierwszą.

Wskaźniki są szybsze tam, gdzie mamy własne obiekty, które zajmują trochę więcej miejsca, niż pojedynczy int i musimy je przekazywać np. do funkcji. Wtedy posyłamy wskaźnik, który waży te 4 bajty, zamiast kopiować obiekt, który waży więcej niż 4 bajty.

---

Wskaźniki moim zdaniem powinny być szybsze szczególnie, jeśli odwołujesz się kilka razy do tej samej komórki. Wynika to z tego, jak zazwyczaj kompilatory kodują odwołania do komórek tablicy.

Z tablicą to zazwyczaj wygląda tak:

destiny = *(array + offset * sizeof(typeof(array))); //typeof ma zwracać typ zmiennej

więc za każdym odwołaniem procesor wykona mnożenie i dodawanie z których szczególnie to pierwsze jest bardzo wolne.

Mając wskaźnik na komórkę odwołanie wygląda trywialnie:

destiny = *pointer;

Przemieszczanie się po tablicy również jest proste:

pointer += offset * sizeof(typeof(*pointer));

Oczywiście, w parze te dwie operacje będą nieco wolniejsze, bo masz aż dwa zapisy, ale jeśli wykonujesz wiele operacji na jednej komórce, to będzie to szybsze.

---

Jeśli odwołujesz się kilka razy do tej samej komórki, to niezależnie od użycia zwykłej zmiennej, czy wskaźnika, i tak procesor powinien mieć adres owej komórki w cache - takie są założenia podstawowej optymalizacji - wartości które używano przed chwilą są jeszcze 'przez chwilę' trzymane w cache, na wypadek konieczności ich ponownego użycia.

Chciałbym również zwrócić uwagę na arytmetykę wskaźników, która jest jednakowo zaimplementowana przy inkeksowaniu. Tablice to są poukrywane wskaźniki, nic więcej.

Nieprzypadkowo można równoważnie* zapisać:

int a[3][3];
int **b;

Chociaż dziś ogromną rolę pełni optymalizacja na etapie kompilacji, więc tak naprawdę czasem nie wiadomo, co da lepszy efekt (czasem optymalizacja kompilatora jest DZIWNA).

Od razu zaznaczam: jeśli głoszę jakąś herezję, to Ty, hicie02, masz prawo mnie nakierować na ścieżkę prawości. Nigdym się w ASMie nie bawił, a wiadomo, że ASM prawdę Ci powie. >.-
Swoją wiedzę opieram na doświadczeniu i różnych różnistych źródłach, więc i mogę się mylić.

---

* prawie równoważnie: pominąłem aspekt alokacji i zwalniania pamięci

---

Oczywiście, istnieje coś takiego jak cashe, ale on przechowuje tylko liczby z RAM. Nie ma zapamiętanych wyników operacji.  Kompilatory generują to magiczne mnożenie z dodawaniem, bo jest od tego osobna instrukcja i jest to dużo prostrze dla kompilatora.

Pisząc

lea EAX, [EBP + EBX * 4] ;Tu można jeszcze trochę magii zrobić
     ;ale po więcej odsyłam do manuali intela strona 82 tom 1.

 

uzyskasz w EAX adres komórki, gdzie EBP jest wskaźnikiem na tablicę, EBX jest offsetem, a 4 to rozmiar pojedyńczej komórki.

Czasami nawet może się okazać, że to jest lepsze dlatego, bo kompilator nie musi przechowywać adresu, więc ma 1 więcej wolny rejestr. Rejestr, to bardzo szybka i bardzo mała komórka pamięci w procesorze.

---

Chyba się muszę w końcu wziąć za ASMa. :)