[erlang] : Warum ist tail recursion so viel effizienter als normale Rekursion was den Speicherverbrauch angeht?

[erkurz]

mngbd schrieb:

Etwa so:

int tail_fact(int n, int acc)
{
anfang:
    if (n == 0)
        return acc;
    else
    {
        // und jetzt entweder ein tail call
        return tail_fact(n - 1, n * acc);
        // oder ein goto:
        acc = n * acc;
        n = n - 1;
        goto anfang;
    }
}

Editier, editier, ...: aber jetzt stimmts.

Du hast doch in dem Beispiel im Kommentar selber geschrieben "oder ein goto". Klar, goto ist effizient, da iteriert man einfach drüber. Aber "return tail_fact(n - 1, n * acc);" bleibt doch dennoch ein rekursiver aufruf, zudem einer bei dem zwei sachen zwischengespeichert werden müssen: n & acc.

[erkurz]

mngbd schrieb:

erkurz schrieb:

Oder muss ich mich wirklich damit abfinden, dass der erlang interpreter bei tail recursion intern ein goto draus macht?

Ja. Der macht das, weil er's kann. Damit fallen auch alle Stackframes bis auf den ersten weg. Und wahrscheinlich nicht nur bei tail recursions, sondern bei allen tail calls.

Hmm okay, das Umdenken ist dann bisschen doof für mich.

[mngbd]

erkurz schrieb:

Hmm okay, das Umdenken ist dann bisschen doof für mich.

Aber wohl auch nur, weil die meisten C(++)-Compiler solche naheliegenden Optimierungen nicht machen.

erkurz schrieb:

Aber "return tail_fact(n - 1, n * acc);" bleibt doch dennoch ein rekursiver aufruf, zudem einer bei dem zwei sachen zwischengespeichert werden müssen: n & acc.

Ja, klar. Aber vergleich das mal mit den 100 Stackframes, die du brauchst, um 100! mit der ersten Variante zu berechnen.

[Gast]

mngbd schrieb:

erkurz schrieb:

Hmm okay, das Umdenken ist dann bisschen doof für mich.

Aber wohl auch nur, weil die meisten C(++)-Compiler solche naheliegenden Optimierungen nicht machen.

Huch? Ist das so? Der gcc hat bei mir iirc immer tail-recursions wegoptimiert. Nicht dass ich ihn extra daraufhin getestet hätte.

[mngbd]

Tim schrieb:

Huch? Ist das so? Der gcc hat bei mir iirc immer tail-recursions wegoptimiert. Nicht dass ich ihn extra daraufhin getestet hätte.

Ich schätze, dass der das macht, wenn er das behauptet. Ich hab zwar dunkel in Erinnerung, dass er es auf irgendeiner Plattform behauptet, doch nicht gemacht hat, aber egal. Was mir viel mehr auf die Nerven geht, ist dass man sowas einfach in den C-Standard schreiben könnte. Sonst will es doch kaum jemand verwenden. Aber dann wäre ja der heilige Compiler ein wenig aufwendiger.

[nman]

mngbd schrieb:

Was mir viel mehr auf die Nerven geht, ist dass man sowas einfach in den C-Standard schreiben könnte. Sonst will es doch kaum jemand verwenden.

Hm? Common-Lisp-Compiler müssen IIRC Tail Calls laut Standard auch nicht optimieren und trotzdem tut das praktisch jeder Compiler und Commmon-Lisper verwenden es sehr oft und gerne.

[nman]

Ach ja, zum Thema: Ich fand das Paper von Guy Steele zum Thema sehr erhellend:
Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO (Achtung, eingescanntes Uralt-Paper, aber sehr interessant und aufschlussreich.)

[mngbd]

nman schrieb:

Hm? Common-Lisp-Compiler müssen IIRC Tail Calls laut Standard auch nicht optimieren und trotzdem tut das praktisch jeder Compiler und Commmon-Lisper verwenden es sehr oft und gerne.

