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

• Item type: Trans(1)
• 公開日: 2013-08-29
• タイトル: L-Closureの呼び出しコストの削減
• タイトル / 言語: en
• タイトル: Reducing Invocation Costs of L-Closures
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [通常論文] 入れ子関数，L-closures，実行スタック，コンパイラ，トランスレータ
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 京都大学大学院情報学研究科／現在，楽天株式会社情報技術部
• 著者所属: 九州工業大学大学院情報工学研究院
• 著者所属: 京都大学学術情報メディアセンター
• 著者所属: 京都大学大学院情報学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University / Presently with IT Department, Rakuten, Inc.
• 著者所属(英): en
• 著者所属(英): Department of Artificial Intelligence, Kyushu Institute of Technology
• 著者所属(英): en
• 著者所属(英): Academic Center for Computing and Media Studies, Kyoto University
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者名: 田附, 正充; 八杉, 昌宏; 平石, 拓; 馬谷, 誠二
• 著者名(英): Masami, Tazuke; Masahiro, Yasugi; Tasuku, Hiraishi; Seiji, Umatani
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では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系列において，これを実装したので報告する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 6, 号 2, p. 13-32, 発行日 2013-08-29
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会