W dniu środa, 17 grudnia 2014 17:08:33 UTC+1 użytkownik bartekltg napisał:
> > Jezeli dana procedura (taka jak np. liczenie sinusa) gwarantuje,
> > ze dla tego samego argumentu zawsze uzyskamy ten sam wynik, to nie
> > ma zadnego powodu, dla ktorego kompilator nie mialby sam tablicowac
> > wynikow. Nazywanie tego rodzaju optymalizacji "zmiana algorytmu"
> > wydaje sie jednak dosc pretensjonalne
>
> Żeby zmienił sposób liczenia algorytmu - nie ma problemu.
> Tak robi. Mi wszytko jedno, czy sin będzie policzony
> koprocesorem czy szeregiem pędzonym SSE.
> Natomiast zamiana na stablicowanie (nie w tym przypadku, tablica
> o gęstości precyzyjnej jak sin[x] z interpolacją
> liniową czy nawet kwadratową jest niepraktyczni duża ) powinna być
> świadomą decyzją programisty.
> Lepszym przykładem byłby dwumian newtona wielokrotnie liczony
> dla małych parametrów. Czasem trzymam sobie go w pamięci,
> ale czasem cache możę być znacznie przydatniejsze gdzie indziej,
> i te kilka pętli jest lepszym wyjściem.

Tzn oczywiscie, jezeli zamiast liczyc wynik, dokonujemy interpolacji,
to tego rodzaju optymalizacja wydaje sie niedopuszczalna, chyba ze
programista dopusci ja explicite

> > Poza tym, jezeli nie mialoby to wplywu na obserwowalne zachowanie programu,
> > to nie widze powodu, dla ktorego kompilator nie mialby w okreslonych
> > okolicznosciach zamieniac bubblesorta na qsorta (choc w tym kontekscie
> > oczywiscie stwierdzenie "zamiana algorytmu" wydaje sie jak najbardziej
> > na miejscu).
>
> A skąd kompilator ma wiedzieć, co mam na myśli.

Kompilator moze wiedziec, jaka funkcje realizuje Twoja procedura,
i jezeli zna wydajniejsza procedure realizujaca te sama funkcje,
to moze ja zastapic

> To, że potrzebuję akurat stabilnego sortowania będzie w stanie wyłapać?

Jezeli Twoj algorytm sortuje stabilnie, to oczywiscie -- zeby procedura
wygenerowana przez kompilator realizowala te sama funkcje -- algorytm
wynikowy musialby rowniez sortowac stabilnie

> Pamiętaj, że kompilator na zanalizować kod, a nie widzi intencje przez
> użycie sort czy stable_sort.
> A może zawsze ten algorytm sortuje jedynie malutkie tablice.
> Albo wstępnie posortowane (dla insertsorta).

Oczywiscie, zdarzaja sie przypadki graniczne, dla ktorych
wydajnosc kodu zoptymalizowanego przez kompilator jest gorsza,
niz wydajnosci kodu niezoptymalizowanego

> Kompilator musiałby zrozumieć nie tylko kod, ale i intencje
> piszącego, oraz to, czy jest baranem, czy taki a nie inny
> sposób przetwarzania danych wynika z jakiejś głębszej analizy.

Dla kompilatora nie ma roznicy pomiedzy kodem a intencja
piszacego. (Oczywiscie z tego wzgledu jest lepiej, jezeli
jezyk programowania umozliwia programiscie dokladne wyrazanie
swoich intencji)

> > Istnieja ciekawe metody dotyczace optymalizacji algorytmow,
> > opisane np. tutaj:
> > http://repository.readscheme.org/ftp/papers/topps/D-
170.ps.gz
>
> Bardzo dokładnie się nie wczytałem, ale czy rozwiązywanie
> sporych NP zupełnych problemów grafowych podczas kompilacji
> nie jest chwilowo przesadą? ;-)

To oczywiscie zalezy od sytuacji, ale czesto do rozwiazywania
NP-trudnych problemow istnieja dobre heurystyki dzialajace
wydajnie na typowych przypadkach

> >>> jeszcze kombinowalem z rugowaniem castow i
> >>
> >> To samo. Każesz kompialtorowi liczyć danymi zmiennymi, musi nimi
> >> liczyć.
> >
> > Nie bardzo rozumiem te uwage, ale znow: jezeli kompilator moze w jakims
> > kontekscie dokonac czesciowej ewaluacji, to nie ma istotnego powodu, dla
> > ktorego nie mialby tego robic
>
> Masz dwa programy. Jeden liczy coś intami, drugi na float.
> Wyniki _NIE_ bądą identyczne, poza przypadkami, gdzie obłożymi
> warunkami praktycznie wszystko.

Wyglada na to, ze wyinterpretowales z wypowiedzi firra duzo wiecej
niz ja :]
Ja nie wiem, czy on dokonywal jakichs interpolacji na sinusach. Byc
moze oryginalny algorytm byl napisany w taki sposob, ze sinusy byly
brane tylko z pewnego dyskretnego rownomiernie rozlozonego podzbioru
odcinka [0, 2pi) i bystry kompilator moglby teoretycznie to zauwazyc
i stablicowac wartosci sinusa?

Dalej firr rzeczywiscie pisal cos o interpolacjach -- i zgodze sie,
ze tego rodzaju optymalizacja jest juz dla semantyki programu inwazyjna,
ale z Twojej odpowiedzi wynikalo, ze zastapienie wywolan funkcji
stablicowanymi wartosciami stanowi zmiane algorytmu. Oczywiscie mozna
dzielic wlos na czworo i dowodzic, ze tak jest, ale moim zdaniem jest
to jedna z prostszych nieinwazyjnych optymalizacj, jakie kompilator
moglby przeprowadzac.