[C++] Dlaczego nie uzyskuję przyspieszenia obliczeń...

Witam,

Nie wkleję tutaj kodu swojego program, bo jest dość duży i składa się z kilkunastu plików, ale zastanawiam się czemu nie uzyskuję żadnego przyspieszenia w związku z wykorzystaniem wielowątkowości.

Ponieważ nie udostępniam kodu (przedstawię tylko charakter obliczeń) proszę tylko o ogólne wskazówki dotyczące powodów gdzie może wystąpić spowolnienie.

Dla uproszczenia przyjmijmy że mam jedną klasę ze zmiennymi statycznymi i lokalnymi (czyli zwykłymi zmiennymi). Zmienne statyczne są tylko odczytywane, nie ma w klasie żadnych semaforów itd., każdy wątek robi swoje i nie przejmuje się drugim. Program w sumie tylko używa pamięci (mały rozmiar) i wykonuje na niej obliczenia. Wątki tworzę funkcją CreateThread(). Próbowałem z różnymi priorytetami.

I tak:

Po uruchomieniu dwóch instancji programu, w którym w każdym z nich uruchomiłem jeden wątek prędkość jest rzeczywiście dwa razy większa (porównując do pojedynczej instancji z jednym wątkiem). Średnie obciążenie procesora ~100%. I to jest ok, ale gdy:
Natomiast gdy uruchamiam jedną instancję programu, a w niej dwa wątki to nie uzyskuję żadnego przyspieszenia! Po prostu każdy wątek liczy dwa razy wolniej... Mimo to średnie obciążenie procesora ~93%

Oczywiście sprawdzałem czy wszystkie obliczenia dają poprawny wynik... Dla uproszczenia też każdy wątek (i niezależnie od tego ile ich jest) za każdym razem robi to samo...

A i wykorzystuję dość mocno pamięć podręczną - wykonuję dużo obliczeń na małej ilości danych. Większość z tych danych jest 'wspólna' dla obu wątków, aczkolwiek tylko z nich czytam, nic do nich nie zapisuję.

Właśnie sprawdziłem doświadczalnie - po powieleniu danych współdzielonych prędkość obliczeń wzrosła od razu. Czemu dane, które są dzielone między wątkami powodują aż tak duży narzut? Przecież ich nie modyfikuję i nie używam sekcji krytycznych, żeby się do nich odwołać... Jedyne co na nich robię to ich czytanie... Oczywiście dane te były inicjalizowane - ale tylko raz na samym początku działania programu.

Właśnie czytam poradnik http://www.agner.org/optimize/optimizing_cpp.pdf:

4. The different threads need separate storage. No function or class that is used by
   multiple threads should rely on static or global variables. The threads have each
   their stack. This can cause cache contentions if the threads share the same cache.
   Nie wiem czy dobrze to rozumiem - powinno być jak najmniej danych dzielonych między wątkami, nawet jeśli tylko je odczytuję (i dane te nie są też modyfikowane przez zewnętrzne procedury) i nie używam do tych celów żadnej synchronizacji?

A i mam procesor Core Duo :) Mam on jedną L2 dzieloną między oba rdzenie i każdy rdzeń ma też swój L1. Czy to jest tak, że jak jakaś dana jest w jednym L1, to nie może być w drugim? No bo co innego może powodować taki spadek wydajności?

Aplikacja dostaje czas na wykonanie swoich wątków od systemu .
Utworzenie nowego wątku może co najwyżej odebrać czas na wykonanie innemu .
Można ustawić event priorytet aby aplikacja otrzymywała więcej czasu do własnych celów .

Optymalizację raczej prowadzi się udoskonalając algorytmy obliczeń i takie wykorzystanie
wątków aby wzajemnie sobie nie przeszkadzały a nie poprzez zwiększanie ich ilości ,
co przy dostępie do wspólnych danych spowoduje spadek wydajności .

każdy wątek liczy dwa razy wolniej...

I to jest chyba ok...

A i mam procesor Core Duo Mam on jedną L2 dzieloną między oba rdzenie

Podziel wykonywanie kodu na dwa rdzenie.
Ale może lepiej i to pozostawić systemowi , wymuszanie na siłę powinowactwa danego
wątku do konkretnego procesora może utrudnić ich szeregowanie przez system i spadek
wydajności .

