Optymalizacja kodu - jak to działa?

0

podam tez przyklad kodu ktory jest szybszy w php niz asemblerze

for ($i = 0; $i < 100; $i++) chodzi o to ze asembler musi sprawdzac czy dana liczba jest liczba a php to wie i nie musi.

LOL, owned ;>
Troszeczkę pomyliło Ci się ;> Jest odwrotnie ;>
To PHP musi sprawdzić w strukturze zmiennej jakiego typu zmienna to jest. Natomiast w asemblerze nie ma podziału na typy. Jeśli użyjesz instrukcji dedykowanej np dla DWORDów to dane bity (bajty/wordy/dwordy/etc) zostaną potraktowane jak DWORD, ort! były stringiem. Procesor nie będzie musiał się zastanawiać co tam jest, co tam było etc. Instrukcja mu powie jak ma to w danej chwili traktować, i go więcej nie obchodzi.
poza tym wiesz ile kodu musi się wykonać w PHP żeby tą pętle wykonać ? Nie mało
W assemblerze to będzie ledwo kilka bajtów ;>

0
fr3 napisał(a)
qu napisał(a)

Odwrotnie - int jest zmieniany na float;

No tu mnie ściąłeś:

fr3 napisał(a)
  1. konwersja z inta do floata

Odwrotnie? O_O

& jest operatorem arytmetycznym.

Nie, & jest funkcją boolowską.

Generalnie twój post można przedstawić jako:
(ja) "nieprawda, jest inaczej"
(ty) "nie zgadzam się, jest tak jak mówisz"
...

(poza ostatnim zdaniem)

Tak pisałeś:

Kompilator NIE MOŻE zmienić inta na float gdyż może zmienić to wynik; w rezultacie dodawanie będzie całkowite (add) co razem daje nam dwie niepotrzebne operacje:

float x = 5.4;
int k = 1;
x = x + k; // normalnie piszemy: x += k

zgodnie z tą wersją otrzymasz ostatecznie x = 6 zamiast 6.5:
(int)x + k = 5 + 1
zatem konwersja musi być taka: x + (float)k

Jeśli ktoś nie potrafi zoptymalizować kodu (przynajmniej prowizorycznie,
bez asm i innych komplikacji), to tym bardziej algorytmu,
bo to jest zazwyczaj znacznie trudniejsze.

W C/C++ jest niedopracowana sprawa konwersji float na int;
aby coś zaokrąglić musimy zwyczajnie dodawać 0.5:
x = f*x + 0.5; // f - float

można jawnie użyć funkcji: x = round(f*x); ale w C nie ma funkcji round.
można sobie zrobić swoją, ale to mało pomoże...
a przecież procesor ma rozkaz konwersji float na int z zaokrągleniem:
fist mem;
Tego rozkazu kompilator nigdy nie generuje, gdyż domyślna konwersja float do int polega na obcięciu.
double x = 9.99;
int k = x; // k = 9

dopiero:
k = x + 0.5; // 10
kompletna parodia... :-D
// tak, dobre podsumowanie całego postu (dop. deus)

0
qu napisał(a)

Tak pisałeś:

Kompilator NIE MOŻE zmienić inta na float gdyż może zmienić to wynik; w rezultacie dodawanie będzie całkowite (add) co razem daje nam dwie niepotrzebne operacje:

float x = 5.4;
int k = 1;
x = x + k; // normalnie piszemy: x += k

zgodnie z tą wersją otrzymasz ostatecznie x = 6 zamiast 6.5:
(int)x + k = 5 + 1
zatem konwersja musi być taka: x + (float)k

A punkty po ":" to co? Ładnie tak wyrywać zdanie z kontekstu i przekręcać znaczenie? :/
Kompilator nie może zmienić 'int x' (z tej pętli w poprzednim poście) na float, sama suma oczywiście zostaje floatem...
Znowu potwierdzasz to co powiedziałem, lol.


Jeśli ktoś nie potrafi zoptymalizować kodu (przynajmniej prowizorycznie,
bez asm i innych komplikacji), to tym bardziej algorytmu,
bo to jest zazwyczaj znacznie trudniejsze.

Dlaczego 'nie potrafi'? Może po prostu 'nie widzi najmniejszego sensu'?
No, chyba że ktoś lubi marnować czas...

W C/C++ jest niedopracowana sprawa konwersji float na int;
aby coś zaokrąglić musimy zwyczajnie dodawać 0.5:
x = f*x + 0.5; // f - float

można jawnie użyć funkcji: x = round(f*x); ale w C nie ma funkcji round.

http://www.hmug.org/man/3/round.php

można sobie zrobić swoją, ale to mało pomoże...
a przecież procesor ma rozkaz konwersji float na int z zaokrągleniem:
fist mem;

Mylisz się, metoda konwersji jest określana przez flagi fpu (round, ceiling, floor, truncate) - instrukcja pozostaje ta sama.

W kodzie c/c++ można również zmienić domyślna konwersję...

0

W punktach po ':' masz bzdury - twierdzisz że dodawanie jest całkowite,
a tam będzie zwyczajnie z instrukcji:

suma += i;

otrzymamy:

fild   dword ptr [esp+4]; // sp = i, ładuje int na stos koprocesora
fadd dword ptr [esp];  // sp += suma
fstp  dword ptr [esp]; // suma = sp

a w wersji w której 'i' jest float masz sprawdzanie warunku na float,
i dodawanie 1.0 - z 3x wolniej.

Tamta biblioteka z round nie jest standardem c.
Flagi koprocesora nie są dostępne z poziomu c.

// blużnisz dziecko... obiecałem się nie mieszać to się nie mieszam... (dop. deus)

0
qu napisał(a)

W punktach po ':' masz bzdury - twierdzisz że dodawanie jest całkowite,
a tam będzie zwyczajnie z instrukcji:

suma += i;

otrzymamy:

fild   dword ptr [esp+4]; // sp = i, ładuje int na stos koprocesora
fadd dword ptr [esp];  // sp += suma
fstp  dword ptr [esp]; // suma = sp

A +1 to gdzie się podziało?

float suma=0;
for(float x = 1; x < 10; x++) suma = suma + x;
fld [costam] ;zaladuj 10.0
fld1 ;zaladuj 1
fld1
fldz
;st0-suma st1-x, st2-1.0 st3=10.0
@@:
fcomi st0,st3 ;porownaj x z 10.0
fdecstp
fadd st0,st1
ja @f
fincstp
fadd st0,st1
jmp @b
@@:
fincstp
;wynik w st0
float suma=0;
for(int x = 1; x < 10; x++) suma = suma + x;
push 1 ;x
fldz ;suma
mov ebx,esp
@@:
cmp dword[ebx],10
ja @f
fild dword[ebx]
faddp st1,st0
inc dword[ebx]
jmp @b
pop ecx
; wynik w st0

Pierwsza wersja jest o wiele szybsza - brak odwołań do pamięci, większa równoległość... (fdecstp i fincstp zajmują 0 cykli - są wykonywane w dekoderze instrukcji (fpu nie jest już naprawdę maszyną stosową!))

Tamta biblioteka z round nie jest standardem c.
Flagi koprocesora nie są dostępne z poziomu c.

Jest, ale nie ansi ;)

Flagi koprocesora są dostępne z poziomu C w sposób zależny od kompilatora, np. w VisualC++:
http://msdn2.microsoft.com/en-us/library/aa289157(vs.71).aspx#floapoint_topic13

0
float suma=0;
for(float x = 1; x < 10; x++) suma = suma + x;

Wybaczcie Panowie, ale zamiast schodzić do asma czy bawić się w inny sposób, czy nie sądzicie, że ten konkretny kod można zoptymalizować dużo prościej:

float suma=45;

;)

0
fr3 napisał(a)

Pierwsza wersja jest o wiele szybsza - brak odwołań do pamięci, większa równoległość... (fdecstp i fincstp zajmują 0 cykli - są wykonywane w dekoderze instrukcji (fpu nie jest już naprawdę maszyną stosową!))

Sprawdź czy jest szybsze, bo raczej na to nie wygląda.

A ty nadęty deusiku lepiej się nie odzywaj skoro
nie masz nic do powiedzenia, rób to od czego tu jesteś - sprzątaj.

0
qu napisał(a)

A ty nadęty deusiku lepiej się nie odzywaj skoro
nie masz nic do powiedzenia, rób to od czego tu jesteś - sprzątaj.

Ależ proszę Cię bardzo, obiecałem się nie mieszać ale skoro prosisz...

qu napisał(a)
fr3 napisał(a)

Pierwsza wersja jest o wiele szybsza - brak odwołań do pamięci, większa równoległość... (fdecstp i fincstp zajmują 0 cykli - są wykonywane w dekoderze instrukcji (fpu nie jest już naprawdę maszyną stosową!))

Sprawdź czy jest szybsze, bo raczej na to nie wygląda.

Po pierwsze taki znawca jak Ty powinien przedstawić konkrety. Po drugie powinien zauważyć błędy w obu kodach przedstawionych przez fr3m3na...

qu napisał(a)
for(float x = 1; x < 10; x++) suma = suma + x;

A teraz proszę Cię bardzo, popatrz w kod fr3m3na... co widzisz? U niego pętle są przerywane gdy x > 10. Druga sprawa, pierwszy kod w ogóle nie działa:

fr3 napisał(a)
fld [costam] ;zaladuj 10.0
fld1 ;zaladuj 1
fld1
fldz
;st0-suma st1-x, st2-1.0 st3=10.0
@@:
fcomi st0,st3 ;porownaj x z 10.0
fdecstp
fadd st0,st1
ja @f
fincstp
fadd st0,st1
jmp @b
@@:
fincstp

Aby chociaż warunek był poprawny wartość costam musi zostać zmniejszona o 1. Skoro x jest w st1 to dlaczego x jest porównywany z wartością graniczną? Stos powinien zostać zinkrementowany podczas wchodzenia w pętlę aby licznik był w st0, teraz zaś wartość graniczna jest w st2, nie st3. Moment skoku jest źle dobrany, zaś fincstp na wyjściu z pętli usunie sumę z st0. A właśnie, co z tymi trzema dodatkowymi wartościami na stosie koprocka?
Jeżeli o drugi kod chodzi to jedynie warunek zakończenia jest błędny. Na szybko do testów wydajności skleciłem takie coś. Wszystkie skoki w pętlach wyrównane do 16, dane do 4, kody poprawiłem:

