Effizienz der vorzeitigen Rückkehr in einer Funktion

97

Dies ist eine Situation, der ich als unerfahrener Programmierer häufig begegne und die ich mich besonders für ein ehrgeiziges, geschwindigkeitsintensives Projekt wundere, das ich zu optimieren versuche. Werden diese beiden Funktionen für die wichtigsten C-ähnlichen Sprachen (C, objC, C ++, Java, C # usw.) und ihre üblichen Compiler genauso effizient ausgeführt? Gibt es einen Unterschied im kompilierten Code?

void foo1(bool flag)
{
    if (flag)
    {
        //Do stuff
        return;
    }

    //Do different stuff
}

void foo2(bool flag)
{
    if (flag)
    {
        //Do stuff
    }
    else
    {
        //Do different stuff
    }
}

Grundsätzlich gibt es jemals einen direkten Effizienzbonus / eine direkte Effizienzstrafe, wenn Sie früh breakoder returnfrüh gehen? Wie ist der Stackframe beteiligt? Gibt es optimierte Sonderfälle? Gibt es Faktoren (wie Inlining oder die Größe von "Do stuff"), die dies erheblich beeinflussen könnten?

Ich bin immer ein Befürworter einer verbesserten Lesbarkeit gegenüber kleineren Optimierungen (ich sehe foo1 häufig bei der Parametervalidierung), aber dies kommt so häufig vor, dass ich alle Sorgen ein für alle Mal beiseite lassen möchte.

Und ich bin mir der Fallstricke einer vorzeitigen Optimierung bewusst ... ugh, das sind einige schmerzhafte Erinnerungen.

EDIT: Ich habe eine Antwort akzeptiert, aber die Antwort von EJP erklärt ziemlich prägnant, warum die Verwendung von a returnpraktisch vernachlässigbar ist (bei der Montage returnwird eine 'Verzweigung' bis zum Ende der Funktion erstellt, was extrem schnell ist. Die Verzweigung verändert das PC-Register und Dies kann sich auch auf den Cache und die Pipeline auswirken, was ziemlich winzig ist.) Insbesondere in diesem Fall spielt dies buchstäblich keine Rolle, da sowohl der if/elseals auch returnderselbe Zweig bis zum Ende der Funktion erstellt werden.

Philip Guin
quelle
22
Ich denke nicht, dass solche Dinge einen spürbaren Einfluss auf die Leistung haben werden. Schreiben Sie einfach einen kleinen Test und überzeugen Sie sich. Imo, die erste Variante ist besser, da Sie keine unnötige Verschachtelung erhalten, was die Lesbarkeit verbessert
SirVaulterScoff
10
@SirVaulterScott, es sei denn, die beiden Fälle sind in irgendeiner Weise symmetrisch. In diesem Fall möchten Sie die Symmetrie hervorheben, indem Sie sie auf die gleiche Einrückungsstufe setzen.
Luqui
3
SirVaulterScoff: +1 für die Reduzierung nicht benötigter Verschachtelungen
fjdumont
11
Lesbarkeit >>> Mikrooptimierungen. Tun Sie es auf eine Weise, die für die Wetware, die dies aufrechterhält, sinnvoller ist. Auf Maschinencodeebene sind diese beiden Strukturen identisch, wenn sie selbst einem ziemlich dummen Compiler zugeführt werden. Ein optimierender Compiler löscht jeden Anschein eines Geschwindigkeitsvorteils zwischen den beiden.
SplinterReality
12
Optimieren Sie Ihr "geschwindigkeitsintensives" Projekt nicht, indem Sie sich über solche Dinge Gedanken machen. Profilieren Sie Ihre App, um herauszufinden, wo sie tatsächlich langsam ist - wenn sie tatsächlich zu langsam ist, wenn Sie damit fertig sind. Sie können mit ziemlicher Sicherheit nicht erraten, was es tatsächlich verlangsamt.
Blueshift

Antworten:

92

Es gibt überhaupt keinen Unterschied:

=====> cat test_return.cpp
extern void something();
extern void something2();

void test(bool b)
{
    if(b)
    {
        something();
    }
    else
        something2();
}
=====> cat test_return2.cpp
extern void something();
extern void something2();

void test(bool b)
{
    if(b)
    {
        something();
        return;
    }
    something2();
}
=====> rm -f test_return.s test_return2.s
=====> g++ -S test_return.cpp 
=====> g++ -S test_return2.cpp 
=====> diff test_return.s test_return2.s
=====> rm -f test_return.s test_return2.s
=====> clang++ -S test_return.cpp 
=====> clang++ -S test_return2.cpp 
=====> diff test_return.s test_return2.s
=====> 

Dies bedeutet, dass auch ohne Optimierung in zwei Compilern kein Unterschied im generierten Code besteht

Dani
quelle
59
Oder besser: Es gibt mindestens eine Version eines bestimmten Compilers, der für beide Versionen denselben Code generiert.
Onkel Zeiv
11
@UncleZeiv - Die meisten, wenn nicht alle Compiler übersetzen die Quelle in ein Ausführungsflussdiagrammmodell. Es ist schwer vorstellbar, dass eine vernünftige Implementierung für diese beiden Beispiele signifikant unterschiedliche Flussdiagramme liefert. Der einzige Unterschied, den Sie möglicherweise sehen, besteht darin, dass die beiden verschiedenen Aufgaben ausgetauscht werden - und selbst dies kann in vielen Implementierungen rückgängig gemacht werden, um die Verzweigungsvorhersage zu optimieren, oder bei einem anderen Problem, bei dem die Plattform die bevorzugte Reihenfolge festlegt.
Steve314
6
@ Steve314, klar, ich habe nur nicht gepickt :)
UncleZeiv
@UncleZeiv: auch auf Clang getestet und das gleiche Ergebnis
Dani
Ich verstehe nicht. Es scheint klar, something()dass immer ausgeführt wird. In der ursprünglichen Frage hat OP Do stuffund Do diffferent stuffabhängig von der Flagge. Ich bin nicht sicher, ob der generierte Code der gleiche sein wird.
Luc M
65

