Googleが昔採用していたバグ予測アルゴリズムをやってみた
今回はGoogleが昔採用していたバグ予測アルゴリズムのもとになっているFixCacheについて書きたいと思います。
バグ予測アルゴリズム
かなり前の記事ですが、こんなものがありました。
元の記事はこちらです。
巨大なコードを一つのリポジトリで管理しているGoogleはバグ予測アルゴリズムによって、レビュー時にどのファイルをより注意深く見るべきかの指標を出していたようです。
アルゴリズムの説明
FixCacheというアルゴリズムについての説明はこの論文に書かれています。
執筆者は UC Davis の方のようです。
ではこのアルゴリズムの説明に入る前にキャッシュについて理解する必要があります。CPUはメモリへのアクセス時にキャッシュを使うことでI/O時間を削減することでより効率的に動作するようになっています。ここで理解するべきキャッシュの特性は、
- temporal locality
- spatial locality
の二つです。この二つの説明は僕のブログでしていますが、簡単にいうと
- 一度アクセスされたデータは近いうちにアクセスされる可能性が高い
- 一度アクセスされたデータの周辺にあるデータはアクセスされる可能性が高い
という意味です。
本題
ではFixCacheのアルゴリズムはどうなっているかというと、バグの発生とこのキャッシュの仕組みになぞらえて考えることができるというものです。先ほどの特性をバグに当てはめて見ると。
- 一度バグを修正されたファイルは再び修正される可能性が高い
- バグが発見されたファイルと一緒によく編集されるファイルはバグを含んでいる可能性が高い
というふうに言えます。さらに論文ではもう一つの churn locality というものを加えています。これは
- 最近編集されたファイルはバグがあるかもしれない
という感じです。おそらくこのポリシーはLRU(Least Recent Used)というコンピューターサイエンス用語で、最も最近使われていないものから交換するというキャッシュの更新法のことだと思います。
この３つのポリシーに従ってコミット履歴を見ていくことでバグの予測ができるというわけです。
実際にやって見た結果
コードがどこかにいってしまって載せられないのですが、弊社の古くからあるプロジェクトでコミット修正した基準を、コミットメッセージに修正またはfixという文字が入っているかどうかという基準でやって見たところヒットレートが50%でした。キャッシュに置くファイルの数を全ファイルの20%にしたら良いという記述があった気がするのでそれに従いました。
この結果は結構すごいいい感じかも？と思いましたが、原論文では完璧に評価するには
- バグ予測されたがバグはないファイル (FP)
- バグ予測されてバグのあるファイル (TP)
- バグ予測されてなくてバグのあるファイル (FN)
- バグ予測されてなくてバグのないファイル (TN)
を考えた時に精度は
Precision = TP / (TP + FP) = TP / InCache
というふうに考えられるという感じのこととか色々書いてありましたが、これは理論上のお話です。論文中でも実際の評価は普通のヒットレートを使用したようです。
実はもう使われていない
頑張って紹介して見ましたが、このアルゴリズムというよりもバグ予測ツール自体がもう使われていないようです。
- Bug Prediction at Google | Hacker News
- Does Bug Prediction Support Human Developers? Findings From a Google Case Study [Chris Lewis, 2013]
このようなバグ予測ツールがエンジニアにとってあまり有益な結果を出さなかったみたいです。
詳しいことはリンク先の論文やサイトを見るとわかると思います。
