Jeg tror kun at det kan gøres lidt hurtigere, mod at koden bliver lidt
grimmere.
Jeg kan ikke se at algoritmen kan forbedres, medmindre værdierne har nogle
særlige egenskaber der kan udnyttes.
Kan man skære ned i antallet af gange den bliver kaldt, ved at ændre
algoritme på et højere niveau ?
Det er sikkert der den største mulighed for optimering ligger.
Jeg har målt på et fast dataset, bestående af 1000 tilfældige tal på en IA32
maskine.
Målingerne er naturligvis meget afhængige af compiler og CPU arkitektur.
Programmet er oversat med Microsoft Visual C++ V6.0, og målt med en sampling
profiler på en lang kørsel.
Min måle reference er meget tæt på hvad du postede (de små ændringer skyldes
ikke performance, men personlig preference i kode stilen):
<code>
double interpolate_1(const double pos)
{
int min = 0;
int max = x.size()-1;
if(pos <= x[min])
return y[min];
if(pos >= x[max])
return y[max];
while(1 != (max - min)) {
const int guess = (max+min)/2;
if(x[guess] < pos)
min = guess;
else if(x[guess] > pos)
max = guess;
else
return y[guess];
}
return y[min] + (y[max]-y[min])/(x[max]-x[min])*(pos-x[min]);
}
</code>
Sammenligningen
while(1 != (max - min)) {
tager knap 10 % af tiden.
Ved at udnytte at inde i løkken tildeles "max" ca. halvt så ofte som "min"
kan man gøre betigelsen i løkken simplere:
while(max_minus_one != min) {
// ...
else if(x[guess] > pos)
max_minus_one = (max = guess) -1;
// ...
Det giver noget der ligner 5-7 % forbedret hastighed.
I et forsøg på at udnytte CPU'ens flere pipelines
if(x[guess] < pos)
min = guess;
else {
max_minus_one = (max = guess) -1;
if(x[guess] == pos)
return y[guess];
}
udnyttes at der som regel gælder at "x[guess] != pos".
Ved at optimere for det mest almindelige tilfælde når ikke "x[guess] <
pos"og tildele "max" uden yderligere test og derefter teste på om "x[guess]
== pos" kan tildelingen og testen måske foregå parallelt på CPU niveau.
Det giver en performance forbedring på godt 1%.
Jeg prøvede at cache "x[guess]" for at spare beregningen af adressen, men
det giver en performance degradering, fordi "x[guess]" kun bliver læst een
gang fra hukommelsen og lagt på FPU stakken, hvor den så bliver brugt 2
gange.
Et forbedret bud er således:
<code>
double interpolate_4(const double pos)
{
int min = 0;
int max = x.size()-1;
if(pos <= x[min])
return y[min];
if(pos >= x[max])
return y[max];
int max_minus_one = max - 1;
while(max_minus_one != min) {
const int guess = (max+min)/2;
if(x[guess] < pos)
min = guess;
else {
max_minus_one = (max = guess) -1;
if(x[guess] == pos)
return y[guess];
}
}
return y[min] + (y[max]-y[min])/(x[max]-x[min])*(pos-x[min]);
}
</code>
Er "x" og "y" data-medlemmer i en klasse ?
Hvis de er, kan det så svare sig at cache en reference til "x", for at spare
adresse beregning ?
Når man kigger på den generede assembler kode fra
if(x[guess] < pos)
//..
else if(x[guess] > pos)
// ..
bliver der lavet 2 floating point compare, hvor man egentlig kunne nøjes med
1 og derefter lave 2 betingede jump (f.eks. jae og jbe).
Linien
else if(x[guess] > pos)
står for ca 15 % af eksekveringstiden.
Mit bud er at ca. 10 % af eksekveringtiden her ville kunne spare, hvis man
kunne nøjes med 1 compare.
Det kan jeg dog ikke set er muligt i C++ - medmindre compileren kan gøre
det, og det kan mine ikke.
Derfor er et seriøst bud, hvis funktionen virkelig er kritisk og selv små
forbedringer er nødvendige, at skrive den i assembler.
Samlet set ville jeg forvente en 10-20 % forbedring, mod at det ikke er
portabelt.
Hvis det er på en IA32 maskine kan Intel VTune profileren være en utrolig
god hjælp til at hjælpe med optimere for at holde gang i pipelines etc.
Da koden laver binær søgning, vil manuel loop-unrolling kune minimere
antallet af gennemløb af løkken sættes meget ned, og koden gøres mere
lineær.
<code>
double interpolate_5(const double pos)
{
int min = 0;
int max = x.size()-1;
if(pos <= x[min])
return y[min];
if(pos >= x[max])
return y[max];
while(true) {
int guess = (max+min)/2;
switch(max-min) {
case 32:
case 31:
case 30:
case 29:
case 28:
case 27:
case 26:
case 25:
case 24:
case 23:
case 22:
case 21:
case 20:
case 19:
case 18:
case 17:
(x[guess] < pos ? min : max ) = guess;
if(x[guess] == pos)
return y[guess];
guess = (max+min)/2;
// fall through
case 16:
case 15:
case 14:
case 13:
case 12:
case 11:
case 10:
case 9:
(x[guess] < pos ? min : max ) = guess;
if(x[guess] == pos)
return y[guess];
guess = (max+min)/2;
// fall through
case 8:
case 7:
case 6:
case 5:
(x[guess] < pos ? min : max ) = guess;
if(x[guess] == pos)
return y[guess];
guess = (max+min)/2;
// fall through
case 4:
case 3:
(x[guess] < pos ? min : max ) = guess;
if(x[guess] == pos)
return y[guess];
guess = (max+min)/2;
// fall through
case 2:
(x[guess] < pos ? min : max ) = guess;
if(x[guess] == pos)
return y[guess];
// fall through
case 1:
return y[min] + (y[max]-y[min])/(x[max]-x[min])*(pos-x[min]);
default:
(x[guess] < pos ? min : max ) = guess;
if(x[guess] == pos)
return y[guess];
guess = (max+min)/2;
(x[guess] < pos ? min : max ) = guess;
if(x[guess] == pos)
return y[guess];
guess = (max+min)/2;
(x[guess] < pos ? min : max ) = guess;
if(x[guess] == pos)
return y[guess];
guess = (max+min)/2;
(x[guess] < pos ? min : max ) = guess;
if(x[guess] == pos)
return y[guess];
guess = (max+min)/2;
(x[guess] < pos ? min : max ) = guess;
if(x[guess] == pos)
return y[guess];
guess = (max+min)/2;
}
}
}
</code>
Det kører på på ca. 80 % af den oprindelige kodes køre tid.
Det sidste niveau af loop-unrolling ser ikke ud til at give væsentlige
forbedringer for mine testdata.
Koden klarer sig med max n gennemløb for max 32^n datapunkter.
Bemærk iøvrigt at koden ikke er tilstrækkeligt godt testet.
Koden bør testes _meget_ grundigt inden det sættes i produktion.
Så måske med manuel loop-unrolling i assembler kan man komme ned på 60-70%
af den oprindelige kodes køre tid
Intel C++ V6.0 ser iøvrigt ud til at kunne køre funktionen på ca. 97 % af
den tid MSVC 6.0 bruger begge med almindelig release style, og en lille
smule hurtigere når der bruges "profile guided optimization".
Venlig hilsen
Mogens Hansen