Dlaczego przetwarzanie posortowanej tablicy trwa krócej niż nieposortowanej?

Prosty kod napisany w C++ (jak i Javie) wykonuje się znacznie szybciej w sytuacji gdy tablica danych zostanie wcześniej posortowana. Dlaczego? Świetny przykład jak działa i jak istotne jest przewidywanie rozgałęzień w procesorach, polecam przeczytać :)

[anonim1133]

tl;dr Procesor zgaduje jaki będzie kolejny wynik działania, jeżeli się pomyli(a przy losowych danych jest na to 50% szans), to musi zaczynać od początku i liczyć.

Jeżeli zgadnie, przechodzi do kolejnej instrukcji. A przy posortowanych danych jest wysokie prawdopodobieństwo, że zgadnie.

Niżej autor wyjaśnienia prezentuje też sposób który działa równie szybko na posortowanych i nieposortowanych danych. Który w przypadku c++ działa równie szybko co przy posortowanych danych, a więc oszczędzamy czas, bo

[m_i_n]

Procesor zgaduje jaki będzie kolejny wynik działania, jeżeli się pomyli(a przy losowych danych jest na to 50% szans), to musi zaczynać od początku i liczyć.

@anonim1133: Ale skąd wie że się pomylił bądź nie? Bo jeśli wie jaki jest poprawny to po co ma zgadywać? ;) Domyślam się że zastosowałeś jakiś skrót myślowy, możesz to rozwinąć?

[_Liquid]

Nic nie rozumiem. WYKOP!

[t.....4]

Dodałem do zakładek, poczytam jak będę inteligentniejszy

[echelon_]

@t3m4: Inteligencja tu nie ma nic do gadania - raczej wiedza ;)

[czuraj]

@t3m4: @echelon_: Brzmi mądrze i do tego po angielsku - wykop bez żadnego zawahania :).

[applicative_functor]

Do autora najbardziej zaplusowanej odpowiedzi należy również rekord najdłuższego rozwinięcia dziesiętnego liczby pi, mianowicie do 10 bilionów miejsc po przecinku (10^12):

http://www.numberworld.org/misc_runs/pi-10t/details.html

[k.....e]

Ale jak to:

if (data[c] >= 128)

    sum += data[c];

zamieniło się w to

[a.....r]

@kite: To jest hack, który ma realizować dokładnie to samo co wyjściowy program.

Zastanów się co robi

int t = (data[c] - 128) >> 31

. Jeśli data[c] jest większe lub równe 128 to wyjdzie tam liczba nieujemna (a więc bit znaku

[prusi]

Cóż, właściwie można zakopać jako informację nieprawdziwą - otóż wspomniana różnica istnieje tylko gdy kompiluje się bez włączonych w kompilatorze optymalizacji - gdy się je włączy cały warunek znika i zostaje zastąpiony rozkazem cmove i problemu nie ma - pipe jest załadowany do końca, w cache całość danych (bo tablica niewielka), więc procesor to wykonuje szybciutko.

[a.....r]

@prusi: Jest napisane nawet w tej odpowiedzi, że różne kompilatory się różnie zachowują. Testowałem to u siebie i na poziomie -O2 w gcc jest widoczny wpływ sortowania. -O3 faktycznie problem rozwiązuje, ale z tego co wiem, nie jest on powszechnie stosowany (na przykład w Fedorze -O2 to był domyślny poziom optymalizacji, na gentoo chyba też był zalecany). Zawsze byłem uczony, że "-O3" może być zbyt agresywny ale być może coś

[prusi]

@almafater: w wypadkach, gdy O3 jest zbyt agresywne takie różnice w czasie wykonywania nie są istotne. bowiem nie zawsze szybkość wykonania jest priorytetem.

[Regis86]

Odżyły wspomnienia! Prof. Biernat <3

[nargil]

U mnie:

Mingw 4.7.2 (win7 natywnie)

Sorted: 7.44

Unsorted:

[prusi]

@R3d: debug i release to zestaw ustawień kompilatora i linkera, a nie jeden przełącznik w linii poleceń. w dodatku można je dowolnie zmieniać.

[R3d]

@nargil:

Różnica jest ogromna. Myślałem, że w środowiskach dostosowanych pod GCC z automatu środowisko daje -g.

Co do czasów to nie wiem jakie powinny być, ale po prostu bez -g rzeczy się inaczej wykonują. Na bank to odczujesz w MSVC i pojemnikach z STLa, kompilując z GCC powinno być podobnie.

[Cummykaze]

Miniaturka idealnie oddaje zawartość znaleziska

[xanio]

No, wreszcie coś ciekawego a nie animowany gif.

[S.....k]

@xanio: A jakby tak wyjaśnienie w formie animowanego gifu?:)