PRQL Performance in CppDepend

PRQL is designed to run hundreds of queries per seconds against a large real-world code base. This means that most PRQL queries should be executed in a few milliseconds in theory. In practices, this is true for most queries, but if you look at the set of default PRQL queries and rules, you'll see that a few of them are executed in a few dozens of milliseconds on large code bases.

The default value for the time-out for PRQL query execution duration is equals to two seconds, but this value is easily changeable in the Tools & Options & Code Query panel.

While writing the set of dozens of default PRQL rules and queries, we have adapted the PRQL design to make sure that it is always possible to run quickly even complex queries.

The result of this work is shared in the present document.

Performance is an important topic for PRQL, because the philosophy of the CppDepend tool is to provide useful feedbacks to the user as quickly as possible, in a few seconds.

• Always strive for linear time complexity
• Use sequence usage operations if possible
• Declare sub-sets before the main query loop
• Rely extensively on hashset
• Avoid many let clauses in the main query loop
• Performance with many strings constants

When writing a complex query that needs some sort of nested processing, often the most obvious approach is to nest a query inside another one. This is illustrated by the query below, where we are interested to match all methods that calls any method named Add:

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

The problem with this approach is that it leads to query that are executed in a slow polynomial time complexity ( O(#Method^2) here ).

In most cases it is possible to transform a slow polynomial time complexity, into a linear time complexity. For example our query can be rewritten:

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

The query has now a linear time complexity O(#Methods) and concretely it gets executed in a few milliseconds, instead of several dozens of seconds! Notice that here we rely on the fact that PRQL allows a query to begin with a let clause.

Go to top

Actually, the query obtained in the section above can be rewritten to be even faster and more concise thanks to the method UsingAny().

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

Let's take another example to match types that inherit from any interface defined in the namespace MyNamespace. This can be written this way:

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

But by using the extension method ThatDeriveFromAny() tests shows that the rewritten version of query runs 10 times faster.

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

The internal optimization of these extension methods is based on the fact that they actually replace a loop. Hence such implementation is free to rely on a smarter algorithm to filter the input sequence faster than with a loop.

Go to top

If you need to query over a sub-set of the code base, make sure to define this sub-set once for all, before the main query loop.

For example the following query...

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

... can be rewritten this way, to be 5 to 10 times faster.

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

Go to top

The System.Collections.Generic.HashSet class is essential to implement high performance algorithms. Indeed this class represents a collection on which the Contains(T) method is executed in a constant time O(1) (i.e constant no matter the collection size!).

PRQL offers several extension methods to work more effectively with the HashSet class. The most important one is the method ToHashSet() that transforms any enumerable in a hashset.

When a query relies on set operations (union, intersection...) it is often performance wise to transform enumerables into hashsets. For example, by removing the call to the extension method ToHashSet(), the following queries is more than 200 times slower!

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 }

Go to top

Defining a range variable through a let clause is a convenient syntax possibility offered by LINQ. The problem is that this syntax bonus can significantly slow down query execution because under the hood, each let clause forces to create a new object and copy all values already obtained before its declaration.

So we have here a trade-off here between performance and syntax elegance. The performance doesn't necessarily win, for example we decided to keep this default rule with 3 let clauses...

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 }

...that is around two times slower than this much less elegant version with a single let clause:

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 }

Go to top

It might happen that a query needs to enumerate a list of code elements names to match them. For example:

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

On a very large code base with 50.000 types this query takes 25ms at best to run. A small optimization is possible to avoid calling again and again the property Name on t by using an override of the method 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

Now, this version of the query takes at best 20ms to run. The small performance gain is compensated by the fact that the 9 string parameters are passed again and again to the method EqualsAny().

An idea is to use an instance of HashSet to get a string comparison in a constant time:

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

Unfortunatly this version is much slower with a best run time equals to 150ms, because under the hood, the let clause provoques a performance hit for each loop. If we were facing dozens of string constants to compare with, this version with HashSet could end up being faster.

PRQL provides the method WithNameIn() that can be used this way:

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

This version is now much faster with a best run time of 12ms because it removes the need for a LINQ loop, and internally replaces it with a faster loop based on the for syntax, coupled with the usage of a HashSet without the let performance hit.