Wann spielen Funktionsaufrufkosten in modernen Compilern noch eine Rolle?

95

Ich bin eine religiöse Person und bemühe mich, keine Sünden zu begehen. Deshalb neige ich dazu, kleine Funktionen zu schreiben ( kleiner als das , um Robert C. Martin neu zu formulieren), um den verschiedenen Geboten zu entsprechen, die in der Clean Code- Bibel gefordert werden . Aber während ich ein paar Sachen überprüfte, landete ich auf diesem Post , unter dem ich diesen Kommentar las:

Beachten Sie, dass die Kosten eines Methodenaufrufs je nach Sprache erheblich sein können. Es gibt fast immer einen Kompromiss zwischen dem Schreiben von lesbarem Code und dem Schreiben von performantem Code.

Unter welchen Bedingungen ist diese zitierte Aussage angesichts der reichen Industrie leistungsfähiger moderner Compiler heute noch gültig?

Das ist meine einzige Frage. Und es geht nicht darum, ob ich lange oder kleine Funktionen schreiben soll. Ich möchte nur betonen, dass Ihr Feedback möglicherweise dazu beiträgt, meine Einstellung zu ändern, und dass ich der Versuchung der Gotteslästerer nicht widerstehen kann .

Billal Begueradj
quelle
11
Schreiben Sie lesbaren und wartbaren Code. Nur wenn Sie auf ein Problem mit dem Stapelüberlauf stoßen, können Sie Ihren Ansatz überdenken
Fabio
33
Eine generelle Antwort ist hier nicht möglich. Es gibt zu viele verschiedene Compiler, die zu viele verschiedene Sprachspezifikationen implementieren. Und dann gibt es JIT-kompilierte Sprachen, dynamisch interpretierte Sprachen und so weiter. Es genügt jedoch zu sagen, dass Sie sich keine Gedanken über die Kosten eines Funktionsaufrufs machen müssen, wenn Sie nativen C- oder C ++ - Code mit einem modernen Compiler kompilieren. Der Optimierer fügt diese ein, wann immer es angebracht ist. Als Enthusiast der Mikrooptimierung sehe ich selten, dass Compiler Inlining-Entscheidungen treffen, mit denen ich oder meine Benchmarks nicht einverstanden sind.
Cody Grey
6
Ich spreche aus eigener Erfahrung und schreibe Code in einer proprietären Sprache, die in Bezug auf Fähigkeiten ziemlich modern ist, aber Funktionsaufrufe sind lächerlich teuer, bis zu dem Punkt, an dem selbst für Schleifen typische Geschwindigkeit optimiert werden müssen: for(Integer index = 0, size = someList.size(); index < size; index++)statt einfach for(Integer index = 0; index < someList.size(); index++). Nur weil Ihr Compiler in den letzten Jahren erstellt wurde, müssen Sie nicht unbedingt auf die Profilerstellung verzichten.
Phyrfox
5
@phyrfox das macht einfach Sinn, den Wert von someList.size () außerhalb der Schleife abzurufen, anstatt ihn jedes Mal durch die Schleife aufzurufen. Dies gilt insbesondere dann, wenn die Möglichkeit eines Synchronisationsproblems besteht, bei dem Leser und Schreiber versuchen, während der Iteration in Konflikt zu geraten. In diesem Fall möchten Sie die Liste auch vor Änderungen während der Iteration schützen.
Craig
8
Achten Sie darauf, dass kleine Funktionen nicht zu weit gehen, da dies den Code genauso effizient verschleiern kann wie eine monolithische Megafunktion. Wenn Sie mir nicht glauben, schauen Sie sich einige der Gewinner von ioccc.org an : Einige kodieren alles zu einer einzigen main(), andere teilen alles in etwa 50 winzige Funktionen auf und alle sind absolut unlesbar. Der Trick ist, wie immer, eine gute Balance zu finden .
cmaster

Antworten:

148

Das hängt von Ihrer Domain ab.

Wenn Sie Code für Low-Power-Mikrocontroller schreiben, können die Kosten für Methodenaufrufe erheblich sein. Wenn Sie jedoch eine normale Website oder Anwendung erstellen, sind die Kosten für Methodenaufrufe im Vergleich zum Rest des Codes vernachlässigbar. In diesem Fall lohnt es sich immer, sich auf die richtigen Algorithmen und Datenstrukturen zu konzentrieren, anstatt auf Mikrooptimierungen wie Methodenaufrufe.

Und es ist auch eine Frage des Compilers, der die Methoden für Sie integriert. Die meisten Compiler sind intelligent genug, um Funktionen zu integrieren, wo dies möglich ist.

Und zuletzt gibt es eine goldene Regel für die Leistung: IMMER ZUERST PROFILIEREN. Schreiben Sie keinen "optimierten" Code, der auf Annahmen basiert. Wenn Sie ungewöhnlich sind, schreiben Sie beide Fälle und sehen Sie, welche besser ist.

Euphorisch
quelle
13
Und zB führt der HotSpot-Compiler spekulatives Inlining durch , das in gewisser Weise auch dann Inlining ist, wenn dies nicht möglich ist.
Jörg W Mittag
49
Tatsächlich ist in einer Webanwendung der gesamte Code in Bezug auf den DB-Zugriff und den Netzwerkverkehr wahrscheinlich unbedeutend ...
AnoE
72
Ich mag eigentlich Embedded und Ultra Low Power mit einem sehr alten Compiler, der kaum weiß, was Optimierung bedeutet, und glaube mir, obwohl die Funktionsaufrufe wichtig sind, ist es nie der erste Ort, um nach Optimierung zu suchen. Auch in dieser Nische steht in diesem Fall die Codequalität an erster Stelle.
Tim
2
@Mehrdad Auch in diesem Fall wäre ich überrascht, wenn es nichts Relevanteres zur Optimierung im Code gäbe. Wenn ich den Code profiliere, sehe ich Dinge viel schwerer als die Funktionsaufrufe, und dort ist es wichtig, nach Optimierungen zu suchen. Einige Entwickler sind verrückt nach ein oder zwei nicht optimierten LOCs, aber wenn Sie die SW profilieren, stellen Sie fest, dass Design mehr zählt als dies, zumindest für den größten Teil des Codes. Wenn Sie den Engpass finden, können Sie versuchen, ihn zu optimieren. Dies hat weitaus mehr Auswirkungen als eine einfache, willkürliche Optimierung, z. B. das Schreiben großer Funktionen, um den Mehraufwand für Anrufe zu vermeiden.
Tim,
8
Gute Antwort! Ihr letzter Punkt sollte der erste sein: Profilieren Sie immer, bevor Sie sich für eine Optimierung entscheiden .
CJ Dennis
56

