porzebuje kodu ktory dla zadanych trzech
intow

int a = 4;
int b = 19;
int c = 2;
....

int min = ...
int max = ...

zwroci najmniejsza i najwieksza wartosc
przy jak najmniejszej liczbie porownan
(tak zeby szybko dzialalo no jest odpalane w petli)

int min = min(min(a,b),c);
int max = max(max(a,b),c);

chyab nie jest optymalne, zreszta chyba wolalbym uniknac systemowych min() i max() bo
zawsze boje sie
ze sa wolne - nie wiem czy slusznie

do góry

W dniu 2013-12-04 18:36, firr pisze:
> porzebuje kodu ktory dla zadanych trzech intow
>
> int a = 4; int b = 19; int c = 2; ....
>
> int min = ... int max = ...
>
> zwroci najmniejsza i najwieksza wartosc przy jak najmniejszej liczbie
> porownan (tak zeby szybko dzialalo no jest odpalane w petli)
>
> int min = min(min(a,b),c); int max = max(max(a,b),c);
>

Przecież to proste.

int m,M;

if (a>b)
{
M=a;
m=b;
}
else
{
M=b;
m=a;
}

if (c>M)
M=c;
else if (c<m) m=c;

> chyab nie jest optymalne, zreszta chyba wolalbym uniknac systemowych
> min() i max() bo zawsze boje sie
> ze sa wolne - nie wiem czy slusznie

Niesłusznie. Są szybkie.

Ale przy jednoczesnym wyznaczaniu min i max da się
to zrobić szybciej, jeśli robi się jednocześnie.
Tak jak powyżej, mamy maksymalnie 3 porównania, (średnio
2+2/3(?)) a wyznaczając osobno min i max mielibyśmy 4.


W c++11 mamy funkcję minmax, zwracającą uporządkowaną parę
oraz minmax_element, działający na kontenerze.

Szukając naraz min i max w tablicy n elementów, wykonuje
się 1.5n porównań, zamiast 2n.

pzdr
bartekltg

do góry

W dniu środa, 4 grudnia 2013 18:55:37 UTC+1 użytkownik bartekltg napisał:
> W dniu 2013-12-04 18:36, firr pisze:
>
> > porzebuje kodu ktory dla zadanych trzech intow
>
> >
>
> > int a = 4; int b = 19; int c = 2; ....
>
> >
>
> > int min = ... int max = ...
>
> >
>
> > zwroci najmniejsza i najwieksza wartosc przy jak najmniejszej liczbie
>
> > porownan (tak zeby szybko dzialalo no jest odpalane w petli)
>
> >
>
> > int min = min(min(a,b),c); int max = max(max(a,b),c);
>
> >
>
>
>
> Przecież to proste.
>
>
>
> int m,M;
>
>
>
> if (a>b)
>
> {
>
> M=a;
>
> m=b;
>
> }
>
> else
>
> {
>
> M=b;
>
> m=a;
>
> }
>
>
>
> if (c>M)
>
> M=c;
>
> else if (c<m) m=c;
>
>
>
> > chyab nie jest optymalne, zreszta chyba wolalbym uniknac systemowych
>
> > min() i max() bo zawsze boje sie
>
> > ze sa wolne - nie wiem czy slusznie
>
>
>
> Niesłusznie. Są szybkie.
>

moze sa szybkie a moze nie sa - trzebaby chyba zawsze sprawdzac :c przy tym chyba
szybsze od
napisania tego ifem z reki nie są ? min to
logicznie zupelnie inna instrukcja niz if
(teoretycznie chyba powinna byc tańsza -
czesto mowi sie ze branche sa drogie)

dzis mnie glowa boli i nie moge sie skupic,
co do tej wersji to chyba tak tyle ze napisalem
wersje rozwinietą

if(a<b)
{
if(a<c)
{
min = a;

if(b<c)
{
max = c;
}
else
{
max = b;
}
}
else //a > c & a<b
{
min = c;
max = b;
}
}
else //a>b
{
if(a>c)
{
max = a;

if(b>c)
{
min = c;
}
else
{
min = b;
}


}
else //a>b & a<c
{
min = b;
max = c;
}

}

