[C/C++] optimalisatie probleem

[Coca-Cola]

Ik ben bezig met het schrijven van een programma waarin de volgende functie nogal veel (lees 60%) van de tijd in beslag neemt:

code:

   double dist = 0.0, dist_tmp;
    for(int i = 0; i < dim; i++)
    {
        dist_tmp = (mapvector[i] - datavector[i]);
        dist += dist_tmp * dist_tmp;
    }
    return dist;

Oftewel, ik heb 2 arrays met doubles die ik van elkaar af wil trekken en dan per waarde kwadrateer en dan return ik de som van al deze kwadraten (ik bereken maw de 'euclidean' distance tussen 2 vectoren)
Nou heb ik wel al een aantal optimalisaties geimplementeerd, maar die zorgen alleen dat deze functie minder wordt aangeroepen. Het daadwerkelijk optimaliseren van deze functie zou echt heel veel tijd schelen. Is er misschien iemand die mij hiermee kan helpen?
Ik heb zelf al gekeken naar het 'unrollen' van de for loop en dat soort dingen, maar met de juiste compiler optimalisatie instellingen gebeurt dat al vanzelf

Bvd!

[johnwoo]

SSE instructies gebruiken om een hele batch dimensions tegelijk van elkaar af te trekken?

[Coca-Cola]

daar zat ik idd zelf ook al aan te denken, maar ik heb geen idee hoe ik zoiets in mijn code kwijt moet. Ik zal er in ieder geval eens op gaan googlen!

[staefke]

je zou eens kunnen kijken bij http://www.codeproject.com/cpp/sseintro.asp

[Coca-Cola]

hmm volgens mij werkt sse alleen op floats en niet op doubles en mijn programma moet op een computer draaien zonder sse2 dus dat wordt ff niks... ben nu bezig uit te zoeken of ik eventueel met floats kan werken, maar ik betwijfel het

[Zoijar]

Je zou het misschien als vertex program gedeeltelijk door je GPU kunnen laten doen.

Waar gebruik je dit dan? Minimalisatie MSE bij compressie? Misschien kan je je algoritme veranderen zodat het incremental werkt. Ie. als je een punt veranderd, dan bereken je de niewe waarde op basis van de vorige en dat punt.

[Coca-Cola]

Ik ben bezig een programma te schrijven dat input data moet gaan clusteren. Om een goede clustering te bereiken moet ik de 'afstand' tussen een input data vector en een data vector op de cluster map berekenen, en dat dan heel vaak. Dit is echt een wezenlijk deel van het algoritme, dus dat kan ik niet aanpassen. Misschien is het echter wel mogelijk dezelfde afstandswaarden te krijgen op een andere manier, maar dan zou die formule dus herschreven moeten worden en daar mis ik de wiskundige kennis voor.

[Zoijar]

Ik dacht aan zoiets: http://ieeexplore.ieee.org/xpl/abs_free.jsp?arNumber=969446 . Maar verder weet ik het ook niet, je kan die formule zelf niet sneller schrijven. Misschien dat zoeken op fast mean square error oid iets oplevert.

[MSalters]

Zijn die twee vectoren ook doubles?

[Coca-Cola]

yep, de vectoren zijn doubles... maar misschien kan ik er floats van maken... dan zou ik dus die sse instructies kunnen gebruiken

hmm de map kwaliteit gaat nogal achteruit van floats, dus dat gaat waarschijnlijk niet werken

[ Voor 28% gewijzigd door Coca-Cola op 14-07-2004 14:28 ]

[Soultaker]

Welke compiler gebruik je? Hoe ziet de gegenereerde code eruit? Soms kun je dit soort dingen nog wel redelijk optimaliseren door de gegenereerde code te nemen en die aan te passen. Je kunt dan ook goed zien of loops daadwerkelijk unrolled worden (is dim bijvoorbeeld een compile time constant?).

Overigens denk ik dat de tijd verloren gaat doordat de FPU veel moet rekenen; loop unrolling zal misschien wel iets schelen, maar ik vermoed dat het niet heel veel uitmaakt.

[ Voor 25% gewijzigd door Soultaker op 14-07-2004 15:02 ]

[Coca-Cola]

ik gebruik nu gcc version 3.3.3 en op de computer waar het straks op gecompiled en gedraait moet worden draait (GCC) 3.2.2 (lui systeembeheer ) Hoe de code er uit ziet kan ik nu ff niet checken.
Die dim wordt runtime uitgelezen uit een input file en het unrollen heb ik geprobeert, maar zelfs als ik de for helemaal unrol (je kan je maar vervelen) wordt het er niet sneller op (je kan met optimize options bij de compiler al zoiets instellen)

