Takie głupie pytanie - która pętla jest lepsza:

1: for i = 0 to n do call subroutine();
2: for i = n downto 0 call subroutine();

Na zdrowy rozum, obie są takie same. Ale chwila - pierwsza rozwija się
(przynajmniej w niektórych językach) do

cośtam-cośtam-cośtam [zmniejsz rejestr o 1] [porównaj rejestr z wartością
n] [podejmij decyzję o kontynuacji]

natomiast druga do

cośtam-cośtam-cośtam [zmniejsz rejestr o 1] [podejmij decyzję o
kontynuacji]

gdyż znakomita większość CPU nie potrzebuje porównania z zerem po
dekrementacji (ZF się ustawia sama).

Czyli druga postać pętli działa o JEDNĄ INSTRUKCJĘ CPU NA PĘTLĘ SZYBCIEJ -
*WOW*

A teraz bez kłamania - kto tak robi? Wszędzie jak pamiętam pętle są robione
"w górę" nawet jak mogą być "w dół", np. przy przeglądaniu po kolei
wszystkich kontrolek itp.

(Nota Benka - optymalizacja nie bardzo coś dać może, bo czasami trudno
odgadnąć, że n nie zmieni się wewnątrz pętli.)

:)

do góry

nie no wydaje mi się, że teraz to już na pewno grant dostaniesz...

do góry

W dniu sobota, 27 kwietnia 2013 18:00:03 UTC+2 użytkownik slawek napisał:
> A teraz bez kłamania - kto tak robi? Wszędzie jak pamiętam pętle są robione
> "w górę" nawet jak mogą być "w dół", np. przy przeglądaniu po kolei
> wszystkich kontrolek itp.

Czasami używam takiej pętli:
while( --n ) {
}

Pozdrawiam

do góry

On 27.04.2013 18:00, slawek wrote:
> Takie głupie pytanie - która pętla jest lepsza:
>
> 1: for i = 0 to n do call subroutine();
> 2: for i = n downto 0 call subroutine();
>
> Na zdrowy rozum, obie są takie same. Ale chwila - pierwsza rozwija się
> (przynajmniej w niektórych językach) do

Ogólnie to gcc (icc też, nie wiem jak kompilator MS i inne) robią
transformacje niezmienników - czyli jeżeli wykryją, że i ma za zadanie
tylko kontrolę iteracji to zamienią to w zjazd do zera, i to nawet w
bardziej złożonych przypadkach jak:
for(int i=5;i<10;i++)
foo();
zostanie zamienione w:
for(int i=5;i;i--)
foo();

Do tego dochodzi -floop-interchange, które potrafi przekształcać
zagnieżdżone pętle, stip-mining, gromadzenie w bloki i masa innych
optymalizacji które jakby je robić ręcznie zaowocowały by prawie
kompletnie nie nadającym się do utrzymania kodem.


--
Pozdrawiam
Michoo

do góry

W dniu niedziela, 28 kwietnia 2013 21:04:51 UTC+2 użytkownik M.M. napisał:
> W dniu sobota, 27 kwietnia 2013 18:00:03 UTC+2 użytkownik slawek napisał:
>
> > A teraz bez kłamania - kto tak robi? Wszędzie jak pamiętam pętle są robione
>
> > "w górę" nawet jak mogą być "w dół", np. przy przeglądaniu po kolei
>
> > wszystkich kontrolek itp.
>
>
>
> Czasami używam takiej pętli:
>
> while( --n ) {
>
> }
>
ciekawe, nie wiedzielem jeszcze takiego czegos

ale to dla n = 1 nie wykona sie chyba ni razu
nie powinno byc wiec

while(n--)
{

}

?

do góry

W dniu 2013-04-28 21:17, Michoo pisze:
> On 27.04.2013 18:00, slawek wrote:
>> Takie głupie pytanie - która pętla jest lepsza:
>>
>> 1: for i = 0 to n do call subroutine();
>> 2: for i = n downto 0 call subroutine();
>>
>> Na zdrowy rozum, obie są takie same. Ale chwila - pierwsza rozwija się
>> (przynajmniej w niektórych językach) do
>
> Ogólnie to gcc (icc też, nie wiem jak kompilator MS i inne) robią
> transformacje niezmienników - czyli jeżeli wykryją, że i ma za zadanie
> tylko kontrolę iteracji to zamienią to w zjazd do zera, i to nawet w
> bardziej złożonych przypadkach jak:
> for(int i=5;i<10;i++)
> foo();
> zostanie zamienione w:
> for(int i=5;i;i--)
> foo();

VC2010
double d;
cin>>d;
for(int i=5;i<10;i++)
d = 4*d*(1-d);
cout<<d;

na domyślnych ustawieniach (/O2) rozwija na 5 powtórzeń.

Po załączeniu opcji Favor small code (/Os)
***
; 31 : for(int i=5;i<10;i++)

dec eax

; 32 : d = 4*d*(1-d);

fld1
fsub QWORD PTR _d$[ebp]
fld QWORD PTR _d$[ebp]
fmul QWORD PTR __real@4010000000000000
fmulp ST(1), ST(0)
fstp QWORD PTR _d$[ebp]
jne SHORT $LL3@wmain
***

Czyli tak, jak chcemy.