format PE Console

ITER = 10000000

section '.baiji' code readable executable

        finit
        call    get_time
        mov     ecx, ITER
        align   0x10
_kod1:
        fld     [costam]
        fld1
        fsub    st1, st0
        fld1
        fldz
        fincstp
  @@:
        fcomi   st0, st2
        fdecstp
        ja      @f
        fadd    st0, st1
        fincstp
        fadd    st0, st1
        jmp     @b
        align   0x10
  @@:
        fstp    [suma]
        ffreep  st0
        ffreep  st0
        ffreep  st0

        dec     ecx
        jnz     _kod1

        call    get_time
        mov     ecx, ITER
        align   0x10
_kod2:
        push    1
        fldz
        mov     ebx, esp
        db      0x8d, 0x80, 0, 0, 0, 0  ; lea eax, [eax+0] ; imm32 - odpowiednik nop'a
        db      0x8d, 0x49, 0  ; lea ecx, [ecx+0] - imm8
        nop     ; lacznie wyrownanie do 16.
  @@:
        cmp     dword [ebx], 10
        jge     @f
        fild    dword [ebx]
        faddp   st1, st0
        inc     dword [ebx]
        jmp     @b
        align   0x10
  @@:
        pop     edx

        dec     ecx
        jnz     _kod2

        call    get_time
        call    print_time
        call    print_time
        pop     ecx ecx
        retn

get_time:
        xor     eax, eax
        cpuid
        rdtsc
        pop     ecx
        push    eax
        push    edx
        push    ecx
        retn

print_time:
        pop     ecx
        pop     edx
        pop     eax
        push    ecx
        sub     eax, [esp]
        sbb     edx, [esp+4]
        push    eax
        push    edx
        push    _format
        call    [printf]
        add     esp, 0x0c
        retn

section '.data' data readable writeable

_format db 'cykli: %08lx%08lx', 0x0d, 0x0a, 0

        align   0x10

costam  dd 10.0
suma    dd 0.0

        align   0x20

        data    import
        dd      0, 0, 0, rva msvcrt, rva printf
        rd      5
        end     data

msvcrt  db 'msvcrt.dll', 0
printf  dd rva @f, 0
@@:     db 0, 0, 'printf', 0

Kompilacja fasmem, kod jest całkowicie niezależny od zewnętrznych nagłówków itd... Wyniki oczywiście nie będą dokładne, pomiary dokonywane podczas normalnej pracy systemu, ale wystarczą. Ten printf jest dosyć wredny ale nie chciało mi się konwertera pisać, niestety printf z msvcrt nie obsługuje long long, trzeba było zrobić to j\w. Wyniki:

  • PIII 1GHz
bash-2.03$ ./times.EXE
cykli: 00000006448fbe60
cykli: 000000009292c261
bash-2.03$ ./times.EXE
cykli: 00000004c8626214
cykli: 0000000087955e30
bash-2.03$ ./times.EXE
cykli: 00000006a9fd7980
cykli: 000000007cf1cef6
  • Intel Core Duo 1.63GHz
C:\times.EXE
cykli: 0000000545108da4
cykli: 00000000b3f5e755
C:\times.EXE
cykli: 00000004dbc0dc12
cykli: 000000004015d04b
C:\.times.EXE
cykli: 000000057ee6d748
cykli: 00000000df21cf69
  • Intel Core 2 Duo 2.13GHz
C:\>times.EXE
cykli: 0000000527282c3a
cykli: 0000000102ce61f5
C:\>times.EXE
cykli: 000000053f83a052
cykli: 000000011c39381d
C:\>times.EXE
cykli: 00000005f7a73f22
cykli: 00000000d0197b35
fr3 napisał(a)

Pierwsza wersja jest o wiele szybsza - brak odwołań do pamięci, większa równoległość... (fdecstp i fincstp zajmują 0 cykli - są wykonywane w dekoderze instrukcji (fpu nie jest już naprawdę maszyną stosową!))

Cóż, wyniki mówią same za siebie, nie muszą być dokładne. Fantazyjny kod fr3m3na jest po prostu wolny... fr3, sam pisałeś jak szybki jest dostęp do danych w cache'u - w nim mieszczą się wartości tymczasowe drugiego algorytmu, obroty stosu fpu zaś jednak kosztują, chociażby czas dekoderów. Dobra, czyli teoretyzowanie nt. szybkości algorytmów mamy z głowy? Hm... nie całkiem:

einstein^2 napisał(a)

Wybaczcie Panowie, ale zamiast schodzić do asma czy bawić się w inny sposób, czy nie sądzicie, że ten konkretny kod można zoptymalizować dużo prościej:

float suma=45;