ale ciagle nie wiem czy nie daloby sie moze
tego jakos jeszcze podoptymalizowac, przepisywanie
na asma by cos dalo?



>
>
> Ale przy jednoczesnym wyznaczaniu min i max da się
>
> to zrobić szybciej, jeśli robi się jednocześnie.
>
> Tak jak powyżej, mamy maksymalnie 3 porównania, (średnio
>
> 2+2/3(?)) a wyznaczając osobno min i max mielibyśmy 4.
>
>
>
>
>
> W c++11 mamy funkcję minmax, zwracającą uporządkowaną parę
>
> oraz minmax_element, działający na kontenerze.
>
>
>
> Szukając naraz min i max w tablicy n elementów, wykonuje
>
> się 1.5n porównań, zamiast 2n.
>
>
>
> pzdr
>
> bartekltg

do góry

W dniu 2013-12-04 19:29, firr pisze:
> W dniu środa, 4 grudnia 2013 18:55:37 UTC+1 użytkownik bartekltg napisał:
>> W dniu 2013-12-04 18:36, firr pisze:
>>
>>> porzebuje kodu ktory dla zadanych trzech intow
>>
>>>
>>
>>> int a = 4; int b = 19; int c = 2; ....
>>
>>>
>>
>>> int min = ... int max = ...
>>
>>>
>>
>>> zwroci najmniejsza i najwieksza wartosc przy jak najmniejszej liczbie
>>
>>> porownan (tak zeby szybko dzialalo no jest odpalane w petli)
>>
>>>
>>
>>> int min = min(min(a,b),c); int max = max(max(a,b),c);
>>
>>>
>>
>>
>>
>> Przecież to proste.

>> int m,M;

>> if (a>b)
>> {
>> M=a;
>> m=b;
>> }
>> else
>> {
>> M=b;
>> m=a;
>> }

>> if (c>M)
>> M=c;
>> else if (c<m) m=c;

>>
>>
>>
>> Niesłusznie. Są szybkie.
>>
>
> moze sa szybkie a moze nie sa - trzebaby chyba zawsze sprawdzac :c przy tym chyba
szybsze od
> napisania tego ifem z reki nie są ? min to


W c++ min _jest_ napisany ifem. W c podejrzewam, że też.

> logicznie zupelnie inna instrukcja niz if
> (teoretycznie chyba powinna byc tańsza -
> czesto mowi sie ze branche sa drogie)

Nie ma chyba w x86 i pochodnch instrukcji procesora wybirającej
min albo max z inta lub zmiennego przecinka. Ale w pewnych prockach
są:
http://www.ti.com/lit/ug/sprueo2a/sprueo2a.pdf

>
> dzis mnie glowa boli i nie moge sie skupic,
> co do tej wersji to chyba tak tyle ze napisalem
> wersje rozwinietą
>
> if(a<b)
> {
> if(a<c)

[ciach]

A co to za kloc?
Dostałeś przecież _całą_ procedurę. Nic więcej nie trzeba.

pzdr
bartekltg

do góry

>
>
> [ciach]
>
>
>
> A co to za kloc?
>
> Dostałeś przecież _całą_ procedurę. Nic więcej nie trzeba.
>

no to jest to samo tylka ta krotsza nadpisuje
ram dwa razy, moze te bylaby costam szybsza
(choc ciezko powiedziec - najlepiej by bylorozmawaic o procedurach w asmie ale
niestety
malo kto zna dzis asma na przyzwoitym poziomie)

do góry

Użytkownik "firr" <p...@g...com> napisał w wiadomości
news:500c67b8-6712-4449-942a-eb02a783732a@googlegrou
ps.com...
>
>
> [ciach]
>
>
>
> A co to za kloc?
>
> Dostałeś przecież _całą_ procedurę. Nic więcej nie trzeba.
>
==========================================
>no to jest to samo tylka ta krotsza nadpisuje
>ram dwa razy, moze te bylaby costam szybsza
>(choc ciezko powiedziec - najlepiej by bylorozmawaic o procedurach w asmie ale
niestety
>malo kto zna dzis asma na przyzwoitym poziomie)

tragedia - poczytaj sobie coś o używanych narzędziach
jeśli to VS - a wydaje się, że tak to
/FA , /FAs

http://msdn.microsoft.com/en-us/library/367y26c6.asp
x


i możesz sobie zobaczyć w asm jak kompilator to zrobił za ciebie
zapewne - jak jest optymalizacja - to nieważne co napiszesz i tak
wyjdzie to samo :)))