Ist ja auch ein grundvernünftiges Feature. Trotzdem müssen sie unter Umständen dazusagen, dass sie sich darauf verlassen haben; und im schlimmsten Fall müsste man den Code dann umschreiben, um ihn mit einer anderen Sprach-Implementation zu verwenden, obwohl sie standardkonform ist.

Da fragt man sich, warum das eigentlich nicht wie in Scheme oder Lua oder ... vorgeschrieben ist. Scheinbar sind proper tail calls erst so richtig in Mode gekommen, nachdem der letzte CL-Standard verabschiedet wurde.

[hustbaer]

mngbd schrieb:

Was mir viel mehr auf die Nerven geht, ist dass man sowas einfach in den C-Standard schreiben könnte. Sonst will es doch kaum jemand verwenden. Aber dann wäre ja der heilige Compiler ein wenig aufwendiger.

C++ Compiler sind schon aufwendig genug, und da willst du noch sowas verlagnen?

Klar könnte man es in den Standard schreiben, wie viele andere Dinge auch. Nur was nützt es? Auch ohne zusätzliche Auflagen im Standard gibt es keinen einzigen standard-konformen C++ Compiler. Soll heissen: es würde dir garnix bringen, da es einfach nicht jeder C++ Compiler implementieren würde. Auch wenn es im Standard steht.

[mngbd]

hustbaer schrieb:

C++ Compiler sind schon aufwendig genug, und da willst du noch sowas verlagnen?

Weil es die Stärke der Sprache erhöht, ohne irgendeine Änderung an der Syntax und der Semantik. Aber ich hab da eher an C gedacht.

AIM 353 ist zu dem Thema vielleicht auch lesenswert.

[Gast]

mngbd schrieb:

Aber ich hab da eher an C gedacht.

Es ist halt einfach nicht so schick in C. In C schreibt man die Enrekursion halt gleich als Iteration. Wie sich das entwickelt hätte wenn man solche Optimierungen von Anfang an drin gehabt hätte mag ich nicht beurteilen, aber heute ist da der Zug schon mehrfach abgefahren.

[rüdiger]

Tim schrieb:

mngbd schrieb:

erkurz schrieb:

Hmm okay, das Umdenken ist dann bisschen doof für mich.

Aber wohl auch nur, weil die meisten C(++)-Compiler solche naheliegenden Optimierungen nicht machen.

Huch? Ist das so? Der gcc hat bei mir iirc immer tail-recursions wegoptimiert. Nicht dass ich ihn extra daraufhin getestet hätte.

Wobei der GCC da wohl ein Experte ist. Andere Compiler (icc, suncc, msvc) machen das wohl nicht: http://dl.fefe.de/optimizer-isec.pdf (s.32)

[rapso]

rüdiger schrieb:

Tim schrieb:

mngbd schrieb:

erkurz schrieb:

Hmm okay, das Umdenken ist dann bisschen doof für mich.

Aber wohl auch nur, weil die meisten C(++)-Compiler solche naheliegenden Optimierungen nicht machen.

Huch? Ist das so? Der gcc hat bei mir iirc immer tail-recursions wegoptimiert. Nicht dass ich ihn extra daraufhin getestet hätte.

Wobei der GCC da wohl ein Experte ist. Andere Compiler (icc, suncc, msvc) machen das wohl nicht: http://dl.fefe.de/optimizer-isec.pdf (s.32)

mein VC macht das seit version 6 (anno 1999).
Es gibt aber bei jedem compiler bedingungen unter welchen er das macht, genau wie mit (N)RVO.
Wenn man sichergehen will dass das gemacht wird, bleibt nichts anderes als ins disassembly zu schauen.

[Gast]

rüdiger schrieb:

Tim schrieb:

mngbd schrieb:

erkurz schrieb:

Hmm okay, das Umdenken ist dann bisschen doof für mich.

Aber wohl auch nur, weil die meisten C(++)-Compiler solche naheliegenden Optimierungen nicht machen.