[Infinitive]

Is die wortel trouwens van belang voor je afstandsmaat?
[edit] Laat maar zitten. Je gebruikt niet eens een wortel. Niet goed gekeken (beter: niet correct herinnert. Ik had alleen euclidische afstand onthouden...)

[ Voor 70% gewijzigd door Infinitive op 14-07-2004 15:36 ]

[Soultaker]

Als ik de functie zo schrijf:

C:

double dist(int dim, double *v, double *w)
{
        double dist = 0.0, diff;
        unsigned n;
        for(n = 0; n < dim; ++n)
        {
                diff = v[n] - w[n];
                dist += diff*diff;
        }
        return dist;
}

Dan genereert GCC 3.3.3 met -O3 als optie de volgende code:

GAS:

dist:
        pushl   %ebp
        movl    %esp, %ebp
        movl    8(%ebp), %ecx
        xorl    %eax, %eax
        cmpl    %ecx, %eax
        pushl   %ebx
        movl    16(%ebp), %edx
        movl    12(%ebp), %ebx
        fldz
        jae     .L8
.L6:
        fldl    (%edx,%eax,8)
        fsubrl  (%ebx,%eax,8)
        incl    %eax
        fmul    %st(0), %st
        cmpl    %ecx, %eax
        faddp   %st, %st(1)
        jb      .L6
.L8:
        popl    %ebx
        leave
        ret

Hij stopt de pointers in %ebx en %edx en de dimensie in %ecx. Vervolgens gebruikt 'ie %eax om van 0 tot %ecx (dim) te tellen. De code tussen de labels is de body van de for-loop en daarin worden de daadwerkelijke berekeningen uitgevoerd; zoals je ziet bestaat die uit slechts vier FPU instructies; een load en een sub om het verschil tussen twee elementen te berekenen, een mul om 'm te kwadrateren, en een FPU add om de som bij te werken.

Naar mijn idee is dit redelijk efficiënte 386 code; er valt niet veel aan te optimaliseren zonder naar een geavanceerdere instructieset over te schakelen, waarmee je de elementen parallel kunt aftrekken en vervolgens kunt optellen. Misschien zou loop unrolling kunnen helpen om de processor zover te krijgen om het aftrekken en vermenigvuldigen parallel uit te voeren, maar da's maar een gok.

Misschien dat ik later nog wat performance testing kan doen, maar ik heb daar nu even geen tijd voor.

[Macros]

Als je de forloop omdraait, scheelt het ongeveer 1% snelheid. Dat komt omdat het vergelijken van 2 vars langer duurt dan he vergelijken van 1 var met 0 sneller is. Ook kan bij sommige compilers --i sneller zijn dan i--, omdat hij dan geen tussen waarde hoeft te onthouden.

C:

    double dist = 0.0, dist_tmp;
    for(int i = dim-1; i >= 0; --i)
    {
        dist_tmp = (mapvector[i] - datavector[i]);
        dist += dist_tmp * dist_tmp;
    }
    return dist;

Ik vermoed dat dim niet erg groot is in jouw geval. Als ie wel groot wordt, dus 20+ ofzo, en hij is niet constant bij compile time. Dan kan je handmatig unrollen.
Mijn ervaring met handmatig unrollen van een loop als de size niet constant is werkte best wel goed. Bij grote dimensies tot 30% snelheids winst.
Stel je rolled er 4 op: (8, 16, 32, etc gaan analoog)

C:

static dist(){
    // n = aantal loops
    unsigned int v = n >> 2; // /4
    unsigned int r = n - v << 2; // *4
    unsigned int i, j;
    double dist = 0;
    for(i = 0; i < v; i++){
        j = i >> 2; // i /4
        dist += qd(j);
        dist += qd(++j);
        dist += qd(++j);
        dist += qd(++j);
    }
    i = n-r;
    switch (r){
        case 4: dist += qd(i--);
        case 3: dist += qd(i--);
        case 2: dist += qd(i--);
        case 1: dist += qd(i--);
    }
    return dist;
}
static inline double qd(int i){
    int diff = (mapvector[i] - datavector[i]);
    return diff * diff;
}