Die kurze Antwort lautet: Kein Unterschied. Tun Sie sich selbst einen Gefallen und machen Sie sich keine Sorgen mehr. Der optimierende Compiler ist fast immer schlauer als Sie.

Konzentrieren Sie sich auf Lesbarkeit und Wartbarkeit.

Wenn Sie sehen möchten, was passiert, bauen Sie diese mit Optimierungen auf und sehen Sie sich die Assembler-Ausgabe an.

Blauverschiebung
quelle
8
@Philip: Und tu auch allen anderen einen Gefallen und hör auf, dir darüber Sorgen zu machen. Der Code, den Sie schreiben, wird auch von anderen gelesen und gepflegt (und selbst wenn Sie schreiben, dass er niemals von anderen gelesen wird, entwickeln Sie dennoch Gewohnheiten, die anderen Code beeinflussen, den Sie schreiben und der von anderen gelesen wird). Schreiben Sie immer Code, um so einfach wie möglich zu verstehen.
Hlovdal
8
Optimierer sind nicht schlauer als Sie !!! Sie können nur schneller entscheiden, wo die Auswirkungen nicht allzu wichtig sind. Wo es wirklich darauf ankommt, werden Sie mit etwas Erfahrung mit Sicherheit besser optimieren als der Compiler.
Johannes
10
@johannes Lass mich nicht zustimmen. Der Compiler wird Ihren Algorithmus nicht gegen einen besseren austauschen, aber er leistet hervorragende Arbeit bei der Neuordnung von Anweisungen, um maximale Pipeline-Effizienz und andere nicht so triviale Dinge für Schleifen (Spaltung, Fusion usw.) zu erzielen, die selbst ein erfahrener Programmierer nicht entscheiden kann Was ist a priori besser, wenn er die CPU-Architektur nicht genau kennt?
Fortan
3
@johannes - für diese Frage können Sie davon ausgehen, dass dies der Fall ist. Im Allgemeinen können Sie in einigen Sonderfällen gelegentlich auch besser optimieren als der Compiler. Dies erfordert jedoch heutzutage einiges an Fachwissen - der Normalfall ist, dass der Optimierer die meisten Optimierungen anwendet, die Sie sich vorstellen können, und dies tut systematisch, nicht nur in wenigen Sonderfällen. Bei dieser Frage wird der Compiler wahrscheinlich genau das gleiche Ausführungsflussdiagramm für beide Formulare erstellen. Die Wahl eines besseren Algorithmus ist eine menschliche Aufgabe, aber die Optimierung auf Codeebene ist fast immer Zeitverschwendung.
Steve314
4
Ich stimme dem zu und stimme dem nicht zu. Es gibt Fälle, in denen der Compiler nicht wissen kann, dass etwas etwas anderem entspricht. Wussten Sie, dass dies oft viel schneller geht, x = <some number>als nicht if(<would've changed>) x = <some number>benötigte Zweige wirklich weh tun können ? Auf der anderen Seite würde ich mir darüber auch keine Sorgen machen, es sei denn, dies befindet sich in der Hauptschleife einer extrem intensiven Operation.
user606723
28

Interessante Antworten: Obwohl ich (bisher) allen zustimme, gibt es mögliche Konnotationen zu dieser Frage, die bisher völlig außer Acht gelassen wurden.

Wenn das obige einfache Beispiel um die Ressourcenzuweisung und die Fehlerprüfung mit einer möglichen daraus resultierenden Ressourcenfreigabe erweitert wird, kann sich das Bild ändern.

Betrachten Sie den naiven Ansatz, den Anfänger verfolgen könnten:

int func(..some parameters...) {
  res_a a = allocate_resource_a();
  if (!a) {
    return 1;
  }
  res_b b = allocate_resource_b();
  if (!b) {
    free_resource_a(a);
    return 2;
  }
  res_c c = allocate_resource_c();
  if (!c) {
    free_resource_b(b);
    free_resource_a(a);
    return 3;
  }

  do_work();

  free_resource_c(c);
  free_resource_b(b);
  free_resource_a(a);

  return 0;
}

Das Obige würde eine extreme Version des Stils der vorzeitigen Rückkehr darstellen. Beachten Sie, dass sich der Code im Laufe der Zeit sehr wiederholt und nicht mehr gewartet werden kann, wenn seine Komplexität zunimmt. Heutzutage könnten Leute die Ausnahmebehandlung verwenden , um diese zu fangen.

int func(..some parameters...) {
  res_a a;
  res_b b;
  res_c c;

  try {
    a = allocate_resource_a(); # throws ExceptionResA
    b = allocate_resource_b(); # throws ExceptionResB
    c = allocate_resource_c(); # throws ExceptionResC
    do_work();
  }  
  catch (ExceptionBase e) {
    # Could use type of e here to distinguish and
    # use different catch phrases here
    # class ExceptionBase must be base class of ExceptionResA/B/C
    if (c) free_resource_c(c);
    if (b) free_resource_b(b);
    if (a) free_resource_a(a);
    throw e
  }
  return 0;
}

Philip schlug vor, nachdem er sich das folgende Beispiel angesehen zu haben, einen unterbrechungsfreien Schalter / Koffer im oberen Fangblock zu verwenden. Man könnte wechseln (typeof (e)) und dann durch die free_resourcex()Anrufe fallen, aber dies ist nicht trivial und erfordert Designüberlegungen . Und denken Sie daran, dass ein Schalter / Gehäuse ohne Unterbrechungen genau wie das Goto mit verketteten Etiketten unten ist ...

Wie Mark B hervorhob, wird es in C ++ als guter Stil angesehen, dem Prinzip der Ressourcenerfassung als Initialisierung zu folgen , kurz RAII . Der Kern des Konzepts besteht darin, die Objektinstanziierung zu verwenden, um Ressourcen zu erwerben. Die Ressourcen werden dann automatisch freigegeben, sobald die Objekte den Gültigkeitsbereich verlassen und ihre Destruktoren aufgerufen werden. Bei voneinander abhängigen Ressourcen muss besonders darauf geachtet werden, die richtige Reihenfolge der Freigabe sicherzustellen und die Objekttypen so zu gestalten, dass die erforderlichen Daten für alle Destruktoren verfügbar sind.

Oder in Tagen vor der Ausnahme könnte Folgendes passieren:

int func(..some parameters...) {
  res_a a = allocate_resource_a();
  res_b b = allocate_resource_b();
  res_c c = allocate_resource_c();
  if (a && b && c) {   
    do_work();
  }  
  if (c) free_resource_c(c);
  if (b) free_resource_b(b);
  if (a) free_resource_a(a);

  return 0;
}

Dieses stark vereinfachte Beispiel weist jedoch mehrere Nachteile auf: Es kann nur verwendet werden, wenn die zugewiesenen Ressourcen nicht voneinander abhängen (z. B. kann es nicht zum Zuweisen von Speicher, zum Öffnen eines Dateihandles und zum Einlesen von Daten aus dem Handle in den Speicher verwendet werden ), und es werden keine einzelnen, unterscheidbaren Fehlercodes als Rückgabewerte bereitgestellt.

Um den Code schnell (!), Kompakt, leicht lesbar und erweiterbar zu halten, hat Linus Torvalds einen anderen Stil für Kernel-Code erzwungen, der sich mit Ressourcen befasst, selbst wenn das berüchtigte goto auf eine absolut sinnvolle Weise verwendet wird :

int func(..some parameters...) {
  res_a a;
  res_b b;
  res_c c;

  a = allocate_resource_a() || goto error_a;
  b = allocate_resource_b() || goto error_b;
  c = allocate_resource_c() || goto error_c;

  do_work();

error_c:
  free_resource_c(c);
error_b:
  free_resource_b(b);
error_a:
  free_resource_a(a);

  return 0;
}

Der Kern der Diskussion über die Kernel-Mailinglisten ist, dass die meisten Sprachfunktionen, die der goto-Anweisung "vorgezogen" werden, implizite gotos sind, wie z. B. riesige, baumartige if / else-Ausnahmebehandlungsroutinen, Schleifen- / Unterbrechungs- / Fortsetzungsanweisungen usw. Und gotos im obigen Beispiel gelten als in Ordnung, da sie nur eine kleine Strecke springen, klare Beschriftungen haben und den Code anderer Unordnung freigeben, um die Fehlerbedingungen zu verfolgen. Diese Frage wurde auch hier zum Stackoverflow diskutiert .

Was jedoch im letzten Beispiel fehlt, ist eine gute Möglichkeit, einen Fehlercode zurückzugeben. Ich dachte daran, result_code++nach jedem free_resource_x()Aufruf ein hinzuzufügen und diesen Code zurückzugeben, aber dies gleicht einige der Geschwindigkeitsgewinne des obigen Codierungsstils aus. Und es ist schwierig, im Erfolgsfall 0 zurückzugeben. Vielleicht bin ich nur einfallslos ;-)

Ja, ich glaube, es gibt einen großen Unterschied in der Frage, ob vorzeitige Rückgaben codiert werden sollen oder nicht. Ich denke aber auch, dass es nur in komplizierterem Code offensichtlich ist, dass es schwieriger oder unmöglich ist, den Compiler neu zu strukturieren und zu optimieren. Dies ist normalerweise der Fall, sobald die Ressourcenzuweisung ins Spiel kommt.

cfi
quelle
1
Wow, wirklich interessant. Ich kann definitiv die Unhaltbarkeit des naiven Ansatzes schätzen. Wie würde sich die Ausnahmebehandlung in diesem speziellen Fall verbessern? Wie eine Anweisung ohne catchUnterbrechung switchzum Fehlercode?
Philip Guin
@Philip Grundlegendes Beispiel für die Ausnahmebehandlung hinzugefügt. Beachten Sie, dass nur der goto eine Durchfallmöglichkeit hat. Ihr vorgeschlagener Schalter (Typ von (e)) würde helfen, ist jedoch nicht trivial und erfordert Designüberlegungen . Und denken Sie daran, dass ein Schalter / Gehäuse ohne Unterbrechungen genau wie das Goto mit verketteten Etiketten ist ;-)
cfi
+1 Dies ist die richtige Antwort für C / C ++ (oder jede Sprache, die eine manuelle Speicherfreigabe erfordert). Persönlich mag ich die Version mit mehreren Etiketten nicht. Bei meiner vorherigen Firma war es immer "goto fin" (es war eine französische Firma). In fin würden wir jeden Speicher freigeben, und das war die einzige Verwendung von goto, die die Codeüberprüfung bestehen würde.
Kip
1
Beachten Sie, dass Sie in C ++ keinen dieser Ansätze ausführen würden, sondern RAII verwenden würden, um sicherzustellen, dass die Ressourcen ordnungsgemäß bereinigt werden.
Mark B
12

