テストステ論

高テス協会会長が, テストステロンに関する情報をお届けします.

平安京ビューに対する性能測定. Pythonは速くなっていた

平安京ビューの性能を測定しようと思います. どのようなベンチマークが良いでしょうか?性能測定は簡単な仕事ではありません. それは, 自動化出来ない部分が多く手間だからということではありません. どういう観点で測るか, その観点で性能を測定する場合にもっともシンプルで, 外因の少ないベンチマークは何か. 例えばカーネルを例にとると, それは様々なレイヤーが複雑に関わっているため, 良いベンチマークを考えることはとても難しいですが, 平安京ビューは簡単です.

平安京ビューのコアなアルゴリズムは, 長方形を一つ一つ配置していくところにあります. したがって, RectaglePackingクラスのインスタンスに対して長方形を1つずつ加えていくテストが良さそうです. 純粋なテストとしてはそれで良いですが, 見る人には, 「で, 一体平安京ビューはどれだけ速いんだ?」という疑問が残ります. 平安京ビューの最終目的はツリー上のノード幾何情報を計算することですから, そこまでやり切る方が良いと思います. 純粋すぎても良くなく, 実際の利用方法に合った測定をしなければ, 測定としての純度が高くても説得力に欠けてしまいます.

というわけで, one layer packingというベンチマークを考えます. これは, 深さ3の木に対してTreePacking#pack()を適用した時の時間を計測するものです. この木のlevel=2(ルート直下)には, N個の枝ノードがついています. そして, それらの下にはそれぞれ, 10から1000個の, 乱数生成によって選ばれた個数のリーフノードがついています. level=2のノードの(w,h)は様々なので, 仮に, リーフノードの配置計算が十分に小さいとすると, 上記した純粋なテストがここで実現出来ることになります. 実際はそうはならないのですが, この木自体が十分に典型的なので, 性能の評価としては妥当です. このベンチマークを, Nを100,200,...,1000と変化させて実行します.

以下が, 平安京ビューの現状の性能です. CPUはi7 3770で, メモリは32GB積んでいて, データは実行中に完全に乗り切っています. 非常に遅いと思います. 遅い理由は, リーフノードをまじめに配置しているからだと考えます. リーフノードは全部同じ大きさの正方形であるため, 配置は単純な計算で求められます. 卒論で測った時には, N=1000の時に0.5sec程度でしたから, 100倍以上遅いという結果です. このレベルの差は, 前述した最適化を施しても埋められないかも知れません*1.

f:id:akiradeveloper529:20130621221231p:plain

特記することは以下です.

  • 傾きはほとんど線形です. アルゴリズムの特徴です. 長方形の配置を一瞬で決定しています. それでいて, 以前にLinuxソースツリーの可視化で見せたように, まぁまぁ充填しているというのが, 私の平安京ビューの特徴です*2. 可視化なので, ぎゅうぎゅうだから良いというわけでもありません. 可視化ならではのアルゴリズムなのです.
  • Python2.6と2.7で測ってみましたが, 2.7の方が20%程度速いということが分かりました. 明らかに言語レベルでの性能最適化がなされています. 何が起こったのか分かりませんが, (たぶんグーグルの?)言語野郎どもは素晴らしい仕事をするなと感心した.

以上です. 最適化実装をしたあと, また性能を測ってみたいと思います.

*1:理想的な計算では, 500倍速くなりそうですが

*2:オリジナルのは, 線形ではなく, Nが増えるとどんどん悪くなっていきます