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


> 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.

Teraz pytanie: czy zmiana struktury danych z szachownica[64], na
bierki[12] jest optymalizacją implementacyjną czy algorytmiczną?
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ć.


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


> 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.


> 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%.

Pozdrawiam