Huch? Ist das so? Der gcc hat bei mir iirc immer tail-recursions wegoptimiert. Nicht dass ich ihn extra daraufhin getestet hätte.

Wobei der GCC da wohl ein Experte ist. Andere Compiler (icc, suncc, msvc) machen das wohl nicht: http://dl.fefe.de/optimizer-isec.pdf (s.32)

Ist das überhaupt richtig tail-recursive?

[knivil]

Tim schrieb:

Ist das überhaupt richtig tail-recursive?

Hmm, ich weiss auch nicht, was er mit der Folie sagen will. Die Fakultaetsfunktion ist nicht Endrekursiv (tail recursiv).

[Gast]

Da kam der CCC in ihm durch und musste freie Software lobhudeln

[Bashar]

Als Laie würde ich mal sagen, da steckt entweder ziemlich viel Magie in der gcc-Opti, oder sie haben eine spezielle Transformation für genau dieses Muster.

[µngbd]

rapso schrieb:

Wenn man sichergehen will dass das gemacht wird, bleibt nichts anderes als ins disassembly zu schauen.

Zumindest die glibc kann das bis zur Laufzeit transparent halten:
http://www.gnu.org/s/libc/manual/html_node/Backtraces.html

Bashar schrieb:

Als Laie würde ich mal sagen, da steckt entweder ziemlich viel Magie in der gcc-Opti, oder sie haben eine spezielle Transformation für genau dieses Muster.

Zumindest das Muster "Rekursion modulo primitive Operation, die keinen neuen Speicher anfordert" müsste man eigentlich immer in einen tail call + Akkumulator verwandeln können, oder?

[mngbd]

µngbd schrieb:

Zumindest das Muster "Rekursion modulo primitive Operation, die keinen neuen Speicher anfordert" müsste man eigentlich immer in einen tail call + Akkumulator verwandeln können, oder?

Bin auch Laie, aber das geht scheinbar wirklich so einfach. Unter den Einschränkungen, dass der Körper aus einem einzelnen if besteht, dass der Rekursionsabbruch im then-Teil ist, und dass nur das erste Argument bei der Rekursion verändert wird, geht das in Scheme zB so:

(define (rec->tail fun-def)
  (let ((name (caadr fun-def))
        (first-arg (cadadr fun-def))
        (rest-args (cddadr fun-def))
        (if-expr (caddr fun-def)))
    (let ((test (cadr if-expr))
          (then-part (caddr if-expr))
          (else-part (cadddr if-expr)))
      (let ((operation (car else-part))
            (first-operand (cadr else-part))
            (new-arg (car (cdaddr else-part))))
        `(define ,(cons name (cons first-arg rest-args))
           (define (tail-rec ,first-arg acc)
             (if ,test
                 acc
                 (tail-rec ,new-arg (,operation ,first-operand acc))))
           (tail-rec ,first-arg ,then-part))))))

Das geht natürlich mit der Fakultät:

> (rec->tail '(define (fact n)
                (if (zero? n)
                    1
                    (* n (fact (- n 1))))))
(define (fact n)
  (define (tail-rec n acc) (if (zero? n) acc (tail-rec (- n 1) (* n acc))))
  (tail-rec n 1))

Aber auch mit exotischeren Dingen, solange nur das erste Argument verändert wird:

> (rec->tail '(define (fold lst proc init)
                (if (null? lst)
                    init
                    (proc (car lst)
                          (fold (cdr lst) proc init)))))
(define (fold lst proc init)
  (define (tail-rec lst acc)
    (if (null? lst) acc (tail-rec (cdr lst) (proc (car lst) acc))))
  (tail-rec lst init))

;; die beiden fold-Versionen reagieren gleich, zB:
(fold '(1 2 3 4) + 0)
(fold '(1 2 3 4) cons '())

Heureka.

[knivil]

Man kann jede Rekursion in eine Endrekursion mittels Continuation ueberfuehren. Manchmal geht es aber nicht immer mit einem einfachen Akkumulator, sondern man tauscht Stack gegen Heap.