Ale dalej. Zmieńmy 10 na 100 i wyłączny /Os.
mov eax, 19 ; 00000013H
...
$LN3@wmain:
; 31 : for(int i=5;i<100;i++)
dec eax
; 32 : d = 4*d*(1-d);
fld ST(2)
fsub ST(0), ST(1)
fxch ST(1)
fmul ST(0), ST(2)
fmulp ST(1), ST(0)
....powtórzone jeszcze 4 razy....
jne SHORT $LN3@wmain

Bardziej złośliwe liczby? for(int i=5;i<102;i++)
97 jest pierwsza.
Więc mamy 12 razy wykonywaną pętlę po 8 powtórzeń + jedno
na koniec.
Też odliczamy do zera.

To może coś oczko trudnijszego:
double d;
int k;
cin>>d;
cin>>k;
for(int i=5;i<k+10;i++)
d = 4*d*(1-d);
cout<<d;
***
; 33 : for(int i=5;i<k+10;i++)

mov eax, DWORD PTR _k$[ebp]
add eax, 10 ; 0000000aH
cmp eax, 5
jle SHORT $LN1@wmain

; 29 : double d;
; 30 : int k;
; 31 : cin>>d;

add eax, -5 ; fffffffbH
$LL3@wmain:

; 33 : for(int i=5;i<k+10;i++)

dec eax

; 34 : d = 4*d*(1-d);

fld1
fsub QWORD PTR _d$[ebp]
fld QWORD PTR _d$[ebp]
fmul QWORD PTR __real@4010000000000000
fmulp ST(1), ST(0)
fstp QWORD PTR _d$[ebp]
jne SHORT $LL3@wmain
***
Wersja bez Favor small code (/Os) to pętla po 8 ++ pętla pojedyncza.

Jest dobrze.
Jeszcze paręnaście lat i dogonimy gcc ;-)

pzdr
bartekltg

do góry

Użytkownik "Michoo" napisał w wiadomości grup
dyskusyjnych:kljt4d$mod$...@m...internetia.pl...

>Ogólnie to gcc (icc też, nie wiem jak kompilator MS i inne) robią
>transformacje niezmienników - czyli jeżeli wykryją, że i ma za zadanie

I właśnie z tym jest problem: czy C# też jest takie "mundre" - czy da się
pisać sensownie wydajne programy w C# ?!

do góry

Czasami używam takiej pętli:
while( --n ) {
}

i to właśnie jest przykład na wzorcowego platformowego głupka...
który nauczył się 10 wyjątków i je stosuje zamiast podawać normalny
warunek...

do góry

W dniu 2013-04-27 18:00, slawek pisze:
> Takie głupie pytanie - która pętla jest lepsza:
>
> 1: for i = 0 to n do call subroutine();
> 2: for i = n downto 0 call subroutine();
>
> Na zdrowy rozum, obie są takie same. Ale chwila - pierwsza rozwija się
> (przynajmniej w niektórych językach) do
>
> cośtam-cośtam-cośtam [zmniejsz rejestr o 1] [porównaj rejestr z
> wartością n] [podejmij decyzję o kontynuacji]
>
> natomiast druga do
>
> cośtam-cośtam-cośtam [zmniejsz rejestr o 1] [podejmij decyzję o
> kontynuacji]
>
> gdyż znakomita większość CPU nie potrzebuje porównania z zerem po
> dekrementacji (ZF się ustawia sama).
>
> Czyli druga postać pętli działa o JEDNĄ INSTRUKCJĘ CPU NA PĘTLĘ SZYBCIEJ
> - *WOW*
>
> A teraz bez kłamania - kto tak robi? Wszędzie jak pamiętam pętle są
> robione "w górę" nawet jak mogą być "w dół", np. przy przeglądaniu po
> kolei wszystkich kontrolek itp.
[...]

Nie robię, bo czas czytania kodu przez programistę jest (zwykle) dużo
większy (i droższy) niż czas procesora.

Po za tym - koledzy już zbadali, jak wygląda optymalizacja kompilatorów
praktyce. Ja tylko dorzucę, że swego czasu walczyłem z kompilatorem,
żeby *nie* używał memset() - szczególny przypadek, gdy .dll nie mógł
zależeć od run-time'u C. Zrobiłem pętlę zerującą bufor... i linker
(Visuala) powiedział, że nie wie, gdzie jest memset(), bo kompilator
jej użył, rozpoznając pętlę. Zamazywanie wstecz też nie pomogło. Dopiero
dwie pętle, które fake'owo zapisywały indeks do kolejnych komórek
o odejmowały go pomogły.

--
Paweł Kierski
n...@p...net

do góry

On 29.04.2013 10:28, slawek wrote:
> Użytkownik "Michoo" napisał w wiadomości grup
> dyskusyjnych:kljt4d$mod$...@m...internetia.pl...
>
>> Ogólnie to gcc (icc też, nie wiem jak kompilator MS i inne) robią
>> transformacje niezmienników - czyli jeżeli wykryją, że i ma za zadanie
>
> I właśnie z tym jest problem: czy C# też jest takie "mundre" - czy da
> się pisać sensownie wydajne programy w C# ?!
>
Powinno być mądrzejsze bo nie tylko JITuje kod ale zdaje się, że przy
okazji profiluje i ponownie JITuje w razie potrzeby.

--
Pozdrawiam
Michoo

do góry