Wie inline mit Rekursion verwenden?

Question

Von Programming Language Pragmatics, by Scott, in Bezug auf in-Futter und Rekursion:

In-line Erweiterung ist auch keine Option im allgemeinen Fall für rekursive Unterprogramme. Für den gelegentlichen Fall, in dem ein rekursiver -Aufruf möglich, aber unwahrscheinlich ist, kann es wünschenswert sein, eine echte rekursive Unterroutine zu erzeugen, aber zu eine Ebene dieser Routine inline an jeder Aufrufstelle zu erweitern.

Betrachten Sie als einfaches Beispiel einen Binärbaum, dessen Blätter Zeichenfolgen enthalten. Eine Routine den Rand dieses Baumes zurückzukehren (die von links nach rechts Verkettung der Werte in den Blättern) wie dies in C aussehen könnte ++:

string fringe(bin_tree *t) { 
    // assume both children are nil or neither is 
    if (t->left == 0) return t->val; 
    return fringe(t->left) + fringe(t->right); 
} 

Ein Compiler diesen Code in-line erweitern wenn es jeden verschachtelten Aufruf zu einem echten Unterroutinenaufruf macht. Da die Hälfte der Knoten in einem binären Baum Blätter sind, wird diese Erweiterung die Hälfte der dynamischen Aufrufe zur Laufzeit eliminieren.

Wenn wir nicht nur die Wurzel Anrufe erweitern sondern auch (eine Ebene) die beiden Anrufe innerhalb des wahren Unterprogramm Version, nur ein Viertel der ursprünglichen dynamischen Anrufe bleiben.

Ich habe Probleme, die folgenden Sätze zu verstehen:

• "erweitern einer Ebene dieser Routine in-line bei jedem Anruf Ort"
• „diesen Code in-line erweitern, wenn es jeder macht verschachtelter Aufruf ein wahrer Unterprogrammaufruf. "
• „erweitern nicht nur die Wurzel Anrufe, sondern auch (eine Ebene) die beiden Anrufe innerhalb der wahren Unterprogramm-Version“

Was eigentlich bedeuten sie? Könntest du sie mit dem gegebenen Beispiel erklären, zum Beispiel zeigen, wie der Code nach der Handlung jedes Satzes ist?

Danke.

Answer 1

Einige Compiler können ganz verschachtelte rekursive Aufrufe erweitern und inline einbinden.

Zum Beispiel der folgende Code (wo ich das inline Schlüsselwort nicht!):

static int fact(int n) { 
    if (n<=1) return 1; 
    else return n* fact(n-1); 
} 

extern "C" int f5(); 
int f5() { 
    return fact(5); 
}  

kompiliert wird (mit g++ -O2 -fverbose-asm -S) von GCC 7.2 (Unter Linux/Debian/Sid auf x86-64) in eine einfache Funktion der Rückkehr 120:

  .text 
     .p2align 4,,15 
     .globl f5 
     .type f5, @function 
f5: 
.LFB1: 
     .cfi_startproc 
# e.cc:10: }; 
     movl $120, %eax  #, 
     ret 
     .cfi_endproc 
.LFE1: 
     .size f5, .-f5 
     .ident "GCC: (Debian 7.2.0-1) 7.2.0" 
     .section  .note.GNU-stack,"",@progbits 

Beachten Sie, dass fact in dem erzeugten Assembler-Code wurde vollständig inlined und erscheinen nicht.

"bei jedem Aufruf Website eine Ebene dieser Routine in-line erweitern"

Das würde bedeuten, dass f5 in das Äquivalent von zusammengestellt worden wäre

int f5() { return 5*fact(4); } 

mit fact erscheinen im generierten Code und kompiliert in eine rekursive (Maschinencode) Funktion (den Call-Stack konsumierend).

Answer 2

Bei weitem der einfachste Weg, dies zu verstehen, ist, inlining als eine alternative binäre Darstellung zu erstellen. Z.B. Neben der Erstellung der grundlegenden string fringe(bin_tree *t), kann der Compiler auch entscheiden, string fringe__inlined(bin_tree *t) zu erstellen. Und in fringe__inlined wird die tatsächliche Inlinefunktion (en) eine oder zwei Kopien von fringe sein.

Es wäre sogar möglich, eine fringe__inlined__inlined auf diese Weise (zwei Ebenen, wie erwähnt) zu erstellen.

Answer 3

Können Sie sie mit dem gegebenen Beispiel erklären, zum Beispiel zeigen, was der Code wie

ist

Hinweis: Der Compiler/Optimierer nicht diese Aktionen auf dem C++ Code tut, die Sie schreiben, aber auf einer internen Darstellung. Es ist möglich, die Idee mit C++ zu demonstrieren, aber aufgrund von Syntax- und Lesbarkeitsproblemen müssen wir möglicherweise zusätzliche Änderungen wie temporäre Variablen einführen.

Erweitern Sie eine Ebene dieser Routine inline bei jeder Aufrufstelle.

result = fringe(t); 

wird

if (t->left == 0) result = t->val; 
else result = fringe(t->left) + fringe(t->right); 

erweitern nicht nur die Anrufe Wurzel, sondern auch (eine Ebene) die beiden Anrufe innerhalb des wahren Unterprogramm Version

if (t->left == 0) result = t->val; 
else { 
    string left, right; 

    // one level of expansion for left subtree 
    if (t->left->left == 0) left = t->left->val; 
    else left = fringe(t->left->left) + fringe(t->left->right); 

    // one level of expansion for right subtree 
    if (t->right->left == 0) right = t->right->val; 
    else right = fringe(t->right->left) + fringe(t->right->right); 

    result = left + right; 
}