DaQRT, w związku z fragmentem, który przytoczyłeś, i opisem działania (wzrost nastąpił, kiedy każdy wątek dostał swoje dane), ja to widzę tak:

kiedy czytasz globalną, używasz "globalnego cache'a" L2:
pierwszy wątek odczyta, nastąpiło cache'owanie pod jego kątem
drugi wątek czyta: przetasowano cache, pod kątem drugiego
pierwszy wraca, ale cache ma rozwalony, znowu dostosować go trzeba do jego potrzeb
drugi wraca, znowu wszystko w cache'u swoim odczytem rozwala...

kiedy każdy ma swoje dane, to cache'owanie jest jest w L1, każdy wątek ma "swój L1" i nikt mu go nie rozwala. Pierwszy wątek czyta ze swojego L1 raz, cache się ułożył, czyta znowu, korzysta z cache'a, czyta znowu, i znowu... a jego L1 pięknie się do tego dopasowuje. I w drugim wątku tak samo.

Tak to sobie wyobrażam, wcale nie wiem, czy tak jest.

Problemem mogą być przestoje przy próbie dostępu do wspólnych danych, ponieważ 2 wątki nie mogą jednocześnie czytać z jednego obszaru w pamięci, przez co jeden wątek czeka, aż drugi zakończy odczyt i vice versa.

Co do pamięci typu cache, przy odczycie z niej, kiedy zaliczymy "trafienie", nie jest ona modyfikowana.

Pozdrawiam

squall, słuszne spostrzeżenie, skoro DaQRT pisze, że wątki liczą to samo, to pewnie nie ma cache missów (a więc modyfikacji cache'u), i opóźnienie wynika z tego, co mówisz.

Zalogowałem się na swoje konto (DaQRT) :)

Hmm, muszę powiedzieć, że to zachowanie się pamięci jest dla mnie prawdziwą tajemnicą...

W ogóle to implementuję silnik szukający teoretycznego wyniku gry (alfa-beta) do pewnej gry logicznej.
Planuję użycie wielowątkowości, dlatego muszę uwzględnić istnienie w pamięci danych kilku "wyszukiwań" naraz. Główna część algorytmu znajduje się w jednej klasie. Dane lokalne (tylko dla pojedynczego wyszukiwania) są "normalnymi" zmiennymi obiektu, natomiast wszystkie dane wspólne są zadeklarowane jako static.

To właśnie ten "wspólny" obszar nastręcza mi problemów. O ile danych lokalnych jest niewiele, to wszystkie tablice statyczne zajmują około 30KB pamięci. Dane te są inicjalizowane tylko raz na starcie programu. Za co są odpowiedzialne? Są to głównie maski bitowe i tak zwane tablice look-up - bardzo intensywnie z tego korzystam.

Gdy podwajam ten "wspólny obszar" w pamięci, problem znika i program faktycznie przyspiesza o około 80%. Natomiast gdy nie, to zawsze jest inaczej. Dodałem teraz element losowości w programie (na czas testów), tak, że każdy rdzeń robi zawsze co innego i jest tak, że po uruchomieniu aplikacji za każdym razem mam inną prędkość przeszukiwania węzłów gry (i na dodatek prędkość ta się nie zmienia, mimo znacznej losowości w grze).

Cóż, owe dane statyczne zajmują tylko około 30KB, więc praktycznie mogę sobie pozwolić na to by każdy rdzeń miał ich kopię. Aczkolwiek zastanawiam się jak to elegancko zaprogramować (na razie mam tak żeby działało):

1. Zmienne 'static' przerobić na zwykłe zmienne (wówczas każdy obiekt będzie miał swoje)...
2. Pójść na całość i w ogóle wszystkie zmienne/funkcje przerobić na static. Do klasy dodać szablon np template<int I>, w którym zmienna I nie będzie miała na nic wpływu, aczkolwiek po zrobieniu np Algorytm<0> a, Algorytm<1> b, kompilator podwoi mi cały kod i zmienne w pamięci. W efekcie trochę mi to przyspieszy, bo wówczas np. nie będzie wskaźnika obiektu (skoro wszystko będzie static). Tylko, że to chyba nie jest zbyt eleganckie rozwiązanie w C++...

