研究速報
500

大平直宏†

石尾隆†

楠本谷口 考治†神谷 年洋††（正員）

真二†（正員）井上 克郎†（正員）

Division Method of Object-Oriented Program Execution Traceby Detecting a Shift of Operating Objects

Takashi ISHIO , Nonmembers, Toshihiro KAMIYA

††

2600

200
150
100
5000500
図1

Naohiro OHIRA† , Koji TANIGUCHI† ,†

動作オブジェクト群の変化に着目したオブジェクト指向プログラムの実行履歴分割手法

ID

250t

1000

1500t

2000

2500

3000

    

動作するオブジェクトの時間による変化
Fig. 1 Shift of operating objects,Shinji KUSUMOTO† , and Katsuro INOUE† , Members†

大阪大学大学院情報科学研究科，大阪府豊中市

オブジェクト群の変化に着目することで，実行履歴をGraduate School of Information Science and Technology,††Osaka University, Toyonaka-shi, Osaka, 560-8531 Japan

意味のある機能単位で分割する手法を考案した．本手

独立行政法人 産業技術総合研究所，東京都千代田区

法を用いて分割した実行履歴は，プログラムの機能単

National Institute of Advanced Industrial Science and Technology, Chiyoda-ku, Tokyo, 101-0021 Japan

位を無視した分割とは異なり各ブロックが機能単位で意味的に完結しているため，各ブロック単位でのプログラム解析・可視化手法 [4] の適用が容易になる．

あらまし

本論文では，キャッシュアルゴリズムを2. 動作するオブジェクトの時間変化例

用いることで最近動作したオブジェクト群の変化を捉

一般にプログラムの 1 つの実行履歴は，初期化部やえ，オブジェクト指向プログラムの実行履歴を機能単ユーザ入力部，GUI 出力部など，いくつかの機能単位位毎に分割する手法とその可能性について述べる．

から成り立っている．そして，それらを実現するオブキーワード Java プログラム，実行履歴，動的解析

1. ま え が き

ジェクト群は各機能に固有である可能性が高い．
そこで，著者らの 1 人が作成した，入力された Java

オブジェクト指向プログラムでは，動的束縛等によっプログラムのプログラム依存グラフを出力するツールて実行時に決定される要素が多いため，その理解にはの実行履歴を用いて，時間の経過とともにオブジェクプログラムの実行履歴のような動的情報の利用が有効

トの動作状況が変化する様子をグラフ化した．図 1 は，である [4]．しかし，取得した実行履歴には，一般にそ時刻 t（実行履歴中の t 番目）のメソッド呼び出しに関のサイズが巨大になってしまうという問題がある [3]．

して，呼び出し元と呼び出し先のオブジェクト ID をこの問題を解決する 1 つのアプローチとして，実行プロットしたものである（総オブジェクト数=229，総履歴を複数のブロックに分割する手法が考えられるが，メソッド呼び出し数=2835）．この図より，約 500 番

プログラムの機能的なまとまりを無視した，一定時間目，2600 番目のメソッド呼び出しを境界として，大き区切りでの分割は望ましくない．また，ハードウェア

く 3 つのオブジェクト群が存在するのが分かる．そしパラメータの動的再設定を目的として，時間消費量やて実際に，1〜500 番目，500〜2600 番目までの部分機械命令実行回数などのメトリクスを用いた分割手法

は入力データを個別処理する部分に，2600 番目以降が数多く提案されているが [1]，パフォーマンスチューはファイル出力部に対応していることが確認できた．

ニングを目的とした手法を，プログラム理解を目的と

3. 実行履歴の分割手法

した分割手法へそのまま応用することはできない．あ2. で調べたように，実行履歴を時間順に追跡すると，

るいは，各クラスの被メソッド呼び出し回数からなるプログラムの異なる機能単位に処理が移った部分で，ベクトルによって機能単位を特徴づけ，その境界を特動作オブジェクト群の大きな変化が予想される．

定する研究もあるが [2]，オブジェクト指向プログラム

そこで，サイズ Size のキャッシュC を用いた以下ではクラスが同じでも異なるオブジェクトに対するメのアルゴリズムを用いることで，これら各機能の境界ソッド呼び出しは振る舞いが変化するため，クラスに部分を特定する．この手法は，各時刻 t でメソッド呼着目した手法は必ずしも適切であるとは言えない．