do góry

W dniu 2013-12-04 20:05, firr pisze:
>>
>>
>> [ciach]
>>
>>
>>
>> A co to za kloc?
>>
>> Dostałeś przecież _całą_ procedurę. Nic więcej nie trzeba.
>>
>
> no to jest to samo tylka ta krotsza nadpisuje
> ram dwa razy, moze te bylaby costam szybsza

Ta funkcja przy dobrej optymalizacji w ogóle nie dotyka RAMu
aż do ostatecznego zapisu.


> (choc ciezko powiedziec - najlepiej by bylorozmawaic o procedurach w asmie ale
niestety


A proszę, lekko zmodyfikowana wersja, kompiluje się w VS2010
do ciut lepszego kodu. Miałem podać w c++, ale skoro chcesz w asm.

Argumenty przychodzą w edx, r8d, r9d, wynik do pamięci pod
adres trzymany w rcx (hmm)

ciało funkcji:

cmp edx, r8d
jge SHORT $LN7@minmax3
mov eax, edx //WTF
mov edx, r8d //tu było swap(a,b)
mov r8d, eax //czemu nie po prostu xchg?
$LN7@minmax3:
cmp r9d, edx
jle SHORT $LN3@minmax3
mov edx, r9d

mov DWORD PTR [rcx+4], r8d
mov rax, rcx
mov DWORD PTR [rcx], edx

> malo kto zna dzis asma na przyzwoitym poziomie)

Wiec się ucz, ucz.

pzdr
bartekltg

do góry

On Wednesday, December 4, 2013 10:09:28 PM UTC+1, bartekltg wrote:
> ciało funkcji:
> cmp edx, r8d
> jge SHORT $LN7@minmax3
> mov eax, edx //WTF
> mov edx, r8d //tu było swap(a,b)
> mov r8d, eax //czemu nie po prostu xchg?
>
> $LN7@minmax3:
>
> cmp r9d, edx
> jle SHORT $LN3@minmax3
> mov edx, r9d
> mov DWORD PTR [rcx+4], r8d
> mov rax, rcx
> mov DWORD PTR [rcx], edx
>

Bez sensu te skoki. Porządny kompilator uprości to do przesłań
warunkowych, bo na nowszych architekturach będzie szybsze od skoków.

Nieliniowa zmiana przepływu sterowania to złoooo! :)

w.

do góry

W dniu 2013-12-04 23:16, Wojciech Muła pisze:
> On Wednesday, December 4, 2013 10:09:28 PM UTC+1, bartekltg wrote:
>> ciało funkcji:
>> cmp edx, r8d
>> jge SHORT $LN7@minmax3
>> mov eax, edx //WTF
>> mov edx, r8d //tu było swap(a,b)
>> mov r8d, eax //czemu nie po prostu xchg?
>>
>> $LN7@minmax3:
>>
>> cmp r9d, edx
>> jle SHORT $LN3@minmax3
>> mov edx, r9d
>> mov DWORD PTR [rcx+4], r8d
>> mov rax, rcx
>> mov DWORD PTR [rcx], edx
>>
>
> Bez sensu te skoki. Porządny kompilator uprości to do przesłań
> warunkowych, bo na nowszych architekturach będzie szybsze od skoków.
>

To wypluł całkiem porządny kompilator;>

> Nieliniowa zmiana przepływu sterowania to złoooo! :)

Prawda.
:)

pzdr
bartekltg

do góry

