Clever Geek Handbook

MTAのCheney：スタックがヒープとしても機能するコンパイラ

 

彼は戻ったことがありますか？いいえ、彼は二度と戻ってこなかった、

そして彼の運命はまだ学ばれていない

、

彼はボストンの通りの下で永遠に乗ることができる、 彼は 二度と戻ってこなかった男だ。



「MTAのチャーリー」、1949年


1.閉鎖



最新のプログラミング言語の便利な機能の1つは、ネストされた関数です： 



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


この可能性自体は新しいものではありません。すでにAlgol（1958）にあり、Pascal（1970）の多くの人によく知られています。ネストされた関数のコンパイルは簡単です。たとえば、内部関数のスタックフレームは、外部関数のスタックフレームへのポインタを格納できるため、内部関数は外部関数のパラメータとローカル変数にアクセスできます。誰かが、80186（1982）に登場した命令enter



と leave



がネストされた関数のまさにこの種のサポートを実装していることを思い出すかもしれ ません（私はそれを行ったコンパイラを見たことがありませんが）。



言語で内部関数を外部関数の外部に転送できる場合、問題が発生します。 



def by_field(name):

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

    return comp

bubble(my_records, by_field("year"))


外部関数からの戻りがスタックフレームを破壊した後、内部関数はどのようにして外部のパラメータとローカル変数にアクセスできますか？どういうわけか、内部関数は使用された変数を一緒に「つかむ」必要があります。外部でキャプチャされた変数とともに関数は「クロージャ」と呼ばれます。Pascalはこれをサポートしなくなりました。 ただし、たとえば、C＃7（2017）では、このために、内部関数が参照するすべてのパラメーターとローカル変数を含むオブジェクトがヒープ上に作成されます。そして、それと外部関数の両方からの呼び出しは、スタック上の値ではなく、ヒープ上のオブジェクトのフィールドに行きます。この複雑さを伴わずに、スタックでの作業を継続することは可能ですか？不要な間接アドレス指定を回避し、呼び出しの局所性を維持し、ヒープ内のジャンプでデータキャッシュを散らかさないようにしますか？



2.継続渡し



関数型プログラミング言語をコンパイルする場合、戻り関数によるローカル変数のキャプチャは非常に一般的な手法ですが、最初のステップは、プログラム全体を「継続渡しスタイル」（CPS）に変換することです。関数からの戻り値は、追加の引数として各関数に渡される明示的なコールバックに置き換えられます。たとえば、1からn



両端までのすべての素数の積を計算するこの単純な関数では、次のようになります 。 



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


-prodprimes



異なるリターンアドレスが暗黙的に2つの呼び出しに転送されます 。これらのアドレスがj



および として指定され h



、戻りアドレスが明示的な引数として渡される場合 c



、制御の転送全体を明示的にすることができます。 



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)


CPSでは、関数を呼び出すことと関数から値を返すことの間に違いはありません。どちらも「指定されたアドレスに値を渡す」として抽象化されます。この手法は、最初（1975年）からほとんどのSchemeコンパイラで使用されています。 「CompilingwithContinuations」（1992年）の本全体が彼に捧げられており、そこから上記の例が取り上げられています。最近では、同様のスタイルのプログラミングが「promises」という名前で普及しています。



CPSがSSAの前の中間表現としてコンパイラーによって内部的に使用された理由 （1988年に発明された）より一般的になりました-単純さ：これは独自のルールを持つ別の言語ではなく、関数または継続呼び出しが最後の関数または継続演算子としてのみ許可されるという制限付きの元のPLのサブ言語です。一連の正式な変換を使用してPLコードをCPSに変換するのは簡単です。また、単純化された変換をCPSコードに適用するのも簡単です。たとえば、継続がh



簡単であることがわかり 、使用法h



をに 置き換えます c



。私たちにとってのCPSの重要な機能は、クロージャが宣言されたのと同じスコープで使用されるため、外部スタックフレームへのポインタを介して、80186と同じ方法で外部からキャプチャされた変数にアクセスできることです。 



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)


CPScomp



に変換した後 、それ自体が入れ子関数2であり、値name



が入れ子フレーム1にあることがわかる ため、への呼び出しをコンパイルして name



も問題は発生しません。



ただし、CPSには欠点があります。継続が実行されないためです。 return



そうすれば、スタックフレームが破壊されることはなく、スタックはすぐにオーバーフローします。一方、継続は、それ自体がそれを参照する場合、またはパラメーターとしてこのフレームを参照する継続を受け取る場合、特定のスタックフレームを必要とする場合があります。さらに、次の継続への移行は、継続内の最後のアクションである必要があります。これにより、次の継続のアドレスとパラメーターは、継続の結果と見なすことができます。（「promises」モデルはこの結果を明示的に返します。）従来のSchemeコンパイラーは、ディスパッチャーを次の無限ループとして使用していました。



  1. 現在の継続を実行し、結果として次の継続のアドレスとパラメーターを取得します。
  2. 渡された次の継続および継続パラメーターによってアクセスできるスタックフレームを確認します。
  3. , .


この実装では、システムコールスタックは使用されず、ディスパッチャと継続の間の遷移は通常どおり実装されます jmp



。継続フレームは、呼び出しスタックから切り離され、LIFOの代わりにランダムな順序で破棄される ため、それらのコレクションは、ヒープとしてだけでなくスタックとしても見なすことができます。