び出しに関与したオブジェクトの ID（呼び出し元をそこで我々は，Java プログラムのメソッド呼び出しCaller(t)，呼び出し先を Callee(t) とする）をキャッ履歴を対象とし，プログラムの実行中に動作しているシュで記憶していき，キャッシュ中のオブジェクトの電子情報通信学会論文誌

D–I Vol. Jxx–D–I No. xx pp. 1–3 xxxx 年 xx 月

1

電子情報通信学会論文誌 xxxx/xx Vol. Jxx–D–I No. xx

入れ替わり頻度が大きくなる部分で実行履歴を分割す

OLD

kflag(k)=0k+1aるというものである（last は実行履歴のサイズ）．

a     NEWbcd:
k : …
k+1: efk+2: fb
k+3: agk+4: …

e（ 1 ） C(0) ← φflag(k+1)=1（ 2 ） for t in [1 . . . last]（3）C(t) ← add(C(t − 1), Caller(t), Callee(t))（4）

C(t) の更新有無 f lag(t) を調べる

（5）

C(t) の更新頻度 ratio(t) を計算する（ 6 ） ratio(t) が閾値 threshold を超えた時刻 t で

k+2flag(k+2)=0

k+3

c d



bcdefcdefbefbag

ratio(k+2)= 1/3

flag(k+3)=1分割する

ratio(k+3)= 2/3

図 2 アルゴリズムの動作例
Fig. 2 Example of the algorithm(3) では，手続き add によって，時刻 t − 1 におけるキャッシュC(t − 1) へ時刻 t で動作したオブジェクトの ID（Caller(t)，Callee(t)）を新しく追加し，更新

つまり，キャッシュにヒットせず空きもなければ，新しいオブジェクト ID の代わりに最も古くから記憶されているものを捨てる．ヒットした場合は，キャッシュに記憶されている集合自体は変化しないが，各要素の 

後のキャッシュを C(t) とする．このとき，キャッシュの更新は Least Recently Used アルゴリズムに基づく．

10.8
0.6
0.4
0.200500t

1000

1500

t

2000

2500

3000

    

図 3 キャッシュの更新頻度
Fig. 3 Ratio of cache’s update

順序は入れ替わることに注意されたい．

(4) では，時刻 t におけるキャッシュC の更新有無

ない．更新頻度については，ratio(k + 2) は過去 3 回

f lag(t) を次のように計算する．つまり，それまで記中 1 回更新が起こっているので 1/3，ratio(k + 3) は憶されていないオブジェクト ID が少なくとも 1 つ追過去 3 回中 2 回更新が起こっているので 2/3 となる．

加されたとき，キャッシュが更新されたとみなす．

 0 if (t <= 0) orf lag(t) =(∀x ∈ C(t) ⇒ x ∈ C(t − 1)),

 1 otherwise.

そして (5) では，f lag(t) を基に時刻 t におけるキャッ4. 適 用 事 例
図 1 の実行履歴に対し，提案手法による分割を試みた．分割結果が適切であるかを判断するために，結果を対象プログラムの開発者に見てもらい，開発者が意図していた処理の区切りと，提案手法による分割結果がどの程度一致しているかを評価した．その一例とシュの更新頻度 ratio(t) を次式によって計算する．こして，Size = 50, n = 20, threshold = 0.5 として計こで，n は過去何回分のメソッド呼び出しにおける更算した更新頻度 ratio(t) を図 3 に示す．ここで，各パ新回数を平均するかを表すパラメータであり，以後ラメータの値は経験的に設定したものであるが，パラウィンドウサイズと呼ぶことにする．

メータ設定に関する考察は 5. で述べる．

∑tratio(t) =この例からは，システムの異なる機能単位に処理がx=t−n+1

f lag(x)n移行したと考えられる部分で，実際にキャッシュの更新頻度が高くなっていることが確認できた（約 500，

例えば図 2 は，同図中右の実行履歴（アルファベッ

2600 番目）．アルゴリズムの特性上，2600 番目付近

トはオブジェクト ID，矢印はメソッド呼び出しを表のようにオブジェクトの入れ替わりが更新頻度に反映す）に対して，Size = 5, n = 3 とした場合のアルゴされるまでに多少遅れる場合もあるが，これは分割後リズムの動作例を表す．k+1 番目のメソッド呼び出しのブロックにマージンを持たせればさほど問題になら

では，キャッシュ中にないオブジェクト f が追加され，ないと考える．

