Cheney auf dem MTA: Ein Compiler, in dem der Stack auch als Heap dient

 

Ist er jemals zurückgekehrt? Nein, er ist nie zurückgekehrt,

und sein Schicksal ist immer noch verlernt.

Er kann für immer durch die Straßen von Boston reiten.

Er ist der Mann, der nie zurückgekehrt ist.



"Charlie auf dem MTA", 1949

1. Verschlüsse

Eine der praktischen Funktionen moderner Programmiersprachen sind verschachtelte Funktionen:

def bubble(arr, comp):

    def swap(i, j):
        temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp

    flag = True
    while flag:
        flag = False
        for i in range(len(arr) - 1):
            if comp(arr[i], arr[i+1]) > 0:
                swap(i, i+1)
                flag = True

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Diese Möglichkeit selbst ist nicht neu: Sie war bereits in Algol (1958) und ist vielen aus Pascal (1970) bekannt. Das Kompilieren verschachtelter Funktionen ist einfach: Beispielsweise kann der Stapelrahmen der inneren Funktion einen Zeiger auf den Stapelrahmen der äußeren Funktion speichern, so dass die innere Funktion auf die Parameter und lokalen Variablen der äußeren Funktion zugreifen kann. Jemand kann sich daran erinnern, dass die Anweisungen enter



und leave



, die in 80186 (1982) erschienen sind, genau diese Art der Unterstützung für verschachtelte Funktionen implementieren (obwohl ich noch nie einen Compiler gesehen habe, der dies getan hat).



Schwierigkeiten beginnen, wenn die Sprache es Ihnen ermöglicht, eine interne Funktion außerhalb einer externen zu übertragen:

def by_field(name):

    def comp(x, y):
        return x[name] – y[name]

    return comp

bubble(my_records, by_field("year"))

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Wie kann die innere Funktion auf die Parameter und lokalen Variablen der äußeren zugreifen, nachdem die Rückkehr der äußeren Funktion ihren Stapelrahmen zerstört hat? Irgendwie muss die innere Funktion die verwendeten Variablen zusammen "greifen"; Eine Funktion zusammen mit extern erfassten Variablen wird als "Abschluss" bezeichnet. Pascal unterstützt dies nicht mehr; In C # 7 (2017) wird hierfür beispielsweise ein Objekt auf dem Heap erstellt, das alle Parameter und lokalen Variablen enthält, auf die sich die interne Funktion bezieht. und Aufrufe sowohl von ihm als auch von der externen Funktion gehen nicht zu den Werten auf dem Stapel, sondern zu den Feldern des Objekts auf dem Heap. Ist es möglich, auf diese Komplikation zu verzichten und weiter mit dem Stapel zu arbeiten, um unnötige indirekte Adressierung zu vermeiden und die Lokalität von Aufrufen zu erhalten, und den Datencache nicht mit Sprüngen im Heap zu verschmutzen?

2. Fortsetzung bestanden

Beim Kompilieren funktionaler Programmiersprachen, bei denen das Erfassen lokaler Variablen durch eine Rückgabefunktion eine weit verbreitete Technik ist, besteht der erste Schritt darin, das gesamte Programm in einen „Continuation-Passing-Style“ (CPS) zu übersetzen. Rückgaben von Funktionen werden durch einen expliziten Rückruf ersetzt, der als zusätzliches Argument an jede Funktion übergeben wird. Zum Beispiel in dieser einfachen Funktion, die das Produkt aller Primzahlen von 1 bis n



einschließlich berechnet :

def prodprimes(n):
    if n == 1:
        return 1
    elif isprime(n):
        return n * prodprimes(n-1)
    else:
        return prodprimes(n-1)

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

- prodprimes



Unterschiedliche Absenderadressen werden implizit an zwei Anrufe übertragen . Wenn diese Adressen als j



und bezeichnet h



sind und die Rücksprungadresse als explizites Argument übergeben wird c



, kann die gesamte Übertragung der Kontrolle explizit erfolgen:

def prodprimes(n, c):
    if n == 1:
        c(1)
    else:
        def k(b):
            if b:
                def j(p):
                    c(n * p)
                prodprimes(n-1, j)
            else:
                def h(q):
                    c(q)
                prodprimes(n-1, h)
        isprime(n, k)

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

In CPS gibt es keinen Unterschied zwischen dem Aufrufen einer Funktion und dem Zurückgeben eines Werts von einer Funktion. Beide werden als "Übergeben eines Werts an eine angegebene Adresse" abstrahiert. Diese Technik wurde in den meisten Scheme-Compilern seit dem ersten Mal (1975) verwendet. Ihm ist ein ganzes Buch "Compiling with Continuations" (1992) gewidmet, aus dem das obige Beispiel stammt. In jüngerer Zeit ist ein ähnlicher Programmierstil unter dem Namen „Versprechen“ populär geworden.



Der Grund, warum CPS intern von Compilern als Zwischendarstellung vor SSA verwendet wurde(erfunden 1988) ist populärer geworden - Einfachheit: Dies ist keine andere Sprache mit eigenen Regeln, sondern eine Subsprache des ursprünglichen PL mit der Einschränkung, dass ein Funktions- oder Fortsetzungsaufruf nur als letzter Funktions- oder Fortsetzungsoperator zulässig ist. Es ist einfach, PL-Code mit einer Reihe formaler Transformationen in CPS zu übersetzen, und es ist einfach, vereinfachende Transformationen auf CPS-Code anzuwenden. Stellen Sie beispielsweise fest, dass die Fortsetzung h



trivial ist, und ersetzen Sie die Verwendung h



durch c



. Ein wichtiges Merkmal von CPS ist für uns, dass Verschlüsse in demselben Bereich verwendet werden, in dem sie deklariert wurden, und daher auf von außen erfasste Variablen wie in 80186 zugreifen können - über Zeiger auf externe Stapelrahmen:

def by_field(name, c):

    def comp(x, y, c):
        c(x[name] – y[name])

    c(comp)

def by_year(comp):
    bubble(my_records, comp, halt)

by_field("year", by_year)

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Nach der Konvertierung in CPS comp



weiß es, dass es sich selbst um eine Verschachtelungsfunktion 2 handelt und der Wert name



im Verschachtelungsrahmen 1 liegt, sodass die Kompilierung des Aufrufs an name



keine Schwierigkeiten verursacht.



CPS hat jedoch einen Nachteil: Da Fortsetzungen niemals ausgeführt werden return



dann werden ihre Stapelrahmen niemals zerstört und der Stapel läuft sehr schnell über. Andererseits kann eine Fortsetzung einen bestimmten Stapelrahmen benötigen, entweder wenn sie sich selbst darauf bezieht oder wenn sie als Parameter eine Fortsetzung empfängt, die sich auf diesen Rahmen bezieht. Außerdem muss der Übergang zur nächsten Fortsetzung die letzte Aktion innerhalb der Fortsetzung sein, damit die Adresse und die Parameter der nächsten Fortsetzung als Ergebnis der Fortsetzung betrachtet werden können. (Das Modell "Versprechen" gibt dieses Ergebnis explizit zurück.) Die klassischen Schema-Compiler verwendeten einen Dispatcher als folgende Endlosschleife:

1. Führen Sie die aktuelle Fortsetzung aus und erhalten Sie als Ergebnis die Adresse und die Parameter der nächsten Fortsetzung.
2. Überprüfen Sie, auf welche Stapelrahmen durch die nächsten an sie übergebenen Fortsetzungs- und Fortsetzungsparameter zugegriffen werden kann.
3. , .

Bei dieser Implementierung wird der Systemaufrufstapel nicht verwendet, und Übergänge zwischen dem Dispatcher und den Fortsetzungen werden wie gewohnt implementiert jmp



