Który kod jest lepszy do optymalizacji przewidywania gałęzi?

10

Biorąc pod uwagę przewidywania gałęzi, a także efekt optymalizacji kompilatora, który kod oferuje lepszą wydajność?

Zauważ, że bRareExceptionPresent stanowi rzadki warunek. To nie jest normalna ścieżka logiki.

/* MOST COMMON path must branch around IF clause */

bool SomeFunction(bool bRareExceptionPresent)
{
  // abort before function
  if(bRareExceptionPresent)
  {
     return false;
  }    
  .. function primary body ..    
  return true;
}

/* MOST COMMON path does NOT branch */

bool SomeFunction(bool bRareExceptionPresent)
{
  if(!bRareExceptionPresent)
  {
    .. function primary body ..
  }
  else
  {
    return false;
  }
  return true;
}
dyasta
źródło
9
Wyjdę tutaj na kończynę i powiem, że nie ma żadnej różnicy.
Robert Harvey
7
Prawdopodobnie zależy to od konkretnego procesora, dla którego się kompilujesz, ponieważ mają one różne architektury potoków (przedziały opóźnień vs brak przedziałów opóźnień). Czas poświęcony na myślenie o tym jest prawdopodobnie znacznie dłuższy niż czas zaoszczędzony podczas uruchamiania - najpierw profil, a następnie optymalizacja.
2
To prawie na pewno przedwczesna mikrooptymalizacja.
Robert Harvey
2
@MichaelT Tak, profilowanie jest rzeczywiście jedynym niezawodnym sposobem, aby dowiedzieć się, co naprawdę dzieje się z wydajnością kodu na docelowej platformie w jego kontekście. Byłem jednak ciekawy, czy ktoś jest ogólnie preferowany.
dyasta
1
@RobertHarvey: Jest to przedwczesna mikrooptymalizacja, z wyjątkiem przypadków, w których oba warunki są spełnione: (1) pętla nazywana jest miliardami (nie milionami) razy; i (2) jak na ironię, gdy korpus pętli jest niewielki pod względem kodu maszynowego. Warunek nr 2 oznacza, że ​​część czasu poświęconego na koszty ogólne nie jest nieznaczna w porównaniu do czasu poświęconego na użyteczną pracę. Dobrą wiadomością jest to, że zwykle w sytuacjach, w których oba warunki są spełnione, SIMD (wektoryzacja), która z natury jest bez rozgałęzień, rozwiąże wszystkie problemy z wydajnością.
rwong 27.04.13

Odpowiedzi:

10

W dzisiejszym świecie nie ma to większego znaczenia, jeśli w ogóle.

Prognozowanie gałęzi dynamicznych (coś, o czym myślano przez dziesięciolecia (patrz Analiza obciążeń systemu schematów prognozowania dynamicznego opublikowane w 1996 r.)) Jest dość powszechnym miejscem.

Przykład tego można znaleźć w procesorze ARM. Z centrum informacyjnego uzbrojenia w prognozach gałęzi

Aby poprawić dokładność przewidywania gałęzi, stosuje się kombinację technik statycznych i dynamicznych.

Powstaje zatem pytanie „czym jest dynamiczne przewidywanie gałęzi w procesorze uzbrojenia?” Ciągły odczyt przewidywania gałęzi dynamicznej pokazuje, że wykorzystuje on 2-bitowy schemat predykcji (opisany w artykule) budujący informacje o tym, czy gałąź jest silnie, czy słabo pobrana, czy nie.

Z biegiem czasu (a czasem mam na myśli kilka przejść przez ten blok) gromadzi to informacje o tym, w którą stronę pójdzie kod.

W przypadku przewidywania statycznego sprawdza, jak wygląda sam kod i w jaki sposób gałąź jest tworzona w teście - do poprzedniej instrukcji lub kolejnej w kodzie:

Schemat zastosowany w procesorze ARM1136JF-S przewiduje, że nie zostaną pobrane wszystkie gałęzie warunkowe do przodu i wszystkie gałęzie wsteczne. Około 65% wszystkich gałęzi poprzedza wystarczająca liczba cykli niezwiązanych z gałęziami, aby można było je całkowicie przewidzieć.

