著者

前田 敦司 曽和 将容

出版者

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

雑誌

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

巻号頁・発行日

vol.41, no.4, pp.1-10, 2000-06-15

参考文献数

20

---

末尾再帰的な関数呼び出しをジャンプに変換する処理は,コンパイラの最適化として広く行なわれている.特に,Lispの一方言であるScheme言語においては末尾再帰呼び出しを空間計算量ο()で実行することが言語仕様で要求されている.このように,空間計算量ο()で実行することができる末尾再帰呼び出しを真の末尾再帰呼び出し(roper tail recursio)と呼ぶ.動的スコープを持つ変数が存在する場合,通常の実装では,スコープを規定する構文の実行が終るまで変数束縛を保持しておく必要があるため,構文の末尾で再帰的な関数呼び出しがあってもそれを真の末尾再帰呼び出しとすることができない.しかしながら,リスト構造を用いて変数束縛を保持する,いわゆる深い束縛を用いるLispインタプリタについては,事実上定数空間計算量で末尾再帰呼び出しを処理することができる手法が知られている.本論文では,動的スコープ変数の実装として現一般的な,浅い束縛を用いた場合について,真の末尾再帰呼び出しを実現するための手法について述べる.Conversion of tail recursive function call into simple jump is a technique widely used as optimization in compilers. Especially, Scheme, a dialect of Lisp, requires as part of language specification that tail recursion be performed in ο(1) space complexity. Tail recursion implemented in ο(1) space complexity is called "proper tail recursion". With existance of dynamically-scoped variables, ordinary implementation keeps variable bindings until binding construct exits. Thus, syntactic tail call cannot be implemented in a properly tail recursive fashion. For Lisp interpreters which keeps variable bindings in list structures (i.e. deep binding), there is a known way to achieve almost-proper tail recursion with dynamic scoping. In this paper, we argue about an implementation method of proper tail recursion with shallow binding, which is a common way of implementing dynamically-scoped variables in current Lisp implementations.

著者

前田 敦司 山口 喜教

出版者

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

雑誌

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

巻号頁・発行日

vol.44, no.13, pp.47-57, 2003-10-15

参考文献数

15

被引用文献数

1

---

スタックアーキテクチャの仮想マシン命令を解釈実行するSchemeインタプリタの効率的な実装法について述べる.単純な命令セット定義から出発し,ベンチマークプログラムにおける命令列の実行頻度に応じて命令セットを最適化することで解釈実行のオーバへッドを最小化する体系的な手法を示す.本手法を用いて構成したインタプリタの性能評価を行い,インタプリタの移植性,対話性,デバッグの容易さを損なうことなく,ネイティブコードの20?40%程度の,比較的高い性能が得られていることを示す.An effcient implementation methodology for Scheme interpreters that interpretes stackoriented virtual machine instructions is presented. Starting from simple instruction set definition, we show how our systematic optimization techniques reduces the interpretation overhead based on dynamic frequency of instruction sequence. Evaluation shows that our interpreter can achieve 20 to 40 percent of the performance of native code, without losing portability, interactivity, and ease of debugging.

著者

笹田 耕一 松本 行弘 前田 敦司 並木 美太郎

雑誌

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

巻号頁・発行日

vol.48, no.SIG10(PRO33), pp.1-16, 2007-06-15

---

本論文ではスクリプト言語Ruby 用仮想マシンYARV: Yet Another RubyVM における並列実行スレッド処理機構の実装について述べる.Ruby はその使いやすさから世界中で広く利用されているプログラム言語である.Ruby の特徴の1 つにマルチスレッドプログラミングに対応しているという点があるが,現在広く利用されているRuby 処理系は移植性を高めるため,すべてユーザレベルでスレッド制御を行っている.しかし,このスレッド実現手法では,実行がブロックしてしまう処理がC 言語レベルで記述できない,並列計算機において複数スレッドの並列実行による性能向上ができないなどの問題がある.そこで,現在筆者らが開発中のRuby 処理系YARV において,OS やライブラリなどによって提供されるネイティブスレッドを利用するスレッド処理機構を実装し,複数スレッドの並列実行を実現した.並列化にあたっては,適切な同期の追加が必要であるが,特に並列実行を考慮しないC 言語で記述したRuby 用拡張ライブラリを安全に実行するための仕組みが必要であった.また,同期の回数を減らす工夫についても検討した.本論文では,これらの仕組みと実装についての詳細を述べ,スレッドの並列実行によって得られた性能向上について評価した結果を述べる.

著者

笹田 耕一 松本 行弘 前田 敦司 並木 美太郎

出版者

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

雑誌

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

巻号頁・発行日

vol.48, no.10, pp.1-16, 2007-06-15

被引用文献数

2

---

本論文ではスクリプト言語Ruby 用仮想マシンYARV: Yet Another RubyVM における並列実行スレッド処理機構の実装について述べる.Ruby はその使いやすさから世界中で広く利用されているプログラム言語である.Ruby の特徴の1 つにマルチスレッドプログラミングに対応しているという点があるが,現在広く利用されているRuby 処理系は移植性を高めるため,すべてユーザレベルでスレッド制御を行っている.しかし,このスレッド実現手法では,実行がブロックしてしまう処理がC 言語レベルで記述できない,並列計算機において複数スレッドの並列実行による性能向上ができないなどの問題がある.そこで,現在筆者らが開発中のRuby 処理系YARV において,OS やライブラリなどによって提供されるネイティブスレッドを利用するスレッド処理機構を実装し,複数スレッドの並列実行を実現した.並列化にあたっては,適切な同期の追加が必要であるが,特に並列実行を考慮しないC 言語で記述したRuby 用拡張ライブラリを安全に実行するための仕組みが必要であった.また,同期の回数を減らす工夫についても検討した.本論文では,これらの仕組みと実装についての詳細を述べ,スレッドの並列実行によって得られた性能向上について評価した結果を述べる.In this paper, we describe an implementation of parallel threads for YARV: Yet Another RubyVM. The Ruby language is used worldwide because of its ease of use. Ruby also supports multi-threaded programming. The current Ruby interpreter controls all threads only in user-level to achieve high portability. However, this user-level implementation can not support blocking task and can not improve performance on parallel computers. To solve these problems, we implement parallel threads using native threads provided by systems software on YARV: Yet Another RubyVM what we are developing as another Ruby interpreter. To achieve parallel execution, correct synchronizations are needed. Especially, C extension libraries for Ruby which are implemented without consideration about parallel execution need a particular scheme for running in parallel. And we also try to reduce a number of times of synchronization. In this paper, we show implementations of these schemes and results of performance improvement on parallel threads execution.

著者

笹田 耕一 松本 行弘 前田 敦司 並木 美太郎

出版者

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

雑誌

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

巻号頁・発行日

vol.47, no.2, pp.57-73, 2006-02-15

被引用文献数

5

---

本稿ではオブジェクト指向スクリプト言語Ruby を高速に実行するための処理系であるYARV: Yet Another RubyVM の実装と,これを評価した結果について述べる.Ruby はその利用のしやすさから世界的に広く利用されている.しかし,現在のRuby 処理系の実装は単純な構文木をたどるインタプリタであるため,その実行速度は遅い.これを解決するためにいくつかの命令実行型仮想マシンが提案・開発されているが,Ruby のサブセットしか実行できない,実行速度が十分ではないなどの問題があった.この問題を解決するため,筆者はRuby プログラムを高速に実行するための処理系であるYARV を開発している.YARV はスタックマシンとして実装し,効率良く実行させるための各種最適化手法を適用する.実装を効率的に行うため,比較的簡単なVM 生成系を作成した.本稿ではRuby の,処理系実装者から見た特徴を述べ,これを実装するための各種工夫,自動生成による実装方法について述べる.また,これらの高速化のための工夫がそれぞれどの程度性能向上に寄与したかについて評価する.In this paper, we describe the implementation and evaluation results of YARV, next generation Ruby implementation. The Ruby language is used worldwide because of its ease of use. However, current interpreter is slow due to its evaluation method. To solve this problem, several virtual machine designs were proposed, but none of them exhibited adequate performance/functionality combination. Our implementation, called YARV (Yet Another Ruby VM), is based on a stack machine architecture. YARV incorporates a number of optimization techniques for high speed execution of ruby programs. In this paper, we describe the characteristics of Ruby from implementor's point of view, and present concrete solutions for these issues as well as implementation of optimization techniques. We also show how each of these optimizations contributed to the speed-up.

著者

白畑 有加 前田 敦司 山口 喜教

雑誌

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

巻号頁・発行日

vol.4, no.3, pp.97-97, 2011-06-29

---

プログラムの処理の流れを扱う概念に,継続がある.継続とは,ある処理のある瞬間における,「次にどのような処理を行うのか」 という処理過程の未来全体を表すものである.Scheme では継続をファーストクラスの機能としてサポートしており,call/cc 関数を用いて継続を扱うことができる.しかし,そのほかほとんどのプログラミング言語は継続を明示的に扱っていない.そのような言語に継続をファーストクラスの機能とし導入する手法として CPS 変換や例外処理を用いた手法など様々な研究がなされているが,導入後の実行効率が大幅に落ちてしまうという問題点をかかえている.本発表では対象言語を JavaScript とし,Pettyjohn らの手法をもとにした新しい,継続を導入する変換手法を提案する.変換後の実行効率の向上のため,継続から処理を再開するときのコードを別途定義する.これにより継続を使用しない場合の処理は変換前後で実行速度が変わらない.また,継続による処理の再開位置を示す Resumption Point を導入することで変換後のコードの重複を削減した.さらに,本発表では継続をキャプチャするタイミングに例外処理を用いる手法と 2 返戻値法の両方を使い分ける.このハイブリッドな継続のキャプチャ手法の採用により,さらに変換後の実行効率の向上を見込むことができる.Continuation is an idea which deals with flow of control inprograms. Although Scheme has continuation as a first-class feature, most other programming languages don't support it explicitly. Various approaches have proposed to adopt the continuation as a first-class feature in such languages, e.g., CPS conversion and stack-traversal and rebuilding using exception. But these conversions have significant impact on execution efficiency and slows down the execution of programs after conversion considerably. In this presentation, we propose a new transformation algorithm based on Pettyjohn, et al.'s approach, which can introduce continuation more efficiently to programming languages that don't support them (we use JavaScript as a specific example). To improve execution efficiency after transformation, we separately generate the code run in ordinary execution and the code executed when continuation is invoked. When executed without using continuations, the execution efficiency after transformation is almost equal to the one before transformation. Since we separately generate the code for two cases, code size may increase after conversions. This code expansion is reduced by sharing code using labels called Resumption Point, which marks the point to resume when continuations are invoked. We use two techniques for stack traversal when capturing continuations: exception handling and two return values method. We combine these two techniques to get better performance in continuation capturing, and believe our approach has the advantages over existing techniques.

著者

前田 敦司 遠藤 匠 山口 喜教

出版者

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

雑誌

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

巻号頁・発行日

vol.45, no.5, pp.83-83, 2004-05-15

---

マークスイープアルゴリズムに基づくインクリメンタルガーベジコレクタは,停止時間をごく短時間に抑えることが可能であるが,効率が悪く,CPU時間が増加する.この性能低下の原因は,一括型GCと比較してマークする時期が早いことに起因するmark/cons比の悪化,GCルーチンを呼び出す回数の増加,write barrierのオーバヘッドなどによる.一方,世代別ガーベジコレクタは高いCPU効率が得られ,また平均の停止時間は比較的短いため良いレスポンスが得られるが,旧世代領域のGC( メジャーコレクション)の際には長い時間にわたって計算処理が停止してしまい,リアルタイム応用には適さない.本発表では,世代別GCがある意味でインクリメンタルGCの一種と見なせることを指摘する.この観察に基づき,新世代領域のGC(マイナーコレクション)のたびに,インクリメンタルに旧世代領域のガーベジコレクションを行う新しいGCアルゴリズムを提案する.インクリメンタル化のために必要となるライトバリアは,世代別ガーベジコレクタの実装にいずれにせよ必要なライトバリアと同じ仕組みを利用する.このアルゴリズムは,通常の世代別ガーベジコレクタに近い効率を保ちながら,停止時間を短く保ち,ガーベジコレクタのリアルタイム性を向上させることができる.Incremental garbage collectors based on mark-sweep algorithms can minimize the pause time caused by garbage collection at the expense of increased CPU time. The main reasons for this performance degradation include: (1) mark/cons ratio gets worse in incremental collectors because objects are marked earlier than in non-incremental counterparts, (2) increase in number of calls to collector routine and (3) write barrier overhead. Generational collectors, on the other hand, can achieve high efficiency and relatively short average pause time, while occasional long pause for collection of old generation space (major collection) makes these collectors unsuitable for real-time applications. In this presentation we point out that certain class of generational collectors can be viewed as a special case of incremental garbage collection. Based on this observation, we propose a new GC algorithm which incrementally reclaims old generation space every time a minor collection is performed. Write barrier for generational collector is also used for incremental collection. With this algorithm, we can improve real-time response of garbage collector by keeping pause time short, with little overhead added to ordinary generational collectors.

著者

山口 大貴 前田 敦司 山口 喜教

雑誌

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

巻号頁・発行日

vol.5, no.3, pp.63-63, 2012-08-20

---

多くのスクリプト言語同様,RubyはCやJavaといった従来の言語と比較して非常に複雑な文法を持っている.そのため,構文解析器の作成において現在主流となっている,yacc(またはbison)とlexを用いて構文解析器と字句解析器を生成しそれらを組み合わせる手法では,文法の記述や実装が困難であったり実装が複雑化しメンテナンスが困難となってしまったりする場合がある.たとえばRubyでは,文字列リテラルに任意の式を埋め込み可能な文法を実現するため等の理由で,手書きの字句解析器を含めて8000行以上にもおよぶ巨大な文法定義を行っている.これは,現在用いられている構文解析アルゴリズムが字句解析をベースとしているために,字句解析器に状態を付加する等のアドホックな実装を行わなければこのような文法を実現することができないためである.そこで本研究では,Parsing Expression Grammar(PEG)をベースとした,強力な解析力を持つ構文解析アルゴリズムPackrat ParsingをRuby処理系(JRuby)に導入することを提案する.Packrat Parsingを実際にRuby処理系に用いることで,従来の構文解析アルゴリズムで問題となっていた部分を改善し,文法定義の保守性を向上させることが本研究の目標である.本研究の構文解析器の実装は,PEGをベースとした文法定義をPackrat Parser生成系Rats!に与えることで行い,その文法定義は従来の文法定義を変換することで作成する.また提案手法による処理系と従来手法による処理系に対して実際のスクリプトを使用した比較評価を行い,その結果として,提案手法によって文法定義の保守性が向上することを示す.

著者

高橋 聡子 岩井 輝男 田中 良夫 前田 敦司 中西 正和

出版者

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

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.38, no.5, pp.1050-1057, 1997-05-15

参考文献数

14

---

リスト処理プロセスとGCプロセスを同時に複数動作させることによって,リスト処理を並列化することによる処理時間の短縮が可能になった.しかし,セルの消費のペースはアプリケーションによって異なり,CPUの数も計算機によって異なるので,リスト処理プロセスの最適な数はアプリケーション,計算機によって異なると考えられる.本稿では,セルの消費速度やフリーセルの残量によってリスト処理プロセスとGCプロセスのCPU割当てを動的に決定する機能により,Lispの代表的なアプリケーションに対し,処理速度と実時間性とのバランスのとれた処理を行うことを可能とする並列Lispシステムの報告を行う.本システムの実装にあたっては,できるだけリスト処理の中断が生じることがなく,リスト処理に最大数のCPUが割り当てられるようCPU割当てのパラメータを設定し,CPU割当てを動的に決定した.その結果,リスト処理の中断がなくなり実行時間が短縮された.Parallel lisp system with parallel garbage collection(GC)can produce improvements in throughput by executing list processing in parallel.But,the optimal number of list processes and GC processes depends on machines and applications because the number of processors on a machine and cells which are consumed by various applications is different.In this paper,we report parallel lisp system which makes it possible to balance throughput and real time performance by dynamic allocation of CPU depending on speed of consuming cells and the number of remaining free cells.We dynamically changed CPU allocation according to the parameter which was set to avoid a disruption of list processing and allocateas many CPU as possible to list processing.Consequently,our system yielded improvements in throughput without any disruption of list processing.

著者

山口 大貴 前田 敦司 山口 喜教

雑誌

全国大会講演論文集

巻号頁・発行日

vol.72, pp.501-502, 2010-03-08

著者

水島 宏太 前田 敦司 山口 喜教

出版者

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

雑誌

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

巻号頁・発行日

vol.49, no.1, pp.117-126, 2008-01-15

---

Packrat parsingは,バックトラック付き再帰下降構文解析にメモ化を組み合わせた構文解析法であり,parsing expression grammar(以下PEG)で記述できる広範囲の文法を入力サイズの線形時間で解析することができるという特徴を持っている.しかし,packrat parsingには,メモ化を行うために入力サイズに比例する記憶領域を要するという欠点がある.本論文では,カット演算子をPEGに加えることにより,不要な記憶領域を削除する機能を持つpackratパーザ生成系を提案する.カットはPrologから借用した概念であり,構文規則中でカットより後ろでバックトラックが不要な場合にそのことを処理系に指示し,不必要なバックトラックが起こらないようにするための機能である.カットの評価によって,ある入力位置より前にバックトラックしないということが判明した場合,その入力位置より前にバックトラックしたときのために使用されているメモ化領域を動的に削除し,再利用することができる.我々は,構文規則中にカットを適切に挿入することで,多くの実用的文法について有界なメモリ量で解析できるパーザを生成可能と考えている.一方,カットによるメモリ効率の改善は,パーザ生成系のユーザが手動でカットを挿入しなければならないという問題点があるが,本論文ではこの問題点を解決するために,解析する言語の構文の意味を変えない範囲でカットを自動的に挿入する手法と,不要なメモ化が行われている箇所を検出して必要な記憶領域を静的に削減するための手法についても提案する.Packrat parsing is a parsing technique that combines memoization with backtracking recursive descent parser. It can handle any grammars that can be expressed in powerful grammar notation called parsing expression grammar (PEG). Generated parsers can analyze its input in linear time. However, to memoize intermediate result, packrat parsing requires storage area proportional to the input size. In this paper, we propose the packrat parser generator system that disposes unnecessary storage area by adding the notion of a cut operator to PEG. Cut operators is the notion we borrowed from Prolog that can be used by programmers to 'cut off' an alternative execution branch of a choice point in a syntax rule when the alternative should not be tried for suppressing unnecessary backtracking. When an alternative is removed by execution of a cut operator (and thus the parser can make sure that no backtracking can occur before a particular input positon), the memoization storage kept against backtracking can be deallocated and reclaimed dynamically. We believe that, for most pratical grammars,parsers which only use bounded memory size can be generated by appropriate insertion of cut operators in syntax rules. Although memory efficiency that can be achieved by hand-insertion of cut operators would be valuable, it is awesome and error-prone. In this paper, we also propose a technique to reduce required storage area by statically detecting syntax rules which memoization is unnecessary and another technique for automatically inserting cut operators without changing meanings of syntax rules.

著者

笹田 耕一 松本 行弘 前田 敦司 並木 美太郎

雑誌

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

巻号頁・発行日

vol.47, no.SIG2(PRO28), pp.57-73, 2006-02-15

---

本稿ではオブジェクト指向スクリプト言語Ruby を高速に実行するための処理系であるYARV: Yet Another RubyVM の実装と,これを評価した結果について述べる.Ruby はその利用のしやすさから世界的に広く利用されている.しかし,現在のRuby 処理系の実装は単純な構文木をたどるインタプリタであるため,その実行速度は遅い.これを解決するためにいくつかの命令実行型仮想マシンが提案・開発されているが,Ruby のサブセットしか実行できない,実行速度が十分ではないなどの問題があった.この問題を解決するため,筆者はRuby プログラムを高速に実行するための処理系であるYARV を開発している.YARV はスタックマシンとして実装し,効率良く実行させるための各種最適化手法を適用する.実装を効率的に行うため,比較的簡単なVM 生成系を作成した.本稿ではRuby の,処理系実装者から見た特徴を述べ,これを実装するための各種工夫,自動生成による実装方法について述べる.また,これらの高速化のための工夫がそれぞれどの程度性能向上に寄与したかについて評価する.

著者

前田 敦司 中西 正和

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.38, no.3, pp.574-583, 1997-03-15

---

本論文では,幅優先で式の評価を行う新たな計算機アーキテクチャであるキューマシンを提案し,その実行モデルを用いて関数型言語を特殊なハードウェアのサポートのない密結合並列計算機上で効率良く自動並列実行する言語処理系の構築法を述べる.関数型言語においては複数の関数呼び出しを並列に処理することが可能であるが,すべての関数呼び出しの実行が終了するまで待って実行を再開するための同期オーバヘッドが問題となる.また,通常スタックに保持する局所的な実行の文脈をヒープ上に保持する必要があるため,メモリ管理のオーバヘッドも増大する.本論文では,キューマシンの実行モデルを模倣してスタックをキューに置き換えることにより上記のオーバヘッドを大幅に削減することができ,既存の計算機上で並列関数呼び出しが効率良く実現できることを示す.この手法を用いたプロトタイプ言語処理系の実行時間を密結合並列計算機で測定した結果,逐次実行ではCなどの他の(逐次)言語処理系に劣るものの,2CPU以上では他の処理系を上回り,高い台数効果が得られている.

