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ć :)

[prusi]

@nme: ale to bzdura jest, bo jeśli miałbyś obie struktury w tablicy to i tak będą wyrównane. do drugiej powinieneś dodać jeszcze padding.

[neoandrew]

2 FAKTY

Kompilator intela jak zwykle zdetronizował konkurencję

.NET jest bardzo szybki jak umie się go użyć, na moim pc usprawniony przykład wykonuje się w ~0,1741 milisekundy.

[prusi]

@neoandrew: bo .NET to nie do końca maszyna wirtualna - dość powiedzieć, że taka biblioteka standardowa jest ładowana w postaci dll-ek, a kod wewnątrz jest tłumaczony właściwie tak jak w kompilatorze - jedyne czym się zajmuje maszyna dotnetowa to tłumaczenie adresów. a jeśli chodzi o kompilator intela - cóż, najlepiej znają swoją architekturę - nic dziwnego.

[neoandrew]

@kemek: Benchmark polega na sprawdzeniu ile czasu zajmuje wykonanie funkcji robiącej dokładnie to samo, ale różnymi algorytmami.

[n.....e]

Więcej jest takich ciekawostek. Np. pierwsza z tych struktur ma rozmiar 24, a druga 16.

struct Test {

int b;

long

[badasq]

@nme: W jakim języku programowania? 24 i 16 czego? A wiesz że standard nie definiuje rozmiarów typów które podałeś i zależą one od maszyny i kompilatora?

Wiem, co chciałeś pokazać (chyba wyrownanie sie to nazywalo), ale bez otoczki, czyli tak jak to przedstawiles, nie ma to najmniejszego sensu.

[Balon]

@nme: @badasq: Jesteś na dobrym tropie (tak mi się wydaje, bo nie znam polskiej terminologii). Chodzi tutaj o http://en.wikipedia.org/wiki/Data_structure_alignment . Kompilator organizuje dane w taki sposób by dostęp do nich był jak najszybszy.

[programista_abc]

@rss: Jako, ze jest to taki programistyczny wykop to nie mogem sie powstrzymac przed dodaniem komentarza na temat zjawiska ktore zaobserwowalismy u nas w firmie a po Twoim komentarzu wnisokuje, ze dostrzezesz pewne analogie do samego siebie :). Jezeli sie myle, to nie traktuj tego komentarza jako atak na siebie, a jesli trafilem to potraktuj to jako rade.

Otoz u nas w firmie, mamy tzw. "smieciowych programistow" ktorzy to pisza kod

[m.....n]

@rss:

@programista_abc:

Ale @GilbertEatingGrape pisał o regulacji gaźnika. ;)