Der Aufwand für Funktionsaufrufe hängt vollständig von der Sprache ab und davon, auf welcher Ebene Sie optimieren.

Auf einer extrem niedrigen Ebene können Funktionsaufrufe und vor allem virtuelle Methodenaufrufe kostspielig sein, wenn sie zu Verzweigungsfehlvorhersagen oder CPU-Cache-Fehlern führen. Wenn Sie Assembler geschrieben haben , wissen Sie auch, dass Sie einige zusätzliche Anweisungen zum Speichern und Wiederherstellen von Registern für einen Aufruf benötigen. Es ist nicht wahr, dass ein „ausreichend intelligenter“ Compiler die richtigen Funktionen einbinden könnte, um diesen Overhead zu vermeiden, da Compiler durch die Semantik der Sprache eingeschränkt sind (insbesondere in Bezug auf Features wie den Versand von Schnittstellenmethoden oder dynamisch geladene Bibliotheken).

Auf hohem Niveau führen Sprachen wie Perl, Python und Ruby pro Funktionsaufruf eine Menge Buchhaltung durch, was diese vergleichsweise kostspielig macht. Dies wird durch Meta-Programmierung noch verschlimmert. Ich habe einmal eine Python-Software 3x beschleunigt, indem ich Funktionsaufrufe aus einer sehr heißen Schleife geholt habe. In leistungskritischem Code können Inlining-Hilfsfunktionen spürbare Auswirkungen haben.

Die überwiegende Mehrheit der Software ist jedoch nicht so leistungskritisch, dass Sie einen Funktionsaufruf-Overhead bemerken könnten. In jedem Fall zahlt es sich aus, sauberen, einfachen Code zu schreiben:

  • Wenn Ihr Code nicht leistungskritisch ist, erleichtert dies die Wartung. Selbst in leistungskritischer Software wird der Großteil des Codes kein „Hot Spot“ sein.

  • Wenn Ihr Code leistungskritisch ist, erleichtert der einfache Code das Verständnis des Codes und die Suche nach Optimierungsmöglichkeiten. Die größten Gewinne werden normalerweise nicht durch Mikrooptimierungen wie Inlining-Funktionen erzielt, sondern durch algorithmische Verbesserungen. Oder anders formuliert: Machen Sie nicht das Gleiche schneller. Finde einen Weg, weniger zu tun.

Beachten Sie, dass "einfacher Code" nicht "in tausend winzige Funktionen zerlegt" bedeutet. Jede Funktion stellt auch ein wenig kognitiven Aufwand - es ist schwieriger Grund über abstraktere Code. Irgendwann könnten diese winzigen Funktionen so wenig bewirken, dass sie Ihren Code vereinfachen, wenn Sie sie nicht verwenden.

amon
quelle
16
Ein wirklich kluger DBA sagte mir einmal: "Normalisieren, bis es weh tut, dann denormalisieren, bis es nicht mehr weh tut." Mir scheint, es könnte umformuliert werden in "Methoden extrahieren, bis es weh tut, dann inline, bis es nicht mehr weh tut".
RubberDuck
1
Zusätzlich zum kognitiven Overhead gibt es in den Debugger-Informationen einen symbolischen Overhead, und normalerweise ist ein Overhead in den endgültigen Binärdateien unvermeidbar.
Frank Hileman
In Bezug auf intelligente Compiler - das KÖNNEN sie nur nicht immer. Zum Beispiel kann jvm Dinge basierend auf dem Laufzeitprofil mit einem sehr günstigen / kostenlosen Trap für einen ungewöhnlichen Pfad oder einer inline-polymorphen Funktion, für die es nur eine Implementierung einer bestimmten Methode / Schnittstelle gibt, inline setzen und diesen Aufruf dann deaktivieren, um richtig polymorph zu werden, wenn eine neue Unterklasse dynamisch geladen wird Laufzeit. Aber ja, es gibt viele Sprachen, in denen solche Dinge nicht möglich sind, und viele Fälle sogar in jvm, wenn dies im Allgemeinen nicht kosteneffektiv oder möglich ist.
Artur Biesiadowski
19

Fast alle Aussagen zur Leistungsoptimierung sind Sonderfälle des Amdahlschen Gesetzes . Die kurze, humorvolle Aussage von Amdahls Gesetz ist

Wenn ein Teil Ihres Programms 5% der Laufzeit beansprucht und Sie dieses Teil so optimieren, dass es jetzt null Prozent der Laufzeit beansprucht, ist das gesamte Programm nur 5% schneller.

(Eine Optimierung auf null Prozent der Laufzeit ist durchaus möglich. Wenn Sie sich hinsetzen, um ein umfangreiches, kompliziertes Programm zu optimieren, werden Sie mit ziemlicher Wahrscheinlichkeit feststellen, dass mindestens ein Teil der Laufzeit für Dinge aufgewendet wird , die gar nicht benötigt werden .)

Dies ist der Grund, warum die Leute normalerweise sagen, dass sie sich keine Gedanken über Funktionsaufrufkosten machen sollen: Ganz gleich, wie teuer sie sind, normalerweise gibt das Programm als Ganzes nur einen winzigen Bruchteil seiner Laufzeit für Anrufkosten aus, weshalb es nicht sehr hilfreich ist, sie zu beschleunigen .

Aber wenn es einen Trick gibt, mit dem Sie alle Funktionsaufrufe beschleunigen können, lohnt sich dieser Trick wahrscheinlich. Compiler-Entwickler verbringen viel Zeit mit der Optimierung der Funktionen "Prologe" und "Epiloge", da dies allen Programmen zugute kommt , die mit diesem Compiler kompiliert wurden, auch wenn es nur ein winziges Stück für jedes ist.

