[es] - Sta je brze za min (moze i max)?

mmix
Miljan Mitrović
Chief Software Architect
Financial Intelligence Software Ltd.
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6050

+4631 Profil

Sta je brze za min (moze i max)?

^{26.10.2013. u 10:44 - pre 140 meseci}

Recimo da program treba da uradi stotine miliona puta (mozda i milijardu) minum dva broja. Sta je brze?

Pitanje je malo komplikovanije kad se ubaci optimizacija, multi-threading i moderna arhitektura (cache miss) u pricu.

Code (c):

int min(int x, int y)

{

    return x < y ? x : y;

}

// ili 

int min(int x, int y)

{

    return (x < y) * x + !(x < y) * y;

}

Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog
naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji
je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan,
sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv - Z.Đinđić

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3570

Jabber: djoka_l

+1527 Profil

Re: Sta je brze za min (moze i max)?

^{26.10.2013. u 11:22 - pre 140 meseci}

Prva funkcija radi čitanje dve memorijske lokacije, jednu komparaciju. Druga čita dve memorijske lokacije, radi dve komparacije, dva množenja i jedno sabiranje. Nema sumnje, osim ako neka luda optimizacija shvati šta se radi, da druga rutina bude brža.
Ako radiš C++, funkcija je odličan kandidat za inline, pa nema zezanja sa stekom.

Odgovor na temu

Igor Gajic

Član broj: 93194
Poruke: 747
*.dynamic.isp.telekom.rs.

+987 Profil

Re: Sta je brze za min (moze i max)?

^{26.10.2013. u 12:20 - pre 140 meseci}

Ako imas bas toliko komparacija koje radis u odjednom, onda mozes da predjes na asembler i SSE.

PMINSW trazi minimum od 16 bitnih integera, i moze da izvrsi 8 komapracija po instrukciji. Kombinovano sa MFENCE, PREFETCHh moze da se izvuce maksimum od procesora, tj. da ti memorijski protok ne bude bottleneck.

Dugo nisam radio u asembleru, tako da mogu ponuditi samo uopstene direkcije....

Odgovor na temu

mmix
Miljan Mitrović
Chief Software Architect
Financial Intelligence Software Ltd.
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6050

+4631 Profil

Re: Sta je brze za min (moze i max)?

^{26.10.2013. u 18:05 - pre 140 meseci}

Ne, ja sam radio merenja inline, nije to frka. Samo nisam hteo da kacim svoje rezultate da ne uticem na druge

Nije konkretna prakticna primena, pa da idem na asembler, vise je pitanje akademsko, pa onda prakticne problematike.

Fora je sto je drugu rutinu pokupio ortak od negde i "prodaje" mi kao superiornu. Moja merenja medjutim to ne potkrepljuju. Sa ukljucenom optimizacijom dobijam 20% sporije, bez optimizacije skoro duplo sporije, bez nekog uticaja paralelizacije.

Prica, zbog koje i nisam odmah odbio tvrdnju, je da se drugom rutinom izbegava branching, te da se optimalno koristi L1/L2 kes. I to nije daleko od istine, ?: ima branching, dok drugi nema, tj bar ne bi trebao da ima. Medjutim, ne vidim da se nedostatak branchinga materijalizovao, moja sumnja je na to da ili kompajler izbegava nekako branching u ?: (hmm?) ili na to da moj procesor (2600K) ima dovoljno dobar branch predictor da mu je branching u ovom slucaju non-issue. Nazalost, zbog drugih obaveza nisam jos imao vremena da se poigram sa ovim kodom na nivou asemblera.

Odgovor na temu

Ivan Dimkovic

Administrator
Član broj: 13
Poruke: 16752
*.dip0.t-ipconnect.de.

+7204 Profil

Re: Sta je brze za min (moze i max)?

^{26.10.2013. u 19:22 - pre 140 meseci}

@mmix,

Evo sta Intel kompajler daje (asembler) na -O2, iskljucen inline - obe f-je su podrutine bez unrolling-a:

Prva varijanta:

Code:

; parameter 1(x): ecx
; parameter 2(y): edx

        cmp       ecx, edx                                      ;9.3
        cmovl     edx, ecx                                      ;9.3
        mov       eax, edx                                      ;9.3
        ret                                                     ;9.3

^ jedno poredjenje sa kondicionalnim mov-om.

Druga varijanta:

Code:

; parameter 1(x): ecx
; parameter 2(y): edx

        mov       r8d, 1                                        ;16.3
        xor       eax, eax                                      ;16.3
        xor       r9d, r9d                                      ;16.3
        cmp       ecx, edx                                      ;16.3
        cmovl     eax, r8d                                      ;16.3
        cmovge    r9d, r8d                                      ;16.3
        imul      eax, ecx                                      ;16.3
        imul      r9d, edx                                      ;16.3
        add       eax, r9d                                      ;16.3
        ret                                                     ;9.3

^ Malo vise operacija ;-) - mada je dobar deo njih ocigledno suvisan ako se kod inlajnuje

Ako se ostavi inlining, stavi -O3, kompajler ce unroll-ovati ako je moguce i, naravno, inlajnovati.

Ali i pored toga ce ti prva f-ja biti brza.

Kompajler i jednu i drugu f-ju prevodi u asm koristeci cmov instrukcije.

DigiCortex (ex. SpikeFun) - Cortical Neural Network Simulator:
http://www.digicortex.net/node/1 Videos: http://www.digicortex.net/node/17 Gallery: http://www.digicortex.net/node/25
PowerMonkey - Redyce CPU Power Waste and gain performance! - https://github.com/psyq321/PowerMonkey

Odgovor na temu

mmix
Miljan Mitrović
Chief Software Architect
Financial Intelligence Software Ltd.
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6050

+4631 Profil

Re: Sta je brze za min (moze i max)?

^{26.10.2013. u 23:19 - pre 140 meseci}

Vidis zanimljiv kod, kompajler ocigledno nije odradio optimizaciju kako treba. Trebalo bi da zna da rezultat bool oepracije moze da im bude 0/1 tako da je imul potpuni visak ovde. I X not(X) je isto podlozno optimizaciji. Mada, koliko god da ga optimizuje, i meni se cini da je varijanta jedan definitivni pobednik.

Odgovor na temu

Ivan Dimkovic

Administrator
Član broj: 13
Poruke: 16752
*.dip0.t-ipconnect.de.

+7204 Profil

Re: Sta je brze za min (moze i max)?

^{26.10.2013. u 23:38 - pre 140 meseci}

Probaj da implementiras drugu varijantu u asembleru najoptimalnije moguce cisto da vidimo koja je minimalna moguca razlika izmedju prve i druge varijante.

Btw, moderni Intel-ovi procesori su izuzetno dobri u branch predikciji tako da je izbegavanje po svaku cenu upitna praksa.

Inace, VS2012 kompajler daje malo drugaciji kod za drugu varijantu:

Code:

; 16   :   return (x < y) * x + !(x < y) * y;

    xor    r8d, r8d
    cmp    ecx, edx
    mov    eax, r8d
    setl    al
    imul    eax, ecx
    cmp    ecx, edx
    setge    r8b
    imul    r8d, edx
    add    eax, r8d
    ret 0

Odgovor na temu

X Files
Vladimir Stefanovic
Pozarevac

SuperModerator
Član broj: 15100
Poruke: 4939
*.dynamic.sbb.rs.

+646 Profil

Re: Sta je brze za min (moze i max)?

^{27.10.2013. u 08:38 - pre 140 meseci}

Treba pogledati i ovo, makar radi eksperimenta:
http://www.elitesecurity.org/t247378-Bit-Twiddling-Hacks
http://graphics.stanford.edu/~.../bithacks.html#IntegerMinOrMax

Odgovor na temu

mmix
Miljan Mitrović
Chief Software Architect
Financial Intelligence Software Ltd.
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6050

+4631 Profil

Re: Sta je brze za min (moze i max)?

^{27.10.2013. u 13:29 - pre 140 meseci}

Mislim da nema ptorebe, iskreno, nakon sto sam video implementaciju ?: koju si okacio.

registry to registry cmovX ne moze da izazove ni branch prediction failure ni cache miss, samim tim je dalja prica bespredmetna. Ne verujem da postoji optimalnije resenje od tog.

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8704
*.dynamic.isp.telekom.rs.

+2801 Profil

Re: Sta je brze za min (moze i max)?

^{28.10.2013. u 14:58 - pre 140 meseci}

Mislim da je pitanje iz naslova izlišno. Kad bi mi to neko prodavao, ja ne bih upio, ali bih mu čestitao. Sa takvima ne vredi raspravljati.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu