ホーム/ドキュメント/PRQLとコードクエリ/CppDependのPRQLパフォーマンス

CppDependのPRQLパフォーマンス

このドキュメントは、読者が次に精通していることを前提としています LINQ構文に関するドキュメントを読んだ PRQL構文 Wikipedia の次の定義も参照してください時間計算量この概念の意味を知らない場合。

PRQL は、大規模な実際のコードベースに対して 1 秒間に数百のクエリを実行するように設計されています。これは、理論上、ほとんどの PRQL クエリが数ミリ秒で実行されるべきであることを意味します。実際には、ほとんどのクエリでこれは当てはまりますが、既定の PRQL クエリとルールのセットを見ると、大規模なコードベースで数十ミリ秒かかるものもいくつかあることがわかります。

PRQL クエリ実行時間のタイムアウトのデフォルト値は 2 秒ですが、この値は次の場所で簡単に変更できます ツールとオプションとコードクエリ パネル。

数十の既定の PRQL ルールとクエリのセットを作成する際に、複雑なクエリでも常に高速に実行できるように PRQL の設計を調整しました。

この作業の結果は本ドキュメントで共有されています。

パフォーマンスは PRQL にとって重要なトピックです。CppDepend ツールの哲学は、数秒以内にできるだけ早くユーザーに有用なフィードバックを提供することだからです。

常に線形時間計算量を目指す
可能であればシーケンス使用操作を使用
メインクエリループの前にサブセットを宣言
ハッシュセットを多用
メインクエリループで多くのlet句を避ける
多数の文字列定数でのパフォーマンス

常に線形時間計算量を目指す

何らかのネストされた処理を必要とする複雑なクエリを記述する場合、多くの場合、最も明白なアプローチはクエリを別のクエリの中にネストすることです。これは以下のクエリで示されています。ここでは、次の名前のメソッドを呼び出すすべてのメソッドに一致させたいと考えています追加:

1from m in Methods
2
3from users in Methods
4
5where m.SimpleName == @"Add" && users.IsUsingMethod(m)
6
7select users

このアプローチの問題は、低速な多項式時間計算量で実行されるクエリになることです（ O(#メソッド^2) ここ)。

ほとんどの場合、遅い多項式時間計算量を線形時間計算量に変換できます。たとえば、クエリは次のように書き換えられます。

1let addMethods =
2
3   from m in Methods
4
5   where m.SimpleName == @"Add"
6
7   select m
8
9
10
11from m in addMethods
12
13from user in m.MethodsCallingMe
14
15select user

クエリは線形時間計算量になりました O(#メソッド) そして実際には、数十秒ではなく数ミリ秒で実行されます。ここでは、次の事実に依存していることに注意してください PRQLではクエリをで開始可能 させる 句.

トップへ

可能であればシーケンス使用操作を使用

実際、上のセクションで得られたクエリは、次のメソッドのおかげで、さらに高速かつ簡潔に書き換えることができます UsingAny().

1Methods.UsingAny(Methods.WithSimpleName(@"Add")).Select(m => m)

名前空間で定義された任意のインターフェイスを継承する型に一致させる別の例を見てみましょう MyNamespace。これは次のように書けます:

1let types = Namespaces.WithName("MyNamespace").ChildTypes()
2
3from t in Application.Types
4
5from t2 in types
6
7where t.DeriveFrom(t2)
8
9select t

しかし、拡張メソッド ThatDeriveFromAny() を使用すると、書き換えられたクエリバージョンが 10 倍高速に実行されることがテストで示されています。

1Types.ThatDeriveFromAny(
2
3  Namespaces.WithName("MyNamespace").ChildTypes()
4
5).Select(t => t)

これらの拡張メソッドの内部最適化は、実際にループを置き換えるという事実に基づいています。したがって、このような実装は、ループよりも高速に入力シーケンスをフィルタリングするよりスマートなアルゴリズムに依存することができます。

トップへ

メインクエリループの前にサブセットを宣言

コードベースのサブセットをクエリする必要がある場合は、メインクエリループの前に、このサブセットを一度だけ定義してください。

例えば次のクエリ...

1from m in Application.Methods where
2
3  m.IsUsing("MyClass.MyMethod()".AllowNoMatch()) ||
4
5  m.IsUsing("MyClass.MyMethod(int)".AllowNoMatch()) ||
6
7  m.IsUsing("MyClass.MyMethod(int,int)".AllowNoMatch())
8
9select m

... はこのように書き換えると 5～10 倍高速になります。

1let gcCollectMethods = ThirdParty.Methods.WithFullNameIn(
2
3   "MyClass.MyMethod()",
4
5   "MyClass.MyMethod(int)",
6
7   "MyClass.MyMethod(int,int)")
8
9from m in Application.Methods.UsingAny(gcCollectMethods)
10
11select m

トップへ

ハッシュセットを多用

この System.Collections.Generic.HashSet クラスは、高パフォーマンスアルゴリズムの実装に不可欠です。実際、このクラスは、次の操作が可能なコレクションを表します Contains(T) メソッドは一定時間で実行 O(1) (すなわちコレクションサイズに関わらず一定!)。

PRQL は次をより効果的に扱うためのいくつかの拡張メソッドを提供します HashSet クラス。最も重要なのは、任意の列挙をハッシュセットに変換する ToHashSet() メソッドです。

クエリが集合演算（和集合、積集合…）に依存する場合、パフォーマンスの観点から列挙可能オブジェクトをハッシュセットに変換することが多くの場合賢明です。たとえば、拡張メソッドの呼び出しを削除することで ToHashSet() は、次のクエリは 200 倍以上遅くなります！

1// <Name>Callers of refactored methods</Name>
2
3let refactoredMethods = Application.Methods.Where(m => m.CodeWasChanged()).ToHashSet()
4
5from caller in Application.Methods.UsingAny(refactoredMethods)
6
7let refactoredMethodsCalled = caller.MethodsCalled.Intersect(refactoredMethods)
8
9where refactoredMethodsCalled.Count() > 0
10
11select new { caller, refactoredMethodsCalled }

トップへ

メインクエリループで多くのlet句を避ける

で範囲変数を定義 させる 句は LINQ が提供する便利な構文です。問題は、この構文の利便性がクエリの実行を大幅に遅くする可能性があることです。なぜなら内部的には各 させる 句は、新しいオブジェクトを作成し、その宣言前に取得したすべての値をコピーすることを強制します。

ここにあるのは トレードオフ ここではパフォーマンスと構文のエレガンスの間のトレードオフがあります。パフォーマンスが必ずしも優先されるわけではなく、たとえばこの既定のルールを 3 のまま維持することにしました させる 句...

1// <Name>CRAP methods</Name>
2
3// Source: http://www.artima.com/weblogs/viewpost.jsp?thread=215899
4
5from method in Application.Methods
6
7where method.CyclomaticComplexity != null && method.PercentageCoverage != null
8
9let CC = method.CyclomaticComplexity
10
11let uncov = (100 - method.PercentageCoverage) / 100f
12
13let CRAP = (CC * CC * uncov * uncov * uncov) + CC
14
15where CRAP > 30
16
17orderby CRAP descending, method.NbLinesOfCode descending
18
19select new { method, CRAP, CC, uncov, method.PercentageCoverage, method.NbLinesOfCode }

...これは、単一の次を使用するはるかに洗練度の低いバージョンより約 2 倍遅くなります させる 句:

1// <Name>CRAP methods</Name>
2
3// Source: http://www.artima.com/weblogs/viewpost.jsp?thread=215899
4
5from method in Application.Methods
6
7where method.CyclomaticComplexity != null && method.PercentageCoverage != null
8
9let CRAP = (method.CyclomaticComplexity * method.CyclomaticComplexity *
10
11            ((100 - method.PercentageCoverage) / 100f)*
12
13            ((100 - method.PercentageCoverage) / 100f)*
14
15            ((100 - method.PercentageCoverage) / 100f)) + method.CyclomaticComplexity
16
17where CRAP > 30
18
19orderby CRAP descending, method.NbLinesOfCode descending
20
21select new { method,
22
23             CRAP,
24
25             CC = method.CyclomaticComplexity ,
26
27             uncov = ((100 - method.PercentageCoverage) / 100f),
28
29             method.PercentageCoverage,
30
31             method.NbLinesOfCode }

トップへ

多数の文字列定数でのパフォーマンス

クエリがコード要素名のリストを列挙してマッチさせる必要がある場合があります。例：

1from t in Types where
2
3t.Name == "int" || t.Name == "Uint" || t.Name == "Int16" || t.Name == "UInt16" ||
4
5t.Name == "Int64" || t.Name == "UInt64" || t.Name == "Byte" || t.Name == "SByte" ||
6
7t.Name == "Single" || t.Name == "Double" || t.Name == "Decimal"
8
9select t

50,000 個の型を持つ非常に大きなコードベースでは、このクエリの実行には最良の場合でも 25 ミリ秒かかります。プロパティを繰り返し呼び出すのを避ける小さな最適化が可能です名前上 t EqualsAny() メソッドのオーバーライドを使用して：

1from t in Types where
2
3t.Name.EqualsAny("int","Uint", "Int16","UInt16",
4
5                 "Int16","UInt16", "Byte","SByte",
6
7                 "Single","Double", "Decimal")
8
9select t

このバージョンのクエリは、最良の場合で 20 ミリ秒かかります。この小さなパフォーマンスの向上は、9 つの文字列パラメータが繰り返しメソッドに渡されるという事実によって相殺されます EqualsAny().

のアイデアは、のインスタンスを使うこと HashSet 定数時間での文字列比較を得るには：

1let hashset = new [] { "int","Uint", "Int16","UInt16",
2
3                       "Int16","UInt16", "Byte","SByte",
4
5                       "Single","Double", "Decimal" }.ToHashSet()
6
7from t in Types where
8
9hashset.Contains(t.Name)
10
11select t

残念ながら、このバージョンは大幅に遅く、最高実行時間は 150 ms です。内部的には させる 句はループごとにパフォーマンスの低下を引き起こします。比較対象の文字列定数が数十個ある場合、次を使用するこのバージョンは HashSet 結果的に速くなる可能性。

PRQL は次のように使用できる WithNameIn() メソッドを提供します：

1Types.WithNameIn("int","Uint", "Int16","UInt16",
2
3                 "Int16","UInt16", "Byte","SByte",
4
5                 "Single","Double", "Decimal").Select(t => t)

このバージョンは、LINQ ループの必要性をなくし、内部的にそれをより高速なループに置き換えたため、最良の実行時間 12 ミリ秒ではるかに高速になりました。 のために 構文との使用の組み合わせ HashSet なしで させる パフォーマンスへの影響。

今すぐCppDependを試す

ドキュメントの全機能にアクセスできる14日間無料トライアル。クレジットカード不要。

無料トライアルをダウンロード価格を見る

PRQLの機能 PRQL構文