W dniu poniedziałek, 15 kwietnia 2013 16:49:56 UTC+2 użytkownik Edek napisał:
> Procesory tak się rozwijają. M.in. Haswell i wcześniejsze są znacznie
> [...]
> na fałszywą zależność danych. Jest mnóstwo takich drobnych różnic.
No tak, jeśli dane są niezależne, to procesor (potencjalnie) może je
wykonać równolegle.

> To prawda, że kompilator sam nie zamieni booleanów na rejestr
> bitów, ale można by już sprawdzić czy bitset nie ma implementacji
> takiej, że to zadziała automagicznie. Twórcy kompilatorów tylko
> na to poświęcają mnóstwo swojego czasu, często więcej niż
> pojedynczy programista jest w stanie poświęcić na swój kod.
> Optymalne jest wykorzystanie włąsciwości kompilatora i dopisanie
> ręcznie tego, czego kompilator nie załatwia. W zasadzie dopiero
> rozumiejąc kompilator można faktycznie poznać procesor - ja
> sam często odkrywam, że to co wygląda fatalnie na pierwszy
> rzut oka jest celowym działaniem desantu intela w gcc i hula
> jednak lepiej.
Może to mój błąd że nie zaglądam do kodu wygenerowanego przez kompilator.


[...]
> Po pierwsze: cały program przyspieszył 2-4 razy czy fragment? Ja
> mówiłem o całym.
Myślę że cały. Jak jest dokładnie, to nie wiem. Nie widziałem żadnego
bardzo zaawansowanego programu na reprezentacji intuicjonistycznej, więc
nie mogę porównać. Jeśli nie mogę porównać, to dlaczego napisałem że 2-4 razy?
Otóż w reprezentacji intuicyjnej mamy planszę:
Pole plansza[8][8];

Chcemy sprawdzić czy pole (src_x,src_y) jest atakowane przez damę, więc
musimy zrobić 8 pętli, każda w innym kierunku.

W dużym przybliżeniu taki kod:

for( i=0 ; i<8 ; i++ ) {
dst_x = src_x + offset[i].x;
dst_y = src_y + offset[i].y;
while( dst_x >= 0 && dst_x < 8 && dst_y >= 0 && dst_y < 8 ) {
czy_jest_dama( plansza , dst_x , dst_y );
dst_x += offset[i].x;
dst_y += offset[i].y;
}
}

Na reprezentacji bitowej mamy:
Maski bierki[12];


Więc jedna instrukcja warunkowa daje podobny efekt jak cały kod powyżej:
if( bierki[DAMA] & maski_atakow[x][y] )


Analogiczną różnicę mamy gdy chcemy zliczyć ilość bierek. Na reprezentacji
intuicyjnej iterujemy po 64 polach. Na reprezentacji bitowej
robimy popcount - zdaje się, że to jeden takt procesora. Oczywiście dla
reprezentacji intuicyjnej też można stosować pewne zabiegi przyspieszające,
nie trzeba zawsze wykonywać 64 pętli aby policzyć jakąś statystykę. Ale
i tak myślę że przyspieszenie na reprezentacji bitowej można oszacować
na 2-4 razy. Może jeszcze dodam, że zostały opracowane specjalne tablice
masek bitowych na różne okoliczności i specjalne algorytmy indeksowania w
tych tablicach. Kto dokładnie wie... może przyspieszenie jest nawet większe
niż 4 razy.


> Po drugie szachy są niszą. Z tego co się orientuję
Tak, szachy są niszą. Ale też są przykładem aplikacji gdzie w
jakość implementacji i w jakość mini-algorytmów wielu zdolnych ludzi
włożyło dużo pracy. Na przykładzie szachów widać efekt, widać
co można uzyskać dzięki dobrej implementacji i dzięki wielu
minimalnym ulepszeniom algorytmów. Więc może w innych aplikacjach, w
których niejednemu programiście wydaje się, że implementacja jest
prawie optymalna, też by się okazało, że można wydajność poprawić o 2-4
razy?


> w innych analizach danych część ludzi wyciska każdy %, a część
> używa Javy. Oba podejścia mają sens, ja preferuję "najpierw wygoda
> a potem przepisujemy krytyczne algorytmy". Rozsądnie napisany kod nie
> jest 2x wolniejszy od optymalnego, najczęściej jest w granicach 10-20%
> max i 5-6% jako całość.
Kiedyś porównywałem szybkość wyśrubowanej (ale i tak jeszcze nieoptymalnej)
implementacji z implementacją zwykłą/rozsądną. Wyśrubowana
była w proceduralnym C++, rozsądna/wygodna była w Javie. Oba programy miały
za zadanie policzenie ilości węzłów w drzewie gry na ograniczoną z góry
głębokość. No i ta wyśrubowana była kilka razy szybsza na procesorze intel
atom N270, od tej w Javie na jakimś procesorze 64bitowym. Na tym samym
procesorze różnica była pewnie niecałe 10 razy.

Napiszę jeszcze raz to samo, może programistom często się tylko wydaje
że są w okolicach tych 10% od optimum?


> Dobry przykład na porażkę teoretycznej złożoności bez uwzględnienia
> sprzętu, tutaj cache.
> Chciałbym coś odróżnić. Jest jedna granica pomiędzy naiwnym lub zepsutym
> kodem a takim, który jest napisany rozsądnie. Druga granica dopiero
> jest pomiędzy rozsądnym a "optymalizowanym". W tej pierwszej
> usuwałem babole na 30x szybciej, w tej drugiej już +-10% to bardzo dużo.
> Zaraz ktoś rzuci przykład małego algorytmu z lepszym zyskiem,
> ale mam na myśli setki tysięcy linii kodu.

Ok, dzielmy na trzy: implementacje rozsądne, optymalne i zepsute.
Zastanawiamy się czy w sytuacji gdy mamy do czynienia z implementacją
rozsądną, to jest ona gorsza o 10% od optymalnej czy o 75% (o 75% czyli
4 razy). Nawiązuję do szachów, bo to była sytuacja w które myślałem
że mam rozsądną implementację i wielu mi podobnych myślało podobnie, a
okazało się, że w ogóle nie zdawaliśmy sobie sprawy z możliwości. Otworzyły
się nam oczy jak zobaczyliśmy źródła najlepszych programów.

Szachy nie mają setek tysięcy linii kodu. Zwykle mają kilka, kilkanaście
tysięcy, rzadko 30tys. Jednak szachy to taki specyficzny program, w który
prawie cały kod jest gorącym punktem. Nawet interfejs komunikacyjny
implementuje się wydanie, ponieważ gdy się rozgrywa turnieje na ultra-krótki
czas (np. 5s na całą grę) to zepsuta komunikacja pomiędzy programami, czy
zepsuty zapis logów do plików tekstowych, zajmuje stosunkowo duży procent
mocy obliczeniowej.

Pozdrawiam