Warum verwenden Programme Aufrufstapel, wenn verschachtelte Funktionsaufrufe eingebunden werden können?

32

Warum lässt der Compiler nicht ein Programm wie das folgende ausführen:

function a(b) { return b^2 };
function c(b) { return a(b) + 5 };

und konvertiere es in ein Programm wie dieses:

function c(b) { return b^2 + 5 };

Dadurch entfällt die Notwendigkeit des Computers, sich die Absenderadresse von c (b) zu merken.

Ich nehme an, dass der erhöhte Festplattenspeicher und RAM, die zum Speichern des Programms bzw. zur Unterstützung seiner Kompilierung erforderlich sind, der Grund ist, warum wir Aufrufstapel verwenden. Ist das korrekt?

moonman239
quelle
30
Sehen Sie, was passiert, wenn Sie dies in einem Programm mit einer sinnvollen Größe tun. Insbesondere werden Funktionen von mehr als einer Stelle aus aufgerufen.
user253751
10
Manchmal weiß der Compiler auch nicht, welche Funktion aufgerufen wird! window[prompt("Enter function name","")]()
Dummes
26
Wie implementieren Sie function(a)b { if(b>0) return a(b-1); }ohne Stack?
pjc50
8
Wo ist der Bezug zur funktionalen Programmierung?
Mastov
14
@ pjc50: Es ist rekursiv, also übersetzt der Compiler es in eine Schleife mit einer veränderlichen b. Es sei jedoch angemerkt, dass nicht alle rekursiven Funktionen die Rekursion beseitigen können, und selbst wenn die Funktion dies im Prinzip kann, ist der Compiler möglicherweise nicht schlau genug, dies zu tun.
Steve Jessop

Antworten:

75

Dies wird als "Inlining" bezeichnet, und viele Compiler tun dies als Optimierungsstrategie, wenn dies sinnvoll ist.

In Ihrem speziellen Beispiel würde diese Optimierung sowohl Platz als auch Ausführungszeit sparen. Wenn die Funktion jedoch an mehreren Stellen im Programm aufgerufen würde (nicht ungewöhnlich!), Würde dies die Codegröße erhöhen, sodass die Strategie zweifelhafter wird. (Und wenn sich eine Funktion direkt oder indirekt selbst aufruft, ist es natürlich unmöglich, sie in die Zeile einzufügen, da der Code dann unendlich groß wird.)

Und natürlich ist es nur für "private" Funktionen möglich. Funktionen, die für externe Anrufer verfügbar sind, können nicht entfernt werden, zumindest nicht in Sprachen mit dynamischer Verknüpfung.

JacquesB
quelle
7
@Blrfl: Moderne Compiler benötigen keine Definitionen mehr im Header. Sie können in mehrere Übersetzungseinheiten eingebunden werden. Dies erfordert jedoch einen anständigen Linker. Definitionen in Header-Dateien sind eine Problemumgehung für dumme Linker.
MSalters
3
"Funktionen, die für externe Anrufer verfügbar gemacht werden, können nicht entfernt werden" - die Funktion muss vorhanden sein, es kann jedoch ein beliebiger Aufrufstandort (entweder in Ihrem eigenen Code oder wenn sie die Quelle haben, der externe Anrufer) eingebunden werden.
Random832
14
Wow, 28 Upvotes für eine Antwort, die nicht einmal den Grund nennt, warum es unmöglich ist, alles zu inlinen: Rekursion.
Mastov
3
@R ..: LTO ist die LINK-Zeitoptimierung, nicht die LOAD-Zeitoptimierung.
MSalters
2
@immibis: Aber wenn der explizite Stapel durch den Compiler eingeführt wird, dann , dass Stapel ist der Call - Stack.
user2357112 unterstützt Monica
51

Ihre Frage besteht aus zwei Teilen: Warum haben Sie überhaupt mehrere Funktionen (anstatt Funktionsaufrufe durch ihre Definition zu ersetzen) und warum implementieren Sie diese Funktionen mit Aufrufstapeln, anstatt ihre Daten statisch irgendwo anders zuzuweisen?

