Krótko na temat tego, czy ten sam algorytm może działać szybciej. Tak! Proste testy, które udało mi się zrobić pokazują wzrost prędkości o ok. 30% przy odpowiednim czarowaniu z danymi, bez ingerencji w sam algorytm.
Skoro nie ruszamy O(n) ani algorytmy, to o czym mowa? O cache procesora i cache instrukcji. Weźmy na przykład ukochanego przez niektórych akademików Quick Sorta. Ze swoim O(n log n) działa szybciej niż Buble Sort z O(n*n). Ale czy na pewno? Na uczelni za to ostatnie pytanie można dostać 2.0 i zostać oddelegowanym na ten sam rok, tylko rok później 🙂
L1, L2, L3, ram i swap
Większość programistów powinna kojarzyć czym jest cache procesora, ram i swap (lub plik wymiany w znienawidzonych przeze mnie okienkach). Większość też kojarzy jak różni się prędkość zapisu do poszczególnych pamięci, albo chociaż wie, że im bardziej w prawo w tej liście, tym wolniej. Natomiast mało który programista zapytany jak skorzystać z cache procesora będzie wiedział jak to się robi. “Gdzieś kiedyś na studiach było, ale dawno i pewnie się pozmieniało, no i pewnie java/python/js zoptymalizuje za mnie”.
A gdyby ktoś Ci powiedział, że układając odpowiednio dane w pamięci możesz przyspieszyć swój kod? No może kosztem jego czytelności.
L1 i RAM tak samo jak RAM i Swap
Korzystanie ze swapu jest dla większości oczywiste – gdy coś się nie mieści w RAM’ie, to wędruje na dysk. Podobnie jest z cache każdego poziomu. Jeśli procesor nie jest w stanie pomieścić przetwarzanych danych w cache, to wymienia jego zawartość na nowe, aktualnie potrzebne dane z RAM’u. I tak jak ze swap’em, dzieje się to nie pojedynczych bajtach, ale całych blokach danych.
Gdybyś miał zrobić program, który nie zmieści się w ramie, to prawdopodobnie zaprojektowałbyś dostęp do pamięci tak, aby jak najmniej skakać po pamięci i powodować wymianę stron z dysku. Podobnie możesz zrobić z przetwarzaniem danych i trzymaniem ich w cache. Efekt nie jest tak zauważalny jak przy swapowaniu, które dosłownie zabija wydajność, ale porównując da się zobaczyć sporą różnicę, nawet 30%.
Zróbmy przykład!
Zacznijmy od prostego przykładu – zróbmy z dwóch czarno białych zdjęć jedno, będące średnią jasności. Na przykład:
char image1[width*height]; char image2[width*height]; // Load images char image_diff[width*height]; for (int x = 0; x < width; x++) { for (int y = 0; y < height; y++) { image_diff[y*width + x] = (image1[y*width + x] + image1[y*width + x]) / 2 } } |
Na pierwszy rzut oka kodu nie da się zbytnio zoptymalizować. Jeśli tylko dane są ułożone kolumnami (tj. cała pierwsza kolumna, później cała druga itd.), to nie będziemy odczuwać zbyt dużego efektu przeładowywania cache i program zadziała.
Jeśli natomiast dane w obrazkach są ułożone wierszami, to już tutaj tracimy cały zysk z cache (które jest ładowane przez procesor transparentnie dla programisty). Dane pierwszego i drugiego piksela leżą w obszarach na tyle oddalonych od siebie, że konieczne jest przeładowanie zawartości cache, co spowolni nasz program do prędkości działania RAM’u.
Co jeszcze zoptymalizować?
Wydaje się, że takie ułożenie to wszystko, na co możemy się porwać, aby było szybciej. Ale nie – jest jeszcze jedna możliwość. Każda iteracja powyższej pętli odwołuje się do trzech różnych obszarów RAM’u. Pierwsze dwa to obrazki źródłowe, natomiast trzeci to obrazek z wynikiem.
Możemy tak ułożyć nasze dane, aby wszystkie trzy obszary przepleść pomiędzy sobą. Dzięki temu kod programu będzie generował żądanie pobrania bloku danych do cache 3 razy częściej, ale tylko w jednym miejscu kodu i tylko jednego (zamiast oryginalnych trzech). W przetwarzaniu potokowym, w które wyposażona jest teraz większość procesorów spowoduje to, że informacja o konieczności pobrania strony pojawia się dość szybko i jest realizowana, gdy pozostała część procesora jeszcze ma co robić.
char images[width*height*3]; // Load images... for (int i = 0; i < width*height; i++) { images[i*3] = (images[i*3 + 1] + images[i*3 + 2])/2; } |
W sumie ilość tzw. cache miss w L1, gdy potrzebny obszar pamięci nie jest w cache jest taka sama, ale docelowo zawartość cache L2 (lub niższych) pozwala wczytać te dane trochę szybciej i w praktyce ten sam algorytm wykonuje się ze znaczącą różnicą. W testach na Core2Duo, przy przetwarzaniu 20M bajtów było to około 30%.
Wracając do naszego akademickiego przykładu Buble Sort vs. Quick Sort – w przypadku dużych dysproporcji w prędkościach przetwarzania danych i ilości tych danych, lepsza złożoność może być “zjedzona” przez ilość cache-miss generowanych przez Quick Sort, względem Buble Sort idącego prosto przez pamięć, bez skoków. Prawdopodobnie nie będzie to częsty przypadek, ale też należy mieć go na uwadze 🙂
Pozostają jeszcze kwestie takie jak instruction cache i przewidywanie skoków w procesorze, ale do tego odsyłam do wujka google.
Zanim zmierzysz 64ns
Przy testach warto też wziąć pod uwagę optymalizacje kompilatorów. Gcc widząc pętle, z której wyników nikt później nie korzysta (pierwsza, wolniejsza wersja kodu) potrafi ją całkowicie wyciąć z binarnego kodu. Z taką wydajnością wtedy ciężko walczyć 🙂