Przewidywanie skoków w procesorze

Przeanalizujmy następujący program.

const n = 10000000;
int P[n];

for (int i = 0; i < n; i++)
  scanf("%d", &p[i]);

for (int i = 0; i < n; i++)
{
  if (p[i] < N/2) ++w;
  else ++y;

  if (p[(i+100)%N] < N/2) ++w;
  else ++h;
}

Program na wejściu dostaje permutację liczb 1, 2, ..., n. Program nie liczy nic ciekawego. Ważną rzeczą jest, że dla dowolnej permutacji każda instrukcja w programie zostanie wykonana dokładnie taką samą ilość razy. Mimo to dla permutacji <1, 2, ..., n> program działa szybciej niż dla jakiejkolwiek losowej permutacji:

Losowa permutacja: 4.07 s
Posortowane dane: 3.91 s

Minimalnej różnicy mogliśmy się spodziewać. Czas działania tego programu jest opóźniony przez operację wejścia / wyjścia. Jednak dlaczego program na posortowanych danych działa szybciej?

W każdym programie około 10% instrukcji to skoki. Problemem dla procesora są zwłaszcza tak zwane skoki warunkowe. Gdy procesor wykonuje jakąś komendę, to następne instrukcje już lądują w specjalnej kolejce do tego przeznaczonej. W sytuacji w której wykonujemy skok warunkowy, nie możemy stwierdzić które instrukcje powinny być następnie wykonywane, dopóki nie zostanie sprawdzony warunek. Jednak czekając tak długo tracimy cenne cykle procesora... Jest jednak wyjście z tej sytuacji.

Procesor gdy napotyka na skok warunkowy próbuje "przewidzieć" wynik skoku i odpowiednie instrukcje trafiają do kolejki. Jeśli procesor "zgadł", to instrukcje są wykonywane normalnie. W przeciwnym przypadku instrukcje znajdujące w kolejce są anulowane i wszelkie efekty działania tych instrukcji (tak, tak - procesor czasem wykona te operacje), a do kolejki trafiają poprawne instrukcje.

W sytuacji w której dane są posortowane - procesorowi będzie łatwiej przewidzieć skoki, podczas gdy dla losowych danych takie przewidywania są niemal niemożliwe. Dlatego program dla danych posortowanych działał szybciej.

Jaki jest morał z tego wykładu? Przecież zwykle nie mamy wpływu na dane wejściowe. Zgadza się! Ale czasami chcielibyśmy obliczyć ile program działa w najgorszym wypadku. Mimo, że permutacja <1, 2, ..., n> jest największa z możliwych, a każda instrukcja wykonywana jest w każdej permutacji taką samą ilość razy, to jednak to nie jest najgorsza możliwa permutacja dla tego programu.. Niejeden programista się na tym przejechał.

Mały FAQ dla chcących wiedzieć więcej:
Jak dobrze procesor "przewiduje skoki"? Bardzo dobrze. W zależności od procesora ok 70 - 90%.
Czy gra jest warta świeczki? Czy procesor po prostu nie mógłby poczekać aż zostanie obliczony warunek skoku? Nie! Jeśli w kolejce trzymanych jest 100 operacji to wśród nich jest około 10 skoków! Bez zgadywania w takiej sytuacji procesor byłby 10-krotnie mniej wydajny.
Na podstawie czego procesor przewiduje skoki? Istnieją dwie metody. Pierwsza z nich to metoda statyczna. Każdemu skokowi przyporządkowuje przepowiednię. Faktycznie - dla większości skoków możemy powiedzieć, która z opcji będzie częściej wykonywana po warunku. Druga metoda to metoda dynamiczna. Dla każdego skoku spamiętujemy jego ostatnie wyniki. Na podstawie nich obliczamy naszą "przepowiednię".
Coś więcej na temat algorytmu dynamicznego? Spragnionych wiedzy odsyłam do wyszukiwarki google.