Und wenn Sie Grund zu der Annahme haben , dass ein Programm ist viel von seiner Laufzeit der Ausgaben nur Funktionsaufrufe macht, dann sollten Sie anfangen , darüber nachzudenken , ob einige dieser Funktionsaufrufe unnötig sind. Hier sind einige Faustregeln, um zu wissen, wann Sie dies tun sollten:

  • Wenn die Laufzeit einer Funktion pro Aufruf weniger als eine Millisekunde beträgt, diese Funktion jedoch hunderttausend Mal aufgerufen wird, sollte sie wahrscheinlich inline sein.

  • Wenn in einem Programmprofil Tausende von Funktionen angezeigt werden und keine davon mehr als 0,1% der Laufzeit beansprucht, ist der Funktionsaufruf-Overhead insgesamt wahrscheinlich erheblich.

  • Wenn Sie über " Lasagne-Code " verfügen , in dem es viele Abstraktionsebenen gibt, die über das Versenden an die nächste Ebene hinaus kaum Arbeit leisten, und alle diese Ebenen mit virtuellen Methodenaufrufen implementiert sind, besteht eine gute Chance, dass die CPU a verschwendet viel Zeit auf indirekt verzweigten Pipeline-Ständen. Leider besteht die einzige Heilung dafür darin, einige Schichten loszuwerden, was oft sehr schwierig ist.

