eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingPętla FOR (w sam raz na poziom FIR'a)
Ilość wypowiedzi w tym wątku: 10

  • 1. Data: 2013-04-27 18:00:03
    Temat: Pętla FOR (w sam raz na poziom FIR'a)
    Od: "slawek" <h...@s...pl>

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

    :)


  • 2. Data: 2013-04-27 18:38:53
    Temat: Re: Pętla FOR (w sam raz na poziom FIR'a)
    Od: "Ministerstwo Propagandy" <...@...s>

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


  • 3. Data: 2013-04-28 21:04:51
    Temat: Re: Pętla FOR (w sam raz na poziom FIR'a)
    Od: "M.M." <m...@g...com>

    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


  • 4. Data: 2013-04-28 21:17:02
    Temat: Re: Pętla FOR (w sam raz na poziom FIR'a)
    Od: Michoo <m...@v...pl>

    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


  • 5. Data: 2013-04-28 21:53:38
    Temat: Re: Pętla FOR (w sam raz na poziom FIR'a)
    Od: firr kenobi <p...@g...com>

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

    }

    ?



  • 6. Data: 2013-04-28 23:31:57
    Temat: Re: Pętla FOR (w sam raz na poziom FIR'a)
    Od: bartekltg <b...@g...com>

    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




  • 7. Data: 2013-04-29 10:28:03
    Temat: Re: Pętla FOR (w sam raz na poziom FIR'a)
    Od: "slawek" <h...@s...pl>

    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# ?!


  • 8. Data: 2013-04-29 18:53:47
    Temat: Re: Pętla FOR (w sam raz na poziom FIR'a)
    Od: "identyfikator: 20040501" <N...@g...pl>

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


  • 9. Data: 2013-04-30 07:32:43
    Temat: Re: Pętla FOR (w sam raz na poziom FIR'a)
    Od: Paweł Kierski <n...@p...net>

    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


  • 10. Data: 2013-05-01 20:26:32
    Temat: Re: Pętla FOR (w sam raz na poziom FIR'a)
    Od: Michoo <m...@v...pl>

    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

strony : [ 1 ]


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: