首页/文档/PRQL 与代码查询/CppDepend中的PRQL性能

CppDepend中的PRQL性能

本文档假定您熟悉 LINQ语法并已阅读关于的文档 PRQL语法另请参阅维基百科中关于以下内容的定义时间复杂度如果您不知道这个概念的含义。

PRQL 旨在针对大型真实代码库每秒运行数百个查询。这意味着大多数 PRQL 查询理论上应该在几毫秒内执行。在实践中，大多数查询确实如此，但如果您查看默认的 PRQL 查询和规则集，会发现其中少数在大型代码库上需要几十毫秒才能执行。

PRQL 查询执行时长的超时默认值为两秒，但可以在以下位置轻松更改此值 工具与选项与代码查询 面板。

在编写数十个默认 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 }

……这比使用单个以下元素的不太优雅版本慢约两倍让子句:

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 毫秒，因为在底层让子句会在每次循环时造成性能损失。如果我们需要与数十个字符串常量进行比较，这个使用以下内容的版本 HashSet 最终可能更快。

PRQL 提供 WithNameIn() 方法，可以这样使用：

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

此版本现在快得多，最佳运行时间为 12 毫秒，因为它消除了对 LINQ 循环的需要，并在内部用基于……的更快循环替代了它为了语法，结合使用 HashSet 没有让性能损失。

立即试用 CppDepend

开始 14 天免费试用，畅享全部文档功能。无需信用卡。

下载免费试用版查看价格

PRQL 功能 PRQL 语法