zwol
quelle
7
Hüten Sie sich nur vor teuren Dingen, die tief in verschachtelten Schleifen ausgeführt werden. Ich habe eine Funktion optimiert und Code erhalten, der 10x so schnell läuft. Das war, nachdem der Profiler den Täter aufgezeigt hatte. (Es wurde immer wieder aufgerufen, in Schleifen von O (n ^ 3) bis zu einem kleinen n O (n ^ 6).)
Loren Pechtel
"Leider besteht die einzige Heilung darin, einige Schichten loszuwerden, was oft sehr schwierig ist." - Dies hängt stark von Ihrem Sprachcompiler und / oder der Technologie der virtuellen Maschine ab. Wenn Sie den Code ändern können, um dem Compiler das Inline-Arbeiten zu erleichtern (z. B. durch Verwendung von finalKlassen und Methoden, sofern in Java zutreffend, oder Nicht- virtualMethoden in C # oder C ++), kann die Indirektion vom Compiler / der Laufzeit entfernt werden. Ich sehe einen Gewinn ohne massive Umstrukturierung. Wie @JorgWMittag oben ausführt, kann die JVM sogar Inline-Operationen ausführen, wenn nicht nachgewiesen werden kann, dass die Optimierung ...
Jules
... gültig, also kann es gut sein, dass es in Ihrem Code trotz der Überlagerung sowieso tut.
Jules
@Jules Es stimmt zwar, dass JIT - Compiler können spekulative Optimierung durchführen, es bedeutet nicht , dass eine solche Optimierungen sind gleichmäßig aufgetragen. Insbesondere in Bezug auf Java ist meine Erfahrung, dass die Entwicklerkultur Schichten bevorzugt, die auf Schichten gestapelt sind, was zu extrem tiefen Aufrufstapeln führt. Anekdotisch, das trägt zum trägen, aufgeblähten Gefühl vieler Java-Anwendungen bei. Eine derart stark geschichtete Architektur wirkt der JIT-Laufzeit entgegen, unabhängig davon, ob die Schichten technisch inlinierbar sind. JIT ist kein Wundermittel, mit dem strukturelle Probleme automatisch behoben werden können.
amon
@amon Meine Erfahrung mit "Lasagne Code" stammt aus sehr großen C ++ - Anwendungen mit viel Code aus den 1990er Jahren, als tief verschachtelte Objekthierarchien und COM die Mode waren. C ++ - Compiler unternehmen ziemlich heldenhafte Anstrengungen, um die Abstraktionsstrafen in Programmen wie diesem auszumerzen, und dennoch werden sie möglicherweise einen erheblichen Bruchteil der Laufzeit für Pipeline-Stalls mit indirekten Verzweigungen ausgeben (und einen weiteren erheblichen Teil für I-Cache-Ausfälle). .
zwol
17

Ich werde dieses Zitat anfechten:

Es gibt fast immer einen Kompromiss zwischen dem Schreiben von lesbarem Code und dem Schreiben von performantem Code.

Dies ist eine wirklich irreführende Aussage und eine möglicherweise gefährliche Haltung. Es gibt einige spezielle Fälle, in denen Sie einen Kompromiss eingehen müssen, aber im Allgemeinen sind die beiden Faktoren unabhängig.

Ein Beispiel für einen notwendigen Kompromiss ist, wenn Sie einen einfachen Algorithmus im Vergleich zu einem komplexeren, aber performanteren haben. Eine Hashtable-Implementierung ist deutlich komplexer als eine Implementierung mit verknüpften Listen, die Suche ist jedoch langsamer, sodass Sie möglicherweise die Leistung durch Einfachheit (was einen Faktor für die Lesbarkeit darstellt) beeinträchtigen müssen.

In Bezug auf den Funktionsaufruf-Overhead kann die Umwandlung eines rekursiven Algorithmus in einen iterativen Algorithmus je nach Algorithmus und Sprache einen erheblichen Vorteil haben. Dies ist jedoch wieder ein sehr spezifisches Szenario, und der Overhead von Funktionsaufrufen wird im Allgemeinen vernachlässigbar oder wegoptimiert.

(Einige dynamische Sprachen wie Python sind mit einem erheblichen Aufwand für Methodenaufrufe verbunden. Wenn die Leistung jedoch zu einem Problem wird, sollten Sie Python wahrscheinlich gar nicht erst verwenden.)

Die meisten Prinzipien für lesbaren Code - konsistente Formatierung, aussagekräftige Bezeichnernamen, geeignete und hilfreiche Kommentare usw. haben keine Auswirkung auf die Leistung. Und einige - wie die Verwendung von Aufzählungen anstelle von Zeichenfolgen - haben auch Leistungsvorteile.

JacquesB
quelle
5

Der Funktionsaufruf-Overhead ist in den meisten Fällen unwichtig.

Der größere Vorteil von Inlining-Code ist jedoch die Optimierung des neuen Codes nach dem Inlining .

Wenn Sie beispielsweise eine Funktion mit einem konstanten Argument aufrufen, kann der Optimierer dieses Argument jetzt konstant falten, wo er es vor dem Inlinen des Aufrufs nicht konnte. Wenn das Argument ein Funktionszeiger (oder Lambda) ist, kann der Optimierer jetzt auch die Aufrufe dieses Lambdas einbinden.

Dies ist ein wichtiger Grund, warum virtuelle Funktionen und Funktionszeiger nicht attraktiv sind, da Sie sie erst dann inline setzen können, wenn der eigentliche Funktionszeiger konstant bis zur Aufrufstelle gefaltet wurde.

Ratschenfreak
quelle
5

Angenommen, die Leistung ist für Ihr Programm von Bedeutung und es werden sehr viele Anrufe getätigt. Je nach Art des Anrufs können die Kosten dennoch von Bedeutung sein oder auch nicht.

Wenn die aufgerufene Funktion klein ist und der Compiler sie einbinden kann, sind die Kosten im Wesentlichen Null. Moderne Compiler / Sprachimplementierungen verfügen über JIT-, Link-Time-Optimization- und / oder Modul-Systeme, um die Inline-Funktionalität zu maximieren, wenn dies von Vorteil ist.

OTOH, Funktionsaufrufe verursachen nicht offensichtliche Kosten: Ihre bloße Existenz kann Compiler-Optimierungen vor und nach dem Aufruf verhindern.

Wenn der Compiler nicht beurteilen kann, was die aufgerufene Funktion tut (z. B. virtueller / dynamischer Versand oder eine Funktion in einer dynamischen Bibliothek), muss er möglicherweise pessimistisch davon ausgehen, dass die Funktion irgendwelche Nebenwirkungen haben könnte - eine Ausnahme auslösen, ändern globaler Zustand, oder ändern Sie den Speicher durch Zeiger gesehen. Der Compiler muss möglicherweise temporäre Werte im Speicher sichern und sie nach dem Aufruf erneut lesen. Anweisungen rund um den Anruf können nicht neu angeordnet werden, sodass Schleifen möglicherweise nicht vektorisiert werden können oder redundante Berechnungen aus Schleifen nicht ausgeführt werden können.

Wenn Sie beispielsweise in jeder Schleifeniteration unnötigerweise eine Funktion aufrufen:

for(int i=0; i < /* gasp! */ strlen(s); i++) x ^= s[i];

Der Compiler weiß möglicherweise, dass es sich um eine reine Funktion handelt, und verlässt die Schleife (in einem schrecklichen Fall wie diesem Beispiel wird der zufällige O (n ^ 2) -Algorithmus sogar auf O (n) festgelegt):

for(int i=0, end=strlen(s); i < end; i++) x ^= s[i];

Und dann vielleicht sogar die Schleife neu schreiben, um 4/8/16 Elemente gleichzeitig mit wide / SIMD-Anweisungen zu verarbeiten.

Wenn Sie jedoch einen Aufruf zu einem undurchsichtigen Code in der Schleife hinzufügen, muss der Compiler das Schlimmste annehmen, dass der Aufruf auf eine globale Variable zugreift, die auf denselben Speicher verweist wie schange Sein Inhalt (auch wenn er constin Ihrer Funktion ist, kann er constnirgendwo anders sein), was die Optimierung unmöglich macht:

for(int i=0; i < strlen(s); i++) {
    x ^= s[i];
    do_nothing();
}
Kornel
quelle
3

Dieses alte Papier könnte Ihre Frage beantworten:

Guy Lewis Steele, Jr. MIT AI Lab. AI Lab Memo AIM-443. Oktober 1977.

Abstrakt:

Folklore besagt, dass GOTO-Anweisungen "billig" sind, während Prozeduraufrufe "teuer" sind. Dieser Mythos ist größtenteils auf schlecht gestaltete Sprachimplementierungen zurückzuführen. Das historische Wachstum dieses Mythos wird berücksichtigt. Es werden sowohl theoretische Ideen als auch eine bestehende Implementierung diskutiert, die diesen Mythos entlarven. Es wird gezeigt, dass die uneingeschränkte Verwendung von Prozeduraufrufen große stilistische Freiheit erlaubt. Insbesondere kann jedes Flussdiagramm als "strukturiertes" Programm geschrieben werden, ohne zusätzliche Variablen einzuführen. Die Schwierigkeit mit der GOTO-Anweisung und dem Prozeduraufruf wird als Konflikt zwischen abstrakten Programmierkonzepten und konkreten Sprachkonstrukten charakterisiert.

Alex Vong
quelle
12
Ich bezweifle sehr, dass ein so altes Papier die Frage beantworten wird, ob "Funktionsaufrufkosten in modernen Compilern immer noch eine Rolle spielen ".
Cody Grey
6
@CodyGray Ich denke, die Compilertechnologie hätte seit 1977 Fortschritte machen müssen. Wenn Funktionsaufrufe also 1977 billig gemacht werden können, sollten wir dies jetzt tun können. Die Antwort lautet also nein. Dies setzt natürlich voraus, dass Sie eine anständige Sprachimplementierung verwenden, die Funktionen wie Inlining ausführen kann.
Alex Vong
4
@AlexVong Sich auf die Compiler-Optimierungen von 1977 zu verlassen, ist wie sich auf die Entwicklung der Rohstoffpreise in der Steinzeit zu verlassen. Alles hat sich zu sehr verändert. Beispielsweise wurde früher die Multiplikation durch Speicherzugriff als billigere Operation ersetzt. Derzeit ist es um einen großen Faktor teurer. Virtuelle Methodenaufrufe sind relativ viel teurer als früher (Speicherzugriff und Verzweigungsfehler), können jedoch häufig wegoptimiert werden und der virtuelle Methodenaufruf kann sogar inline ausgeführt werden (Java erledigt dies ständig) genau null. Es gab nichts
Vergleichbares
3
Wie andere bereits betont haben, haben nicht nur Änderungen in der Compilertechnologie die alte Forschung zunichte gemacht. Wenn sich die Compiler weiter verbessert hätten, während die Mikroarchitekturen weitgehend unverändert geblieben wären, wären die Schlussfolgerungen des Papiers weiterhin gültig. Aber das ist nicht passiert. Wenn überhaupt, haben sich Mikroarchitekturen mehr verändert als Compiler. Was früher schnell war, ist heute relativ langsam.
Cody Grey
2
@AlexVong Genauer gesagt zu den CPU-Änderungen, die das Papier überflüssig machen: Im Jahr 1977 bestand ein Hauptspeicherzugriff aus einem einzelnen CPU-Zyklus. Selbst ein einfacher Zugriff auf den L1 (!) - Cache hat heute eine Latenz von 3 bis 4 Zyklen. Jetzt sind Funktionsaufrufe bei Speicherzugriffen (Erstellen eines Stapelrahmens, Speichern einer Rücksprungadresse, Speichern von Registern für lokale Variablen) ziemlich schwer, was die Kosten eines einzelnen Funktionsaufrufs leicht auf 20 und mehr Zyklen erhöht. Wenn Ihre Funktion nur die Argumente neu anordnet und möglicherweise ein weiteres konstantes Argument zur Übergabe an einen Call-Through hinzufügt, ist dies fast 100% Overhead.
cmaster
3
  • In C ++ sollten Sie keine Funktionsaufrufe entwerfen, die Argumente kopieren. Der Standardwert ist "Übergeben nach Wert". Der Funktionsaufruf-Overhead, der durch das Speichern von Registern und anderen auf Stapelrahmen bezogenen Elementen entsteht, kann durch eine unbeabsichtigte (und möglicherweise sehr teure) Kopie eines Objekts überfordert werden.

  • Es gibt Optimierungen im Zusammenhang mit Stapelrahmen, die Sie untersuchen sollten, bevor Sie auf Code mit hohem Faktor verzichten.

  • Die meiste Zeit, als ich mit einem langsamen Programm zu tun hatte, stellte ich fest, dass algorithmische Änderungen eine weitaus höhere Geschwindigkeit ergaben als das Einfügen von Funktionsaufrufen. Beispiel: Ein anderer Ingenieur hat einen Parser überarbeitet, der eine Map-of-Maps-Struktur gefüllt hat. Als Teil davon entfernte er einen zwischengespeicherten Index von einer Karte zu einer logisch verbundenen. Das war ein guter Schritt zur Verbesserung der Code-Robustheit, machte das Programm jedoch aufgrund der 100-fachen Verlangsamung unbrauchbar, da für alle zukünftigen Zugriffe eine Hash-Suche durchgeführt wurde, anstatt den gespeicherten Index zu verwenden. Die Profilerstellung ergab, dass die meiste Zeit für die Hashing-Funktion aufgewendet wurde.

user2543191
quelle
4
Der erste Rat ist ein bisschen alt. Seit C ++ 11 ist das Verschieben möglich. Insbesondere für Funktionen, deren Argumente intern geändert werden müssen, kann es die effizienteste Wahl sein, ein Argument nach Wert zu sortieren und an Ort und Stelle zu ändern.
MSalters
@MSalters: Ich denke du hast "insbesondere" mit "weiterhin" oder so verwechselt. Die Entscheidung, Kopien oder Referenzen zu übergeben, war vor C ++ 11 (obwohl ich weiß, dass Sie es wissen).
Phresnel
@phresnel: Ich denke, ich habe es richtig verstanden. Der besondere Fall ich mich beziehe, ist der Fall , wenn Sie eine temporäre im Anrufer erstellen, bewegen es zu einem Streit, und es dann in den Angerufenen ändern. Dies war vor C ++ 11 nicht möglich, da C ++ 03 eine nicht
konstante
@MSalters: Dann habe ich deinen Kommentar beim ersten Lesen falsch verstanden. Ich hatte den Eindruck, dass Sie implizierten, dass die Übergabe von Werten vor C ++ 11 nichts ist, was man tun würde, wenn man den übergebenen Wert ändern möchte.
Phresnel
Das Aufkommen von "Bewegen" hilft am bedeutendsten bei der Rückgabe von Objekten, die zweckmäßiger in der Funktion aufgebaut sind als außen und als Referenz übergeben werden. Bevor ein Objekt von einer Funktion zurückgegeben wurde, wurde eine Kopie aufgerufen, oft ein teurer Schritt. Hier geht es nicht um Funktionsargumente. Ich habe das Wort "designing" sorgfältig in den Kommentar eingefügt, da man dem Compiler explizit die Erlaubnis geben muss, sich in Funktionsargumente zu "bewegen" (&& Syntax). Ich habe es mir zur Gewohnheit gemacht, Kopierkonstruktoren zu "löschen", um Stellen zu identifizieren, an denen dies sinnvoll ist.
user2543191
3

Wie andere sagen, sollten Sie zuerst die Leistung Ihres Programms messen und werden in der Praxis wahrscheinlich keinen Unterschied feststellen.

Aus konzeptioneller Sicht dachte ich jedoch, ich würde ein paar Dinge klären, die in Ihrer Frage zusammenfließen. Zunächst fragen Sie:

Sind Funktionsaufrufkosten in modernen Compilern immer noch wichtig?

Beachten Sie die Schlüsselwörter "function" und "compilers". Ihr Zitat ist subtil anders:

Beachten Sie, dass die Kosten eines Methodenaufrufs je nach Sprache erheblich sein können.

Hierbei handelt es sich um Methoden im objektorientierten Sinne.

Während "function" und "method" häufig synonym verwendet werden, gibt es Unterschiede hinsichtlich der Kosten (nach denen Sie fragen) und der Kompilierung (nach dem von Ihnen angegebenen Kontext).

Insbesondere müssen wir den statischen Versand im Vergleich zum dynamischen Versand kennen . Ich werde Optimierungen für den Moment ignorieren.

In einer Sprache wie C rufen wir normalerweise Funktionen mit statischem Versand auf . Zum Beispiel:

int foo(int x) {
  return x + 1;
}

int bar(int y) {
  return foo(y);
}

int main() {
  return bar(42);
}

Wenn der Compiler den Aufruf sieht foo(y), weiß er, auf welche Funktion sich dieser fooName bezieht, sodass das Ausgabeprogramm direkt zu der fooFunktion springen kann , die recht billig ist. Das ist , was statische Dispatch bedeutet.

Die Alternative ist der dynamische Versand , bei dem der Compiler nicht weiß, welche Funktion aufgerufen wird. Hier ist ein Beispiel für einen Haskell-Code (da das C-Äquivalent chaotisch wäre!):

foo x = x + 1

bar f x = f x

main = print (bar foo 42)

Hier barruft die Funktion ihr Argument auf f, was alles sein kann. Daher kann der Compiler nicht einfach barzu einer schnellen Sprunganweisung kompilieren , da er nicht weiß, wohin er springen soll. Stattdessen wird der Code, für den wir generieren bar, dereferenziert f, um herauszufinden, auf welche Funktion er zeigt, und dann zu dieser zu springen. Das bedeutet dynamischer Versand .

Beide Beispiele beziehen sich auf Funktionen . Sie haben Methoden erwähnt , die als ein bestimmter Stil einer dynamisch versendeten Funktion angesehen werden können. Hier ist zum Beispiel Python:

class A:
  def __init__(self, x):
    self.x = x

  def foo(self):
    return self.x + 1

def bar(y):
  return y.foo()

z = A(42)
bar(z)

Der y.foo()Aufruf verwendet den dynamischen Versand, da der Wert der fooEigenschaft im yObjekt abgefragt und alles aufgerufen wird , was er findet. Es ist nicht bekannt, ob yeine Klasse vorhanden sein Awird oder ob die AKlasse eine fooMethode enthält , daher können wir nicht direkt zu ihr springen.

OK, das ist die Grundidee. Beachten Sie, dass der statische Versand schneller ist als der dynamische Versand, unabhängig davon, ob er kompiliert oder interpretiert wird. alles andere ist gleich. Für die Dereferenzierung fallen in beiden Fällen zusätzliche Kosten an.

Wie wirkt sich das auf moderne, optimierte Compiler aus?

Das Erste, was zu beachten ist, ist, dass der statische Versand stärker optimiert werden kann: Wenn wir wissen, zu welcher Funktion wir springen, können wir Dinge wie Inlining tun. Beim dynamischen Versand wissen wir nicht, dass wir erst zur Laufzeit springen, daher können wir nicht viel optimieren.

Zweitens ist es in einigen Sprachen möglich, abzuleiten, wohin einige dynamische Versendungen springen, und sie daher zu statischen Versendungen zu optimieren. Auf diese Weise können wir weitere Optimierungen wie Inlining usw. durchführen.

In dem obigen Python-Beispiel ist eine solche Folgerung ziemlich hoffnungslos, da Python zulässt, dass anderer Code Klassen und Eigenschaften überschreibt, sodass es schwierig ist, auf vieles zu schließen, was in allen Fällen Bestand hat.

Wenn unsere Sprache uns mehr Einschränkungen auferlegen lässt, zum Beispiel durch Beschränkung yauf Klassen Amithilfe einer Annotation, könnten wir diese Informationen verwenden, um auf die Zielfunktion zu schließen. In Sprachen mit Unterklassen (das sind fast alle Sprachen mit Klassen!) Reicht das eigentlich nicht aus, da es ymöglicherweise eine andere (Unter-) Klasse gibt, sodass wir zusätzliche Informationen wie Java- finalAnnotationen benötigen , um genau zu wissen, welche Funktion aufgerufen wird.

Haskell ist keine OO - Sprache, aber wir können den Wert ableiten fvon inlining bar(welches statisch versendet) in main, unter Substitution foofür y. Da das Ziel von fooin mainstatisch bekannt ist, wird der Aufruf statisch weitergeleitet und wird wahrscheinlich vollständig eingebunden und optimiert (da diese Funktionen klein sind, werden sie vom Compiler eher eingebunden, obwohl wir uns im Allgemeinen nicht darauf verlassen können ).

Daher belaufen sich die Kosten auf:

  • Versendet die Sprache Ihren Anruf statisch oder dynamisch?
  • Kann die Implementierung in letzterem Fall auf andere Informationen (z. B. Typen, Klassen, Anmerkungen, Inlining usw.) zurückgreifen?
  • Wie aggressiv kann der statische Versand (abgeleitet oder anderweitig) optimiert werden?

Wenn Sie eine "sehr dynamische" Sprache mit viel dynamischem Versand und wenigen Garantien verwenden, die dem Compiler zur Verfügung stehen, fallen für jeden Aufruf Kosten an. Wenn Sie eine "sehr statische" Sprache verwenden, wird ein ausgereifter Compiler sehr schnellen Code erzeugen. Wenn Sie dazwischen sind, kann dies von Ihrem Codierungsstil und der Art der Implementierung abhängen.

Warbo
quelle
Ich bin nicht einverstanden , dass eine Schließung (oder eine Funktion aufrufen Zeiger ) -wie Ihre Haskell Beispiel- ist dynamisch Versand. Der dynamische Versand erfordert einige Berechnungen (z. B. die Verwendung einer vtable ), um diesen Abschluss zu erzielen , und ist daher teurer als indirekte Aufrufe. Ansonsten nette Antwort.
Basile Starynkevitch
2

Ja, eine fehlende Verzweigungsvorhersage ist für moderne Hardware teurer als vor Jahrzehnten, aber die Compiler sind viel schlauer geworden, dies zu optimieren.

Betrachten Sie als Beispiel Java. Auf den ersten Blick sollte der Funktionsaufruf-Overhead in dieser Sprache besonders dominant sein:

  • Winzige Funktionen sind aufgrund der JavaBean-Konvention weit verbreitet
  • Funktionen standardmäßig auf virtuell und sind in der Regel
  • die Zusammenstellungseinheit ist die Klasse; Die Laufzeit unterstützt das jederzeitige Laden neuer Klassen, einschließlich Unterklassen, die zuvor monomorphe Methoden überschreiben

Entsetzt über diese Praktiken würde der durchschnittliche C-Programmierer vorhersagen, dass Java mindestens eine Größenordnung langsamer sein muss als C. Und vor 20 Jahren hätte er recht gehabt. Moderne Benchmarks setzen jedoch idiomatischen Java-Code innerhalb weniger Prozent des entsprechenden C-Codes. Wie ist das möglich?

Ein Grund dafür ist, dass moderne JVMs selbstverständlich Inline-Funktionen aufrufen. Dazu wird spekulatives Inlining verwendet:

  1. Frisch geladener Code wird ohne Optimierung ausgeführt. Während dieser Phase verfolgt die JVM für jeden Aufrufstandort, welche Methoden tatsächlich aufgerufen wurden.
  2. Sobald Code als Leistungs-Hotspot identifiziert wurde, verwendet die Laufzeit diese Statistiken, um den wahrscheinlichsten Ausführungspfad zu identifizieren, und fügt diesen hinzu, wobei ein bedingter Zweig vorangestellt wird, falls die spekulative Optimierung nicht angewendet wird.

Das heißt, der Code:

int x = point.getX();

wird umgeschrieben

if (point.class != Point) GOTO interpreter;
x = point.x;

Und natürlich ist die Laufzeit intelligent genug, um diese Typprüfung zu beschleunigen, solange kein Punkt zugewiesen ist, oder sie zu löschen, wenn der Typ dem aufrufenden Code bekannt ist.

Zusammenfassend lässt sich sagen, dass selbst wenn Java das automatische Inlining von Methoden verwaltet, es keinen inhärenten Grund gibt, warum ein Compiler das automatische Inlining nicht unterstützen kann, und zwar aus jedem Grund, weil Inlining für moderne Prozessoren von großem Vorteil ist. Ich kann mir daher kaum einen modernen Mainstream-Compiler vorstellen, der diese grundlegendsten Optimierungsstrategien nicht kennt, und würde einen Compiler voraussetzen, der dazu in der Lage ist, sofern nichts anderes bewiesen ist.

Meriton
quelle
4
"Es gibt keinen inhärenten Grund, warum ein Compiler automatisches Inlining nicht unterstützen könnte" - das gibt es. Sie haben über die JIT-Kompilierung gesprochen, bei der es sich um sich selbst ändernden Code handelt (den ein Betriebssystem aus Sicherheitsgründen möglicherweise verhindert) und die Möglichkeit zur automatischen profilgesteuerten Vollprogrammoptimierung. Ein AOT-Compiler für eine Sprache, die dynamisches Verknüpfen ermöglicht, weiß nicht genug, um einen Anruf zu dedirtualisieren und zu integrieren. OTOH: Ein AOT-Compiler hat Zeit, alles zu optimieren, was er kann. Ein JIT-Compiler hat nur Zeit, sich auf kostengünstige Optimierungen an Hotspots zu konzentrieren. In den meisten Fällen ist die JIT dadurch geringfügig benachteiligt.
amon
2
Nennen Sie mir ein Betriebssystem, das die Ausführung von Google Chrome "aus Sicherheitsgründen" verhindert (V8 kompiliert JavaScript zur Laufzeit in nativen Code). Das Inline-Schalten von AOT ist auch kein inhärenter Grund (dies hängt nicht von der Sprache ab, sondern von der Architektur, die Sie für Ihren Compiler ausgewählt haben). Dynamische Verknüpfungen verhindern zwar das Inlining von AOT über Kompilierungseinheiten hinweg, jedoch nicht das Inlining innerhalb der Kompilierung Einheiten, in denen die meisten Anrufe stattfinden. Tatsächlich ist nützliches Inlining in einer Sprache, in der dynamische Verknüpfungen weniger häufig verwendet werden als in Java, wahrscheinlich einfacher.
Meriton
4
Insbesondere unter iOS wird JIT für nicht privilegierte Apps verhindert. Chrome oder Firefox müssen die von Apple bereitgestellte Webansicht anstelle ihrer eigenen Engines verwenden. Ein guter Punkt ist jedoch, dass AOT vs. JIT eine Implementierungsebene und keine Sprachauswahl ist.
amon
@meriton Windows 10 S und Betriebssysteme für Videospielkonsolen blockieren in der Regel auch JIT-Engines von Drittanbietern.
Damian Yerrick
2

Beachten Sie, dass die Kosten eines Methodenaufrufs je nach Sprache erheblich sein können. Es gibt fast immer einen Kompromiss zwischen dem Schreiben von lesbarem Code und dem Schreiben von performantem Code.

Dies ist leider stark abhängig von:

  • die Compiler-Toolchain, einschließlich der JIT,
  • die Domain.

Zunächst ist das erste Gesetz der Leistungsoptimierung das Profil . In vielen Bereichen spielt die Leistung des Softwareteils keine Rolle für die Leistung des gesamten Stacks: Datenbankaufrufe, Netzwerkoperationen, Betriebssystemoperationen, ...

Dies bedeutet, dass die Leistung der Software völlig irrelevant ist, auch wenn die Latenz nicht verbessert wird. Durch die Optimierung der Software können Energie- und Hardwareeinsparungen (oder Batterieeinsparungen bei mobilen Apps) erzielt werden, die von Bedeutung sein können.

Diese können jedoch in der Regel NICHT in die Augen geschlossen werden, und oftmals trumpfen algorithmische Verbesserungen Mikrooptimierungen bei weitem auf.

Bevor Sie also optimieren, müssen Sie verstehen, wofür Sie optimieren ... und ob es sich lohnt.


In Bezug auf die reine Software-Leistung sind die Unterschiede zwischen den Toolchains sehr groß.

Es gibt zwei Kosten für einen Funktionsaufruf:

  • die Laufzeitkosten,
  • die Kompilierzeit kostet.

Die Laufzeitkosten sind ziemlich offensichtlich; Um einen Funktionsaufruf auszuführen, ist ein gewisser Arbeitsaufwand erforderlich. Wenn Sie beispielsweise C auf x86 verwenden, müssen für einen Funktionsaufruf (1) Register in den Stapel geschrieben, (2) Argumente in die Register geschrieben, der Aufruf ausgeführt und anschließend (3) die Register aus dem Stapel wiederhergestellt werden. In dieser Zusammenfassung der Aufrufkonventionen sehen Sie die damit verbundene Arbeit .

Diese Registerüberlappung / -wiederherstellung nimmt nicht unerhebliche Zeit in Anspruch (Dutzende von CPU-Zyklen).

Es wird allgemein erwartet, dass diese Kosten im Vergleich zu den tatsächlichen Kosten der Ausführung der Funktion geringfügig sind, jedoch sind einige Muster hier kontraproduktiv: Getter, durch eine einfache Bedingung geschützte Funktionen usw.

Ein Programmierer hofft daher, dass sein Compiler oder JIT neben den Interpreten die unnötigen Funktionsaufrufe herausoptimiert. obwohl diese Hoffnung manchmal nicht Früchte tragen kann. Weil Optimierer keine Zauberei sind.

Ein Optimierer kann erkennen , dass ein Funktionsaufruf trivial ist und inline den Anruf: Im Wesentlichen Kopieren / Einfügen des Körpers der Funktion an der Aufrufstelle. Dies ist nicht immer eine gute Optimierung (kann zu Aufblähen führen), lohnt sich jedoch im Allgemeinen, da durch Inlining der Kontext verfügbar gemacht wird und der Kontext weitere Optimierungen ermöglicht.

Ein typisches Beispiel ist:

void func(condition: boolean) {
    if (condition) {
        doLotsOfWork();
    }
}

void call() { func(false); }

Wenn funceingeblendet ist, erkennt der Optimierer, dass die Verzweigung niemals verwendet wird, und optimiert callauf void call() {}.

In diesem Sinne können Funktionsaufrufe bestimmte Optimierungen verhindern, indem sie Informationen aus dem Optimierer verbergen (sofern diese noch nicht eingebettet sind). Hieran sind insbesondere virtuelle Funktionsaufrufe schuld, da die Devirtualisierung (der Nachweis, welche Funktion letztendlich zur Laufzeit aufgerufen wird) nicht immer einfach ist.


Abschließend rate ich, zunächst klar zu schreiben , um eine vorzeitige algorithmische Pessimierung (kubische Komplexität oder schlimmeres beißt schnell) zu vermeiden und dann nur das zu optimieren, was optimiert werden muss.

Matthieu M.
quelle
1

"Denken Sie daran, dass die Kosten eines Methodenaufrufs je nach Sprache erheblich sein können. Es gibt fast immer einen Kompromiss zwischen dem Schreiben von lesbarem Code und dem Schreiben von performantem Code."

Unter welchen Bedingungen ist diese zitierte Aussage angesichts der reichen Industrie leistungsfähiger moderner Compiler heute noch gültig?

Ich werde einfach nie sagen. Ich glaube, das Zitat ist leichtsinnig, es einfach rauszuwerfen.

Natürlich spreche ich nicht die vollständige Wahrheit, aber es ist mir egal, ob ich so ehrlich bin. Es ist wie in diesem Matrix - Film, ich habe vergessen, ob es 1 oder 2 oder 3 war - ich denke, es war die mit der sexy italienischen Schauspielerin mit den großen Melonen (ich mochte wirklich keine außer der ersten), als die Orakeldame sagte zu Keanu Reeves: "Ich habe dir gerade gesagt, was du hören musst."

Programmierer brauchen das nicht zu hören. Wenn sie Erfahrung mit Profilern in der Hand haben und das Zitat in gewisser Weise auf ihre Compiler zutrifft, wissen sie dies bereits und lernen es auf die richtige Weise, vorausgesetzt, sie verstehen ihre Profilausgabe und warum bestimmte Blattaufrufe Hotspots sind, durch Messen. Wenn sie noch keine Erfahrung haben und ihren Code noch nie profiliert haben, ist dies das Letzte, was sie hören müssen, damit sie anfangen sollten, den Code abergläubisch zu kompromittieren, bevor sie Hotspots identifizieren, in der Hoffnung, dass dies der Fall sein wird performanter werden.

Wie auch immer, für eine genauere Antwort kommt es darauf an. Einige der Bootladungen von Bedingungen sind bereits unter den guten Antworten aufgeführt. Die möglichen Bedingungen, nur eine Sprache zu wählen, sind selbst schon riesig, wie C ++, das in virtuellen Aufrufen in den dynamischen Versand geraten müsste und wann es optimiert werden kann und unter welchen Compilern und sogar Linkern, und das schon eine detaillierte Antwort rechtfertigt, geschweige denn einen Versuch die Bedingungen in jeder möglichen Sprache und Compiler da draußen anzugehen. Aber ich werde oben hinzufügen, "wen interessiert das?" Selbst wenn ich in leistungskritischen Bereichen als Raytracing arbeite, werde ich mich als letztes mit Hand-Inlining-Methoden befassen, bevor ich Messungen vornehme.

Ich glaube, einige Leute sind übereifrig, wenn sie vorschlagen, dass Sie vor dem Messen niemals Mikrooptimierungen vornehmen sollten. Wenn die Optimierung nach Referenzlokalität als Mikrooptimierung gilt, beginne ich häufig gleich zu Beginn mit der Anwendung solcher Optimierungen, und zwar mit einer datenorientierten Design-Denkweise in Bereichen, von denen ich weiß, dass sie für die Leistung von entscheidender Bedeutung sind (z. B. Raytracing-Code). weil ich sonst weiß, dass ich große Abschnitte umschreiben muss, nachdem ich jahrelang in diesen Bereichen gearbeitet habe. Das Optimieren der Datendarstellung für Cache-Treffer kann oft die gleiche Leistungsverbesserung wie algorithmische Verbesserungen bewirken, es sei denn, es handelt sich um eine quadratische bis lineare Zeit.

Ich sehe jedoch nie einen guten Grund, vor den Messungen mit dem Inlining zu beginnen, zumal die Profiler in der Lage sind, den Nutzen von Inlining zu offenbaren, aber nicht, den Nutzen von Inlining zu offenbaren (und das Nicht-Inlining kann den Code tatsächlich beschleunigen, wenn die unlinierter Funktionsaufruf ist ein seltener Fall, der die Referenzlokalität für den Icache für Hot-Code verbessert und es manchmal sogar Optimierern ermöglicht, eine bessere Arbeit für den normalen Ausführungspfad zu leisten.


quelle