[C++] optimalisatie probleempje

[Zoijar]

Ik heb het volgende stukje code:

C++:

void piCurveRecurse(int level, int x, int y) {
    if (level > 1) {
        /* recurse */
        level >>= 1;

        piCurveRecurse(level, x,       y);
        piCurveRecurse(level, x,       y+level);
        piCurveRecurse(level, x+level, y+level);
        piCurveRecurse(level, x+level, y);
    } else {
        /* output vertex */
        nodesoutput++;
        //Gaia::blaat(x, y);
        heightsamples->fetchHeightSample(x, y);
    }
}

Met 16 miljoen vertices duurt het bovenstaande zo'n 10 seconden. De fetchheigth sample member functie is leeg, returned gewoon 0.

Nu heb ik ook die blaat() functie gemaakt die leeg is en 0 returned (wordt zeker niet inlined) en dan duurt het 0,5 seconden.

Dus een indirectie member functie herhaaldelijk aanroepen is 20 keer zo traag als een gewone functie aanroep. Ik vind dat vreemd gedrag, je zou denken dat het wel gecached wordt in L1 of L2.

[Verwijderd]

(met welke compiler werk je?)
Kan je niet tijdens het uitvoeren op assembly niveau door de instructies heenstappen, en dan naar het verschil (tussen die twee) kijken. Als blaat inlined wordt gemaakt en dan verder weggeoptimaliseerd en fetchHeightSample is een memory indirect jump (uit geheugen ophalen waarnaartoe er gesprongen moet worden) kan het inderdaad wel veel langer duren.

[Zoijar]

Verwijderd schreef op 17 februari 2004 @ 13:37:
(met welke compiler werk je?)
Kan je niet tijdens het uitvoeren op assembly niveau door de instructies heenstappen, en dan naar het verschil (tussen die twee) kijken. Als blaat inlined wordt gemaakt en dan verder weggeoptimaliseerd en fetchHeightSample is een memory indirect jump (uit geheugen ophalen waarnaartoe er gesprongen moet worden) kan het inderdaad wel veel langer duren.

Ja dat heb ik al gedaan. Blaat() wordt idd gewoon een call 12345, en die andere wordt iets van "mov eax,[ebx] mov eax,[eax+ebx] call [eax]" zoiets in ieder geval. Ik wist nooit dat het zo veel zou schelen. Ik dacht dat al die indirects in principe in 1 tick zouden gaan vanwege cache...blijkbaar niet

[Soultaker]

Hmz, lijkt me dat het niet zoveel hoeft te schelen. Als ik het goed begrijp gaat het om het uitvoeren van ofwel Gaia::blaat() (een static member function) ofwel heightsamples->fetchHeightSample(x, y), maar niet beiden?

Kun je een wat vollediger voorbeeld laten zien en daarbij vermelden hoe je 'm test? (Welke compiler, welke optimalisaties, bijbehorende assembly code desnoods)

[ Voor 61% gewijzigd door Soultaker op 17-02-2004 14:31 ]

[Count]

Het inlinen van blaat() en compileren in Release mode zal waarschijnlijk een stuk helpen.

[Verwijderd]

Wedje leggen dat je het grootste snelheids-verschil bereikt door de functie niet meer recursief te maken ..?

Edit: Sorry, probleem niet goed gelezen

[ Voor 18% gewijzigd door Verwijderd op 17-02-2004 17:52 ]

[.oisyn]

is fetchHeightSample virtual? Dat heeft over het algemeen wel invloed, maar een factor 20 vind ik wel overdreven

Ik heb even een testje gedraaid (Athlon xp 3200+);
Als fetchHeightSample niet virtual is

0.300236 seconds
0.312036 seconds
0.289774 seconds
0.294467 seconds
0.291954 seconds

Als ie wel virtual is

0.389757 seconds
0.373421 seconds
0.36544 seconds
0.374421 seconds
0.371735 seconds

En dit was in debug-mode
(in release is het ongeveer 0.11 vs 0.18 seconden)

[ Voor 6% gewijzigd door .oisyn op 17-02-2004 21:39 ]

[MSalters]

Uiteraard moet het non-virtual zijn; dat is je eerste 30%. Verder, voor zo'n frequente aanroep wil je gewoon dat die geinlined wordt. VC7 zou dat moeten kunnen, zeker met LTGC, en andere compilers zouden dat ook moeten kunnen als fetchHeightSample() in de header staat. Je assembly suggereert dat het een virtual call is. Dat betekent 100% zeker een pipeline stall, omdat je voor de call [eax] niet weet wat eax is, en je dus de pipeline niet kunt vullen. Pentium 4, toevallig?

In zulke gevallen kan een handmatige typeswitch helpen:

code:

if (x.type==1) foo_type1( args );
else if (x.type==2) foo_type2( args );
else if (x.type==3) foo_type3( args );

heeft tot gevolg dat de CPU wel een branch-prediction probeert. In een geval waarin alle types even waarschijnlijk zijn heb je dan nog maar een 66% branch misprediction op de eeste jump.