著者

内山 雄司 脇田 建

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.43, no.1, pp.10-24, 2002-01-15

参考文献数

19

被引用文献数

1

---

メモリ管理機能のモジュラーかつ効率的な実装手法を提案する.言語処理系の実装においてメモリ管理機能をモジュラーな設計とすることは,既存の処理系に新たなメモリ管理アルゴリズムを実装することを容易にする点で有用である.まず,メモリ管理機能のモジュラーな実装を可能とするために,本研究では,実行時システムとメモリ管理機能との間に抽象的なインタフェースを定義する.このインタフェースはプログラム実行時のメモリ操作を抽象化し,広範なメモリ管理アルゴリズムを抽象的に記述する手段を提供する.また,メモリ管理機能をモジュラーな実装とした処理系の高速化のために,本研究では,実行時システムの特化手法を提案する.一般に,インタフェースの導入による抽象化には,実装上のさまざまな工夫による高速化を妨げるという問題がある.提案する手法は,メモリ管理機能の仕様に基づいて実行時システムの実装を自動的に特殊化することで,モジュラーな実装にともなうオーバヘッドを解消する.本研究では,提案した手法に従って既存の処理系のメモリ管理機能を再実装し,ベンチマークテストを用いて,それぞれの実装での実行性能を比較した.その結果,本研究が提案した特化手法がモジュラーな実装にともなう10%程度のオーバヘッドを解消し,既存の処理系と同等の性能を達成することを示した.The article describes a novel design and implementation scheme of memory management systems for programming languages. The scheme is modular in that it allows the memory management system to be replaced without modifying the rest of the programming language implementation. It is efficient in that the scheme incorporates optimization of the memory management interface to eliminates possible overhead incurred from using this interface. The paper defines an abstract interface between the runtime system and the memory management substratum. Though the interface is simple it is flexible enough to describe variety of memory management algorithms. Execution efficiency is achieved by a specialization technique that specializes the programming language implementation with respect to the implementation of the memory management system. Modular design typically incurs execution overhead due to use of generic interface definitions. This inefficiency is resolved by adding efficient bytecode instructions which are specialized for a given memory management system and also applying a bytecode transformation technology that make use of the added instructions. This memory management interface and the specialization technique has been implemented used for description of various memory management algorithms and tested effectiveness of the approach with a number of small- to medium-scale benchmark programs. The results show that for most cased the specialization technique removes 10\% overhead which is otherwise incurred from using our abstract interface."

著者

内山 雄司 緒方 大介 脇田 建

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.46, no.6, pp.1-17, 2005-04-15

被引用文献数

1

---

著者らが開発したバイトコードインタプリタ生成系であるVirtualMachineBuilder(VMB)について発表する.VMBは,仮想機械の仕様記述を入力として,仮想機械の中核をなすインタプリタの実装を生成するシステムである.VMBに与える仕様記述は,仮想機械を構成するレジスタやスタックの定義と,仮想機械で実行される各バイトコード命令の意味の定義からなる.バイトコード命令の意味は,仮想機械の状態遷移の形で表現される.以前のVMBには,データ型の宣言やオブジェクト間の参照の表現力に不十分な点があり,バイトコード命令の意味を記述する際に特別な工夫を必要とする場合があった.本研究では,仕様記述言語を再設計して,より自然な形で仮想機械の仕様を記述できるように工夫した.VMBを適用した処理系開発の事例として,簡単な手続き型言語に対するバイトコード言語を設計し,その処理系を実装した.さらに,VMBを利用してObjectiveCamlのインタプリタを実装し,仕様記述言語の表現力と生成されるインタプリタの性能という2つの観点からVMBの評価を行った.表現力については,146命令のうち133命令を自然な形で記述できた.インタプリタの性能については,ベンチマークテストの結果,手書きのインタプリタで実行した場合の93%の性能が得られた.The article proposes Virtual Machine Builder (VMB) which is a bytecode interpreter generator developed by authors group. VMB takes a specification of a virtual machine and generates implementation of the interpreter which compose a main part of the virtual machine. A specification of a virtual machine comprises a definition of a virtual hardware composed from registers and stacks, and a definition of the behavior of each virtual machine instruction. The behavior of an instruction is specified in terms of a machine state transition system. In the previous version of VMB, there were cases that we needed some tricks to specify the behavior of an instruction since the specification language lacked the way to declare data types of objects and to express references between objects. We redesigned the language so one could specify instructions more naturally. The article also shows an experience in developing tiny imperative language system using VMB. Also the expressiveness of the specification language and the perormance of the generated interpreter are evaluated by the use of a virtual machine of Objective Caml 3.08 generated by VMB. On the former point, 133 of 146 bytecode instructions can be defined naturally. On the latter point, a benchmark test shows that the efficiency of the generated virtual machine is 93% of a carefully implemented human-crafted one.