Jak wspomniał Sparky, opiera się to na zrozumieniu, że pętle częściej niż nie, pętle. Pętla rozgałęzia się do tyłu (ma gałąź na końcu pętli, aby ponownie uruchomić ją u góry) - zwykle robi to.

Niebezpieczeństwo próby odgadnięcia kompilatora polega na tym, że nie wiesz, jak ten kod zostanie skompilowany (i zoptymalizowany). I w większości nie ma to znaczenia. W przypadku przewidywania dynamicznego dwukrotnie funkcja ta przewiduje przeskakiwanie instrukcji wartownika w celu przedwczesnego powrotu. Jeśli wydajność dwóch przepłukanych rurociągów ma krytyczną wydajność, należy martwić się innymi sprawami.

Czas potrzebny do odczytania jednego stylu nad drugim ma większe znaczenie - oczyszczenie kodu, aby człowiek mógł go odczytać, ponieważ kompilator dobrze sobie poradzi, bez względu na to, jak niechlujny lub wyidealizowany zostanie kod.


źródło
7
Słynne pytanie o przepełnienie stosu pokazało, że przewidywanie gałęzi ma znaczenie, nawet dzisiaj.
Florian Margaine
3
@FlorianMargaine, mimo że ma znaczenie, staje się w sytuacji, w której tak naprawdę ma znaczenie, wydaje się, że wymaga zrozumienia tego, na czym się kompilujesz i jak to działa (uzbrojenie vs x86 vs mips ...). Pisanie kodu próbującego wykonać tę mikrooptymalizację na początku prawdopodobnie działa w błędnych przesłankach i nie osiąga pożądanego efektu.
Cóż, oczywiście, nie cytujmy DK. Ale myślę, że to pytanie było wyraźnie w sensie optymalizacji, kiedy już minąłeś etap profilowania. :-)
Florian Margaine
2
@MichaelT Ładna odpowiedź i zgadzam się bardzo z twoim wnioskiem. Ten rodzaj wstępnego profilowania / optymalizacji abstrakcyjnej może zdecydowanie przynieść efekt przeciwny do zamierzonego. Ostatecznie jest to gra polegająca na zgadywaniu, powodująca podejmowanie decyzji projektowych z irracjonalnych powodów. Mimo to byłem ciekawy; o
dyasta
5
@ 90h stackoverflow.com/questions/11227809/…
Florian Margaine
9

Rozumiem, że gdy procesor po raz pierwszy napotka gałąź, będzie przewidywał (jeśli jest obsługiwany), że gałęzie do przodu nie są pobierane, a gałęzie do tyłu są. Uzasadnieniem tego jest założenie, że pętle (które zwykle rozgałęziają się do tyłu) są przyjmowane.

Na niektórych procesorach możesz podpowiedzieć w instrukcji asemblera, która ścieżka jest bardziej prawdopodobna. Szczegóły tego w tej chwili mi uciekają.

Ponadto niektóre kompilatory C obsługują również przewidywanie gałęzi statycznych, dzięki czemu można powiedzieć kompilatorowi, która gałąź jest bardziej prawdopodobna. Z kolei może zreorganizować wygenerowany kod lub użyć zmodyfikowanych instrukcji, aby skorzystać z tych informacji (a nawet po prostu zignorować je).

__builtin_expect((long)!!(x), 1L)  /* GNU C to indicate that <x> will likely be TRUE */
__builtin_expect((long)!!(x), 0L)  /* GNU C to indicate that <x> will likely be FALSE */

Mam nadzieję że to pomoże.

iskrzący
źródło
3
„Rozumiem, że gdy procesor po raz pierwszy napotka gałąź, będzie przewidywał (jeśli jest obsługiwany), że gałęzie do przodu nie są pobierane, a gałęzie do tyłu”. To bardzo interesująca myśl. Czy masz jakieś dowody na to, że jest to rzeczywiście realizowane we wspólnych architekturach?
blubb
5
Prosto z pyska konia: Domyślnie gałąź naprzód nie jest brana. Domyślnie brana jest gałąź wstecz . I z tej samej strony: „przedrostek 0x3E - statycznie przewiduj odgałęzienie, jak zostało zrobione”.
MSalters
Czy istnieje platforma agnostyczna, która jest równoważna __builtin_expect?
MarcusJ