著者

齋地 崇大 前田 敦司

雑誌

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

巻号頁・発行日

vol.13, no.4, pp.1-20, 2020-10-23

---

リージョンによるメモリ管理は,メモリ空間をリージョンと呼ばれる単位で分割し,リージョン単位でLIFO順にメモリの割付けと解放を行う.プログラム中のメモリを必要とするオブジェクトは,それぞれの生存期間に対応したリージョンにメモリが割り付けられる.オブジェクトとリージョンの対応付けは,プログラムの構造を静的に解析することによって決定できる.実行の前にオブジェクトの生存期間を決定するため,ガベージコレクションによる実行時オーバヘッドの削減が期待できる.Ruby,Python,そしてJavaScriptといった動的言語は,実行時まで得られない動的な情報がプログラムに含まれるため,不要となったオブジェクトの割り付けられたリージョンを速やかに解放できる精度の高いオブジェクトとリージョンの対応付けを静的な解析で決定するのは困難である.本研究では,精度の高いリージョンによるメモリ管理を動的言語へ適用する手法として,実行時リージョン解析を提案する.実行時まで決定しない情報を用いてリージョンを解析するため,静的な解析と比較して精度の高いリージョン対応付けを決定できる.提案手法の性能を計測するため,プログラミング言語Rubyの処理系へ実行時リージョン解析機構を実装し評価を行った.いくつかのケースでは,ガベージコレクションの頻度や停止時間が削減され,実行時間の短縮が確認された.

著者

松井 祥悟 田中 良夫 前田 敦司 中西 正和

出版者

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

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.36, no.8, pp.1874-1884, 1995-08-15

参考文献数

12

被引用文献数

4

---

本論文では、並列型(parallel)および漸次型(incremental)ガーベジコレクションの基本アルゴリズムである相補型ガーベジコレクタ(Complementary Garbage Collector)の提案およびその評価を行う。このアルゴリズムは、増分更新型(incremental update)とスナップショット型(snapshot-at-begiming)という2つの基本アルゴリズムを相補的に組み合わせたものである。ゴミの回収効率の良さと正当な(無矛盾な)実装の容易さという両者の長所を併せ持つ。このアルゴリズムは、現在広く便用されているスナップショット型アルゴリズムを代替する。この型を基本アルゴリズムとしている現存の並列型および漸次型ガーベジコレクションに直ちに応用できる。Complementary Garbage Conectorを並列型mark-and-sweep法および潮次型mark-and-sweep法に組み込み、評価を行った結果、ゴミセルの回収効率は一括型GCと同程度まで改善されることが確認された。これにより実行速度、実時間性(無停止性)が改善された。

著者

前田 敦司

出版者

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

雑誌

情報処理 = IPSJ Magazine (ISSN:04478053)

巻号頁・発行日

vol.42, no.10, pp.1020-1021, 2001-10-15

著者

林 拓人 前田 敦司

雑誌

第56回プログラミング・シンポジウム予稿集

巻号頁・発行日

vol.2015, pp.121-130, 2015-01-09

---

従来のクラスベース・オブジェクトシステムは,メソッドをクラスに格納するものと総称関数に格納するもの(メソッドがクラスに属すものと総称関数に属すもの)とに分けられる.本論文はこれらのいずれとも異なり,環境にメソッドを直接格納する新しいオブジェクトシステムを提案する.クラスや総称関数といった枠を廃し,クラス名とメソッド名の組をキーとして環境にメソッドを直接格納する.これにより変数に対して行えるあらゆる操作がメソッドに対しても自然に行えるようになり,従来の方式に比べシンプルな仕組みで柔軟なオブジェクト指向プログラミングが可能となる.提案する手法の有用性を実証するため,このオブジェクトシステムを搭載する独自言語Suzuの処理系を実装した.Suzuの特徴を生かすプログラム例として言語内DSL(Domain Specific Language)の構築例を挙げる.従来のオブジェクトシステムにおける類似した概念等との関連についても議論する.

著者

矢口 拓実 池袋 教誉 前田 敦司

雑誌

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

巻号頁・発行日

vol.9, no.1, pp.14-14, 2016-02-26

---

