2014年2月12日水曜日

PHREAKアルゴリズムを使った Drools 6 のパフォーマンス

原文: Drools 6 Performance with the PHREAK Algorithm by Mark Proctor (Drools & jBPM)

Drools 6 では新しく lazy matchingアルゴリズムが導入されました。アルゴリズムの詳細については、以前 2つの記事で紹介しました。

さらば RETE、PHREAKの時代だ
Drools: PHREAK スタックベースの評価(Stack Based Evaluations)と逆行連鎖化(backward chaining)
※リンク先の記事は、和訳する予定です

最初の記事ではパフォーマンスについてと、アルゴリズムが持つバッチ処理と遅延評価機能がもたらすパフォーマンスを既存のアルゴリズムと比較することが何故難しいか説明しています。
パフォーマンスについて、最後に1点触れます。一般的に 1つのルールを評価するにあたり、RETEよりもPHREAKが早く動作することはありません。投入されたルールとデータセット(マッチングのオン/オフをコントロールするルートコンテキストオブジェクトが存在する前提)に対しては、どちらのアルゴリズムも同じ分評価し、ルールインスタンスを生成し、だいたい同じ処理時間が発生します。subnetwork と accumulate が使われるユースケースは別です。

下手に書かれたルールが増え複雑性が増すと、RETEのパフォーマンスは劣化しますが、PHREAK はさほど影響を受けません。

RETEはその他、すべてジョインされた中でデータを保持しないルールに対し、パーシャルマシンを生成することをやめてしまいます。PHREAK はこのような動作をしません。

よって、PHREAK は RETE より高速であるというわけではありません。運用されているシステムの規模が拡大しても、同じペースでパフォーマンスが低下しないということです :)

最近、OptaPlannerチームは ReteOO と Phreakに対して同じルールを使い、ベンチマークを取り始めました。
ルールエンジンのアルゴリズムはどっちが速い? ReteOO? Phreak?

記事によると、Phreak は ReteOO に比べ 3つのテストでは 20%高速で、1つのテストでは 4%低速でした。記事に記載されたコメントによると、17%のパフォーマンス差があったそうです。

OptaPlannerチームは、利用されたルールが Reteの制限に触れていないか、かなりの時間を使い確認しました。彼らは複数のバグを修正しました。例えば、1つのルールに複数の accumulate が存在する状況です。

あるユーザーは、ReteOO で問題となる書き方を使いルールを実装したらどうなるか興味を持ちました。Phreak がどれだけ優秀に処理するか気になったのです。彼は 4つルールを作成しました。個々のルールには 2つ accumulate があります。こちらからDRLファイルをダウンロードしていただけます。ルールのコピーを1つ掲載します。

rule gold_account
when
  account: Account()
  Number(this >= 50000) from accumulate(t: Transaction(source == account); sum(t.amount))
  Number(this >= 50000) from accumulate(t: Transaction(target == account); sum(t.amount))
then
  //System.out.println("Gold account: " + account);
end

結果は期待された通り、Phreak を使用すると 500%(5x)のパフォーマンス向上が計測されました : ) これは主に、Phreak がバッチでルールを評価し、たくさんの無駄な作業を辟けられたことに起因します。数段落前で別の記事の内容を引用しましたが、そこで述べられた狙いが当たった良い例と言えます。
下手に書かれたルールが増え複雑性が増すと、RETEのパフォーマンスは劣化しますが、PHREAK はさほど影響を受けません。

あなたもこのベンチマークを試されたい場合、こちらからプロジェクトをチェックアウトしてください。
https://github.com/winklerm/phreak-examples

このアルゴリズムはいまのところ、正確性と将来のマルチコア対応を考慮したスレッドの安全性に力を入れて設計されています。よって、まだ始まりに過ぎません。私達はまだ、たくさんの最適化案や改善案を持っています。

原文: Drools 6 Performance with the PHREAK Algorithm by Mark Proctor (Drools & jBPM)

0 件のコメント:

コメントを投稿