著者

鵜川 始陽 湯淺 太一 小宮 常康 八杉 昌宏

出版者

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

雑誌

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

巻号頁・発行日

vol.42, no.11, pp.25-36, 2001-11-15

参考文献数

12

---

「ぶぶ」は,Java 言語とのシームレスなインタフェースを備えたオブジェクト指向型のScheme 処理系である.Java の機能を最大限に利用しつつScheme を使って対話的にプログラミングができることを目標としており,Scheme の継続機能,Java の例外処理機能の両方に対応していることが望まれる.ぶぶではScheme とJava で記述したメソッドを相互に呼び出し合うことができる.Scheme部分の実行には専用に確保した制御スタックを使っているが,Java 部分の実行にはJava VM の制御スタックを使っている.したがって,完全なファーストクラスの継続を実現するためには,Java の継続も得なければならない.しかし,Java 言語はこのような手段を提供していない.そこで,継続オブジェクトを生成するときは実行中のScheme 部分だけの継続をヒープに保存しておき,Java 部分の継続はJava VM の制御スタック上に残しておくことにした.継続を呼び出すときにJava 部分の継続が制御スタック上に残っているかどうかを調べ,残っていれば完全な継続呼び出しとして動作する.残っていないときはScheme 部分だけの部分継続として呼び出す.また,Java の例外処理機能をScheme で記述したプログラムでも直接利用できるようにした.この例外処理機能は継続機能と同時に使うことができる."Bubu" is an object-oriented Scheme system with seamless interface to Java. Because the goal of Bubu is to provide an interactive environment of Scheme and draw out maximum functionality of Java, we expect it to support both first-class continuations of Scheme and the exception system of Java. In Bubu, methods written in Java and Scheme can call each other. The control stack for methods in Scheme is implemented by using an array object of Java. On the other hand, methods in Java uses the control stack of Java VM. Therefore, when a first-class continuation is captured, a continuation of Java must be also saved to heap. However, Java does not support this facility. In our proposal, when a continuation is captured, only a continuation of Scheme part is saved to heap and the continuation of Java part is left on the control stack of Java VM. When the continuation is called, whether the continuation of Java part is left on the stack of Java VM or not is checked, and if left, this call works as a traditional continuation call. If not, this works as a partial continuation call which has only the Scheme part. In addition, we developed a seamless interface to the Java exception system which can cooperate with the continuation facility.

著者

鵜川 始陽 信岡 孝佳 海野 弘成 湯淺 太一

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.29, no.3, pp.3_143-3_156, 2012-07-25 (Released:2012-08-20)

---

ロックやメモリバリア命令の実行には多くのCPUサイクルを消費するため,並行GC(ごみ集め)では,書込みバリアからロックやメモリバリア命令を排除することが容易なインクリメンタルアップデートGCが使われることが多い.しかし,インクリメンタルアップデートGCの通常の実装では,マークフェーズ後にミューテータを止めて多くのオブジェクトをマークする可能性があり,実時間アプリケーションには向かない.本論文では,この処理が必要のないスナップショットGCを使った並行GCを提案する.提案するGCでは,ロックやメモリバリア命令の頻繁な使用を避けるために,ミューテータは書込みの履歴を溜めておいて,GCとハンドシェイクすることで,履歴をまとめてGCに渡す.このGCをDalvik VMに実装し,評価を行った.

著者

飯干 寛幸 松本 康太郎 鵜川 始陽

雑誌

研究報告システムソフトウェアとオペレーティング・システム(OS) (ISSN:21888795)

巻号頁・発行日

vol.2020-OS-148, no.2, pp.1-10, 2020-02-20

---

近年,電源が失われても内容が保持されるメモリとして不揮発性メモリ(NVM)が市場に登場した.NVM を使ったシステムでは,データがキャッシュから NVM に書き出されて初めて永続化される.そのため,いつ電源が失われても良いように,常に NVM 上のデータの整合性を保つための方法が研究されている.その中には,個々のデータ構造を NVM に対応させるアプローチと,汎用のデータ構造を永続化するためのシステムを開発するアプローチがある.本研究では,NVM を使ってデータ構造を永続化するためのシステムである NV-HTM の評価を行った.そのために,NV-HTM を使い永続化した B+-木と,B+-木を NVM に特化させた FPTree の性能を比較した.NV-HTM は性能評価用の DRAM を用いたエミュレータを使うソースコードしか存在しなかったため,実機で動作するように修正が必要だった.FPTree もアルゴリズムの記述から実装する必要があった.これらを実装して比較したところ,NV-HTM は FPTree に比べて遅く,スレッド数を増やしても 4 スレッドまでしかスケールしなかった.そこでさらに,NV-HTM の性能ボトルネックを詳細に調査した.

著者

皆川 宜久 鵜川 始陽 八杉 昌宏 湯淺 太一

出版者

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

雑誌

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

巻号頁・発行日

vol.46, no.11, pp.71-71, 2005-08-15

---

継続とは,計算のある時点の残りの計算である.Scheme では,これをファーストクラスのオブジェクトとして扱え,コルーチンやマルチスレッドなどの機能を実現するのに有用である.ML 言語において一級継続の機能を搭載した処理系としては,Standard ML of New Jersey がある.この処理系はスタックを用いず関数フレームをすべてヒープ領域に割り付けているため,定数オーダの時間で継続の生成を実現している.しかし,一般に関数フレーム生成時にスタックを用いた方が,高速であり,メモリ効率も良い.本研究では,スタックを用いているML 処理系に対し,一級継続の実装を行った.この場合,継続の生成時にスタックの内容をヒープにコピーするスタック法が一般的である.実際,スタックを用いたScheme 処理系で多く採用されている.この方法は動作が単純で実装しやすいなどの利点がある.一方,継続生成のたびにスタックのコピーが行われるので,生成時間,メモリ効率の点などで効率が悪いことがある.そこで本研究では,その効率化手法である遅延スタックコピー法を採用した.この手法は,継続を使用したプログラムの効率を高める一方,オブジェクトの生成時や代入時にオーバヘッドが存在するという欠点がある.そこで,コンパイル時にML の型情報を利用して,そのオーバヘッドを軽減する手法を提案し,実装,評価を行った.A continuation is the remaining task at a point in a computation. In Scheme, a continuation can be captured as a first-class object. This is useful for implementing coroutines and multi-threading. Standard ML of New Jersey is an implemenation of ML with first-class continuations. This system allocates all activation records into the heap, and this feature allows capturing continuations in constant order time. In general, however, a stack is more efficent in terms of execution time and memory space to allocate activation records. We implemented first-class continuations in a stack-based ML system. In order to implement first-class continuations, we adapted the stack strategy which is used in many stack-based implementations of Scheme. With this strategy, the entire stack contents are copied into the heap whenever a continuation is captured. This strategy is simple and easy to implement, but capturing continuations requires a lot of time and memory space. Thus, we employed the lazy stack copying strategy, which is based on the stack strategy but more efficent. While this strategy is useful when creating continuations, there is an overhead when creating and modifying objects. We propose a technique to reduce this overhead by using the type information of ML at compile time, and we applied this techinique to the ML system and evaluated it.

著者

森 翔太郎 近森 凪沙 鵜川 始陽

雑誌

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

巻号頁・発行日

vol.13, no.3, pp.15, 2020-06-17

---

