ワークスアプリケーションズでのアルバイトでFindbugsへ入力するjarファイルを分割するという課題に取り組んでいました。 一区切りついたので試行錯誤なども含めてまとめておきます。
FindBugs - Find Bugs in Java ProgramsとはJavaのプログラムのバグを発見する オープンソースな解析ツール。
FindBugs Downloadsからダウンロード・解凍して
java -jar lib/findbugs.jar -textui myjarfile.jar
で解析ができる。オプションの-effort:max, -effort:minで
解析レベルを指定することができる。
FindBugsには、並列実行の機構がないので、 巨大なjarファイルを入力ではメモリをたくさん使う、計算時間が長いという問題があります。
そこで、jarファイルをクラスの依存関係に基づいて分割し、複数のjarファイル を別のマシンで並列に実行したり、一つのマシンでも一つずつ実行することで 上記の問題を解決しようというアイデアがあって、このアイデアを実現するために、 jarファイルを分割するプログラムを書くことになりました。
FindBugsと同じようにプログラムのバグを発見するソフトとしてcoverity がある。こちらは商用でソースは公開されていないが、並列に検証する仕組みがあるようだ。
今回作ったプログラム(JarSplit)は、大きな一つのjarファイルを受け取り、 分割した複数のjarファイル出力します。 大まかな流れは次のようになります。
- jarファイルを読み込む
- jarファイルに含まれる各classファイルをASMを使って読み、依存関係を求める
- 依存関係に基づき、classファイルを複数のクラスタに分割する
- 各クラスタからjarファイルを書き出す
分割結果としてFindBugsできちんと解析できるようなjarファイルを出力するために、 クラスAがクラスBに依存している場合、クラスAを含むjarファイルにはクラスBも含まれるように 出力する。
基本的にクラスAはクラスA内で出現するすべてのクラスに依存するとした。 これには、継承関係、フィールドの型、メソッドの引数・戻り値、 メソッド内で用いられる変数の型が該当する。例えば
public interface A0{}
public class A1{}
class B0 extends A1 implements A0{}
class B1 extends A1{}
class C{
public void runA1(A1 a1) {
a1.start();
}
}
というようなモジュール構造の時、次のような依存関係が導出できる。
dependency = {
'A0': {},
'B0': {'A0', 'A1'},
'B1': {'A1'},
'C': {'A1'}
}
ここでjava.util.ArrayListなど自分で記述していないクラスはこの依存関係には現れない。
次に、CはrunA1の引数としてA1クラスを受け取るが、
実際にはB0やB1のオブジェクトが渡される可能性もある。これを踏まえて依存関係を、
'C': {'A1', 'B0', 'B1'}に更新する。
これはモジュール構造に出現するis-a関係だけを集めた
super2subs = {
'A0': {'B0'},
'A1': {'B0', 'B1'}
}
と先ほどのdependencyを使って、
for superName, subNames in super2subs.items():
for key, values in dependency.items():
if superName in values and key not in subNames:
values.upadte(subNames)
として計算することができる。
jarファイルはjava.util.jar.JarFile, java.util.jar.JarEntryなどを使って読み込んで、
内部のclassファイルを読み込む。
最終的にclassファイルを出力する必要があるので、バイト列として保存しておく。
参考サイト:
ASM - Home Pageという便利なツールがあるので、これを使って classファイル（バイナリ）を読んでいく。 (ASMは2013/10/29現在4.2がリリースされている)
ASMと同じようとのものとしてApache Commons BCELがある。 最初はこちらを選んだのだが、ドキュメントが少ないことその他諸々あってASMに切り替えた。
ASMはドキュメントが充実している。
特にTracking Class Dependencies with ASM Visitorsの部分が自分の用途にピッタリの内容だった。
注意：チュートリアルはASM2.0系に基づいて記述されている。 ver2ではHogeVisitorはInterfaceとして定義されているが、 ver4ではHogeVisitorがclassとして定義されているという違いがあるので注意。 具体的には、チュートリアルの以下のクラス定義はHogeVisitorがinterfaceで定義されていることを 利用して、自分が作るVisitorを一つのクラスでまとめて書いている。 これはver4ではできないので、それぞれについてHogeVisitorを継承したクラスを 定義する必要がある。
public class DependencyVisitor implements
AnnotationVisitor, SignatureVisitor,
ClassVisitor, FieldVisitor, MethodVisitor {
APIドキュメントOverview (ASM 4.0 Documentation)
- ClassVisitor(http://asm.ow2.org/asm40/javadoc/user/org/objectweb/asm/ClassVisitor.html)
- MethodVisitor(http://asm.ow2.org/asm40/javadoc/user/org/objectweb/asm/MethodVisitor.html)
- SignatureVisitor(http://asm.ow2.org/asm40/javadoc/user/org/objectweb/asm/signature/SignatureVisitor.html)
（ここで、SignatureVisitorだけパッケージが違う、これはGenericsに対応するためのもの。）
APIドキュメントのHogeVisitorの最初の方にvisitXXメソッドがどの順番で呼ばれるかが書いてある。 これを読みながら、必要なvisitXXメソッドをオーバーライドしていく。
依存関係はノードがクラス、有向エッジが依存関係を表すグラフになっている。
自分で書いたクラスの中で他のクラスから参照されていないクラスをルートクラス（ルートノード）と呼ぶ。 ルートクラスの数はプログラムによって変わるが、今回対象とした大規模プログラムでは 4000程度のルートクラスが存在した。
あるノードから到達可能なノードを深さ優先探索で全部集めることで、 あるクラスが依存しているクラスをすべて集めることができる。 全てのルートクラスについて依存しているクラスを集めれば、最小のjarファイルが ルートクラスの個数分出来上がる。
しかし、4000個のjarが出来上がるのは現実的ではない。
どのように分割すればいいのか考える必要があった。 （当初はjava.で始まる依存関係も保持していたためグラフのエッジ数・ノード数が 多かったので計算速度ということも気にしなければならなかった）
そこで、各ノードにそのノードが依存しているすべてのノードをメモするアプローチを試みた。
最終的には採用されなかったが、 各ノードに自分の依存関係が決定した瞬間に、自分に依存している ノードに自分の依存関係をマージするようなアルゴリズムを実装した。
グラフに対してメモ化するのは難しいので、グラフを強連結成分分解して、 木にしてからメモ化するというアプローチも試みた。
強連結成分分解はSpaghetti Source を参考にJavaで実装した。
しかし、この強連結成分分解の計算時間も既に長すぎるため採用されなかった。
このアルゴリズムをやっている最中グラフが大きいので コールスタック不足が発生した。 深さ優先探索がStackで書き換えることでコールスタック不足を解消できるということ、 このアルゴリズムも基本的には深さ優先探索であるということから、Stackで書き直そう と思ったが難しくてできなかった。（jvmの引数で解決したというのもある。） 未だにこの書き換えには興味がありできないかなって考えてる。
最終的にルートノードの数が多すぎるのが問題だということで、 定数個（3とか10くらい）のダミーノードを作り、ルートノードをダミーノードの 子ノードにすることで深さ優先探索の回数を定数回に抑える方法を思いついた。
今回対象としたプログラムでは、各ルートクラスが依存しているクラスが多い。 また、異なるルートクラスの依存しているクラスの共通部分が大きいという性質が あったので、ダミーノードに対する深さ優先探索の時間が ルートノードに対する計算時間と比べてそこまで長くならなかった。
ルートクラスがR0, R1, ..., RnをダミーノードD0, D1, ..., Dkに振り分ける(n>>k)。 この振り分け方によって、深さ優先探索の計算時間と出力されるjarファイルの大きさが 大きく変わるので賢い振り分け方を検討しなければならない。
大前提として、同じダミーノードに振り分けるルートノードは依存しているノードの 共通部分が大きくなるのが好ましい。 しかし先ほども述べたように、実際にルートノードが依存しているノードは計算することができない。 そこでルートクラスが直接依存しているクラス（一次クラス）の共通部分で考えることにした。
あるクラスの依存関係は要素が0,1のベクトルで表現出きるので、 ベクトルのクラスタリングとして解くことにした。 今回ベクトルサイズ（一次クラスの数）が6000弱、ベクトルの数（ルートクラスの数）が4000弱 なので高速なクラスタリングアルゴリズムであるK-means法を 改善したK-means++法を用いることにした。
K-means法ではクラスタの中心(centroid)の初期値を乱数で決めていたのを、 K-means++法ではなるべく離れたベクトルを選ぶように改良している。 よって初期centroidはクラスタリング対象のベクトルの部分集合となる。
参考サイト：
この一次クラス使ったK-means++法のクラスタリングはそこそこいい成果がでて、 今までよりすごく速くなったし、出来上がったjarファイルも一部はきちんと小さくなって 確かに依存している部分だけでうまいこと切り分けることができてることがわかった。
しかし、いくつかのjarファイルは元のjarファイルと比べてそれほど小さくならなかった。 これはK-means++法で一部のクラスタに多くのルートノードが入っていることが原因だ。
例えば
v1=[1, 1, 1, 1, 0, 0, 0, 0], v2=[1, 1, 0, 0, 1, 1, 1, 1]
という二つのベクトルが同じクラスタになると、
[1, 1, 1, 1, 1, 1, 1, 1]とすべての一次クラスに依存したクラスタになり、
これではこのクラスタから出力されるjarファイルは元のjarファイルから
このクラスタに属していないルートクラスを除いた程度にしか小さくならない。
cfm.jar(25MB)を5つに分割した場合、次のように分割された。
- jarsample0.jar 23M
- jarsample1.jar 7.3M
- jarsample2.jar 2.2M
- jarsample3.jar 693K
- jarsample4.jar 1.3M
それぞれについてfindbugsを
time java -jar lib/findbugs.jar -textui ~/workspace/JarSplit/jarsample0.jar > ~/workspace/JarSplit/time_0.txtで実行した時の時間は
- cfm.jar 991.94s user 4.40s system 128% cpu 12:57.62 total
- 0: 891.94s user 3.02s system 159% cpu 9:22.12 total
- 1: 374.84s user 1.70s system 139% cpu 4:30.89 total
- 2: 144.37s user 0.91s system 208% cpu 1:09.59 total
- 3: 80.91s user 0.58s system 234% cpu 34.700 total
- 4: 109.31s user 0.69s system 174% cpu 1:03.22 total
となった。
各クラスタに割り振るベクトルの数やベクトルの大きさを考慮した高速な クラスタリングについてご存知でしたらぜひ教えてください。
高速化・生成jarを小さくするために依存関係の見直しも行った。 当初は自分が実装していないクラスでも、java.lang.Object以外はすべて 依存関係に含めていた。これをjava.で始まるものをすべて無視した場合も考えた。 でもこれが適切かどうかはもう少しきちんと検討しないといけない。
当初java.で始まるクラスに関しても依存関係を保持していたため、ルートクラスが 依存するクラスを全て取得するという（深さ優先探索）のコストがかなりありました。 そのため、メモ化・強連結成分分解といった高速に探索する方法を模索し、そして グラフが大きいのでこれらもうまくいかず、最終的にダミーノードを使うという 方法に至りました。しかし現在java.を無視した実装になったので、先ほどの方法が使える かもしれないということがあります。 また、最初にルートクラスが依存するクラス全部を調べてからの分割ということも可能 かもしれません。こういった部分については今後の課題としておきます。
最後に、ベクトルやクラスタのサイズを気にしたクラスタリングに関しては修士論文の方でも 模索しているところです。アドバイスありましたらよろしくお願いします。