Ich habe mir einen Vortrag angesehen, "Effizienz mit Algorithmen, Leistung mit Datenstrukturen ", und war überrascht von dem Kommentar, dass in:
%Vor% getFooBetter() ist besser. Ich war der Überzeugung gewesen, dass ich mich darauf verlassen konnte
auf dem Compiler für die Durchführung dieser Art von Transformation in der gleichen
So würde ich erwarten, dass mehrere Vorkommen von x+y nur ausgewertet werden
Einmal. Es überrascht nicht, dass das generierte LLVM IR tatsächlich mit dem übereinstimmt
Moderator. Selbst mit -O9 bleiben uns 3 Aufrufe von cache[key] in
die getFoo() version.
Ich habe das lange LLVM IR von beiden verschoben, wobei C ++ - Symbole nicht verschoben wurden , um visuell nicht beleidigend zu sein. p>
Eine weitere StackOverflow-Frage enthüllt, dass ein Teil der Antwort hier ist, dass operator[]
Es wird angenommen, dass er in der Lage ist, den von ihm gewünschten globalen Zustand zu ändern
also können wir nicht anrufen. Ein verknüpfter Vorschlag zur Einführung eines
[[pure]] Annotation spricht über seine Anwendungen mit CSE.
Wenn wir bei vier Anrufen bleiben würden, wäre ich hier zufrieden.
Wenn ich jedoch die IR richtig gelesen habe, sieht es so aus, als ob wir optimiert hätten
getFoo() in, als ob wir geschrieben hätten:
Wäre jemand in der Lage zu erklären, wie Clang den Code sieht?
dass es die beiden letzten cache[key] s zusammenführen konnte, aber nicht alle
Sie? (Mein lokaler Klang ist 3.4.)
Die CSE-Implementierung in llvm funktioniert mit Arithmatic Expressions. Sie können den Quellcode llvm Common Tonexpression Elimination in llvm / lib / Transforms / Scalar / EarlyCSE.cpp
sehenIm vorliegenden Fall handelt es sich um interprozedurale Optimierungen.
Dieser Aufruf cache[key] stellt sich als [](cache,key) -Funktion heraus. So können Optimierungen wie Inlining in Abhängigkeit von den Kosten der Inlining-Funktion [] in Aktion treten. Chandler erwähnte das gleiche Problem, da die Hash-Funktion rechenintensiv ist, das Inlining verhindert wird, man am Ende mehr als einmal Hash-Funktionen berechnet!
Wenn Inlining passiert ist, wurde IR bei -O3, cache[key] zuerst berechnet und cache key wurde überhaupt nicht mutiert. Ein solcher Aufruf wird für denselben SSA-Wert optimiert.
Im Fall von cache[key].get() würden wir normalerweise IR schreiben, während cache [key] das Objekt zurückgibt und den Wert des Feldes mit getementpointer in get() abruft. Wenn die Optimierung eingeschaltet ist, stellt sich heraus, dass dieser IR unser zuvor berechneter SSA-Wert für 'cache [key]' ist, wobei das Element von der Struktur des eindeutigen Zeigers aus zugreift.
Kommt im schlimmsten Fall zu getFooBetter() zurück, wenn der Compiler keine prozedurübergreifenden Optimierungen durchführt, werden mehr Vorkommen von cache[key] zu mehr Berechnung führen, und dieser Aufruf wird sogar bei O3 so aussehen wie er ist!
In einer unordered_map-Suche werden viele Dinge ausgeführt. Es gibt Hash-Berechnungen, die ein Bin durchsuchen, zur Bin hinzufügen, wenn es nicht dort war, und vielleicht die Tabelle vergrößert, wenn sie jetzt zu groß ist. Es ist nicht das Gleiche wie der Vergleich von zwei Instanzen von "x + y" in Ihrem Code. Sie sollten erstaunter sein, dass tatsächlich festgestellt wurde, dass zwei der Anrufe zusammengeführt werden können. (Ich bin.)
Als allgemeine Regel würde ich nicht damit rechnen, dass ein Compiler entdeckt, dass zwei Funktionsaufrufe geteilt werden können, und wenn es auf die Leistung ankommt, würde ich die gemeinsame Unterdrückung von Unterausdrücken in der Quelle selbst vornehmen. Ich würde nicht einmal erwarten, dass sin (x) gleich sein würde, bis consxpr vollständig implementiert ist.
Tags und Links c++ clang compiler-optimization