L-Closureの呼び出しコストの削減

IPSJ

Bibliographic Information

Other Title
  • Reducing Invocation Costs of L-Closures

Search this article

Abstract

本論文ではL-closureという言語機構に関して2つの実装を提案する．1つは複数回同じL-closureが呼び出された場合などの呼び出しコストの削減，もう1つはGNU Cコンパイラ（GCC）4系列への元々呼び出しコストの低いclosureの実装である．L-closureは入れ子関数定義を評価すると生成される軽量レキシカルクロージャで，これを持つ拡張C言語を，高水準言語コンパイラの中間言語として採用することで，ごみ集めなどの高水準サービスを効率良く実装できる．現在L-closureの実装として，GCC 3系列の拡張によるコンパイラ実装と標準C言語への翻訳による実装があり，これらはL-closureの初期化処理を遅延したり，低い維持コスト（アクセスされる変数のレジスタ割当て）を実現しているが，呼び出しコストは高い．翻訳による実装では，Cのスタックとは別のスタック（明示的スタック）を用意し，L-closure呼び出し時にCのスタックの内容を明示的スタックへ一時的に移すことで，入れ子関数を持つ関数の局所変数へのアクセスを実現していた．本研究では，L-closureからのリターンの後，Cスタック全体を再構築するのではなく，フレームごとに再構築することで，再度L-closureが呼び出されたときのスタック間の値の移動を減らし，呼び出しコストを削減する．L-closureの研究の一環として，生成/維持コストはかかるものの呼び出しコストが低いclosureも提案してきた．本研究ではまた，高度な最適化のために内部構造が刷新されたGCC 4系列において，これを実装したので報告する．

This paper proposes two new implementations for a language mechanism called “L-closures.” First, we reduce the invocation costs of L-closures especially when an L-closure is called multiple times. Second, we implement an associated language mechanism called “closures” with inherently low invocation costs in GNU C Compiler (GCC) version 4. L-closures are lightweight lexical closures created by evaluating nested function definitions. By using intermediate languages extended with L-closures in high-level compilers, we can implement high-level services such as garbage collection efficiently. As existing implementations of L-closures, we have a compiler-based implementation as an enhanced GCC version 3, and a transformation-based implementation as a translator into standard C. In these existing implementations, the initialization of an L-closure is delayed until the L-closure is actually invoked, and low maintenance costs of L-closures (register allocation for accessed variables) are realized; however, we accept high invocation costs. In the existing translator, we enable L-closures to access local variables of the enclosing function, by preparing an explicit stack in C other than the C (execution) stack and by temporarily moving contents of the C stack into the explicit stack upon every invocation of an L-closure. In the first new implementation of this study, we reduce invocation costs by restoring the C stack frame by frame rather than restoring the entire C stack after returning from the L-closure, so that we can eliminate value movements between the stacks upon the subsequent invocations of the L-closure. In our study of L-closures, we have proposed “closures” to enable low invocation costs by accepting moderate initialization/maintenance costs. In this study, we also report the second new implementation, in which we implement closures in GCC version 4 whose internal structure has been reformed for advanced optimizations.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top