Der erste Grund ist die Rekursion. Nicht nur die Art "Oh, machen wir einen neuen Funktionsaufruf für jeden einzelnen Eintrag in dieser Liste", sondern auch die bescheidene Art, bei der möglicherweise zwei Aufrufe einer Funktion gleichzeitig aktiv sind, mit vielen anderen Funktionen dazwischen. Sie müssen lokale Variablen auf einen Stapel legen, um dies zu unterstützen, und Sie können im Allgemeinen keine rekursiven Funktionen einbinden.

Dann gibt es ein Problem für Bibliotheken: Sie wissen nicht, welche Funktionen von wo und wie oft aufgerufen werden, so dass eine "Bibliothek" niemals wirklich kompiliert werden kann, sondern nur in einem geeigneten Hochformat an alle Clients ausgeliefert wird in die Anwendung eingebunden. Abgesehen von anderen Problemen verlieren Sie die dynamische Verknüpfung mit all ihren Vorteilen vollständig.

Darüber hinaus gibt es viele Gründe, Funktionen nicht zu integrieren, selbst wenn Sie Folgendes könnten:

  1. Es ist nicht unbedingt schneller. Das Einrichten und Abreißen des Stapelrahmens sind möglicherweise ein Dutzend Einzelzyklusanweisungen für viele große Funktionen oder Schleifenfunktionen, die nicht einmal 0,1% ihrer Ausführungszeit ausmachen.
  2. Es kann langsamer sein. Das Duplizieren von Code hat Kosten, z. B. wird der Befehls-Cache stärker unter Druck gesetzt.
  3. Einige Funktionen sind sehr umfangreich und werden von vielen Stellen aus aufgerufen. Wenn Sie sie überall einfügen, steigt die Binärzahl weit über das Vernünftige hinaus.
  4. Compiler haben es oft schwer mit sehr großen Funktionen. Wenn alles andere gleich ist, benötigt eine Funktion der Größe 2 * N mehr als 2 * T Zeit, während eine Funktion der Größe N T Zeit benötigt.

quelle
1
Punkt 4 überrascht mich. Was ist der Grund dafür?
JacquesB
12
@JacquesB Viele Optimierungsalgorithmen sind quadratisch, kubisch oder sogar technisch NP-vollständig. Das kanonische Beispiel ist die Registerzuordnung, die in Analogie zur Graphenfärbung NP-vollständig ist. (Normalerweise versuchen Compiler nicht, eine exakte Lösung zu finden, sondern es werden nur wenige sehr schlechte Heuristiken in linearer Zeit ausgeführt.) Viele einfache Optimierungen in einem Durchgang erfordern zuerst superlineare Analysedurchläufe, beispielsweise alles, was von der Dominanz in Kontrollabläufen abhängt (im Allgemeinen) n log n Zeit mit n Grundblöcken).
2
"Sie haben hier wirklich zwei Fragen." Nein, das tue ich nicht. Nur eine - warum nicht einen Funktionsaufruf als Platzhalter behandeln, den der Compiler beispielsweise durch den Code der aufgerufenen Funktion ersetzen könnte?
Moonman239
4
@ moonman239 Dann warf mich deine Formulierung ab. Ihre Frage kann jedoch genauso zerlegt werden, wie ich es in meiner Antwort getan habe, und ich denke, das ist eine nützliche Perspektive.
16

Stapel erlauben es uns, die durch die endliche Anzahl von Registern auferlegten Grenzen elegant zu umgehen.

Stellen Sie sich vor, Sie haben genau 26 globale "Register az" (oder sogar nur die 7-Byte-Register des 8080-Chips). Jede Funktion, die Sie in diese App schreiben, teilt diese flache Liste.

Ein naiver Start wäre, die ersten paar Register der ersten Funktion zuzuweisen, und zu wissen, dass es nur 3 dauerte, mit "d" für die zweite Funktion zu beginnen ... Sie sind schnell erschöpft.

Stattdessen , wenn Sie eine metaphorische Band haben, wie die Turing - Maschine, können Sie jede Funktion einen „Aufruf einer anderen Funktion“ starten , indem alle Variablen Spar es mit und nach vorn () , um das Band, und dann kann der Angerufene Funktion wursteln mit so vielen registriert sich wie es will. Wenn der Anruf beendet ist, gibt er die Kontrolle an die übergeordnete Funktion zurück, die weiß, wo die Ausgabe des Anrufs nach Bedarf abzufangen ist, und spielt das Band dann rückwärts ab, um seinen Zustand wiederherzustellen.

Ihr grundlegender Aufrufrahmen ist genau das und wird durch standardisierte Maschinencodesequenzen erstellt und gelöscht, die der Compiler um die Übergänge von einer Funktion zur anderen erstellt. (Es ist lange her, dass ich mich an meine C-Stack-Frames erinnern musste, aber Sie können sich über die verschiedenen Möglichkeiten informieren , welche Aufgaben bei X86_calling_conventions fallen gelassen werden .)

(Rekursion ist fantastisch, aber wenn Sie jemals Register ohne Stapel jonglieren müssten, würden Sie Stapel wirklich schätzen.)


Ich nehme an, dass der erhöhte Festplattenspeicher und RAM, die zum Speichern des Programms bzw. zur Unterstützung seiner Kompilierung erforderlich sind, der Grund ist, warum wir Aufrufstapel verwenden. Ist das korrekt?

Heutzutage können wir zwar mehr inlineen ("mehr Geschwindigkeit" ist immer gut; "weniger KB Assembly" bedeutet in einer Welt mit Videostreams sehr wenig). Die Haupteinschränkung liegt in der Fähigkeit des Compilers, bestimmte Codemustertypen zu reduzieren.

Zum Beispiel polymorphe Objekte - wenn Sie den einzigen Objekttyp, den Sie erhalten, nicht kennen, können Sie ihn nicht abflachen. Sie müssen sich die Vtable der Features des Objekts ansehen und diesen Zeiger durchlaufen ... was zur Laufzeit trivial ist und zur Kompilierungszeit nicht möglich ist.

Eine moderne Toolchain kann gerne eine polymorph definierte Funktion einbinden, wenn die Anzahl der Aufrufer abgeflacht ist, um genau zu wissen , welche Variante von obj ist:

class Base {
    public: void act() = 0;
};
class Child1: public Base {
    public: void act() {};
};
void ActOn(Base* something) {
    something->act();
}
void InlineMe() {
    Child1 thingamabob;
    ActOn(&thingamabob);
}

In den obigen Fällen kann der Compiler festlegen, dass das statische Inlining von InlineMe über die in act () enthaltenen Elemente beibehalten werden soll oder dass zur Laufzeit keine vtables berührt werden müssen.

Aber jede Unsicherheit in dem, was Geschmack des Objekts verlassen wird es als ein Anruf auf eine diskrete Funktion, auch wenn einige andere Anrufungen der gleichen Funktion sind inlined.

Xander
quelle
11

Fälle, die dieser Ansatz nicht behandeln kann:

function fib(a) { if(a>2) return fib(a-1)+fib(a-2); else return 1; }

function many(a) { for(i = 1 to a) { b(i); };}

Es gibt Sprachen und Plattformen mit begrenzten oder keinen Aufrufstapeln. PIC-Mikroprozessoren verfügen über einen Hardware-Stack, der auf 2 bis 32 Einträge beschränkt ist . Dies schafft Entwurfsbeschränkungen.

COBOL verbietet die Rekursion: https://stackoverflow.com/questions/27806812/in-cobol-ist-moglich-zu-rekursiv-einen-Absatz- aufrufen

Das Auferlegen eines Rekursionsverbots bedeutet, dass Sie den gesamten Aufruf des Programms statisch als DAG darstellen können. Ihr Compiler könnte dann eine Kopie einer Funktion für jede Stelle ausgeben, von der aus sie mit einem festen Sprung anstelle einer Rückkehr aufgerufen wird. Kein Stack erforderlich, nur mehr Programmspeicher, möglicherweise ziemlich viel für komplexe Systeme. Für kleine eingebettete Systeme bedeutet dies jedoch, dass zur Laufzeit kein Stapelüberlauf auftritt. Dies wäre eine schlechte Nachricht für Ihren Kernreaktor, Ihre Düsenturbine, die Drosselklappensteuerung usw.

pjc50
quelle
12
Ihr erstes Beispiel ist die Grundrekursion, und Sie haben dort Recht. Aber Ihr zweites Beispiel scheint eine for-Schleife zu sein, die eine andere Funktion aufruft. Das Inlining der Funktion unterscheidet sich vom Abrollen einer Schleife. die funktion kann ohne abrollen der schleife inliniert werden. Oder habe ich subtile Details übersehen?
jpmc26
1
Wenn Ihr erstes Beispiel die Fibonacci-Reihe definieren soll, ist es falsch. (Es fehlt ein fibAnruf.)
Paŭlo Ebermann
1
Während das Verbieten der Rekursion bedeutet, dass der gesamte Aufrufgraph als DAG dargestellt werden kann, bedeutet dies nicht, dass die vollständige Liste der verschachtelten Aufrufsequenzen auf angemessenem Raum aufgelistet werden kann. Bei einem meiner Projekte für einen Mikrocontroller mit 128 KB Codespeicherplatz habe ich den Fehler gemacht, nach einem Aufrufdiagramm zu fragen, das alle Funktionen enthält, die sich auf die maximale Anforderung an Parameter-RAM auswirken können. Dieses Aufrufdiagramm war länger als ein Gig. Eine vollständige Aufrufgrafik wäre sogar noch länger gewesen, und das galt für ein Programm, das in 128 KB Code-Speicherplatz passte.
Supercat
8

Sie möchten Function Inlining und die meisten ( optimierenden ) Compiler tun dies.

Beachten Sie, dass beim Inlining die aufgerufene Funktion bekannt sein muss (und nur wirksam ist, wenn die aufgerufene Funktion nicht zu groß ist), da sie den Aufruf konzeptionell durch das Umschreiben der aufgerufenen Funktion ersetzt. Daher können Sie im Allgemeinen keine unbekannte Funktion einbinden (z. B. einen Funktionszeiger - und der Funktionen aus dynamisch verknüpften gemeinsam genutzten Bibliotheken enthält -, der in einigen vtables möglicherweise als virtuelle Methode sichtbar ist, in einigen Compilern jedoch möglicherweise durch Devirtualisierungstechniken optimiert wird). Natürlich ist es nicht immer möglich, rekursive Funktionen inline zu setzen (einige clevere Compiler verwenden möglicherweise eine teilweise Auswertung und können in einigen Fällen rekursive Funktionen inline setzen).

Beachten Sie auch, dass das Inlining, auch wenn es leicht möglich ist, nicht immer effektiv ist: Sie (tatsächlich Ihr Compiler) könnten die Codegröße so stark erhöhen, dass CPU-Caches (oder Verzweigungsvorhersagen ) weniger effizient funktionieren und Ihr Programm dadurch ausgeführt wird Langsamer.

Ich konzentriere mich ein bisschen auf den funktionalen Programmierstil , da Sie Ihre Frage als solche gekennzeichnet haben.

Beachten Sie, dass Sie keinen Aufrufstapel benötigen (zumindest im maschinellen Sinne des Ausdrucks "Aufrufstapel"). Du könntest nur den Haufen benutzen.

