Optymalizacja wydajności pętli

Question

I've profilowania wąskie gardło w moim kodu (funkcja pokazana poniżej), który jest wywoływana kilka milionów razy. Mogłabym skorzystać z porad dotyczących zwiększania wydajności. Numery XXXs zostały pobrane z Sleepy.

Zestawione ze studiem wizualnym 2013, /O2 i innymi typowymi ustawieniami wydania.

indicies zwykle zawiera od 0 do 20 wartości, a inne parametry mają ten sam rozmiar (b.size() == indicies.size() == temps.size() == temps[k].size()).

1:   double Object::gradient(const size_t j, 
2:         const std::vector<double>& b, 
3:         const std::vector<size_t>& indices, 
4:         const std::vector<std::vector<double>>& temps) const 
5: 23.27s { 
6:    double sum = 0; 
7: 192.16s  for (size_t k : indices) 
8: 32.05s   if (k != j) 
9: 219.53s    sum += temps[k][j]*b[k]; 
10:  
11: 320.21s  return boost::math::isfinite(sum) ? sum : 0; 
13: 22.86s } 

Wszelkie pomysły?

Dzięki za porady facetów. Tutaj były wyniki dostałam od sugestii:

znalazłem to ciekawe, że przejście na cbegin() i cend() miał tak duży wpływ. Domyślam się, że kompilator nie jest tak inteligentny, jak mógłby. Cieszę się z uderzenia, ale wciąż jestem ciekawy, czy jest tu więcej miejsca przez rozwijanie lub wektoryzację.

Dla zainteresowanych tu mój punkt odniesienia dla isfinite(x):

boost::isfinite(x): 
------------------------ 
SPEED: 761.164 per ms 
TIME: 0.001314 ms 
    +/- 0.000023 ms 

std::isfinite(x): 
------------------------ 
SPEED: 266.835 per ms 
TIME: 0.003748 ms 
    +/- 0.000065 ms 

Answer 1

Jeśli wiesz, że warunkowe zostanie spełnione (że w każdej iteracji spełnisz k == j), wyeliminuj warunkowe i zastąp warunki zwrotu prostym magazynem warunkowym.

double sum = -(temps[j][j]*b[j]); 
for (size_t k : indices) 
    sum += temps[k][j]*b[k]; 
if (!std::isfinite(sum)) 
    sum = 0.0; 
return sum; 

Oparte na zasięgach jest wciąż na tyle nowe, aby nie zawsze uzyskać doskonałą optymalizację. Możesz również wypróbować:

const auto it = cend(indices); 
for (auto it = cbegin(indices); it != end; ++it) { 
    sum += temps[*it][j]*b[*it]; 
} 

i sprawdzić, czy wartość jest różna.

Answer 2

nie jestem pewien, że jego możliwe rozwiązania, ale należy rozważyć przechowywanie danych wejściowych tak, że feets do pamięci podręcznej procesora. Oprócz innych kosztów, takich jak niejawne wywołania begin() end(), które możesz zoptymalizować na końcu, problemy z pamięcią podręczną będą cię bolały. Nie używaj wskaźnika do wskaźnika w swoim kluczowym pod względem perfekcji kodzie. Należy również wypróbować:

for (const size_t& k : indices) 

, aby uniknąć kopiowania. Jednak może to być zoptymalizowane dla ciebie przez kompilator.

Answer 3

Istnieją dwa punkty, które wystają:

(a) boost :: Matematyka :: isFinite trwa stosunkowo długo. Jeśli to możliwe, spróbuj ustalić innymi sposobami, że twoje wyniki mieszczą się w prawidłowym zakresie.

(b) przechowywanie tablicy 2D jako wektora zagnieżdżonego nie jest postem. Prawdopodobnie byłoby szybsze uczynienie temp 1D tablicy i przekazanie rozmiaru wiersza jako parametru. Aby uzyskać dostęp do elementu, musisz sam wykonać obliczenia indeksu. Ale ponieważ jeden z indeksów (j) jest stały w pętli, możesz obliczyć indeks elementu początkowego przed pętlą, a wewnątrz po prostu zwiększyć indeks 1. To może spowodować znaczną poprawę.

Answer 4

Pierwszy stosunkowo prosta optymalizacja będę próbować, to:

const std::vector<std::vector<double>>& temps 

Jest to potencjalnie w każdym miejscu w pamięci i nie buforują przyjazne w ogóle, jak to w zasadzie dynamicznej tablicy dynamicznych tablic z oddzielna dynamiczna tablica dla każdego wiersza (lub kolumny) macierzy przechowywanej w potencjalnie zupełnie innym miejscu w pamięci.

Jeśli możesz utworzyć klasę "Matrix", która przechowuje dane w pojedynczej tablicy (np. Pojedynczy wektor), może to pomóc całkiem sporo.

Następną rzeczą, którą próbuję to:

7: 192.16s  for (size_t k : indices) 
8: 32.05s   if (k != j) 
9: 219.53s    sum += temps[k][j]*b[k]; 

Widzimy, że „j” nie zmienia się w pętli, więc jeśli „temp” może być transponowane z góry (również łatwe do zrobienia, jeśli piszesz odpowiednią klasę Matrix), możesz po prostu uzyskać dostęp do pamięci sekwencyjnie od lewej do prawej i uzyskać dostęp do wielu składników macierzy w jednej linii pamięci podręcznej.

Czy naprawdę napotykasz na nieskończoność lub NaN z wejściami, z którymi pracujesz? Gdyby to drugie, sprawdziłbym, czy mogę przenieść sprawdzanie NaN w innym miejscu, sprawdzając poprawność tych tablic temps (pod warunkiem, że wielokrotnie używałeś tych samych plików). O ile nie natknąłeś się już na awarie lub nie pracujesz z naprawdę krytycznym oprogramowaniem, spróbowałbym przekształcić tę kontrolę w asercję w trybie debugowania i obsługiwać taki przypadek skrajny, jeśli faktycznie napotkałeś go podczas produkcji.

Answer 5

Wierzę, że uzyskasz znaczący wzrost wydajności, jeśli przestawisz swój temps. Poniższy wiersz kodu

temps[k][j]*b[k]

powtórzyć poprzez wartości k jest (przynajmniej tego, co rozumiem, że jest) mnożenie jeśli (transpozycja) macierzy przez wektor. Teraz dostęp do elementu temps[k][j] polega w rzeczywistości na przeczytaniu temps[k], wydziedziczeniu go (wskaźnik do przydzielonego wektora), a następnie odczytaniu jego elementu [j].

Zamiast używać vector<vector<double> można użyć 1-wymiarowego vector Ponadto, ponieważ ta funkcja jest wąskim gardłem, można przechowywać dane w niej w "transponowany" sposób. Środki, dostęp do temps[k][j] w nowym formacie zamienia się w temps[j * N + k], gdzie "N" to zakres j. Dzięki temu bardziej wydajnie wykorzystujesz pamięć podręczną.