ご想像のとおり、継続間のすべてのブランチでスタックチェックを行うと、プログラムのパフォーマンスには多くの要望が残されました。可能な最適化の1つは、継続を終了する前に現在のスタックサイズを確認し、指定されたしきい値を超えていない場合は、次の継続に直接進むことです。それ以外の場合は、制御をディスパッチャに移して、スタックからすべてのガベージを収集します。ボストン卒業生 MITヘンリーベイカーはこのアプローチについて次のようにコメントしています。「トランポリンで常に跳ね返る代わりに、エンパイアステートビルから飛び降りますが、それほど頻繁ではありません。」



3.MTAについて



1948年、ボストンメトロ（メトロポリタントランジットオーソリティ）は運賃を10セントから15セントに引き上げました。すべての10セント硬貨を交換する代わりに、地下鉄の入り口で、車掌は列車を出るときに5セントの追加料金を請求するように指示されました。このアプローチをからかって、ボストン市長の候補者は、出口を支払うのに十分なペニ​​ーを持っていなかったあるチャーリーについての歌の録音を注文しました、そして彼は延々と地下鉄に乗る運命にありました。候補者は共産主義者としての評判を獲得し、選挙で投票の1.2％しか獲得せず、政治を永遠に去りました。しかし、地球の表面に二度と戻らない乗客についての歌は、はるかに人気があることが判明しました。2006年に導入されたボストンの地下鉄カードでさえ、同じ乗客に敬意を表してチャーリーカードと呼ばれています。



チャーリーの話は、ヘンリー・ベイカーが1994年に、すべての継続をC関数に変換して、それらの関数の実行が決して到達しないようにするSchemeコンパイラーを作成するように促しました return



。 



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


- になる 



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);
}


このreturn



ような変換後の演算子の意味は 、継続を呼び出す前にレジスターを保存する必要がないことをCコンパイラーに伝えることです。実際、オペランドとして呼び出された関数 return



は決して戻りません。とマークされた場所に /* Should check stack here. */



スタックサイズチェックが挿入され、必要に応じてディスパッチャがガベージコレクションのために呼び出されます。



このアプローチには、従来のアプローチに比べていくつかの利点があります。



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



    fold



    , , .


一方、Cはネストされた関数をサポートしていません。つまり、外部からキャプチャされた変数へのすべてのポインタは、クロージャとともに明示的に渡される必要があります。さらに、継続フレームを自作フレームではなくシステムスタックに配置すると、問題が発生します。特定のアーキテクチャ上の特定のCコンパイラのデバイスに関連付けられていないシステムスタックのガベージコレクションを実装する方法は？



4.チェイニーのガベージコレクター



1969年にLISP用に最初で最も単純なガベージコレクターが実装されました。ヒープの半分がいっぱいになると、プログラムが停止し、すべての「ライブ」データが再帰的に（深さ優先トラバーサル）ヒープの後半に転送されました。 1970年、同じくケンブリッジにあるがMITから海の反対側にあるChris Cheneyは、ライブデータを幅広くトラバースすることで、コレクター自体がビルド中に追加のメモリを必要としないことに気づきました。それ以来、プログラムを停止し、ライブオブジェクトをヒープの後半に移動するガベージコレクションは、「チェイニーアルゴリズム」と呼ばれています。その主な欠点は、ライブデータが使用可能なメモリの半分しか占有できず、残りの半分が「コピー用のバッファ」によって占有されることです。



一般的なプログラムのデータが「非常に短命」と「非常に長命」に分けられることを観察することで、ガベージコレクションの効率を向上させることができます。オブジェクトが1つのガベージコレクションを生き残った場合、次のガベージコレクションを生き残る可能性が非常に高くなります。コレクションも。したがって、ヒープは、新しく作成されたオブジェクトの「ナーサリー」と、2つの半分の「アダルトヒープ」に分けられます。苗床がいっぱいになると、苗床からのライブデータが大人のヒープに転送されます。アダルトヒープの半分がオーバーフローすると、そこからのライブデータが残りの半分に引き継がれます。これにより、メモリ（ヒープの後半で短期間のデータ用にスペースが予約されていない）とビルド時間（長期のデータがナーサリの各ガベージコレクションで前後にコピーされない）の両方が節約されます。



「MTAのチェイニー」を使用する場合、スタックはキャッテリーとして機能します。スタックオーバーフローで呼び出されたディスパッチャは、すべてのライブデータへのポインタをパラメータとして明示的に受け取ります。これらは、暗黙のパラメータとして継続に渡されるキャプチャされた変数を含む、呼び出し継続のすべてのパラメータとローカル変数です。従来のガベージコレクターとは異なり、MTAのCheneyは、スタック内のライブデータを探す必要はありません。CPSは、最後のフレームから利用できない場合、最後のスタックフレームより下のすべてのデータがデッドであることを保証します。これは、ガベージコレクターがスタックフレームの構造や、他の言語の関数から残されたスタック内の「外部」フレームの存在の可能性を気にしないことを意味します。







「Cheneyonthe MTA」アプローチは、Cスキームコンパイラの「ChickenScheme」（2000）および「CycloneScheme」（2016）で使用されています。Cycloneでは、Bakerの長年の考えに、スタックが処理されている収集中に1つのスレッドのみが停止され、残りは引き続き機能する並列ガベージコレクションのサポートが追加されました。





More articles:


All Articles