Auch wenn dies keine gute Antwort ist, kann ein Produktions-Compiler viel besser optimieren als Sie. Ich würde Lesbarkeit und Wartbarkeit gegenüber solchen Optimierungen bevorzugen.

Lou
quelle
9

Um genau zu sein, returnwird das zu einem Zweig bis zum Ende der Methode kompiliert, wo es eine RETAnweisung gibt oder was auch immer es sein mag. Wenn Sie es weglassen, wird das Ende des Blocks vor dem elsezu einem Zweig bis zum Ende des elseBlocks kompiliert . Sie können also in diesem speziellen Fall sehen, dass es überhaupt keinen Unterschied macht.

Marquis von Lorne
quelle
Erwischt. Ich denke tatsächlich, dass dies meine Frage ziemlich prägnant beantwortet; Ich denke, es ist buchstäblich nur eine Registerergänzung, die ziemlich vernachlässigbar ist (es sei denn, Sie machen vielleicht Systemprogrammierung und selbst dann ...). Ich werde dies ehrenvoll erwähnen.
Philip Guin
@Philip welches Register hinzufügen? Es gibt überhaupt keine zusätzlichen Anweisungen im Pfad.
Marquis von Lorne
Nun, beide hätten Registerzusätze. Das ist alles, was ein Montagezweig ist, nicht wahr? Eine Ergänzung zum Programmzähler? Ich könnte mich hier irren.
Philip Guin
1
@Philip Nein, ein Assembly-Zweig ist ein Assembly-Zweig. Es wirkt sich natürlich auf den PC aus, aber es könnte sein, dass es vollständig neu geladen wird, und es hat auch Nebenwirkungen im Prozessor in Bezug auf die Pipeline, Caches usw.
Marquis of Lorne
4

Wenn Sie wirklich wissen möchten, ob es einen Unterschied im kompilierten Code für Ihren speziellen Compiler und Ihr System gibt, müssen Sie die Assembly selbst kompilieren und betrachten.

Im großen Rahmen ist es jedoch fast sicher, dass der Compiler besser optimieren kann als Ihre Feinabstimmung, und selbst wenn dies nicht möglich ist, ist es sehr unwahrscheinlich, dass dies tatsächlich für die Leistung Ihres Programms von Bedeutung ist.

Schreiben Sie stattdessen den Code so, dass der Mensch ihn am besten lesen und warten kann, und lassen Sie den Compiler das tun, was er am besten kann: Generieren Sie die bestmögliche Assembly aus Ihrer Quelle.

Mark B.
quelle
4

In Ihrem Beispiel ist die Rendite spürbar. Was passiert mit der Person, die debuggt, wenn die Rückgabe eine oder zwei Seiten über / unter ist, auf denen // verschiedene Dinge auftreten? Viel schwieriger zu finden / zu sehen, wenn mehr Code vorhanden ist.

void foo1(bool flag)
{
    if (flag)
    {
        //Do stuff
        return;
    }

    //Do different stuff
}

void foo2(bool flag)
{
    if (flag)
    {
        //Do stuff
    }
    else
    {
        //Do different stuff
    }
}
PCPGMR
quelle
Natürlich sollte eine Funktion nicht länger als eine (oder sogar zwei) Seiten sein. Der Debugging-Aspekt wurde jedoch in keiner der anderen Antworten behandelt. Punkt genommen!
cfi
3

Ich stimme Blueshift sehr zu: Lesbarkeit und Wartbarkeit zuerst!. Aber wenn Sie wirklich besorgt sind (oder einfach nur erfahren möchten, was Ihr Compiler tut, was auf lange Sicht definitiv eine gute Idee ist), sollten Sie selbst nachsehen.