Also, werfen Sie einen Blick auf Fortsetzungen und mehr über lesen Fortsetzung vorbei Stil (CPS) und CPS - Transformation (intuitiv, Sie Fortsetzung nutzen könnten Verschlüsse als verdinglichte „Call Rahmen“ zugeordnet , in dem Haufen, und sie sind sorten eines Call - Stack imitiert; dann brauchen sie einen effizienten müllsammler .

Andrew Appel schrieb ein Buch Compiling with Continuations und eine alte Papiermüllsammlung kann schneller sein als die Stapelzuweisung . Siehe auch A.Kennedys Arbeit (ICFP2007) Kompilieren mit Fortsetzungen, Fortsetzung

Ich empfehle außerdem, Queinnecs Buch „ Lisp In Small Pieces“ zu lesen , das mehrere Kapitel zum Thema Fortsetzung und Zusammenstellung enthält.

Beachten Sie auch, dass einige Sprachen (z. B. Brainfuck ) oder abstrakte Maschinen (z. B. OISC , RAM ) keine Aufrufmöglichkeiten haben, aber immer noch Turing-vollständig sind , sodass Sie (theoretisch) nicht einmal einen Funktionsaufrufmechanismus benötigen, selbst wenn es ist sehr bequem. Übrigens haben einige alte Befehlssatzarchitekturen (z. B. IBM / 370 ) nicht einmal einen Hardware-Aufrufstapel oder einen Push-Aufrufmaschinenbefehl (der IBM / 370 hatte nur einen Branch- und Link- Maschinenbefehl).

Wenn Ihr gesamtes Programm (einschließlich aller benötigten Bibliotheken) keine Rekursion aufweist, können Sie die Rücksprungadresse (und die "lokalen" Variablen, die tatsächlich statisch werden) jeder Funktion an statischen Positionen speichern. Alte Fortran77- Compiler haben dies in den frühen 1980er-Jahren getan (so dass die kompilierten Programme zu diesem Zeitpunkt keinen Aufrufstapel verwendeten).

Basile Starynkevitch
quelle
2
Es ist sehr fraglich, ob CPS keinen "Call Stack" hat. Es ist nicht auf dem Stack , der mystischen Region des gewöhnlichen RAM, die ein wenig Hardware-Unterstützung %espusw. bietet, aber es behält immer noch die entsprechende Buchhaltung auf einem passend benannten Spaghetti-Stack in einer anderen Region des RAM. Insbesondere die Absenderadresse ist in der Fortsetzung im Wesentlichen verschlüsselt. Und natürlich sind Fortsetzungen nicht schneller (und meiner Meinung nach war dies das Ziel von OP) als überhaupt keine Anrufe über Inlining zu tätigen .
Appels alte Papiere behaupteten (und demonstrierten mit Benchmarking), dass CPS so schnell sein kann wie ein Call-Stack.
Basile Starynkevitch
Ich bin skeptisch, aber trotzdem habe ich das nicht behauptet.
1
Tatsächlich war dies eine MIPS-Workstation aus den späten 1980er Jahren. Wahrscheinlich würde die Cache-Hierarchie auf aktuellen PCs die Leistung etwas verändern. Es gab mehrere Veröffentlichungen, in denen Appels Behauptungen analysiert wurden (und in der Tat könnte die
Stapelzuweisung
1
@ Gilles: Viele neuere ARM-Kerne wie der Cortex M0 und M3 (und wahrscheinlich auch andere wie der M4) unterstützen Hardware-Stapel für Dinge wie die Interrupt-Behandlung. Ferner enthält der Thumb-Befehlssatz eine begrenzte Untermenge der STRM / STRM-Befehle, die STRMDB R13 mit einer beliebigen Kombination von R0-R7 mit / ohne LR und LDRMIA R13 mit einer beliebigen Kombination von R0-R7 mit / ohne PC enthält, die effektiv behandelt R13 als Stapelzeiger.
Superkatze
8

Inlining (Ersetzen von Funktionsaufrufen durch äquivalente Funktionen) eignet sich gut als Optimierungsstrategie für kleine, einfache Funktionen. Der Overhead eines Funktionsaufrufs kann effektiv gegen eine kleine Strafe in der hinzugefügten Programmgröße (oder in einigen Fällen überhaupt keine Strafe) eingetauscht werden.

Große Funktionen, die wiederum andere Funktionen aufrufen, könnten jedoch zu einer enormen Explosion der Programmgröße führen, wenn alles inline wäre.

Der springende Punkt bei aufrufbaren Funktionen ist die Ermöglichung einer effizienten Wiederverwendung, nicht nur durch den Programmierer, sondern auch durch den Computer selbst. Dazu gehören Eigenschaften wie angemessener Arbeitsspeicher oder Platzbedarf auf der Festplatte.

Für das, was es wert ist: Sie können aufrufbare Funktionen ohne einen Aufrufstapel haben. Zum Beispiel: IBM System / 360. Bei der Programmierung in Sprachen wie FORTRAN auf dieser Hardware wird der Programmzähler (Rücksprungadresse) in einem kleinen Speicherbereich gespeichert, der unmittelbar vor dem Funktionseinstiegspunkt reserviert ist. Es ermöglicht wiederverwendbare Funktionen, erlaubt jedoch keine Rekursion oder Multithread-Code (ein Versuch eines rekursiven oder erneuten Aufrufs würde dazu führen, dass eine zuvor gespeicherte Rücksprungadresse überschrieben wird).

Wie in anderen Antworten erläutert, sind Stapel gute Dinge. Sie erleichtern Rekursions- und Multithread-Aufrufe. Während jeder Algorithmus, der zur Verwendung der Rekursion codiert wurde, ohne auf die Rekursion angewiesen zu sein, codiert werden könnte, ist das Ergebnis möglicherweise komplexer, schwieriger zu warten und möglicherweise weniger effizient. Ich bin nicht sicher, ob eine Architektur ohne Stack überhaupt Multithreading unterstützen könnte.

Zenilogix
quelle