Lassen N
eine vorzeichenlose Ganzzahl zur Kompilierzeit sein.
GCC kann optimieren
unsigned sum = 0;
for(unsigned i=0; i<N; i++) sum += a; // a is an unsigned integer
zu einfach a*N
. Dies kann verstanden werden, da die modulare Arithmetik sagt (a%k + b%k)%k = (a+b)%k
.
GCC wird jedoch nicht optimiert
float sum = 0;
for(unsigned i=0; i<N; i++) sum += a; // a is a float
zu a*(float)N
.
Aber durch die Verwendung von assoziativer Mathematik mit zB -Ofast
Ich entdeckte, dass GCC dies in Ordnung reduzieren kann log2(N)
Schritte. Bsp für N=8
es kann die Summe in drei Additionen machen.
sum = a + a
sum = sum + sum // (a + a) + (a + a)
sum = sum + sum // ((a + a) + (a + a)) + ((a + a) + (a + a))
Obwohl irgendwann danach N=16
GCC geht zurück zum Tun N-1
Summen.
Meine Frage ist, warum GCC nicht funktioniert a*(float)N
mit -Ofast
?
Anstatt zu sein O(N)
oder O(Log(N))
es könnte einfach sein O(1)
. Seit N
zur Kompilierzeit bekannt ist, ist es möglich festzustellen, ob N
passt in einen Schwimmer. Und selbst wenn N
ist zu groß für einen Schwimmer, den es tun könnte sum =a*(float)(N & 0x0000ffff) + a*(float)(N & ffff0000)
. Tatsächlich habe ich einen kleinen Test gemacht, um die Genauigkeit zu überprüfen und a*(float)N
ist sowieso genauer (siehe Code und Ergebnisse unten).
//gcc -O3 foo.c
//don't use -Ofast or -ffast-math or -fassociative-math
#include <stdio.h>
float sumf(float a, int n)
{
float sum = 0;
for(int i=0; i<n; i++) sum += a;
return sum;
}
float sumf_kahan(float a, int n)
{
float sum = 0;
float c = 0;
for(int i=0; i<n; i++) {
float y = a - c;
float t = sum + y;
c = (t -sum) - y;
sum = t;
}
return sum;
}
float mulf(float a, int n)
{
return a*n;
}
int main(void)
{
int n = 1<<24;
float a = 3.14159;
float t1 = sumf(a,n);
float t2 = sumf_kahan(a,n);
float t3 = mulf(a,n);
printf("%f %f %f\n",t1,t2,t3);
}
Das Ergebnis ist 61848396.000000 52707136.000000 52707136.000000
was zeigt, dass Multiplikation und die Kahan-Summe haben das gleiche Ergebnis, was meiner Meinung nach zeigt, dass die Multiplikation genauer ist als die einfache Summe.
Haben Sie darüber nachgedacht, dass drei Additionsoperationen möglicherweise schneller sind als eine Fließkomma-Multiplikation? Dies würde damit übereinstimmen, dass es bei N = 16 auf eine fp-Multiplikation zurückschaltet.
– Bob
15. Oktober 2015 um 15:29 Uhr
Es führt keine Optimierung durch, weil die Optimierung nicht gültig ist; im Allgemeinen führt es zu einem anderen Ergebnis. Gleitkomma-Arithmetik gehorcht nicht den üblichen normalen arithmetischen Eigenschaften, die Sie erwarten, wie Assoziativität oder das Distributivgesetz. Multiplikation ist keine wiederholte Addition.
– R.. GitHub HÖR AUF, EIS ZU HELFEN
15. Oktober 2015 um 15:40 Uhr
@R..: Er verwendet (implizit).
-ffast-math
die tut erlauben diese Art von Optimierungen. stackoverflow.com/questions/7420665/…– Karoly Horvath
15. Oktober 2015 um 15:42 Uhr
Wenn
-Ofast
impliziert-ffast-math
dann mischt sich diese Frage-ffast-math
und Kahan-Summierung, die kein gutes Rezept ist (Kahan-Summierung ist das prototypische Beispiel für Code, der nicht mit nicht konformen Optimierungen kompiliert werden darf).– Pascal Cuoq
15. Oktober 2015 um 23:50 Uhr
@Zboson: Es ist höchst nicht offensichtlich (sogar Kahan war schockiert, als ich ihm diese Tatsache erzählte, obwohl er sofort verstand, warum es wahr war, als ich es ihm sagte). Der einfachste Weg, um zu sehen, dass es wahr ist, besteht wahrscheinlich darin, die Rundung für alle möglichen nachgestellten Bitmuster von x gründlich zu überprüfen, wenn Sie neugierig sind. Ein tieferer Beweis kann wahrscheinlich erreicht werden, indem man beweist, dass (2^n – 1)x + x = 2^nx ist, wenn 2^n-1 darstellbar ist, und dann beachtet, dass x + x + x = 3x. Die Eigenschaft gilt für 2, 3, 4 und 5; 6 ist das erste n, für das es fehlschlägt.
– Stefan Kanon
16. Oktober 2015 um 13:58 Uhr