Dies bedeutet, dass Sie einen Dekompiler verwenden oder die Compilerausgabe auf niedriger Ebene betrachten (z. B. Assemblersprache). In C # oder einer beliebigen .NET-Sprache bieten Ihnen die hier dokumentierten Tools das, was Sie benötigen.

Aber wie Sie selbst beobachtet haben, ist dies wahrscheinlich eine vorzeitige Optimierung.

Mr. Putty
quelle
1

Aus sauberem Code: Ein Handbuch für agile Software-Handwerkskunst

Flaggenargumente sind hässlich. Das Übergeben eines Booleschen Werts an eine Funktion ist eine wirklich schreckliche Praxis. Es verkompliziert sofort die Signatur der Methode und verkündet lautstark, dass diese Funktion mehr als eine Sache tut. Es macht eine Sache, wenn die Flagge wahr ist und eine andere, wenn die Flagge falsch ist!

foo(true);

im Code wird den Leser nur dazu bringen, zur Funktion zu navigieren und Zeit damit zu verschwenden, foo zu lesen (boolesches Flag)

Eine besser strukturierte Codebasis bietet Ihnen eine bessere Möglichkeit, den Code zu optimieren.

Yuan
quelle
Ich benutze dies nur als Beispiel. Was an die Funktion übergeben wird, kann ein int, double, eine Klasse sein, wie Sie es nennen, es ist nicht wirklich das Herzstück des Problems.
Philip Guin
Die Frage, die Sie gestellt haben, betrifft das Umschalten innerhalb Ihrer Funktion. In den meisten Fällen handelt es sich um einen Codegeruch. Es kann auf viele Arten erreicht werden und der Leser muss nicht die ganze Funktion lesen. Sagen Sie, was bedeutet foo (28)?
Yuan
0

Eine Denkrichtung (ich kann mich nicht an den Eierkopf erinnern, der sie im Moment vorgeschlagen hat) ist, dass alle Funktionen aus struktureller Sicht nur einen Rückgabepunkt haben sollten, damit der Code leichter zu lesen und zu debuggen ist. Das ist wohl eher für die Programmierung religiöser Debatten gedacht.

Ein technischer Grund, warum Sie möglicherweise steuern möchten, wann und wie eine Funktion beendet wird, die gegen diese Regel verstößt, besteht darin, dass Sie Echtzeitanwendungen codieren und sicherstellen möchten, dass alle Steuerpfade durch die Funktion dieselbe Anzahl von Taktzyklen benötigen.

MartyTPS
quelle
Äh, ich dachte, es hat mit Aufräumen zu tun (besonders beim Codieren in C).
Thomas Eding
Nein, egal wo Sie eine Methode verlassen, solange Sie den Stapel zurückgeben, wird er zurückgestoßen (das ist alles, was "aufgeräumt" wird).
MartyTPS
-4

Ich bin froh, dass Sie diese Frage aufgeworfen haben. Sie sollten die Filialen immer über eine frühzeitige Rückgabe verwenden. Warum dort aufhören? Führen Sie alle Ihre Funktionen zu einer zusammen, wenn Sie können (mindestens so viel wie möglich). Dies ist möglich, wenn keine Rekursion vorliegt. Am Ende werden Sie eine massive Hauptfunktion haben, aber genau das brauchen / wollen Sie für diese Art von Dingen. Benennen Sie anschließend Ihre Bezeichner so kurz wie möglich um. Auf diese Weise wird beim Ausführen Ihres Codes weniger Zeit für das Lesen von Namen aufgewendet. Weiter machen ...

Thomas Eding
quelle
3
Ich kann Ihnen sagen, dass Sie Witze machen, aber das Beängstigende ist, dass manche Leute Ihren Rat einfach ernst nehmen!
Daniel Pryden
Stimme Daniel zu. So sehr ich Zynismus liebe - er sollte nicht in technischen Dokumentationen, Whitepapers und Q & A-Sites wie SO verwendet werden.
cfi
1
-1 für eine zynische Antwort, die für Anfänger nicht unbedingt erkennbar ist.
Johan Bezem