netail.net

_ 炊飯ジャー ▲

煮物も作れる炊飯ジャーというヘッドラインに惹かれて見てみた．http://nikkeibp.jp/wcs/leaf/CID/onair/jp/mech/313078

煮物作ってるとご飯が炊けないと思うのだけど．

_ [論文] 動的スライス＋プログラムの逆実行 ▲

ICSE 2004 Technical Papers, Slicing より．

Tankut Akgul, Vincent J. Mooney III, and Santosh Pande:A Fast Assembly Level Reverse Execution Method via Dynamic Slicing.Proceedings of ICSE 2004, pp.522-531.

Reverse Execution (逆実行) というのは，プログラムを前の状態に戻すように実行していく手法．普通にやると，途中で捨てられていく情報を保存しておかないといけないので，激しくメモリを消費する．そこで，動的スライスを使って，注目してる部分に関連したところだけが回復すればいい，と割り切った手法．

命令の逆転についても，全部の状態を保存していくのではなく，命令列に対して逆命令列を生成する方法を用いるので，各時点でのレジスタ値を保存する方法よりは経済的になっている．

逆実行がどのくらい役立つかは Agrawal か誰かが研究してたような気がする．特定の値だけ復帰させて，もう一度そこだけ細かく実行して，とかできると，かなり面白いデバッグ作業は展開できる気はする．一度ブレークポイントで止めて「システムの状態を保存」とか指示するのと，後から「戻ってみよう」というのとで，どのくらい開発効率が違うのかは分からないが．

_ [論文] 動的スライス用の実行履歴圧縮 ▲

ICSE 2004 Technical Papers, Slicing より．

Tao Wang, Abhik Roychoudhury:Using Compressed Bytecode Traces for Slicing Java Programs.Proceedings of ICSE 2004, pp.512-521.

Java バイトコードの実行履歴を，RLESe とかいう文から文法を構成するタイプのアルゴリズムで圧縮して，圧縮した状態でも実はそのままスライス計算ができますよーという論文．

動的スライスはコストさえ何とかすれば使える，というふうにみんな考えているのだろうか．静的スライスに比べて研究が活発な気がする．

_ [論文] 動的スライスのメモリ節約 ▲

ICSE 2004 Technical Papers, Slicing より．

Xiangyu Zhang, Rajiv Gupta, Youtao Zhang:Efficient Forward Computation of Dynamic SlicingUsing Reduced Ordered Binary Decision Diagrams.Proceedings of ICSE 2004, pp.502-511.

動的スライスの Forward Computation （１ステップ進むごとに，その時点でのスライスを計算して蓄積していく手法）を使うとき，メモリ消費量を抑える方法の提案．

Binary Decision Diagrams は各ノードが０と１のエッジ（２本だけ）を持っていて末端ノードが０または１でラベル付けされている．で，プログラムスライスはスライスに含まれるIDの集合なので，開始頂点から，IDを表現する２進数（0110とか）で表現されるパスをたどっていくと，末端が０か１かでそのIDがスライスに含まれているかいないか分かる．

で，この論文では，reduced-ordered BDD という，途中のノードをできるだけ共有・省略した状態にすることで各スライスの中身を共有して，全体のデータ量を減らしている．すべてのスライスを合計すると200GB相当のデータになるところが400MB程度で収まるとか．

加えて，スライス基点情報の圧縮とかも何かやっているらしい．（これは去年のICSEで発表されたものっぽい）

プログラムの実行時間については，一番大きい材料（67000LOCくらい）で５時間くらい．一度計算してしまえば好きなだけ動的スライスを取得できるのでおいしいといえるか？

個人的には，ちょっと修正→再実行→スライス計算みたいなやり方で使いたいのであまりうれしくないのだが，空間コスト的には非実用ではなくなった分についてはすごい．CPUがさらに高速化すれば本気で実用になってしまうかも？