Tu by wypadało zaznaczyć, że kompilatory z GCC, ICC czy Microsoftu od jakiegoś czasu zwykle radzą sobie z obliczaniem stałych wyrażeń podczas kompilacji, zabawki Borlanda już nie zawsze... Tak jest toretycznie, w praktyce nie wygląda to tak różowo, ICC chwilowo pod ręką nie mam. Dowody:

float licz (void)
{
	float suma=0;
	int x;
	for(x = 1; x < 10; x++) suma = suma + x;
	return suma;
}
int main ()
{
	return (int) licz();
}

GCC 4.2 z -O3:

.text:00000000                 public _licz
.text:00000000 _licz           proc near
.text:00000000                 push    ebp
.text:00000001                 mov     ebp, esp
.text:00000003                 fld     ds:flt_34
.text:00000009                 leave
.text:0000000A                 retn
.text:0000000A _licz           endp
;...
.rdata:00000034 flt_34          dd 4.5e1

Z main był wywoływany licz i procka konwertująca na int. Standardowe ustawienia VC 2k5:

.text:00401000 licz            proc near               ; CODE XREF: _mainp
.text:00401000
.text:00401000 var_4           = dword ptr -4
.text:00401000
.text:00401000                 push    ecx
.text:00401001                 fld1
.text:00401003                 fadd    ds:__real@0000000000000000
.text:00401009                 fstp    [esp+4+var_4]
.text:0040100C                 fld     [esp+4+var_4]
.text:0040100F                 fadd    ds:__real@4000000000000000
.text:00401015                 fstp    [esp+4+var_4]
.text:00401018                 fld     [esp+4+var_4]
.text:0040101B                 fadd    ds:__real@4008000000000000
.text:00401021                 fstp    [esp+4+var_4]
.text:00401024                 fld     [esp+4+var_4]
.text:00401027                 fadd    ds:__real@4010000000000000
.text:0040102D                 fstp    [esp+4+var_4]
.text:00401030                 fld     [esp+4+var_4]
.text:00401033                 fadd    ds:__real@4014000000000000
.text:00401039                 fstp    [esp+4+var_4]
.text:0040103C                 fld     [esp+4+var_4]
.text:0040103F                 fadd    ds:__real@4018000000000000
.text:00401045                 fstp    [esp+4+var_4]
.text:00401048                 fld     [esp+4+var_4]
.text:0040104B                 fadd    ds:__real@401c000000000000
.text:00401051                 fstp    [esp+4+var_4]
.text:00401054                 fld     [esp+4+var_4]
.text:00401057                 fadd    ds:__real@4020000000000000
.text:0040105D                 fstp    [esp+4+var_4]
.text:00401060                 fld     [esp+4+var_4]
.text:00401063                 fadd    ds:__real@4022000000000000
.text:00401069                 fstp    [esp+4+var_4]
.text:0040106C                 fld     [esp+4+var_4]
.text:0040106F                 pop     ecx
.text:00401070                 retn
.text:00401070 licz            endp

gdzie kolejne :__real@... to kolejne stałe - 1.0, 2.0, 3.0...
Natomiast przy ustawieniu na jak najmniejszy kod funkcja licz została włączona w main:

.text:00401003                 push    ecx
.text:00401004                 push    ecx
.text:00401005                 fldz
.text:00401007                 mov     [ebp+var_4], 1
.text:0040100E                 fstp    [ebp+var_8]
.text:00401011
.text:00401011 loc_401011:                             ; CODE XREF: _main+21j
.text:00401011                 fild    [ebp+var_4]
.text:00401014                 inc     [ebp+var_4]
.text:00401017                 cmp     [ebp+var_4], 0Ah
.text:0040101B                 fadd    [ebp+var_8]
.text:0040101E                 fstp    [ebp+var_8]
.text:00401021                 jl      short loc_401011
.text:00401023                 fld     [ebp+var_8]

Sytuacja się chyba nieco wyjaśniła?
Teraz może powiem na sucho kilka słów o użyciu liczb zmiennoprzecinkowych. W przypadku C czy C++ sprawa jest jasna, jeżeli część wyrażenia jest liczbą zmiennoprzecinkową wynik takiego wyrażenia również nią jest... Nie ma znaczenia do czego przypisujesz, konwersja jest dokonywana w momencie przypisania, po wykonaniu całej prawej strony. Przypisujesz to do inta? Całe wyrażenie jest ewaluowane jako float /ew. wyodrębiniane są niezależne operacje na liczbach całkowitych i liczone oddzielnie/ i konwertowane. Z resztą popatrzcie na powyższe kody, użyte kompilatory są zgodne ze standardami. Fr3 ma rację, sposób konwersji można zmienić. Odsyłam do dokumentacji kompilatorów itd...
Nie obchodzi mnie wasz durny spór, może byście się zainteresowali jak to jest zrealizowane, jakie są założenia...

