Performance PRQL dans CppDepend

PRQL est conçu pour exécuter des centaines de requêtes par seconde sur une grande base de code réelle. Cela signifie que la plupart des requêtes PRQL devraient théoriquement s'exécuter en quelques millisecondes. En pratique, c'est vrai pour la plupart des requêtes, mais si vous regardez l'ensemble des requêtes et règles PRQL par défaut, vous verrez que quelques-unes s'exécutent en quelques dizaines de millisecondes sur de grandes bases de code.

La valeur par défaut du délai d'expiration pour la durée d'exécution des requêtes PRQL est de deux secondes, mais cette valeur est facilement modifiable dans Outils & options & requête de code le panneau.

Lors de l'écriture de l'ensemble des dizaines de règles et requêtes PRQL par défaut, nous avons adapté la conception de PRQL pour nous assurer qu'il est toujours possible d'exécuter rapidement même des requêtes complexes.

Le résultat de ce travail est partagé dans le présent document.

La performance est un sujet important pour PRQL, car la philosophie de l'outil CppDepend est de fournir des retours utiles à l'utilisateur le plus rapidement possible, en quelques secondes.

• Visez toujours une complexité temporelle linéaire
• Utilisez si possible des opérations d’utilisation de séquence
• Déclarez les sous-ensembles avant la boucle principale de la requête
• S’appuyer largement sur les hashsets
• Évitez de nombreuses clauses let dans la boucle principale
• Performance avec de nombreuses constantes chaînes

Lors de l'écriture d'une requête complexe nécessitant une sorte de traitement imbriqué, l'approche la plus évidente est souvent d'imbriquer une requête dans une autre. Cela est illustré par la requête ci-dessous, où nous souhaitons trouver toutes les méthodes qui appellent une méthode nommée Ajouter:

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

Le problème de cette approche est qu'elle conduit à des requêtes exécutées avec une lente complexité temporelle polynomiale ( O(#méthode^2) ici ).

Dans la plupart des cas, il est possible de transformer une complexité temporelle polynomiale lente en une complexité temporelle linéaire. Par exemple, notre requête peut être réécrite :

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

La requête a désormais une complexité temporelle linéaire O(#méthodes) et concrètement, elle s'exécute en quelques millisecondes, au lieu de plusieurs dizaines de secondes ! Notez qu'ici nous nous appuyons sur le fait que PRQL permet à une requête de commencer par laisser clause.

Haut de page

En fait, la requête obtenue dans la section ci-dessus peut être réécrite pour être encore plus rapide et concise grâce à la méthode UsingAny().

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

Prenons un autre exemple pour faire correspondre les types qui héritent de n'importe quelle interface définie dans le namespace MyNamespace. Cela peut s’écrire ainsi :

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

Mais en utilisant la méthode d'extension ThatDeriveFromAny(), les tests montrent que la version réécrite de la requête s'exécute 10 fois plus vite.

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

L'optimisation interne de ces méthodes d'extension repose sur le fait qu'elles remplacent en réalité une boucle. Une telle implémentation est donc libre de s'appuyer sur un algorithme plus intelligent pour filtrer la séquence d'entrée plus rapidement qu'avec une boucle.

Haut de page

Si vous devez interroger un sous-ensemble de la base de code, assurez-vous de définir ce sous-ensemble une fois pour toutes, avant la boucle principale de la requête.

Par exemple la requête suivante...

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

... peut être réécrite de cette façon pour être 5 à 10 fois plus rapide.

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

Haut de page

Le System.Collections.Generic.HashSet classe est essentielle pour implémenter des algorithmes haute performance. En effet, cette classe représente une collection sur laquelle Contains(T) méthode s’exécute en temps constant O(1) (c.-à-d. constante quelle que soit la taille de la collection !).

PRQL offre plusieurs méthodes d'extension pour travailler plus efficacement avec HashSet classe. La plus importante est la méthode ToHashSet() qui transforme toute énumération en hashset.

Lorsqu'une requête repose sur des opérations ensemblistes (union, intersection...), il est souvent judicieux, en termes de performance, de transformer les énumérables en hashsets. Par exemple, en supprimant l'appel à la méthode d'extension ToHashSet() la requête suivante est plus de 200 fois plus lente !

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 }

Haut de page

Définir une variable de portée via un laisser clause est une possibilité de syntaxe pratique offerte par LINQ. Le problème est que ce bonus de syntaxe peut ralentir considérablement l'exécution de la requête car sous le capot, chaque laisser clause force la création d'un nouvel objet et la copie de toutes les valeurs déjà obtenues avant sa déclaration.

Nous avons donc ici un compromis ici entre performance et élégance de la syntaxe. La performance ne l'emporte pas nécessairement ; par exemple, nous avons décidé de conserver cette règle par défaut avec 3 laisser 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 }

...qui est environ deux fois plus lente que cette version bien moins élégante avec un seul laisser 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 }

Haut de page

Il peut arriver qu'une requête ait besoin d'énumérer une liste de noms d'éléments de code pour les faire correspondre. Par exemple :

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

Sur une très grande base de code avec 50 000 types, cette requête prend au mieux 25 ms à s'exécuter. Une petite optimisation est possible pour éviter d'appeler encore et encore la propriété Nom sur t en utilisant une surcharge de la méthode 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

Maintenant, cette version de la requête prend au mieux 20 ms à s'exécuter. Le petit gain de performance est compensé par le fait que les 9 paramètres string sont passés encore et encore à la méthode EqualsAny().

Une idée est d’utiliser une instance de HashSet pour obtenir une comparaison de chaînes en temps constant :

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

Malheureusement, cette version est bien plus lente avec un meilleur temps d'exécution de 150 ms, car sous le capot, laisser clause provoque une perte de performance à chaque boucle. Si nous devions comparer avec des dizaines de constantes chaînes, cette version avec HashSet pourrait finir par être plus rapide.

PRQL fournit la méthode WithNameIn() qui peut s'utiliser ainsi :

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

Cette version est maintenant beaucoup plus rapide avec un meilleur temps d'exécution de 12 ms, car elle supprime le besoin d'une boucle LINQ et la remplace en interne par une boucle plus rapide basée sur le pour syntaxe, combinée à l’utilisation d’un HashSet sans le laisser impact sur les performances.