Dies ist eine Frage, die mir beim Lesen der brillanten Antwort von Mysticial auf die Frage in den Sinn kam : Warum ist es schneller, ein sortiertes Array zu verarbeiten als ein unsortiertes Array ?
Kontext für die beteiligten Typen:
const unsigned arraySize = 32768;
int data[arraySize];
long long sum = 0;
In seiner Antwort erklärt er, dass der Intel Compiler (ICC) dies optimiert:
for (int i = 0; i < 100000; ++i)
for (int c = 0; c < arraySize; ++c)
if (data[c] >= 128)
sum += data[c];
... in etwas Äquivalentes dazu:
for (int c = 0; c < arraySize; ++c)
if (data[c] >= 128)
for (int i = 0; i < 100000; ++i)
sum += data[c];
Der Optimierer erkennt, dass diese äquivalent sind, und tauscht daher die Schleifen aus , wodurch der Zweig außerhalb der inneren Schleife bewegt wird. Sehr schlau!
Aber warum macht es das nicht?
for (int c = 0; c < arraySize; ++c)
if (data[c] >= 128)
sum += 100000 * data[c];
Hoffentlich kann Mysticial (oder sonst jemand) eine ebenso brillante Antwort geben. Ich habe noch nie etwas über die Optimierungen erfahren, die in dieser anderen Frage besprochen wurden, deshalb bin ich wirklich dankbar dafür.
quelle
volatile
wären, wäre der Schleifenaustausch ebenfalls eine ungültige Optimierung.Antworten:
Der Compiler kann im Allgemeinen nicht transformieren
in
weil das letztere zu einem Überlauf von vorzeichenbehafteten ganzen Zahlen führen könnte, während das erstere dies nicht tut. Selbst bei einem garantierten Wrap-Around-Verhalten für den Überlauf von vorzeichenbehafteten Zweierkomplement-Ganzzahlen würde sich das Ergebnis ändern (wenn
data[c]
30000 ist, würde das Produkt-1294967296
für die typischen 32-Bit-int
s mit Wrap-Around werden, während 100000-mal 30000 hinzugefügtsum
würden, wenn dies der Fall wäre läuft nicht über, erhöhtsum
um 3000000000). Beachten Sie, dass das Gleiche für vorzeichenlose Mengen mit unterschiedlichen Zahlen gilt. Ein Überlauf von100000 * data[c]
würde normalerweise ein Reduktionsmodul einführen2^32
, das nicht im Endergebnis erscheinen darf.Es könnte es in verwandeln
wenn jedoch wie üblich
long long
ausreichend größer ist alsint
.Warum es das nicht tut, kann ich nicht sagen, ich denke, es ist das, was Mysticial gesagt hat: "Anscheinend führt es nach dem Schleifenaustausch keinen durchlaufenden Durchlauf durch."
Beachten Sie, dass der Schleifenaustausch selbst nicht allgemein gültig ist (für vorzeichenbehaftete Ganzzahlen), da
kann wo zum Überlauf führen
würde nicht. Hier ist es koscher, da die Bedingung sicherstellt,
data[c]
dass alle hinzugefügten Zeichen das gleiche Vorzeichen haben. Wenn also einer überläuft, tun dies beide.Ich wäre mir jedoch nicht sicher, ob der Compiler dies berücksichtigt (@Mysticial, könnten Sie es mit einer Bedingung wie
data[c] & 0x80
oder so versuchen , die für positive und negative Werte zutreffen kann?). Ich ließ Compiler ungültige Optimierungen vornehmen (zum Beispiel hatte ich vor ein paar Jahren einen ICC (11.0, iirc), der eine signierte 32-Bit-Int-zu-Double-Konvertierung verwendete,1.0/n
bein
der eineunsigned int
. War ungefähr doppelt so schnell wie die von gcc Ausgabe. Aber falsch, viele Werte waren größer als2^31
, oops.).quelle
ADD.W A6,$A000
, wobei vergessen würde , dass Wortoperationen mit Adressregistern das Wort vor dem Hinzufügen auf 32 Bit verlängern. Die Fehlerbehebung dauerte eine Weile, da der Code zwischen diesemADD
und dem nächsten Mal, als A6 vom Stapel genommen wurde, nur die Wiederherstellung derMyArray[0] = 4;
ich vor einer Anweisung die Adresse von überprüfenMyArray
und diesen Speicherort vor und nach der Ausführung der Anweisung überprüfen . es würde sich nicht ändern. Code war so etwas wiemove.B @A3,#4
und A3 sollte immer aufMyArray
jedes Mal zeigen, wenn diese Anweisung ausgeführt wurde, aber das tat es nicht. Spaß.Diese Antwort gilt nicht für den jeweiligen verknüpften Fall, sie gilt jedoch für den Fragentitel und kann für zukünftige Leser interessant sein:
Aufgrund der endlichen Genauigkeit ist eine wiederholte Gleitkommaaddition nicht gleichbedeutend mit einer Multiplikation . Erwägen:
Demo
quelle
Der Compiler enthält verschiedene Durchgänge, die die Optimierung durchführen. Normalerweise wird in jedem Durchgang entweder eine Optimierung von Anweisungen oder eine Schleifenoptimierung durchgeführt. Derzeit gibt es kein Modell, das eine Optimierung des Schleifenkörpers basierend auf den Schleifenüberschriften durchführt. Dies ist schwer zu erkennen und seltener.
Die Optimierung, die durchgeführt wurde, war eine schleifeninvariante Codebewegung. Dies kann unter Verwendung einer Reihe von Techniken erfolgen.
quelle
Nun, ich würde vermuten, dass einige Compiler diese Art der Optimierung durchführen könnten, vorausgesetzt, wir sprechen von Integer Arithmetics.
Gleichzeitig lehnen einige Compiler dies möglicherweise ab, da das Ersetzen der wiederholten Addition durch Multiplikation das Überlaufverhalten des Codes ändern kann. Bei vorzeichenlosen Ganzzahltypen sollte dies keinen Unterschied machen, da ihr Überlaufverhalten vollständig von der Sprache festgelegt wird. Aber für signierte könnte es sein (wahrscheinlich nicht auf der 2er-Komplement-Plattform). Es ist wahr, dass ein signierter Überlauf tatsächlich zu undefiniertem Verhalten in C führt, was bedeutet, dass es vollkommen in Ordnung sein sollte, diese Überlaufsemantik insgesamt zu ignorieren, aber nicht alle Compiler sind mutig genug, dies zu tun. Es wird oft von der Menge "C ist nur eine übergeordnete Assemblersprache" kritisiert. (Erinnern Sie sich, was passiert ist, als GCC Optimierungen basierend auf Strict-Aliasing-Semantik eingeführt hat?)
In der Vergangenheit hat sich GCC als Compiler erwiesen, der das Zeug dazu hat, solch drastische Schritte zu unternehmen. Andere Compiler ziehen es jedoch möglicherweise vor, sich an das wahrgenommene "vom Benutzer beabsichtigte" Verhalten zu halten, selbst wenn es nicht durch die Sprache definiert ist.
quelle
Das tut es jetzt - zumindest tut es das Klirren :
Kompiliert mit -O1 bis
Ein ganzzahliger Überlauf hat nichts damit zu tun. Wenn es einen Ganzzahlüberlauf gibt, der undefiniertes Verhalten verursacht, kann dies in beiden Fällen passieren. Hier ist die gleiche Art von Funktion, die
int
anstelle von verwendet wirdlong
:Kompiliert mit -O1 bis
quelle
Es gibt eine konzeptionelle Barriere für diese Art der Optimierung. Compiler-Autoren geben sich viel Mühe mit der Reduzierung der Stärke - zum Beispiel, indem sie Multiplikationen durch Additionen und Verschiebungen ersetzen. Sie gewöhnen sich daran zu denken, dass Multiplikationen schlecht sind. Ein Fall, in dem man in die andere Richtung gehen sollte, ist überraschend und nicht intuitiv. Also denkt niemand daran, es umzusetzen.
quelle
Die Leute, die Compiler entwickeln und warten, haben nur eine begrenzte Zeit und Energie für ihre Arbeit. Daher möchten sie sich im Allgemeinen auf das konzentrieren, was ihren Benutzern am wichtigsten ist: gut geschriebenen Code in schnellen Code umzuwandeln. Sie möchten ihre Zeit nicht damit verbringen, nach Wegen zu suchen, dummen Code in schnellen Code umzuwandeln - dafür ist die Codeüberprüfung gedacht. In einer Hochsprache kann es "albernen" Code geben, der eine wichtige Idee zum Ausdruck bringt, sodass sich die Zeit der Entwickler lohnt, dies schnell zu machen. Beispielsweise ermöglichen die Abkürzung der Entwaldung und die Fusion von Streams Haskell-Programme, die um bestimmte Arten von Faulheit herum strukturiert sind erzeugte Datenstrukturen, die in engen Schleifen kompiliert werden sollen, die keinen Speicher zuweisen. Diese Art von Anreiz gilt jedoch einfach nicht für die Umwandlung von Schleifenaddition in Multiplikation. Wenn Sie möchten, dass es schnell geht,
quelle