Nadęty deusik? Cóż, napisałem co było do napisania, konkretnie i rzeczowo na oryginalny temat tego wątku. Jakieś UFO zarzuciło mi niewiedzę, zaczęło bluzgać, gdy trzeba było konkrety podać to dziwnym trafem zniknęło... pewnie Marooned z Lofiksem odwiedzili chłopaka... Zawsze gdy ktoś napisze coś konkretnego zjawiają się od razu specjaliści gotowi krytykować bez podawania konkretów. Stwierdziłem, że mieszać się nie będę, zdawkowo komentowałem jedynie wyczyny niektórych.
Ludzie, poczytajcie dokumentację, sprawdźcie swoje teorie zanim coś napiszecie... przestaje mnie to bawić. Dlaczego rozważam wyczyszczenie tego tematu? Tylko pierwsza strona coś wnosi, kolejne to przede wszystkim różne herezje przeplatane niedomówieniami i sporami. PHP szybsze od kodu maszynowego... muszę link do tamtego postu do perełek dodać...

Jeszcze jedna sprawa, owszem popełniłem błąd, tak jak fr3 powiedział, 'tylko' na P4, nie zaś jak stwierdziłem - 'od'.

Hm... czas jaki miałem poświęcić na doskonalenie się w lispie poświęciłem na napisanie tego postu :/

OK, mam nadzieję, że przywróciłem nieco porządku w temacie?

0
deus napisał(a)

Po pierwsze taki znawca jak Ty powinien przedstawić konkrety. Po drugie powinien zauważyć błędy w obu kodach przedstawionych przez fr3m3na...

Tu zgoda, błędy były, pisane bez sprawdzenia

Cóż, wyniki mówią same za siebie, nie muszą być dokładne. Fantazyjny kod fr3m3na jest po prostu wolny... fr3, sam pisałeś jak szybki jest dostęp do danych w cache'u - w nim mieszczą się wartości tymczasowe drugiego algorytmu, obroty stosu fpu zaś jednak kosztują, chociażby czas dekoderów.

Ten test to tragedia - więcej czasu zajmuje czyszczenie rejestrów niż same pętle. 10 iteracji to zdecydowanie za mało, a optymalizacja polega przecież na przyśpieszeniu wnętrza pętli, nie otoczki.
(do tego te ffreep... ffree tam starczy a jest dużo szybszy)

Prawidłowe wyniki są takie:

AMD Turion x64 1,6 (działający na 800 mhz) napisał(a)

C:\tmp>test
ticks: 35250
ticks: 38688

C:\tmp>test
ticks: 36578
ticks: 38782

C:\tmp>test
ticks: 36641
ticks: 38687

Pierwszy wynik to wersja float, drugi z intem.
Nikt nie miał racji, oba kody są praktycznie równoważne.
Większa różnica istniałaby gdyby kod był otoczony innymi obliczeniami (nie związanymi z x i suma) -dla 'otoczenia' całkowitego lepszym wyborem byłaby wersja z floatem, dla 'otoczenia' floatowego - intowa.

Chyba koniec dyskusji o tej jednej małej pętli :)

P.S Oczywiście w przypadku akurat tej jednej pętli, z stała wartością, całość zostałaby wykonana albo w czasie kompilacji, albo chociaż rozbita na 10 operacji, bez pętli. Cała dyskusja ma sens tylko w przypadku gdy wartość 'x' nie jest znana podczas kompilacji.

A oto kod testu:

format PE console
include 'C:\fasm\Include\win32ax.inc'
entry start

section '.code' code readable executable

proc start
     fninit
     fldcw [float_precision]
     invoke GetTickCount
     mov [time],eax
     mov ecx,1000
@@:
     call kod1
     ffree st0 ;wartosc zwrocona z kod1
loop @b
     call wyswietl
     invoke GetTickCount
     mov [time],eax
     mov ecx,1000
@@:
     call kod2
     ffree st0
loop @b
     call wyswietl
     invoke  ExitProcess,0
endp

proc wyswietl
      invoke GetTickCount
      sub eax,[time]
      cinvoke printf,<"ticks: %d",0x0A,0x0D>,eax
      ret
endp

proc kod1
align 4
     fld [ile_f] ;zaladuj 10000.0
     fld1 ;warunek
     fldz ;suma
     fldz ;x
     ;st0-x st1-suma st2-1.0 st3=warunek
     align 4
     jmp .in
@@:
     fadd st1,st0 ;dodaj x do suma
.in:
     fucomi st3 ;porownaj x z warunkiem koncowym
     fadd st0,st2 ;dodaj 1
     db 0x3E
     jb @b

     ffree st0
     ffree st2
     ffree st3
     fincstp
     ret
endp

proc kod2
     push 1 ;x
     fldz ;suma
     mov ebx,esp
align 4
@@:
     cmp dword[ebx],ile_i
     db 0x2E
     jge @f
     fild dword[ebx]
     faddp st1,st0
     inc dword[ebx]
     db 0x3E
     jmp @b
align 4
@@:
     pop eax
     ; wynik w st0
     ret
endp

section '.data' data readable writeable
time dd 0

section '.rdata' data readable
float_precision dw 0x7f
ile_f dq 10000000.0
ile_i = 10000000

section '.idata' import data readable writeable
library kernel32,"kernel32.dll",msvcrt,"msvcrt.dll"
import kernel32,ExitProcess,"ExitProcess",GetTickCount,"GetTickCount"
import msvcrt,printf,"printf"
0
fr3 napisał(a)

