[ mmix @ 26.10.2013. 10:44 ] @
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;
}
 


[ djoka_l @ 26.10.2013. 11:22 ] @
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.
[ Igor Gajic @ 26.10.2013. 12:20 ] @
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....

[ mmix @ 26.10.2013. 18:05 ] @
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.
[ Ivan Dimkovic @ 26.10.2013. 19:22 ] @
@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.
[ mmix @ 26.10.2013. 23:19 ] @
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.
[ Ivan Dimkovic @ 26.10.2013. 23:38 ] @
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
[ X Files @ 27.10.2013. 08:38 ] @
Treba pogledati i ovo, makar radi eksperimenta:
http://www.elitesecurity.org/t247378-Bit-Twiddling-Hacks
http://graphics.stanford.edu/~.../bithacks.html#IntegerMinOrMax
[ mmix @ 27.10.2013. 13:29 ] @
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.
[ Nedeljko @ 28.10.2013. 14:58 ] @
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.