W dniu 2014-12-17 o 14:24, g...@g...com pisze:
> 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

I programista nie mógłby porównać działania bubble sorta z quick sortem
nie mówiąc że nie mógłby debugować bo źródła by się znacznie różniły od
wyniku.
Programowanie wyglądało by tak, że programista mówił by do mikrofonu:
"kompilatorze, zrób mi gierkę, taką strzelankę first person perspective,
wymyśl plan okolicy, po której będzie się chodzić"

do góry

teoretyczni juz dzis moglby tablicowac np

float sin_(unsigned char x)
{
return sin((float)x / 255. * 2*PI);
}

ale chyba kompilatory nie robia takich kawalow

do góry

On 17.12.2014 14:24, g...@g...com wrote:
> W dniu środa, 17 grudnia 2014 03:01:18 UTC+1 użytkownik bartekltg napisał:
>>> inicjalna wersja trwala jakies 100 czy nawet 150 ms ms a to glownie
>>> dziki temu ze czas zarly dwa sinusy i pierwiastek na piksel jeszcze
>>> z jakims dzieleniem i rzutowaniami (jak uzyjesz sinusa w kodzie to
>>> program jest wydajnosciowym trupem tak bardzo sinus jest wolny) po
>>> stablicowaniu sinusów i normalizacji i jeszcze ze dwu dniach
>>> glowienia sie nad petla czas spadl do 20 i w koncu do 13 milisekund
>>> 9prawie 10 razy szybciej niz normalny kod dla gcc) ciegle uwazalem ze
>>> to za duzo i zaczalem przepisywac kod na kafelki gdzie mogelem zrobic
>>> na kafelkach pewna interpolacje i pewne tam drobne rozroznienia, to
>>> bylo troche trudne ale spowodowalo ze cza sspadl do 6-10 ms, 910-20
>>> razy sszybciej "niz gcc",
>>
>> Zaraz, wkurzasz się, zę kompilator nie zmienił ci algoruytmu na inny?
>> Znów odpływasz. Kompilator nie może zmienić bublesorta na qsorta.
>> Zmieniłeś algorytm na szybszy, a mniej dokłądny, to masz
>> przyszpieszenie, nie ma to nic wspolnego z jakością generowanego kodu.
>
> 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.


> 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.
To, że potrzebuję akurat stabilnego sortowania będzie w stanie wyłapać?
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).

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.


> 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ą? ;-)

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

Oczywiście, że liczenie pewnyych rzeczy na raz, najlepiej w czasie
kompilacji, po wyciągnieciu prez pętle jest przydatne. Nawet
powszechnie mowimy kompilatorowi, by się IEEE za bardzo przy tym
nie przejmował.

Ale to nie jest to, o czym była tu mowa.

pzdr
bartekltg

do góry

On 17.12.2014 15:27, M.M. wrote:
> On Wednesday, December 17, 2014 2:24:57 PM UTC+1, g...@g...com wrote:
>> Jezeli dana procedura (taka jak np. liczenie sinusa) gwarantuje,
>> ze dla tego samego argumentu zawsze uzyskamy ten sam wynik
> Wystarczy ze gwarantuje taką samą dokładność dla określonego zbioru
> argumentów.
>
>
> Swoją drogą, szkoda że w C++ nie można przy argumencie procedury
> napisać, że dany argument będzie przyjmował wartości tylko z małego
> zbioru. Wtedy kompilator miałbym lepsze możliwości optymalizacji.
>
>
> np.
> f( int x@{1:50%,0:20%,2:10%,other} ) {
> return sin(x);
> }
>
> Kompilator mógłby stablicować dla sin dla 1, 0 i 2, a że 1
> przychodzi statystycznie w 50%, to mógłby 'górnym ifem' sprawdzać,
> czy x==1.

Nie, tablicowanie to inny sposób działania programu.
Chcesz tablicowania, zrób to ręcznie (ile to, 10 linijak jak się
rozpiszesz).

>
> if( x==1 ) return sin(1);
> if( x==0 ) return sin(0);
> if( x==2 ) return sin(2);
> return sin(x);


> Z kolei gdy się nie poda statystyki wystąpień, to kompilator mógłby
> wziąć wartości z pgo.
>
> Dalej, gdy nie ma other, to w ogóle kompilator mógłby wygenerować
> ultra zoptymalizowany kod:
>
> f( int x@{1:60%,0:40%} ) {
> return x==1 ? sin(1) : sin(0);
> }

Kompilator musiałby mieć gwarancje, że innej liczby nie będzie.
Przykładowe uruchomiania przy -fprofile-generate to za mało.
A skoro wpisujesz to ręcznie, to możesz wpisać sam, jak powyżej.

Kompilator ma wykonywać za programistę mechzniczne czynności,
nie myśleć ;-)

pzdr
bartekltg

do góry

On Wednesday, December 17, 2014 4:39:51 PM UTC+1, firr wrote:

> jesli statycznie wiesz co to bezie to sam sobie mozesz
> to napisac w dobrej kolejnosci zamiast troche szpecic zrodlo tymi
> procentami;
Można samemu. Ale kompilator moim zdaniem powinien sam wypróbować
wiele wersji, a jeśli się opłaca, to powinien za programistę
napisać.


> jesli nie to lepiej jednak by kompilatr sobie sam ta statystyke
> trzasnal
Też myślę że lepiej jak kompilator zrobi sam statystykę.


> (i tak jakos slabo wierze w skutecznosc tego rodzaju
> optymizacji -
W szachach taka technika optymalizacji dawała dużo. Poprawiało
się jedna mała procedurę, a wielki program przyspieszał o nawet 3%.
Jeśli się zadba o kolejność ifów w gorącym punkcie, to może
przyspieszyć o 50%.


> za to chyba zgodzilbym sie ze przydaloby sie definiowanie statycznych
> okrojonych typow np float_od_0_do_1 albo int_od_0_do_100)
W sumie wszystko to co napisałem powyżej, można sprowadzić do
okrojonych typów. Też uważam, że ich brakuje.


> I programista nie mógłby porównać działania bubble sorta z quick sortem
> nie mówiąc że nie mógłby debugować bo źródła by się znacznie różniły od
> wyniku.
Powinna być opcja do wyłączenia tej techniki optymalizacji.

> teoretyczni juz dzis moglby tablicowac np
> float sin_(unsigned char x)
Racja. Już dziś teoretycznie może na char, albo na enum.
Też nie wiem, czy jakiś kompilator w praktyce robi takie coś.

Pozdrawiam

do góry

On Wednesday, December 17, 2014 5:16:01 PM UTC+1, bartekltg wrote:
> Kompilator ma wykonywać za programistę mechzniczne czynności,
> nie myśleć ;-)

Nawet gdyby myślenie było jako opcja? :D

Pozdrawiam

do góry

W dniu środa, 17 grudnia 2014 17:21:18 UTC+1 użytkownik M.M. napisał:
> On Wednesday, December 17, 2014 4:39:51 PM UTC+1, firr wrote:
>
> > jesli statycznie wiesz co to bezie to sam sobie mozesz
> > to napisac w dobrej kolejnosci zamiast troche szpecic zrodlo tymi
> > procentami;
> Można samemu. Ale kompilator moim zdaniem powinien sam wypróbować
> wiele wersji, a jeśli się opłaca, to powinien za programistę
> napisać.
>
>
> > jesli nie to lepiej jednak by kompilatr sobie sam ta statystyke
> > trzasnal
> Też myślę że lepiej jak kompilator zrobi sam statystykę.
>
>
> > (i tak jakos slabo wierze w skutecznosc tego rodzaju
> > optymizacji -
> W szachach taka technika optymalizacji dawała dużo. Poprawiało
> się jedna mała procedurę, a wielki program przyspieszał o nawet 3%.
> Jeśli się zadba o kolejność ifów w gorącym punkcie, to może
> przyspieszyć o 50%.
>
>
> > za to chyba zgodzilbym sie ze przydaloby sie definiowanie statycznych
> > okrojonych typow np float_od_0_do_1 albo int_od_0_do_100)
> W sumie wszystko to co napisałem powyżej, można sprowadzić do
> okrojonych typów. Też uważam, że ich brakuje.
>
zgadza sie, odnioslem wrazenie ze w jakims sensie o tym mowa,, tylko jak mowie ja w
ta kolejnosc ifow az tak bardzo nie wierze natomiast w to tablicowanie, jak
najbardziej (zwlaszcza w swietle tych moich ostatnich wynikow z tablicowaniem)