W dniu 2013-12-04 23:16, Wojciech Muła pisze:
> On Wednesday, December 4, 2013 10:09:28 PM UTC+1, bartekltg wrote:
>> ciało funkcji:
>> cmp edx, r8d
>> jge SHORT $LN7@minmax3
>> mov eax, edx //WTF
>> mov edx, r8d //tu było swap(a,b)
>> mov r8d, eax //czemu nie po prostu xchg?
>>
>> $LN7@minmax3:
>>
>> cmp r9d, edx
>> jle SHORT $LN3@minmax3
>> mov edx, r9d
>> mov DWORD PTR [rcx+4], r8d
>> mov rax, rcx
>> mov DWORD PTR [rcx], edx
>>
>
> Bez sensu te skoki. Porządny kompilator uprości to do przesłań
> warunkowych, bo na nowszych architekturach będzie szybsze od skoków.
>
> Nieliniowa zmiana przepływu sterowania to złoooo! :)

Nakarmiłem lepszy kompilator (gcc 4.8.1)

funkcja:
pair <int,int> minmax3 (int a, int b, int c)
{
if (a<b)
swap(a,b);
if (c>a)
a=c;
else if (c<b)
b=c;

return make_pair(a,b);

}

BTW, wie ktoś, jak uzyskiwać ładniejszy plik asm w gcc?
W tej chwili dodaje -g -fverbose-asm -Wa,-adhls=test.s


872:../rozne2/main.cpp **** w = minmax3(a,b,c);
18998 008c 8B542430 movl 48(%rsp),%edx
18999 0090 8B44242C movl 44(%rsp),%eax
19001 0094 8B5C2440 movl 64(%rsp),%ebx

829:../rozne2/main.cpp **** if (a<b) swap(a,b);
19005 .loc 1 829 0
19006 0098 39C2 cmpl %eax,%edx

19007 009a 7F06 jg .L1161
19008 009c 89D1 movl %edx,%ecx
19009 009e 89C2 movl %eax,%edx
19010 .LVL1838:
19011 00a0 89C8 movl %ecx,%eax
19012 .LVL1839:
19013 .L1161:
831:../rozne2/main.cpp **** if (c>a)
19014 .loc 1 831 0
19015 00a2 39D3 cmpl %edx,%ebx
19016 00a4 7F07 jg .L1162
19017 00a6 39D8 cmpl %ebx,%eax
19018 00a8 0F4FC3 cmovg %ebx,%eax
19019 .LVL1840:
19020 00ab 89D3 movl %edx,%ebx
19021 .LVL1841:
19022 .L1162:
...

cmov użył dopiero dla ostatniego warunku/przypisania.

Wersja z poprzedneigo posta też używa tylko raz:
w = minmax2(a,b,c);
18995 .loc 1 889 0
18996 0053 8B542430 movl 48(%rsp),%edx
18997 0057 8B44242C movl 44(%rsp),%eax
18998 .LVL1833:
18999 005b 8B5C2440 movl 64(%rsp),%ebx
19000 .LVL1834:
19001 .LBB13789:
19002 .LBB13790:
842:../rozne2/main.cpp **** if (a>b)
19003 .loc 1 842 0
19004 005f 39C2 cmpl %eax,%edx
19005 0061 7D06 jge .L1162
19006 0063 89D1 movl %edx,%ecx
19007 0065 89C2 movl %eax,%edx
19008 .LVL1835:
19009 0067 89C8 movl %ecx,%eax
19010 .LVL1836:
19011 .L1162:
853:../rozne2/main.cpp **** if (c>M)
19012 .loc 1 853 0
19013 0069 39D3 cmpl %edx,%ebx
19014 006b 7F07 jg .L1163
19015 006d 39D8 cmpl %ebx,%eax
19016 006f 0F4FC3 cmovg %ebx,%eax
19017 .LVL1837:
19018 0072 89D3 movl %edx,%ebx

Nawet po zamianie
if (c>M) M=c;
else if (c<m) m=c;
na
if (c>M) M=c;
if (c<m) m=c;

Jednak te skoki nie są takie straszne, czy kompilator
za głupi? cmov to chyba już pentium pro.


I też używają trzech instrukcji i dodatkowego rejestru
na swap. Czyżby jednak było to szybsze niż xchg?
Internet twierdzi, że nie.
A CMPXCHG?

pzdr
bartekltg

do góry