Ogólnie bardzo mi odpowiada punkt 2), tylko chyba do niego bardziej pasuje język C...
Może ktoś z Was ma jakiś pomysł? :)

Ale o co chodzi? Każdy wątek ma tak czy inaczej własny stos. Piszesz strukturę, która zawiera wszystkie dane, piszesz w niej metody, które operują na tych danych. W głównej funkcji wątku tworzysz lokalny obiekt - na stosie, nie na stercie.

Żadnych statyków - po kiego ciula dalej chodzą ci one po głowie, skoro i tak testy ci wykazały, że współdzielenie danych jest do bani? Statyki odpadają z definicji, bo do współdzielenia właśnie służą, a nie do czego innego.

Mam deja vu, i czuję, że już to było kiedyś. Mianowicie, męczy cię wskaźnik this... Metody i zmienne statyczne nie służą do eliminowania this! Po co tworzyć w takim wypadku obiekt w ogóle?

Chcesz thisa wyeliminować? Wróć na górę postu - sposób tworzenia obiektu jest kluczowy: na stosie. A następnie:

Jeśli krytyczne metody napiszesz jako krótkie inline'y, to nie płacisz nic za wywołanie funkcji. Funkcja jest wplatana w funkcje wątku. Skoro jest wpleciona, to wskaźnik this nie jest przekazywany przez stos/rejestr/cokolwiek - adres obiektu po prostu jest znany.

Co więcej - jeśli jest to obiekt na stosie, to wskaźnik this w ogóle jest potrzebny. Kompilator może w czasie kompilacji policzyć jakie przesunięcie względem szczytu stosu ma każda zmienna-składowa obiektu - i na pewno to zrobi. A dostęp do właściwości powinien, i zapewne będzie, tak samo szybki jak do zmiennych lokalnych typów prostych. A na szybkość lokalnych to już nie narzekaj, bo cię uznam za psychopatę.

Skoro funkcje muszą być krótkie, to nie mogą być to funkcje all-in-one, raczej KISSowe helpery. A główną logiką obliczeń niech po prostu funkcja/klasa wątku się zajmuje (nie wiem, w jakiej bibliotece pracujesz, więc nie wiem, jak u ciebie wątek jest reprezentowany).

W funkcji main tworzysz jeden obiekt z danymi na stercie (new), ładujesz do niego dane skądś tam. Następnie tworzysz wątki i każdemu wątkowi przekazujesz np przez referencję te dane "startowe" - niech je sobie przekopiuje na swój stos (obiekt lokalny w funkcji). Po stworzeniu wszystkich wątków (u ciebie "aż" dwóch) i skopiowaniu przez nie danych możesz te startowe dane usunąć (delete).

I tak to widzę zrobione po ludzku, prosto i wydajnie.

Jak chcesz kombinować, bo wcale nie wierzysz, że kompilator zinline'uje funkcje albo, że dostęp do:

class {
   public:
   int a,b;
};
void run() { 
   Obiekt obiekt;
   obiekt.a = obiekt.b;
   }

jest tak samo szybki, jak dostęp do:

void run() { 
   int a,b;
   a = b;
   }

to stwórz sieczkę z samymi globalami, i zwykłymi funkcjami nań pracującymi, umieść w namespace o jakiejś nazwie. Następnie wielki copy-past i zmień nazwę namespace'a. I uruchom:

name1xav::test();
name2res::test();

ewentualnie, jak nie lubisz copy-past, to niech zrobi to za ciebie prepocesor:

moja_sieczka.inc

namespace SIECZKA_NAME {
   // sieczka
   }

main.cpp

#define SIECZKA_NAME name1xav
#include "moja_sieczka.inc"

#define SIECZKA_NAME name2res
#include "moja_sieczka.inc"

int main() {
   name1xav::test();
   name2res::test();
   }

ale to jest rozwiązanie desperata.

Ok, to zdecydowałem sie na opcję "bez-static".

A - jeden wątek
B - dwa wątki, brak zmiennych static

Zatem przyspieszenie coś koło 80% :)

Oczywiście na razie wątki działają osobno i jako tako do rozwiązywania pojedynczego węzła się to nie przydaje, ale o tym to już wcześniej myślałem i mam pomysły jak można je zesynchronizować by razem rozwiązywały jedną pozycję w grze. Teraz tylko zakodować i przetestować :)