組込みシステム向けにコンパクトに開発されたmRuby/cというRuby処理系がある.組込みシステムの実行環境は一般にメモリが少なく,CPUも非力であるため,時間的オーバヘッドや空間的オーバヘッドが小さい方法でにプログラムを処理する必要がある.現状のmRuby/cのガベージコレクタ(GC)には,参照カウント方式が採用されている.参照カウント方式は,再帰的なオブジェクトの解放が起こらない限り停止時間が短いという利点がある.しかし,参照カウントの操作は時間的なオーバヘッドとなる.また,各オブジェクトが持つ参照カウントを保持するフィールドも空間的なオーバヘッドとなる.さらに,循環参照を回収できないという問題もある.そこで本研究では,mRuby/cで参照カウントの妥当性を調査する.そのために,比較対象としてマークスイープGCを実装する.そのうえで,いくつかの性質の異なるベンチマークプログラムを用いて停止時間や時間的,空間的オーバヘッドの面で比較する.

著者

小野澤 拓 岩崎 英哉 鵜川 始陽

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.38, no.3, pp.3_23-3_40, 2021-07-27 (Released:2021-09-27)

---

ネットワークを介してセンサからデータを収集したり,機器を制御する技術であるIoT (Internet of Things)が近年注目を集めている.eJS (embedded JavaScript)プロジェクトでは,IoTのプログラム開発にJavaScriptを利用可能とすることで,IoTアプリケーション開発の複雑さなどを軽減することを目指している.eJS プロジェクトでは,計算資源が限られるIoT機器や,その上で実行されるIoTアプリケーションに合わせてカスタマイズされたJavaScript仮想機械(eJSVM)を生成するフレームワークeJSTKを提供する.本研究では,eJSVM のふたつの新しいカスタマイズ項目を実現した.ひとつ目に,64 ビット環境向けと32 ビット環境向けのデータ構造を選択できるようにした.ふたつ目に,4種類の異なるごみ集めアルゴリズムから,対象アプリケーションと相性の良いアルゴリズムを選択できるようにした.実験により,これらのカスタマイズ項目の有効性を確認した.

著者

鵜川 始陽 皆川 宜久 小宮 常康 八杉 昌宏 湯淺 太一

雑誌

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

巻号頁・発行日

vol.44, no.SIG13(PRO18), pp.72-83, 2003-10-15

---

実行にスタックを利用している処理系でファーストクラスの継続を生成する場合,スタックの内容をヒープにコピーするのが一般的である.スタックの内容をヒープにコピーする戦略には様々なものが提案されているが,実際の処理系の多くはスタック法を採用している.スタック法では継続の生成のたびに処理系のスタック全体の内容をヒープにコピーする.このように,スタック法は動作が単純なので簡単に実装でき,また他言語呼び出しをサポートした処理系でも利用できるという長所がある.しかし,継続の生成に時間がかかり,また,メモリ効率が悪いという欠点があり,利用の妨げとなる場合もある.本発表では,スタック法による継続の生成に対する効率化手法として,スタックのコピーの遅延を提案する.継続の生成によりコピーされるスタックの内容は,継続を生成した関数からリターンするまでスタック上にも残っている.したがって,スタックのコピーを継続を生成した関数からリターンするまで遅らせてもよい.もし,生成した継続が,スタックをコピーする前にごみになれば,スタックのコピーを省略できる.本発表では,さらに,スタックコピーの遅延により可能となる,継続オブジェクトの部分的共有も提案する.これらの効率化手法をScheme処理系に組み込んで性能を評価したところ,継続を使ったプログラムの実行効率が改善された.

著者

五味真幹 鵜川始陽 岩崎英哉

雑誌

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

巻号頁・発行日

vol.2011, pp.125-132, 2011-01-07

---

半導体記憶素子であるフラッシュメモリを使用した記憶装置の一種として、Solid State Drive(SSD)が、価格の低下や速度の向上に伴い、近年注目を集めている。HDDと比べ、読み書きが速い、耐衝撃性が高い、消費電力が小さいといった利点の反面、書き換え可能回数に上限がある、記憶容量当たりの単価が高いといった欠点もある。そのため、一般的なマシンにおいてはSSDとHDDを併用し、相補的に利用することが重要視されている。そこで本研究では、SSDとHDDの併用によって、ファイルアクセスを高速化するファイルシステムUnion-Extended Cache File System(UECFS)を提案し、実装する。UECFSは、ファイルへのアクセス頻度に応じて、SSDかHDDのどちらかへファイルを自動配置する。ファイルの配置先は、ファイルのアクセス頻度の変化に応じて、動的に変更する。アクセス頻度の高いファイルのみをSSDに自動配置するため、SSDの使用量を抑えつつ、ファイルアクセスの高速化が可能である。また、ユーザはSSDとHDDのどりたにファイルが配置されているか意識しなくてよい。UECFSは、UnionFSを拡張して実装した。UnionFSは、Linux向けに実装されているファイルシステムであり、異なる複数のディレクトリを重ねてマウントし、単一のディレクトリの様に扱うことが出来る。UECFSは、UnionFSの機能を利用して、SSD上のディレクトリとHDD上のディレクトリを重ねてマウントし、独自のファイル自動配置機構により、ファイルアクセスを高速化する。UECFSをLinux Kernel 2.6.30.10に実装し、実験を行ったところ、ファイルがSSDに自動配置されることにより、ファイルアクセスが高速化することを確認した。

著者

岩崎 英哉 中野 圭介 鵜川 始陽

出版者

電気通信大学

雑誌

基盤研究(C)

巻号頁・発行日

2011

---

本研究は,サーバ側で実用的な性能で動作する サーバサイドJavaScript処理系を開発することにより,煩雑な Web アプリケーション開発のコストを大きく低減させることを目指し,以下の成果を得た.(1) プログラムの実行情報を利用した最適化を行い実行速度を向上させるJavaScript処理系を構築した.(2) JavaScriptプログラムとC言語で記述されたプログラムとの連携を可能とする機構を構築した.(3) イベント駆動方式サーバのための並列JavaScript処理系を設計し実装した.(4) JavaScriptプログラムの安全な実行の基礎となる型システムを構築した.

著者

森川 和哉 鵜川 始陽 岩崎 英哉

雑誌

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

巻号頁・発行日

vol.6, no.1, pp.27-27, 2013-01-24

---

Jikes RVM上で,ビットマップマーキングを利用したマークコンパクトごみ集めを実装し評価した.マークコンパクトごみ集めで広く使われているLisp 2アルゴリズムでは,オブジェクトの移動処理のために,生きているオブジェクトをアドレス順に2回探索する.本手法は,オブジェクトの生存情報をビットマップを使って保持し,そのビットマップをスキャンすることによって,生きているオブジェクトを探索する.生きているオブジェクトが少ない場合,ビットマップ上ではゼロビットが連続しているため,この探索を高速化することができる.提案するごみ集めの性能をDaCapoベンチマークを用いて評価したところ,プログラムによっては,ヒープの使用率が低い場合に,Jikes RVMに標準で搭載されているマークコンパクトごみ集めよりも優れた結果を示した.

著者

鵜川 始陽 皆川 宜久 小宮 常康 八杉 昌宏 湯淺 太一

出版者

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

雑誌

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

巻号頁・発行日

vol.44, no.13, pp.72-83, 2003-10-15

---

実行にスタックを利用している処理系でファーストクラスの継続を生成する場合,スタックの内容をヒープにコピーするのが一般的である.スタックの内容をヒープにコピーする戦略には様々なものが提案されているが,実際の処理系の多くはスタック法を採用している.スタック法では継続の生成のたびに処理系のスタック全体の内容をヒープにコピーする.このように,スタック法は動作が単純なので簡単に実装でき,また他言語呼び出しをサポートした処理系でも利用できるという長所がある.しかし,継続の生成に時間がかかり,また,メモリ効率が悪いという欠点があり,利用の妨げとなる場合もある.本発表では,スタック法による継続の生成に対する効率化手法として,スタックのコピーの遅延を提案する.継続の生成によりコピーされるスタックの内容は,継続を生成した関数からリターンするまでスタック上にも残っている.したがって,スタックのコピーを継続を生成した関数からリターンするまで遅らせてもよい.もし,生成した継続が,スタックをコピーする前にごみになれば,スタックのコピーを省略できる.本発表では,さらに,スタックコピーの遅延により可能となる,継続オブジェクトの部分的共有も提案する.これらの効率化手法をScheme処理系に組み込んで性能を評価したところ,継続を使ったプログラムの実行効率が改善された.In order to capture first-class continuations, most stack-based implementations copy contents of the stack to the heap. While various implementation strategies for copying are proposed, most implementations employ the stack strategy. With this strategy, the entire stack contents are copied to the heap whenever a continuation is captured. This simple strategy is easy to implement and can be used for implementations with foreign language interface. However, continuations with this strategy spend a lot of time and memory for their creations and invocations, and this week point often discourages programmers from using first-class continuations. We propose a lazy stack copying technique. The contents of the stack to copy will be preserved on the stack until returning from the function that is capturing the continuation. So we delay stack copying for a continuation until the function returns. We can avoid stack copying if it is detected that the continuation became a garbage before the function returs. In addition, we propose another technique, partial sharing of the copied stack, which is realized by using the lazy stack copying technique. We applied these techniques to Scheme interpreters and found that the proposed techniques improve runtime and memory efficiency of programs that use continuations.

著者

米田 匡史 鵜川 始陽 花井 亮 八杉 昌宏 湯淺 太一

出版者

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

雑誌

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

巻号頁・発行日

vol.47, no.11, pp.38-49, 2006-07-15

---

リージョン推論と呼ばれる静的にオブジェクトの寿命を見積もる手法に基づくメモリ管理が,Tofteらによって提案されている.リージョン推論に基づくメモリ管理では,オブジェクトはリージョンと呼ばれるメモリブロックのいずれかに生成される.リージョンは特定のスコープを抜けると解放され,そのリージョン内に生成されたオブジェクトも同時に解放される.そのため,再帰呼び出しのように,関数呼び出しが連続する場合にはリージョンの解放ができない.Tofteらの処理系では,今後の計算においてアクセスされる可能性のあるオブジェクトが入っていないリージョンにオブジェクトを生成する際に,そのリージョンに入っているオブジェクトに上書きして生成しようとしている.しかし,関数がリージョンをリージョン変数に受け取ることができるため,リージョン変数のエイリアスが生じ,静的にオブジェクトを上書きしてもよいと判定できる箇所が限られる.本論文では,問題となるエイリアスが存在するかどうかを,実行時にオブジェクトを生成する際に調べる手法を提案する.これにより,Tofteらの手法では上書きしてよいか分からなかったオブジェクト生成の箇所で,より厳密に判定できるようになる.その結果,メモリ効率が向上し,これまで妥当なメモリ使用量で動かなかったプログラムが動くようになると期待される.A technique for memory management based on region inference, which statically estimates the life-time of objects, was proposed by Tofte, et al. With this technique, objects are created in one of the memory blocks, called regions. Each region is deallocated when the control flow exits its corresponding scope and all objects in the region are deallocated at that time. This means that systems cannot deallocate regions while function calls are repeated without returning. This often happens in the case of recursive function calls. Tofte implemented a system which creates a new object by overwriting existing objects in a region if the region has no object that might be accessed in the rest of the computation. However, there are not a few points of object creation at which his static analysis cannot find it possible to overwrite. This is because functions may receive regions as region variables and there may be aliases of region variables. In this paper, we propose a technique to improve memory usage by checking the existence of problematic aliases at runtime. Our technique can determine exactly whether it is possible to overwrite in many points of object creation where Tofte's analysis fails. As a result, we expect more programs to run with a relatively small amount of memory in region-based systems.