Ten test to tragedia - więcej czasu zajmuje czyszczenie rejestrów niż same pętle. 10 iteracji to zdecydowanie za mało, a optymalizacja polega przecież na przyśpieszeniu wnętrza pętli, nie otoczki.
(do tego te ffreep... ffree tam starczy a jest dużo szybszy)
Test to tragedia? Odtworzenie stanu stosu koprocesora to tragedia? Zakładając, że stos na wstępie był pusty faktycznie można użyć ffree. W Twoim kodzie zaś etykiety nie są wyrównane - różne skoki mają różne warunki, do tego masz call, który też wpływa na wyniki, zmniejsza różnice, takie rzeczy się inline'uje. Zmieniłem to w kodzie podanym przeze mnie w poprzednim poście, nowe wyniki testu:

  • Mój PIII 1GHz:
bash-2.03$ ./times.EXE
cykli: 0000000498f7954f
cykli: 00000000d41093db
bash-2.03$ ./times.EXE
cykli: 0000000422f4b867
cykli: 00000000514c2750
bash-2.03$ ./times.EXE
cykli: 0000000472c2db74
cykli: 000000007867f743
  • Celeron M 1.6GHz
cykli: 00000004ffc1e8a9
cykli: 000000009cf7a282
  • AMD Sempron Processor 2600+ (at 1608 MHz)
cykli: 000000006e0dbbee
cykli: 000000003e4ebcbb
  • AMD Duron 1.3GHz /spory rozrzut jest niestety/
cykli: 000000006a1a54fa
cykli: 000000003d7b4014

cykli: 00000000a1f12ee2
cykli: 00000000769dbd94

cykli: 00000000391e14d0
cykli: 000000010d2a26bc

cykli: 00000000c6109898
cykli: 000000009a5c5084

cykli: 000000004da83ad7
cykli: 0000000122605934

cykli: 000000009e6b2f7b
cykli: 000000007252be0c

cykli: 0000000129f21ad5
cykli: 00000000fdd7293c

cykli: 00000000e1822072
cykli: 00000000b2b3199c
  • PIII Mobile 1.13GHz
cykli: 00000003ca3aef79
cykli: 00000000bef2ccc4
  • AMD Turion 2.0 GHz
cykli: 00000000f6668684
cykli: 00000000a113af61

cykli: 0000000124a3eb78
cykli: 00000000c5219789

cykli: 0000000139b39db3
cykli: 00000000d4a15bb7
  • AMD Athlon 1700XP [1,47GHz]
cykli: 00000000e82adddc
cykli: 000000009bd72076

cykli: 00000000e298eeab
cykli: 0000000096b0944c
  • Athlon 2600+ (Barton)
cykli: 0000000092b18ca2
cykli: 00000000663f9728

cykli: 000000008c5945e8
cykli: 0000000061f1cce6

cykli: 0000000092673c07
cykli: 0000000066eac67a

cykli: 000000005046269e
cykli: 00000001262138d1

cykli: 0000000047349d5e
cykli: 000000011c0dde5b

Kod w ostatnim poście fr3m3na został zoptymalizowany nieco... ekhm.. zauważyłem po testach, ale inna sprawa jest tu ważna.
I tu doskonale widać zależność - różnice w architekturach. Na Intelach bez porównania szybszy jest standardowy kod, na AMD natomiast różnice nie są wielkie, na nowszych kod fr3m3na faktycznie może nawet być szybszy.

fr3 napisał(a)

Nikt nie miał racji, oba kody są praktycznie równoważne.
Większa różnica istniałaby gdyby kod był otoczony innymi obliczeniami (nie związanymi z x i suma) -dla 'otoczenia' całkowitego lepszym wyborem byłaby wersja z floatem, dla 'otoczenia' floatowego - intowa.

Chyba koniec dyskusji o tej jednej małej pętli

Gdy zapewnić obu kodom identyczne warunki wydajność zależy wyłącznie od architektury, im nowszy AMD tym większą przewagę ma kod pierwszy. Na Intelach zaś zawsze obroty są wolniejsze.
I kto miał rację? Obaj mieliśmy :-) Ty jako zwolennik AMD i ja jako zwolennik Intela... Teraz już można powiedzieć. że dyskusja o jednej małej pętli dobiegła końca.

Tak swoją drogą to troche styl Ci się popsuł fr3, widać, że dawno w asm nie pisałeś...

Dobra, to może dodam jeszcze wyniki testów nowego algo fr3m3na - czyste fpu, już bez obrotów i innego kobinowania:

  • Mój PIII 1GHz:
bash-2.03$ ./fr3.exe
ticks: 52425
ticks: 119712
bash-2.03$ ./fr3.exe
ticks: 51595
ticks: 123237
bash-2.03$ ./fr3.exe
ticks: 54298
ticks: 132541
  • Athlon 2600+ (Barton @1917MHz)
ticks: 29094
ticks: 28687
  • Core 2 Duo T550
ticks: 25516
ticks: 42406
  • Celeron 1.7 GHz
ticks: 55531
ticks: 52219

ticks: 55907
ticks: 52625
  • AMD Duron 1.6GHz
ticks: 33797
ticks: 33859

