PRQL-Leistung in CppDepend

PRQL ist darauf ausgelegt, Hunderte von Abfragen pro Sekunde auf einer großen realen Codebasis auszuführen. Das bedeutet, dass die meisten PRQL-Abfragen theoretisch in wenigen Millisekunden ausgeführt werden sollten. In der Praxis trifft dies auf die meisten Abfragen zu, aber wenn Sie sich den Satz der Standard-PRQL-Abfragen und -Regeln ansehen, werden Sie feststellen, dass einige davon auf großen Codebasen einige Dutzend Millisekunden benötigen.

Der Standardwert für das Timeout der PRQL-Abfrageausführungsdauer beträgt zwei Sekunden, kann aber leicht geändert werden in Tools & Optionen & Codeabfrage Panel.

Beim Schreiben der Dutzenden von Standard-PRQL-Regeln und -Abfragen haben wir das PRQL-Design angepasst, um sicherzustellen, dass selbst komplexe Abfragen immer schnell ausgeführt werden können.

Das Ergebnis dieser Arbeit wird im vorliegenden Dokument geteilt.

Performance ist ein wichtiges Thema für PRQL, da die Philosophie des CppDepend-Tools darin besteht, dem Benutzer so schnell wie möglich, in wenigen Sekunden, nützliches Feedback zu geben.

• Streben Sie stets lineare Zeitkomplexität an
• Verwenden Sie nach Möglichkeit Sequenznutzungsoperationen
• Deklarieren Sie Teilmengen vor der Hauptabfrageschleife
• Umfassend auf Hashsets setzen
• Vermeiden Sie viele let-Klauseln in der Hauptabfrageschleife
• Leistung bei vielen Zeichenfolgenkonstanten

Beim Schreiben einer komplexen Abfrage, die eine Art verschachtelte Verarbeitung benötigt, ist der naheliegendste Ansatz oft, eine Abfrage in eine andere zu verschachteln. Dies wird durch die Abfrage unten veranschaulicht, bei der wir alle Methoden finden wollen, die eine beliebige Methode namens Hinzufügen:

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

Das Problem bei diesem Ansatz ist, dass er zu Abfragen führt, die mit langsamer polynomialer Zeitkomplexität ausgeführt werden ( O(#Methode^2) hier ).

In den meisten Fällen ist es möglich, eine langsame polynomielle Zeitkomplexität in eine lineare Zeitkomplexität umzuwandeln. Unsere Abfrage kann beispielsweise umgeschrieben werden:

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

Die Abfrage hat jetzt lineare Zeitkomplexität O(#Methoden) und konkret wird sie in wenigen Millisekunden ausgeführt statt in mehreren Dutzend Sekunden! Beachten Sie, dass wir uns hier darauf verlassen, dass PRQL erlaubt, dass eine Abfrage mit beginnt lassen Klausel.

Nach oben

Tatsächlich kann die im obigen Abschnitt erhaltene Abfrage dank der Methode UsingAny().

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

Nehmen wir ein weiteres Beispiel, um Typen zu matchen, die von einem beliebigen Interface im Namespace MyNamespace. Dies kann so geschrieben werden:

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

Aber durch Verwendung der Erweiterungsmethode ThatDeriveFromAny() zeigen Tests, dass die umgeschriebene Abfrageversion 10-mal schneller läuft.

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

Die interne Optimierung dieser Erweiterungsmethoden basiert auf der Tatsache, dass sie tatsächlich eine Schleife ersetzen. Daher kann eine solche Implementierung auf einen intelligenteren Algorithmus zurückgreifen, um die Eingabesequenz schneller zu filtern als mit einer Schleife.

Nach oben

Wenn Sie über eine Teilmenge der Codebasis abfragen müssen, definieren Sie diese Teilmenge ein für alle Mal vor der Hauptabfrageschleife.

Zum Beispiel die folgende Abfrage...

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

... kann so umgeschrieben werden, dass es 5- bis 10-mal schneller ist.

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

Nach oben

Der System.Collections.Generic.HashSet Klasse ist essenziell für die Implementierung hochperformanter Algorithmen. Tatsächlich repräsentiert diese Klasse eine Sammlung, auf der Contains(T) Methode wird in konstanter Zeit ausgeführt O(1) (d. h. konstant, egal wie groß die Sammlung ist!).

PRQL bietet mehrere Erweiterungsmethoden, um effektiver mit HashSet Klasse. Die wichtigste ist die Methode ToHashSet(), die jede Aufzählung in ein Hashset umwandelt.

Wenn eine Abfrage auf Mengenoperationen (Vereinigung, Schnittmenge...) beruht, ist es aus Performancegründen oft sinnvoll, Enumerables in Hashsets umzuwandeln. Zum Beispiel durch Entfernen des Aufrufs der Erweiterungsmethode ToHashSet() ist die folgende Abfrage mehr als 200-mal langsamer!

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 }

Nach oben

Definieren einer Bereichsvariablen über lassen Klausel ist eine praktische Syntaxmöglichkeit, die LINQ bietet. Das Problem ist, dass dieser Syntaxbonus die Abfrageausführung erheblich verlangsamen kann, da unter der Haube jede lassen Klausel erzwingt das Erstellen eines neuen Objekts und das Kopieren aller bereits vor seiner Deklaration erhaltenen Werte.

Wir haben hier also Kompromiss hier zwischen Performance und eleganter Syntax. Die Performance gewinnt nicht unbedingt; so haben wir uns beispielsweise entschieden, diese Standardregel mit 3 beizubehalten lassen Klauseln...

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 }

...das etwa zweimal langsamer ist als diese viel weniger elegante Version mit einem einzigen lassen Klausel:

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 }

Nach oben

Es kann vorkommen, dass eine Abfrage eine Liste von Code-Element-Namen aufzählen muss, um sie zu matchen. Zum Beispiel:

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

Auf einer sehr großen Codebasis mit 50.000 Typen benötigt diese Abfrage bestenfalls 25 ms zur Ausführung. Eine kleine Optimierung ist möglich, um das wiederholte Aufrufen der Eigenschaft zu vermeiden Name auf t durch Verwendung einer Überschreibung der Methode 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

Nun benötigt diese Version der Abfrage bestenfalls 20 ms zur Ausführung. Der kleine Performancegewinn wird dadurch kompensiert, dass die 9 String-Parameter immer wieder an die Methode übergeben werden EqualsAny().

Eine Idee ist, eine Instanz von zu verwenden HashSet um einen String-Vergleich in konstanter Zeit zu erhalten:

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

Leider ist diese Version viel langsamer mit einer besten Laufzeit von 150 ms, denn unter der Haube lassen Klausel verursacht bei jeder Schleifeniteration einen Performance-Verlust. Stünden wir Dutzenden von String-Konstanten zum Vergleich gegenüber, wäre diese Version mit HashSet könnte am Ende schneller sein.

PRQL stellt die Methode WithNameIn() bereit, die so verwendet werden kann:

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

Diese Version ist nun viel schneller mit einer besten Laufzeit von 12 ms, da sie die Notwendigkeit einer LINQ-Schleife beseitigt und diese intern durch eine schnellere Schleife ersetzt, die auf dem für Syntax, kombiniert mit der Verwendung von HashSet ohne die lassen Leistungseinbuße.