更新が起こる．一方，k+2 番目では，共にキャッシュ

また，1700 番目付近のメソッド呼び出しで更新頻度中に存在するオブジェクト b，f が動作するため，保存が大きくなっている点について調べると，この部分は順序は変更されるが，キャッシュ自体の更新は起こら同じ入力を処理しているが，制御依存解析からデータ

2

レター依存解析へと処理が変化していることが分かった．つ「オブジェクト指向プログラムらしい」プログラムにまり，提案手法を用いることで，人が図 1 のみからで対しては適用が容易であると考えている．この点に関は判断できない機能境界も特定することができた．

しては，提案手法が適用可能なプログラムの性質とし5. 考察て今後明らかにしていく予定である．

適用事例で見たように，提案手法はキャッシュサイ

また，紹介した適用事例では各パラメータ値を経験ズ（1 <= Size <= 総オブジェクト数），ウィンドウサ<イズ（1 <n= = 総メソッド呼び出し数），および閾値的に設定するという方法をとったが，各種パラメータ（0 <= threshold <= 1）の 3 つのパラメータをもち，こラムの実行履歴に対して適用を行い，提案手法の詳細れらの値を適切に設定することでプログラムの機能境化・一般化を進める中で明確にしていく予定である．

を適切に設定する基準についても，今後様々なプログ文界を特定することができる．しかし，各種パラメータの適切な設定値に関してはまだ明確な基準がなく，経[1]Phase Detection Techniques”，36th Annual Interna-

験的に値を定めているのが現状である．

tional Symposium on Microarchitecture, pp.217-227,

今回紹介した適用事例の場合，キャッシュサイズ

Size をある程度以上（Size >= 30）大きくした場合

献

A.S. Dhodapkar, J.E. Smith，“Comparing Program

San Diego, USA, Dec. 2003.
[2]

Steven P. Reiss, “Dynamic Detection and Visualiza-

もグラフ形状がほぼ同じであったため，Size = 50 とtion of Software Phases”，Proceedings of the 3rd In-いう値を採用した．また，ウィンドウサイズ n に関ternational Workshop on Dynamic Analysis, pp.50-

しては，n を大きくするにつれてグラフの形状が緩や55, St. Louis, USA, May. 2005.
[3]

Steven P. Reiss, Manos Renieris, “Encoding pro-かになる，すなわち外れ値を無視できるようになる

gram executions”，Proceedings of the 23rd Interna-が，逆に大きくし過ぎると全てが平均化されてグラフ

tional Conference on Software Engineering, pp.221-の特徴が失われてしまうという問題がある．そのた

230, Toronto, Canada, May. 2001.
[4]谷口 考治，石尾 隆，神谷 年洋，楠本 真二，井上 克郎，め，メソッド呼び出し数が 3,000 回弱である今回の適“Java プログラムの実行履歴に基づくシーケンス図の作用事例では，n = 20 程度が妥当であると考えた．最成”，ソフトウェア工学の基礎 XI, 日本ソフトウェア科学

後に，閾値 threshold に関しては，動作しているオブ会 FOSE2004，pp.5-15，Nov. 2004.

ジェクトの半分が入れ替われば機能の担い手が変化し（平成 xx 年 xx 月 xx 日受付）たと考えるのに十分であること，及び threshold を小さくし過ぎると急激に分割数が増えることを考慮し，threshold = 0.5 という値を用いた．
このようにして 4. で紹介した適用事例では各パラメータを経験的に設定したが，これらの値は実行履歴をどの程度の数・サイズで分割したいかによって変化するものと考えられる．残念ながらこの事例のみでは他のプログラムに対しても同様のパラメータを使用できるという根拠にはならないが，上と同様のアプローチをとることによってある程度適切なパラメータ値を算出できると考えている．

6. まとめと今後の課題
本論文では，オブジェクト指向プログラムの実行中に動作するオブジェクト群の変化に着目することで，実行履歴を意味のある機能単位で複数ブロックに分割する手法を提案し，その適用事例を示した．
提案手法はプログラムの各機能を実現するオブジェクト群が異なることを想定しているため，今回紹介した解析系プログラムや，あるいはエンタープライズ系プログラムのような，各オブジェクトの役割が明確な
3

Abstract In this letter, we propose a method to divide an execution trace of object-oriented program
into several functional blocks, by using a cache algorithm which detects a shift of recently operating objects.
Key words Java Program, Execution Trace, Dynamic Analysis