ticks: 42453
ticks: 39000
  • AMD Sempron Processor 2600+ (at 1608 MHz)
ticks: 35937
ticks: 39344

AMD X2 4000+

ticks: 25203
ticks: 29031
  • Sempron 2500MHz
ticks: 38328
ticks: 40515
  • PentiumD 2.8Ghz; test wykonany pod... wine :>
ticks: 29972
ticks: 27867
  • Celeron M 1.6GHz
ticks: 42344
ticks: 55063
  • AMD Sepmron 3000+
ticks 33797
ticks:35125
  • Core 2 Duo 6300 @ 1.86GHz
ticks: 23078
ticks: 33937
  • AMD Athlon 64 3500+
ticks: 24094
ticks: 29156

Kolejne wyniki dorzucę za jakiś czas... póki co zbieramy z fr3, na analizę przyjdzie czas później :-)

p.s. dziękuję ekipie #4programmers za pomoc w testach /w szczególności Bula, fr3, Gynvael, Judge, Kele, LukaStrz, Marooned, mith, nav, quetzalcoatl, qyon, Ranides/... i już nie tylko 4p, uw też się włączyło, dzięki [browar]

0

Ale się popisaliście, nad takim badziewiem tyle deliberować. :-D

obliczcie coś konkretnego np. sumę takiego szeregu:

a_n = (2/3+sin(n)/3)^n/n, n = 1, 2,... oo

0

ee.. a co by to zmienilo poza wymiana paru instrukcji FPU na inne..?

ps. imho, on rzeczywiscie nie ma nic do powiedzenia konkretnego..

0
quetzalcoatl napisał(a)

ee.. a co by to zmienilo poza wymiana paru instrukcji FPU na inne..?

To jest szereg nieskończony i dodatkowo nie ma dowodu na jego zbieżność.
Szereg podobny do harmonicznego: 1/n, ale tu ten sinus oscyluje
i nie wiadomo jak często wypada sin(n) blisko 1.

0

A co ma szereg do optymalizacji kodu? Czyżbyś chciał nas zagiąć swoją wiedzą? Z reguły jest tak, że ludzie, którzy nie potrafią wnieść nic do dyskusji (brak wiedzy, argumentów, totalny laicyzm) odbiegają do tematu, z którego coś lizneli aby następnie pokazać swoim towarzyszom dyskusji, że jednak to oni są gorsi.

Jeżeli potrafisz przedstawić problematykę tego szeregu to proszę bardzo. Wykaż się ale to nic nie wniesie do tej dyskusji :)

0
CyberKid napisał(a)

A co ma szereg do optymalizacji kodu? Czyżbyś chciał nas zagiąć swoją wiedzą? Z reguły jest tak, że ludzie, którzy nie potrafią wnieść nic do dyskusji (brak wiedzy, argumentów, totalny laicyzm) odbiegają do tematu, z którego coś lizneli aby następnie pokazać swoim towarzyszom dyskusji, że jednak to oni są gorsi.

Nie marudź.
Masz problem praktyczny, a nie takie tam pierdoły teoretyczne
o wyższości dwurdzeniowca 1.5GHz nad jednordzeniowcem 3GHz,
zwłaszcza w procesie z jednym wątkiem.

Oblicz chociaż sumę tryliona pierwszych wyrazów z błędem poniżej 1%. :-D

0

Słuchaj qu, nic nie wniosłeś do dyskusji, nic nie pokazałeś. Co ma błąd w obliczeniach do optymalizacji? Napisz coś na temat, przedstaw jakieś swoje algo i wytłumacz optymalizację, możemy podyskutować. Skrytykowałeś kod fr3m3na, że wolny? OK... tylko, że tak się mu przypatrzyłeś, że oczywistych błędów nie zauyważyłeś... testować też nie testowałeś. A właśnie, zobacz o czym ten temat, może odniesiesz się jakoś do pierwszego postu? Napiszesz coś konkretniej niż inni?

A propos, swoim ostatnim postem udowodniłeś, zę CyberKid ma rację :-).

qu napisał(a)

Oblicz chociaż sumę tryliona pierwszych wyrazów z błędem poniżej 1%. :-D

Napisz algo, które zrobi to w rozsądnym czasie :>

0
qu napisał(a)

Oblicz chociaż sumę tryliona pierwszych wyrazów z błędem poniżej 1%. :-D

A umiesz stranąć na głowie i kręcić się na niej przez kilka sekund? Założe się, że nawet nie utrzymasz pionu a co dopiero będziesz się kręcił. Takie pierdoły tu wrzucasz o jakiś szeregach. Po co Ci to w życiu? Kręć się na głowie, to jest lepsze.

0

Myślę, że efekt żyroskopowy Ci pomoże. Tylko musisz się dostatecznie szybko kręcić. [green]

A wracając do tematu: przy obecnych prędkościach procków bardzo istotne jest też rozsądne korzystanie z pamięci. Pamięć jest o wiele wolniejsza niż procek i spudłowanie w cache mocno boli. Dlatego np. zbyt agresywne inline'owanie wszystkiego, czy odwijanie pętli może skończyć się spadkiem wydajności, mimo mniejszej liczby skoków i mniejszej liczby wykonanych instrukcji.