. Fortsetzungsrahmen werden vom Aufrufstapel entkoppelt und in zufälliger Reihenfolge anstelle von LIFO zerstört , sodass ihre Sammlung sowohl als Stapel als auch als Heap betrachtet werden kann.



Wie Sie sich vorstellen können, ließ die Leistung des Programms bei einer Stapelprüfung für jeden Zweig zwischen der Fortsetzung zu wünschen übrig. Eine der möglichen Optimierungen besteht darin, die aktuelle Stapelgröße vor dem Verlassen der Fortsetzung zu überprüfen. Wenn sie den angegebenen Schwellenwert nicht überschreitet, fahren Sie direkt mit der nächsten Fortsetzung fort. Andernfalls übertragen Sie die Kontrolle an den Dispatcher, damit dieser den gesamten Müll vom Stapel sammelt. Bostoner Absolvent MIT Henry Baker kommentierte diesen Ansatz wie folgt: "Anstatt die ganze Zeit auf einem Trampolin zu hüpfen, springen wir vom Empire State Building - aber viel seltener."

3. Auf MTA

1948 erhöhte die Boston Metro (Metropolitan Transit Authority) die Tarife von 10 Cent auf 15 Cent. Anstatt alle Groschen zu ersetzen, wurden die Schaffner am Eingang der U-Bahn angewiesen, beim Verlassen des Zuges einen Aufschlag von fünf Cent zu erheben. Ein Kandidat für den Bürgermeister von Boston, der sich über diesen Ansatz lustig machte, bestellte eine Aufnahme eines Liedes über einen bestimmten Charlie, der nicht genug Geld hatte, um für einen Ausgang zu bezahlen, und er war dazu verdammt, endlos mit der U-Bahn zu fahren. Der Kandidat erlangte den Ruf eines Kommunisten, gewann nur 1,2% der Stimmen bei den Wahlen und verließ die Politik für immer; Das Lied über den Passagier, der nie wieder auf die Erdoberfläche zurückkehrt, erwies sich jedoch als weitaus beliebter: Selbst die 2006 eingeführte Bostoner U-Bahn-Karte heißt CharlieCard zu Ehren desselben Passagiers.



Charlies Geschichte inspirierte Henry Baker 1994 dazu, einen Scheme-Compiler zu schreiben, der jede Fortsetzung in eine C-Funktion verwandelt, so dass die Ausführung dieser Funktionen niemals erreicht wird return



: zum Beispiel:

(define (revappend old new)
  (if (null? old)
      new
      (revappend (cdr old) (cons (car old) new))))

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

- verwandelt sich in

void revappend(clos_type *cont, cons_type *old, cons_type *new) {
  if (old == NIL) {
    /* Call continuation with new as result. */
    return (cont->fn)(cont->env, new);
  }
  cons_type newer; /* Should check stack here. */
  /* Code for (revappend (cdr old) (cons (car old) new)). */
  newer.tag = cons_tag; newer.car = old->car; newer.cdr = new;
  return revappend(cont, old->cdr, &newer);
}

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Die Bedeutung des Operators return



nach einer solchen Konvertierung besteht darin, dem C-Compiler mitzuteilen, dass die Register nicht gespeichert werden müssen, bevor die Fortsetzung aufgerufen wird. Tatsächlich wird eine als Operand aufgerufene Funktion return



niemals zurückkehren. An der als gekennzeichneten Stelle /* Should check stack here. */



wird eine Stapelgrößenprüfung eingefügt, und bei Bedarf wird der Dispatcher zur Speicherbereinigung aufgerufen.



Dieser Ansatz hat gegenüber dem klassischen mehrere Vorteile:

1. Scheme : ; – , .. (varargs); – , .. (VLA). 21 . LLVM, .
2. ABI – , Scheme. «» , CPS, . «» callback- «» , , , «» – , . Scheme, map



fold
   
   
   
   , , .

Andererseits unterstützt C keine verschachtelten Funktionen, was bedeutet, dass alle Zeiger auf Variablen, die von außen erfasst werden, explizit zusammen mit dem Abschluss übergeben werden müssen. Darüber hinaus tritt beim Platzieren von Fortsetzungsrahmen auf dem Systemstapel anstelle eines selbstgeschriebenen Rahmens eine Schwierigkeit auf: Wie wird die Speicherbereinigung für den Systemstapel implementiert, der nicht an das Gerät eines bestimmten C-Compilers in einer bestimmten Architektur gebunden ist?

4. Cheneys Müllsammler

Der allererste und einfachste Garbage Collector wurde 1969 für LISP implementiert: Als eine Hälfte des Heaps voll war, wurde das Programm gestoppt und alle "Live" -Daten wurden rekursiv (Tiefen-First-Traversal) in die zweite Hälfte des Heaps übertragen. 1970 bemerkte Chris Cheney - ebenfalls in Cambridge, aber auf der anderen Seite des Ozeans vom MIT -, dass der Sammler selbst beim Durchlaufen von Live-Daten in der Breite keinen zusätzlichen Speicher während des Builds benötigen würde. Seitdem wird die Speicherbereinigung mit dem Stoppen des Programms und dem Verschieben von Live-Objekten in die zweite Hälfte des Heaps als "Cheney-Algorithmus" bezeichnet. Der Hauptnachteil besteht darin, dass Live-Daten nur die Hälfte des verfügbaren Speichers belegen können und die zweite Hälfte von einem "Puffer zum Kopieren" belegt wird.



Die Effizienz der Speicherbereinigung kann verbessert werden, indem beobachtet wird, dass die Daten in einem typischen Programm in "sehr kurzlebig" und "sehr langlebig" unterteilt sind: Wenn ein Objekt eine Speicherbereinigung überlebt hat, ist es sehr wahrscheinlich, dass es die nächste überlebt Sammlung auch. Daher ist der Haufen in einen "Kindergarten" für neu erstellte Objekte und einen "Erwachsenenhaufen" aus zwei Hälften unterteilt. Wenn der Kindergarten voll ist, werden Live-Daten von ihm auf den Erwachsenenhaufen übertragen. Wenn eine Hälfte des erwachsenen Haufens überläuft, werden Live-Daten von diesem auf die andere Hälfte übertragen. Dies spart sowohl Speicher (in der zweiten Hälfte des Heapspeichers ist kein Speicherplatz für kurzlebige Daten reserviert) als auch Erstellungszeit (langlebige Daten werden nicht bei jeder Speicherbereinigung im Kindergarten hin und her kopiert).



Bei Verwendung von „Cheney on the MTA“ fungiert der Stapel als Cattery. Der beim Stapelüberlauf aufgerufene Dispatcher empfängt explizit als Parameter Zeiger auf alle Live-Daten: Dies sind alle Parameter und lokalen Variablen der aufrufenden Fortsetzung, einschließlich der erfassten Variablen, die als impliziter Parameter an die Fortsetzung übergeben werden. Im Gegensatz zu herkömmlichen Garbage Collectors muss Cheney auf dem MTA nicht nach Live-Daten im Stapel suchen: CPS stellt sicher, dass alle Daten unter dem letzten Stapelrahmen tot sind, wenn sie nicht aus dem letzten Rahmen verfügbar sind. Dies bedeutet, dass sich der Garbage Collector weder um die Struktur der Stapelrahmen noch um das mögliche Vorhandensein von "fremden" Rahmen im Stapel kümmert, die von Funktionen in anderen Sprachen übrig geblieben sind.







Der Ansatz „Cheney on the MTA“ wird in den C-Schema-Compilern „Chicken Scheme“ (2000) und „Cyclone Scheme“ (2016) verwendet. In Cyclone wurde Bakers langjähriger Idee die Unterstützung für die parallele Speicherbereinigung hinzugefügt, wenn nur ein Thread während der Erfassung gestoppt wird, dessen Stapel verarbeitet wird, und der Rest weiterhin funktioniert.