W tym artykule chciałbym przedyskutować sposoby stosowania i wydajność arytmetyki wskaźników przy poruszaniu się po tablicach. Na wstępie muszę zaznaczyć, że dosyć trudno było mi wybrać tytuł, bo nie wiedziałem jak nazwać ten problem. ;] Ale do rzeczy. Programując jeden z moich projektów zacząłem zastanawiać się nad tym, w jaki sposób można najbardziej optymalnie wykonać operacje na każdym z elementów, tak, aby był jak najmniejszy narzut na dostęp do każdego z nich. Nie mogłem znaleźć w internecie żadnych informacji, w których byłoby napisane jednoznacznie, jaką konstrukcję należy wybrać, zostałem więc zmuszony do samodzielnego przetestowania wszystkich, jakie znałem. ;]

Jako, że zamierzałem poruszać się po tablicy, potrzebna była pętla, w szranki stanęły więc instrukcje for, while i “do while”. Jeśli chodzi o wskaźniki na elementy, opcje były dwie - dostęp bezpośredni i poprzez zmienną przesunięcia [ang. offset]. W kodzie wyglądało to następująco [ptr - wskaźnik, offset - przesunięcie, value - podstawiana wartość]:

Podejście bezpośrednie [odwołanie i inkrementacja samego wskaźnika]:

(*(++ptr)) = value;

Podejście pośrednie [odwołanie do elementu odległego o wartość zmiennej przesunięcia od wskaźnika na początek tablicy i inkrementacja tej zmiennej]:

(*(ptr + offset)) = value;

Miałem zatem sześć kombinacji do przetestowania [pętla + podejście]:

  • for + bezpośrednie
  • for + pośrednie
  • while + bezpośrednie
  • while + pośrednie
  • do while + bezpośrednie
  • do while + pośrednie
Napisałem więc funkcję umożliwiającą mi pomiar wydajności każdej z kombinacji. Testy polegały na zmierzeniu czasu wykonania określonej liczby iteracji pętli testowej for [ilość testów], w której zawarta była pętla mierzona, dla której liczba iteracji była równa liczbie elementów.

Dane testowe: ilość elementów w wektorze : 100000 ilość przeprowadzonych testów : 10000 typ elementu wektora : unsigned int * wartość każdego elementu : 30000

Wyniki: While + Bezpośrednie: 827.57ms While + Pośrednie: 1352.34ms For + Bezpośrednie: 808.411ms For + Pośrednie: 812.534ms DoWhile + Bezpośrednie: 1642.39ms DoWhile + Pośrednie: 1677.97ms

Rozbieżności pomiędzy wynikami w każdym pomiarze były całkiem spore, więc trudno jednoznacznie stwierdzić, która opcja jest najlepsza. Jedyny wniosek jaki mogę wysnuć to to, że najgorsza opcja to [oczywiście oprócz pętli do while, która okazała się totalnym nieporozumieniem] pętla while + podejście pośrednie. W przypadku reszty trudno to ocenić - przewidywane przeze mnie zwycięstwo kombinacji pętli for i podejścia bezpośredniego nie zawsze wygrywało, za to mogę określić ją jako najbardziej stabilną, ponieważ miała najmniejsze wahania we wszystkich pomiarach. Ze względu na te różnice nie chciałbym nazywać jej najlepszą, ale na pewno najbardziej polecaną.

Jeśli kogoś interesuje kod, to zapraszam do mojego SVNa. Niestety nie będziecie mogli uruchomić zawartej w nim funkcji testowej, ponieważ zawiera odwołania do profilera zawartego w moich “prywatnych” bibliotekach, których niestety nie mogę udostępnić. Jeśli ktoś ma wolę uruchomić ten test u siebie, proszę bardzo, należy dopisać tylko własny kod do pomiaru czasu. ;]

Od razu informuję, że sam w ten sposób kodu nie piszę i w ogóle nie powinno się go tak pisać. Mi się po prostu nudziło, bo chciałem zmieścić wszystko na jednym ekranie. Przy okazji można na własne oczy zobaczyć na jakie cuda pozwala C++. ;]

Linki: [1] PointerArithmeticPerformanceTest.h - kod funkcji testowej w moim repozytorium.