協調動作するオブジェクト群に着目した Javaプログラムの実行履歴分割手法の提案大平直宏†，谷口考治†，石尾隆†，神谷年洋‡，楠本真二†，井上克郎† †大阪大学大学院情報科学研究科 ‡科学技術振興機構さきがけ 2005/3/22 電子情報通信学会総合大会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 発表の流れ  背景と目的 プログラムの実行履歴を用いたオブジェクト指向プログラムの理解支援とその問題点  提案手法 実行履歴の分割手法適用事例  まとめと今後の課題  2005/3/22 電子情報通信学会総合大会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 2 背景と目的 2005/3/22 電子情報通信学会総合大会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 3 オブジェクト指向プログラムの理解支援  プログラムの実行履歴(メソッド呼び出し系列)を取得し， UMLのシーケンス図として可視化  時系列にそってオブジェクト間のメソッド呼び出し関係を可視化  プログラムの実行時に決定する情報を可視化できるオブジェクト A(1).a() { B(1).b() { C(1).c1() { } C(2).c2() { } D(1).d1() { D(1).d2() { } } } 実行履歴 A-1 時間 B-1 C-1 C-2 D-1 シーケンス図 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 4 実行履歴を利用する際の問題点  プログラムの実行履歴のサイズは巨大になる プログラム中のループ，再帰構造によって実際に実行された全てのメソッド呼び出しを記録 全てを1つのシーケンス図として表現するのは望ましくない  実行履歴を複数のブロックに分割し，分割した各ブロック単位でシーケンス図として可視化したい → 動作するオブジェクト群に着目した実行履歴の分割手法を提案 2005/3/22 電子情報通信学会総合大会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 5 分割のアプローチと提案手法 2005/3/22 電子情報通信学会総合大会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 6 実行履歴分割のアプローチ  プログラムの1つの実行履歴はシステムの複数のフェイズを含み，各フェイズ毎に動作しているオブジェクト群は異なるはず   ユーザ入力 → 内部計算 → GUI出力プログラムの実行がシステムの異なるフェイズに入れば，動作しているオブジェクト群も大きく変化するはずオブジェクト A-1 動作するオブジェクト群の変化を捉えて分割することで，ある程度意味のある機能単位での分割が可能 B-1 C-1 C-2 D-1 X-1 X-2 X-3 Y-1 クラス B,C,D,… のオブジェクトがユーザ入力部を実現クラスX,Y,…のオブジェクトがGUI出力部を実現時間 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 7 実行履歴の分割手法キャッシュ・アルゴリズムを用いたフェイズ境界の特定  キャッシュには最近「動作した」オブジェクト群をオブジェクトIDで記憶   「動作した」 = メソッドを呼び出したか，呼び出された実行履歴中の各メソッド呼び出し毎に以下を実行    （呼び出し元オブジェクト，呼び出し先オブジェクト）の組をキャッシュに追加キャッシュ内の古いオブジェクトが捨てられたとき，キャッシュが更新されたとみなす（Least Recently Usedキャッシュ）キャッシュの更新頻度を計算 t番目のメソッド呼び出しに対するキャッシュの更新頻度 f(t) = 過去n回（[t-n+1, t]）のメソッド呼び出しでキャッシュが更新された割合    f(t) = 0 ⇔ 過去n回のメソッド呼び出しはキャッシュ内のオブジェクトのみ動作 f(t) = 0.5 ⇔ n回中n/2回キャッシュ内のオブジェクトが入れ替わったキャッシュの更新頻度大 ⇒ 異なるフェイズに処理が移行したとみなす Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 8 キャッシュ・アルゴリズムの動作例 OLD t番目 a NEW b c d e キャッシュサイズ = 5 更新頻度 = 過去3回の平均更新回数実行履歴（入力）更新 t+1番目 a t+2番目 b c d e f c d e f b d e f b a f(t+2) = 1/3 t: … t+1: e → f t+2: f → b t+3: b → a t+4: … 更新 t+3番目 c f(t+3) = 2/3 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 9 適用事例 2005/3/22 電子情報通信学会総合大会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 10 適用事例  単一の実行履歴に対して適用してみる 人間が考えたフェイズの境界で，実際にキャッシュの更新頻度が大きくなっているか  対象プログラムバイトコード解析ツール 入力として与えられた各メソッド毎に以下の処理を実行 Java 制御フローグラフ構築  制御依存関係の探索  データ依存関係の探索  各処理が明確に区分されている 2005/3/22 電子情報通信学会総合大会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 11 動作するオブジェクトの時間による変化各メソッド毎に，（呼び出し元，呼び出し先）オブジェクトの組をプロット１個データ処理制御フロー解析結果出力１個データ処理制御依存解析データ依存解析望まれる区切り Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 12 キャッシュの更新頻度  キャッシュサイズを50とし，過去20回分のメソッド呼び出しにおけるキャッシュの更新頻度f(t)を計測してグラフ化  更新頻度≧0.5となったのは5ヶ所 0.5 2005/3/22 電子情報通信学会総合大会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 13 処理の区切り更新のピーク人間が予想した結果とほぼ整合フェイズ開始直後にオブジェクトを作るフェイズ開始位置とキャッシュの更新ピークがずれることもある 2005/3/22 電子情報通信学会総合大会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 14 考察  「新しいオブジェクト」は，まとめて登場することが多い ユーザインタフェース用，データ表現用オブジェクトなど 新しいフェイズが始まったことは認識しやすい  キャッシュサイズの影響 キャッシュサイズが大きい ⇒ 「新しいオブジェクト」が登場しにくくなる  分割の単位が大きくなりやすい キャッシュサイズが小さい 2005/3/22 ⇒ その逆電子情報通信学会総合大会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 15 まとめと今後の課題  まとめ 動作するオブジェクト群に着目することで，プログラムの実行履歴を複数のブロックに分割する手法を提案 適用事例を紹介  今後の課題 他のプログラムの実行履歴に対する適用分割によってどのくらいサイズが減るのか  パラメータの影響がどのくらい大きいか  2005/3/22 電子情報通信学会総合大会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 16 おわり 2005/3/22 電子情報通信学会総合大会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 17