Packrat Parsingは,広範囲な構文規則を解析できる構文解析手法である.この手法では,解析が成功するまで構文を探索するバックトラックを用い,一度解析した解析対象文字列の位置と結果を保存するメモ化と呼ばれる手法によって解析時間を線形時間に保っている.既存の多くのPackrat Parsing実装は,PEG(Parsing Expression Grammer)で記述された文法規則を,再帰呼び出しによるバックトラックとメモ化表を用いるプログラムに変換するが,このような処理系の実行速度は,正規表現に基づいて表引きを用いた字句解析器と,同じく表引きとスタックを用いて処理を進めるLALR(1)などのパーサアルゴリズムの組み合わせと比較すると,一般的に劣っている.本発表では,Packrat Parsingの高速化のため,解析の意味が変化しない範囲で表引きによって構文解析を進める手法を検討する.本発表では,Packrat Parsingの処理の中に可能な限り表引きをとり入れることで,実行速度を向上させる手法を提案する.また,基本的な実行方式としてはMedeirosらの提案した仮想マシン方式を改良したものを採用している.既存の手法と比較した性能評価の結果を示す.

著者

遠藤 仁 前田 敦司 山口 喜教

雑誌

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

巻号頁・発行日

vol.4, no.4, pp.38-38, 2011-09-22

---

CPU の性能向上手法がクロックの高周波化からマルチコア化へとシフトした現在,CPU の性能を活用するために処理の並列化を図ることはますます重要性を増している.広く用いられているプログラミング言語の構文解析手法の多くは,有限の (多くの場合 1 つの) トークンを先読みすることによって逐次的に処理を進めるものであり,並列化は困難である.筆者らは,バックトラックによる再帰下降構文解析とメモ化を組み合わせた構文解析アルゴリズムである packrat parsing において,下位の非終端記号の解析結果を記録するメモ化表を,別のスレッドを用いてあらかじめ埋めておくことによって,上位の構文解析スレッドの動作を高速化できるのではないかと考えた.本研究では,Medeiros らの PEG 仮想マシンにメモ化機能を加えて packrat parsing 仮想マシンとし,さらに上記のアイディアを用いて並列化を行った.PEG で表記した文法を与えると,構文木を作成する並列 packrat parser を生成するパーザジェネレータを試作し,生成されたパーザに対して実際のプログラムを入力として評価実験を行い,並列処理の有効性を確認した.Parallelization of programs is getting more importance because recent performance improvement is driven mainly by increasing number of cores, rather than increase in clock frequency. Many of parsing algorithms used in programming language implementations rely on directing their actions by lookahead of finite (in many cases, only one) tokens, thus severly limiting the possibility of parallel processing. Packrat parsing is a variant of backtracking recursive descent parsing combined with memoization. In packrat parsing, memoization table for low-level nonterminals can be filled by distinct prefetch thread to accelerate processing of higher-level nonterminals. Following the idea, we have parallelized packrat parsing abstract machine, which is based on PEG machine by Medeiros. We built a parser generator that generates parallel packrat parser from grammar description written in PEG. We evaluated performance of the generated parser using real program as input, confirming the effectiveness of our approach.

著者

田中良夫 松井 祥悟 前田 敦司 中西 正和

出版者

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

雑誌

情報処理学会記号処理研究会報告

巻号頁・発行日

vol.94, no.49, pp.17-24, 1994

被引用文献数

1

---

通常ガーベッジコレクション(GC)はリスト処理を中断して行なわれる.GCをリスト処理と並列に行なう(並列GC)ことにより,GCによる中断時間をなくし,リスト処理の実時間化が可能となる.並列GCではGCの処理中にリスト処理によってデータが書き換えられるので,GCの正当性を保証するために特殊な処理が必要となる.そのため並列GCは停止型GCに比べてあまり効率が上がらず,実用化されているものもほとんどない.mark and sweep方式の並列GCにおいては,ゴミセルの回収効率が停止型GCに比べて約1/2になってしまうことが知られている.これらの欠点の改善は,並列GCの実用化へ向けての重要な研究テーマである.本論文では,mark and sweep方式の並列GCの欠点を改善したGCである,Partial Marking GC(PMGC)の提案,実装および評価に関する報告を行なう. PMGCはmark and sweep型の並列GCに世代別GCの概念を導入したGCである.PMGCを実装し様々な実験を行なった結果,PMGCによってゴミセルの回収効率は従来の並列GCに比べ最大で2倍に改善されることが確認された.PMGCは並列GCの実用化に向けての有効なGCである.