do góry

On Wednesday, December 17, 2014 5:39:35 PM UTC+1, firr wrote:
> zgadza sie, odnioslem wrazenie ze w jakims sensie o tym mowa,, tylko jak mowie ja w
ta kolejnosc ifow az tak bardzo nie wierze natomiast w to tablicowanie, jak
najbardziej (zwlaszcza w swietle tych moich ostatnich wynikow z tablicowaniem)

Zrozumiałem że nie wierzysz. Ja mierzyłem i widziałem, przynajmniej w
przypadku kilku kompilatorów, kolejność ifów dawała przyspieszenie. Tablicowanie
też stosowałem kilka razy, przyspieszenie raz było, raz nie, zależy co
było tablicowane. Funkcje sin i exp są szybko liczone, nie wiem czy
bym tak proste funkcje tablicował. Może...

Pozdrawiam

do góry

W dniu środa, 17 grudnia 2014 17:55:06 UTC+1 użytkownik M.M. napisał:
> On Wednesday, December 17, 2014 5:39:35 PM UTC+1, firr wrote:
> > zgadza sie, odnioslem wrazenie ze w jakims sensie o tym mowa,, tylko jak mowie ja
w ta kolejnosc ifow az tak bardzo nie wierze natomiast w to tablicowanie, jak
najbardziej (zwlaszcza w swietle tych moich ostatnich wynikow z tablicowaniem)
>
> Zrozumiałem że nie wierzysz. Ja mierzyłem i widziałem, przynajmniej w
> przypadku kilku kompilatorów, kolejność ifów dawała przyspieszenie. Tablicowanie
> też stosowałem kilka razy, przyspieszenie raz było, raz nie, zależy co
> było tablicowane. Funkcje sin i exp są szybko liczone, nie wiem czy
> bym tak proste funkcje tablicował. Może...
>
no spoko, mozliwe ze ma znaczenie, kiedys tu pisalem znaleziona skad informacje ze o
ile przewidziany skok kosztuje ok 1-2 ns to nietrafiony okolo 30 ns (juz troche nie
pamietam ale cos w tym stylu)
wierze w to o tyle mniej ze tu sytuacja zalezy od ukladu danych nie tylko od
kolejnosci ifow, z tad by wynikalo ze
nie tyle zalezy jak te ify zahardkodujesz tylko czy dane beda lecialy spojnymi
blokami (ale to oczywicie troche wyidealizowana sytuacja i w praktyce pewnie zalezy
od jednego i drugiego,

co do wplywo ifów to nie wiem, jesli faktycznie nietrafiony if zajmuje 30 to
bedzie zalezalo bo 30 to duzo, mw kosz sqrt - sqrt mozesz stablicowac i wtedy
kosztuje ze 2 ns, z kolei jak nie stablicujesz to ze 30 (moze nawet costam wiecej juz
nie pamietam ale cos w tym stylu) zawsze, ifow nie stablicujesz
(chyba, costam probowac niby mozna ale nie robilem testow), za to mozesz eliminowac
tymi dobrymi ukladami - kiedys posprawdzam [sinus jest za to zabojczy
zalezy do jakiej libki linkujesz ja uzywam zdaje sie tego z msvcrt.dll i to jest
sinusowe truchlo, cos slyszalem ze jakas wersja z gcc jest lepsza, tylko ze za bardzo
nie wiem o czym mowa jak ja uzywam mingw i msvcrt.dll jest tu chyba jednyna opcją]

do góry

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.

do góry