Ogólnie moja rada jest taka: nie robić optymalizacji dopóki wydajność nie jest problemem.
A jeśli jest, w pierwszej kolejności przejrzeć, czy nie ma się gdzieś jakiegoś idiotycznego kopiowania tablicy 1MB na każdy obrót pętli, albo czy nie czyta się pliku po jednym znaku. Złe algorytmy i/lub takie głupie błedy są najczęstszymi przyczynami kiepskiej wydajności a nie to, czy ktoś napisał "for (float x = ...)" czy "for (int x = ...)"

// qu: Z tym szeregiem to nieźle wyjechałeś. Chłopie, masz za dużo czasu zajmować się jakimiś teoretycznymi pierdołami? Chcesz trudny praktyczny problem, to Ci dam: wyjdź na miasto w godzinach szczytu, zrób 100 fotek, a następnie napisz program, który na każdym zdjęciu rozpozna i zaznaczy wszystkie samochody / ludzi / rowery itp. Przy czym musi rozpoznać również obiekty częściowo zasłonięte.

0
Krolik napisał(a)

Ogólnie moja rada jest taka: nie robić optymalizacji dopóki wydajność nie jest problemem.

Masz rację ale to zastosowałbym raczej do mniejszych projektów. Współczesne procesory są takie szybkie ponieważ posiadają masę rozwiązań przyspieszających ich działanie. Weźmy chociaż taki potok dekodowania instrukcji. Wychodzi na to, że wykonanie większości z nich zabiera o wiele mniej mikro-opów niż w pierwszych procesorach. Znacznie przyspiesza to działanie programu dlatego 300 MHz na procesorze bez potoku nie jest nijak równe 300 MHz na proceszerze z potokiem. MHzy to wcale nie jest moc komputera. Różnicę widać np. gdy w jakiejś grze włączamy lub wyłączamy obsługę akceleratora grafiki. Przed i po procesor pracuje z taką samą częstotliwością, a jednak gra działa szybciej i lepiej. Dzieje się tak dlatego, że używamy dodatkowego układu jakim jest akcelerator graficzny. Podobnie jest z układami zaimplementowanymi w CPU.

Jestem bardzo zadowolony z mojego Dual Core T7200 z 1 GB RAMu. Bardzo często moja praca wygląda tak: kilka edytorów tekstu, FireFox z masą zakładek, 2 kopie oryginalnego Gadu-gadu + 1 kopia konnekta, IDA, DEV c++ lub Visual C++, debugging tools for windows, WinAmp, VMWare i pare innych. Dzięki nowoczesnym technologiom zaimplementowanym w mojej maszynie jest ona w stanie zdzierżyć to wszystko na raz. Gdyby jednak każdy z twórców oprogramowania którego używam myślał: skoro mamy szybkie procesory to po co mamy się gimnastykować, to byłbym w stanie pracować co najwyżej na połowie z wymienionych aplikacji jednocześnie. Gdybym zatem w takim wypadku dostał informację: przepraszamy ale nie chciało nam się optymalizować kodu, to bym się lekko podirytował...

0

Aplikacje desktopowe to inna bajka. Ale też nie do przesady. Nie obchodzi mnie, czy system po załadowaniu zjada 100 MB RAMu czy 120. Ale jeśli w wyniku głupiego błędu zjadałby 2GB to bym się wnerwił. Tylko że to byłby już ten przypadek podpadający pod "dopóki nie sprawia problemów". Jeśli program ma dobrze przemyślaną architekturę, algorytmy i struktury danych, to na ogół nie sprawia problemów.

0
deus napisał(a)

Słuchaj qu, nic nie wniosłeś do dyskusji

Jak to nic?

  • ta bitowa operacja dająca wynik modulo 2 była bardzo dobrym przykładem na przyspieszenie.
    Sprawdź co kompilator wygeneruje z instrukcji:
    if( i % 2 == 1 ) i czy faktycznie wyeliminuje dzielenie.

  • albo te arcy nieoptymalne operacje na piętrowych wskaźnikach w VCL:
    forma66->Image55->Bitmap2->Canvas->... powtarzane wielokrotnie w pętli.

deus napisał(a)
qu napisał(a)

Oblicz chociaż sumę tryliona pierwszych wyrazów z błędem poniżej 1%. :-D

Napisz algo, które zrobi to w rozsądnym czasie :>

Właśnie liczyłem na wasze propozycje - jakieś przekształcenie grupujące wyrazy tej sumy,
albo transformacja Fouriera, czy nawet od razu aproksymować szereg całką i ciachnąć to np. kwadraturką Gaussa...

Przykładowo:
suma po k=1..n: 1/k = ln(n) + stała, i bardzo szybko zsumujemy taki trylionik. :-D

aha, mam jeszcze bardzo zaawansowane obliczenia rekurencyjne do zanalizowania:

inline double fibek(uint n) // n > 0
{ return n > 2 ? fibek(n-1)+fibek(n-2) : 1; }

1 użytkowników online, w tym zalogowanych: 0, gości: 1