Dnia Sun, 14 Apr 2013 21:10:46 -0700 po głębokim namyśle M.M. rzekł:

> W dniu poniedziałek, 15 kwietnia 2013 01:14:17 UTC+2 użytkownik Edek
> napisał:
>
> Zaraz zaczniemy się "kłócić" o to gdzie leży granica pomiędzy
> optymalizacją algorytmiczną a implementacyjną :)

Jedna często wymusza drugą.

>> Właśnie nie, dobrze napisany w C++ kod będzie odporny na działanie
>> czasu. Jedynie trzeba założyć jakiś margines fluktuacji.
> Zgodzę się że będzie, ale dodam, że nie ma cudów. Dobrze napisany kod w
> C++ nawet będzie coraz lepszy, bo kompilatory się wciąż rozwijają, a kto
> wie, może twórcy procesorów zaczną procesory robić tak, aby szybciej
> wykonywały taki kod, jaki kompilator jest w stanie wygenerować. Ale
> właśnie nie ma cudów. Kompilator sam nie zorientuje się, że w takich
> szachach mamy 64 pola na planszy i docelowy procesor też ma 64 bity w
> rejestrze. Kompilator nie zmieni sam szachownica[64], na kilka masek z
> long long.

Procesory tak się rozwijają. M.in. Haswell i wcześniejsze są znacznie
bardziej tolerancyjne dla kiepskiego kodu. Wykonują kod szybciej
nie dlatego, że mają nowe istrukcje - chociaż to też - tylko np.
lepiej sobie radzą z odczytem częściowych słów jak i maskowaniem
przy użyciu części słowa. To powoduje, że można czytać drugiego
shorta a odczyt pierwszego shorta będzie niezależny i branch prediction
pozwoli obie instrukcje wykonywać równocześnie - a wcześniej drugi
short maskował pierwszego i ten wzór wykonywał się wolniej ze względu
na fałszywą zależność danych. Jest mnóstwo takich drobnych różnic.

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.

> Teraz pytanie: czy zmiana struktury danych z szachownica[64], na
> bierki[12] jest optymalizacją implementacyjną czy algorytmiczną?

Taką i taką, jeżeli zmiana użytych prymitywów wpływa na algorytm.
Jako praktyk powiem, że jak zwał tak zwał, ma działać :). Z teoretycznego
punktu widzenia już nie wystarczy uwzględniać złożoności algorytmicznej,
bo sprzęt ma bardzo skomplikowane właściwości.

W zasadzie zamiana bool[38] na bitset[38] to "implementacyjna"?

> Na pewno bierki[12] nie jest dobrze napisanym programem w C++, bo jak
> gdzieś long long nie będzie 64-bitowy, to może nie działać.

Stosuje się alternatywne implementacje fragmentów sprawiających kłopot.

>> Dochodzi też margines opłacalności - programista często kosztuje więcej
>> niż sprzęt (heh, powiedziałem co wiedziałem ;).
> Właśnie dlatego że eksperymentowanie jest bardzo drogie i czasochłonne,
> chciałbym wiedzieć od razu jaka implementacja okaże się najlepsza :)

I bardzo dobrze, zawsze lepiej pomyśleć przed a nie tylko po.

>> Poza HPC i paroma niszami nikomu nie zależy na +-10% jeżeli jest to
>> kosztem funkcjonalności. Jeszcze jeden wyjątek: kod działający na
>> milionach maszyn.
> Myślę że w szachach dzięki dobrej implementacji uzyskuje się
> przyspieszenie 2-4 razy a nie 10%. Test ataku na reprezentacji
> szachownica[64] to iterowanie po polach i cztery warunki do sprawdzania
> czy nie przekroczyliśmy zakresu, a na reprezentacji bitowej to kilka
> operacji logicznych i kilka odczytów masek z tablic.

Po pierwsze: cały program przyspieszył 2-4 razy czy fragment? Ja
mówiłem o całym. Po drugie szachy są niszą. Z tego co się orientuję
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ść.

>> To jest sztuka. Nie jest sztuką próbować do skutku aż się znajdzie
>> optymalny przy tych a nie innych opcjach i wersji, tylko napisać tak,
>> żeby trzymał się w najlepszych 10%.
> Właśnie to jest pytanie czy idzie o te 10% czy o 200-400%. Weźmy naiwne
> mnożenie macierzy i zoptymalizowane. Jakie to są różnice?
> Coś mi się przypomina że 500% - 1000%.

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.

--
Edek