Hier gebruik ik unsigned int, omdat als je * en / daarop doet, moet de compiler dat wel optimaliseren naar shifts. Nu gebruik ik die i en j, maar het moet ook alleen met een i kunnen, dat scheelt dan weer wat berekeningen, maar ik kan het nu even niet testen, en dan ga ik niet teveel proberen. Ik roep nu een functie aan, dat is geen probleem als je hem inline declareerd.

[ Voor 6% gewijzigd door Macros op 14-07-2004 16:20 ]

[12_0_13]

In plaats van geindexte array (of vector) een iterator of pointer gebruiken, omdat je precies weet hoe je hem ophoogt of verlaagt:

C:

double * mapvector_ptr  = &mapvector;
double * datavector_ptr = &datavector;
int i = dim-1;
while (i!=0)
{
 dist_tmp = *mapvector_ptr++ - *datavector_ptr++;
 dist += dist_tmp * dist_tmp;
 --i;
}

Als je nauwkeurigheid niet erg belangrijk is, en je beriek niet al te groot kan je ook fixed point gebruiken.
En dan ook nog MMX

Edit: helaas blijkt uit even testen dat dit niet significant sneller is , zelfs langzamer op mijn pIII

[ Voor 20% gewijzigd door 12_0_13 op 14-07-2004 16:59 ]

[Macros]

Als je pointers en loop unrolling gebruikt, gaat het denk ik het snelst. Ik heb net loop unrolling even getest, met deze functie:

C:

static inline int dos(int i){
    int y = i + 15;
    return (i * i + 5) * 16;
}

Die gaat bij 8 keer unrollen 25% sneller dan zonder unrollen. Als je de indexerings berekeningen eruit haalt door gebruik te maken van pointers, moet dat ook wel weer een paar %en schelen
Als je floats gaat gebruiken en precisie inboet in samenwerking met sse kan je ook wel een versnelling van 50-200% verwachten.

[Soultaker]

12_0_13 schreef op 14 juli 2004 @ 16:40:
In plaats van geindexte array (of vector) een iterator of pointer gebruiken, omdat je precies weet hoe je hem ophoogt of verlaagt:

Dat heb ik ook overwogen maar ik ben er niet van overtuigd dat dat uitkan. Als ik mijn code herschrijf naar:

C:

double dist(int dim, double *v, double *w)
{
        double dist = 0.0;
        while(dim)
        {
                double diff = *(v++) - *(w++);
                dist += diff*diff;
                --dim;
        }
        return dist;
}

Dan ziet de gegenereerde code in de body van de for-loop er als volgt uit (oude code links, nieuwe code rechts):

GAS:

  fldl    (%edx,%eax,8)   |     fldl    (%eax)
  fsubrl  (%ebx,%eax,8)   |     fsubrl  (%edx)
- incl    %eax            |   
                          |   + addl    $8, %eax
                          |   + addl    $8, %edx
  fmul    %st(0), %st     |     fmul    %st(0), %st
- cmpl    %ecx, %eax      |
                          |   + decl    %ecx
  faddp   %st, %st(1)     |     faddp   %st, %st(1)

Omdat je de inc en dec instructies tegen elkaar zou kunnen wegstrepen, ruil je effectief de vergelijking tussen twee registers in voor twee optellingen van een register met een constante, plus dat je misschien voordeel haalt uit de simpelere operands voor fld en fsubr. Al met al ben ik er niet van overtuigd dat dat beter is. (In jou code zat trouwens een foutje, vandaar dat ik mijn eigen implementatie geef.)

[ Voor 10% gewijzigd door Soultaker op 14-07-2004 17:06 ]

[Verwijderd]

Misschien komt dit nog van pas:

http://www.amd.com/us-en/...s_and_tech_docs/22007.pdf

[Verwijderd]

Heeft het bezwaren om deze code als C99 te compileren? Zo nee, probeer eens of dit sneller is?

C++:

    double dist = 0.0, dist_tmp;
    for(int i = 0; i < dim; i++)
    {
        dist_tmp = (mapvector[i] - datavector[i]);
#ifdef FP_FAST_FMA
        dist= fma(dist_tmp, dist_tmp, dist);
#else
        dist += dist_tmp * dist_tmp;
#endif
    }
    return dist;

Dit maakt gebruik van een evt. "multiply-and-add" instructie van de FPU als die minimaal even snel is als de aparte vermenigvuldiging en optelling. (Vergeet niet #include <math.h> c.q. <cmath> in je code op te nemen.)

[ Voor 4% gewijzigd door Verwijderd op 14-07-2004 19:46 ]