(Statisch) Auswahl optimaler Container in C ++ - Programmen

Guten Tag. Heute möchte ich noch einmal über statische Analysen sprechen. Und nochmal zu C ++. Nur werden wir im Gegensatz zu PVS-Studio keine Fehler in unseren Programmen suchen (obwohl sie nicht nur nach Fehlern suchen), sondern auch nach Stellen, die nicht optimal genug geschrieben sind. Und einer dieser Orte ist die Auswahl eines Containers für die Daten im Programm. Wenn ich für Sie von Interesse bin, dann willkommen bei cat!

Das Problem

Auf der CoreHard 2018 Autumn (eine sehr gute Konferenz, komm) habe ich darüber gesprochen, wie C ++ - Compiler derzeit nicht gut optimieren. Und eine meiner Beschwerden war, dass Compiler die Verwendung von Containern in unseren Programmen nicht optimieren können. Schauen wir uns einige Codebeispiele an.

void foo() { std::vector<int> v(42); } 

In einem so einfachen Fall sollte der Compiler in der Lage sein, diese Funktion zu optimieren und einfach eine Variablendeklaration vom Typ std :: vector auszugeben, da der Compiler ab C ++ 14 dynamische Speicherzuordnungen entfernen darf, der Compiler jedoch nicht. Der Grund dafür ist, dass derzeit nur ein C ++ - Compiler eine Optimierung zum Entfernen dynamischer Zuordnungen implementiert - Clang. Alle anderen Compiler wissen bisher nicht, wie das geht. Aber selbst Clang kann dies in einer begrenzten Anzahl von Fällen tun.

In diesem Fall könnten wir std :: vector durch std :: array ersetzen, vorausgesetzt, die Größe des ausgewählten Vektors ist nicht zu groß, da wir möglicherweise nicht genügend Stapel für eine solche Ersetzung haben. Ein solcher Ersatz entfernt eine ziemlich teure Speicherzuordnung zum Heap, und das Plus ist, dass der Compiler bei Verwendung von std :: array bereits std :: array aus der Funktion insgesamt werfen kann!

Wenn wir über Leistungsoptimierung sprechen, schlagen wir vor, das folgende Beispiel zu betrachten:

 void foo() { std::vector<int> v; for(int i = 0; i < 42; ++i) { v.insert(v.begin(), 42); } for(const auto val : v) { std::cout << val << ' '; } } 

In diesem Fall sehen wir die Verwendung einer äußerst ineffektiven Operation im Fall der Einfügung von std :: vector am Anfang des Containers. Alle C ++ - Programmierer wissen, dass dies äußerst schlecht ist, da alle Elemente jedes Mal verschoben werden, was zu hohen Kosten für das Kopieren / Verschieben führt. In diesem Fall wäre es viel schöner, es durch std :: list zu ersetzen, was nicht wichtig ist, wo das Einfügen stattfindet, oder std :: deque (obwohl Sie in diesem Fall deutlich sehen können, dass Sie nicht nur insert verwenden müssen. Dies ist jedoch nur ein Beispiel, nicht mehr :)

Schauen wir uns einen anderen Beispielcode an:

 void foo() { std::list<int> v; for(int i = 0; i < 3; ++i) { v.push_front(i); } for(const auto val : v) { std::cout << val << ' '; } } 

In diesem Fall können wir feststellen, dass wir std :: list (ja, ich weiß, dass nur wenige Leute es verwenden) schmerzlos durch std :: forward_list ersetzen können. In diesem Fall verlieren wir in diesem Fall absolut nichts, aber wir erhalten Speichereinsparungen. Natürlich führt der Compiler eine solche Optimierung jetzt nicht durch.

Ein ähnlicher Trick kann im folgenden Beispiel ausgeführt werden:

 void foo() { std::deque<int> v; for(int i = 0; i < 3; ++i) { v.push_back(i); } for(int i = 0; i < 3; ++i) { std::cout << v.back() << ' '; v.pop_back(); } } 

Hier können wir sehen, dass wir nicht std :: deque, sondern std :: stack wirklich brauchen. Dies kann nicht als Optimierung bezeichnet werden, da std :: stack ein Adapter ist und standardmäßig std :: deque verwendet (sofern der Benutzer nichts anderes angibt). Hier können wir mehr über semantische Optimierung sprechen, d.h. Vereinfachung des Codes zu verstehen. Dies ist aus meiner Sicht auch wichtig. Wenn Sie fragen: "Vielleicht bringt ein solcher Ersatz auch einen Leistungsgewinn?", Antworte ich: "Vielleicht. Einzelheiten zur Implementierung finden Sie in Ihrer Version der Standardbibliothek. “

Ich denke, es gibt genug Beispiele. Jeder von euch kann sich auch viele davon einfallen lassen.

Verwendete Mittel

Zur Implementierung des statischen Analysators habe ich Clang Static Analzyer (CSA) und Clang Tidy verwendet, die Teil des LLVM-Pakets sind. Ich habe diese Tools ausgewählt, da ich sie als die vielversprechendsten unter den offenen Tools für die statische Analyse betrachte. Darüber hinaus bietet Clang einen der hochwertigsten C ++ - Parser, mit denen andere statische Analysatoren nicht aufwarten können (es sei denn, sie verwenden natürlich libclang).

Sowohl CSA als auch Clang Tidy sind statische Analysegeräte, die beide Teil von LLVM sind. Was ist der Unterschied? Der Unterschied besteht darin, dass Clang Tidy so konzipiert ist, dass einfache Überprüfungen geschrieben werden, die im Wesentlichen darin bestehen, ein Muster im abstrakten Syntaxbaum zu finden, eine Art Warnung anzuzeigen und es möglicherweise automatisch durch ein anderes zu ersetzen. Mehr über Clang Tidy erfahren Sie hier .

CSA wurde entwickelt, um "ernsthaftere" und ressourcenintensivere Prüfungen (sowohl unter dem Gesichtspunkt der Implementierung als auch unter dem Gesichtspunkt der Ausführungszeit / des aufgewendeten Speichers) zu schreiben. Dort steht beispielsweise ein symbolischer Ausführungsmechanismus zur Verfügung.

Ich habe mich entschlossen, den Check in CSA zu implementieren, da er mir nicht alltäglich erscheint. Außerdem wird er in Zukunft immer schwieriger. Und es wurde beschlossen, Clang Tidy zu durchlaufen, da dieser statische Analysator viele Integrationen mit verschiedenen IDEs aufweist.

Wie wir versuchen werden, Probleme zu lösen

Zunächst lohnt es sich, einige ziemlich starke Einschränkungen einzuführen, die hauptsächlich damit zusammenhängen, dass dies bislang nur ein Prototyp ist:

• Analyse nur auf Funktionsebene; Diese Einschränkung bedeutet, dass keine Analyse zwischen Funktionen sowie zwischen Übersetzungseinheiten erfolgt. Die Einschränkung der Analyse zwischen Funktionen wurde eingeführt, um die Implementierung dieser Analyse zu vereinfachen, und kann in Zukunft relativ einfach behoben werden, indem eine statische Analyse für die gesamte Übersetzungseinheit und nicht nur für jede Funktion durchgeführt wird. Die Einschränkung der Analyse zwischen Übersetzungseinheiten wird durch die bestehenden Einschränkungen im CSA auferlegt, die in Kürze festgelegt werden (Commits fließen bereits in den Upstream).
• Unterstützung für nur eine begrenzte Anzahl von Containern. Dies lässt sich in Zukunft relativ einfach beheben, indem neue Regeln für neue Container hinzugefügt werden.
• Verwenden Sie für die Analyse nur einen Baum mit abstrakter Syntax. Da dies für das Prototyping die einfachste Art der Analyse ist. Für genauere Ergebnisse können Sie natürlich versuchen, zumindest eine symbolische Ausführung zu verwenden, aber diese Methode hat ihre Nachteile. Weitere Informationen zu Methoden finden Sie hier .

Jetzt implementiert der Prototyp den folgenden einfachen Algorithmus:

• Zunächst finden wir im abstrakten Syntaxbaum die Eckpunkte, die für die Deklaration der von uns unterstützten Containertypvariablen verantwortlich sind.
• Dann finden wir die Operationen, die sich auf diese Container beziehen, klassifizieren sie und speichern diese Informationen in einem temporären Cache.
• Nach Erreichen des Funktionsende analysieren wir die gesammelten Statistiken und geben basierend auf vordefinierten Regeln eine Empfehlung zur Verwendung eines Containers ab.

Die Klassifizierung der Containerbetriebe ist derzeit wie folgt (wird in Zukunft erweitert):

• Fügen Sie einen Artikel oben im Container hinzu.
• Hinzufügen eines Elements zur Mitte des Containers.
• Hinzufügen eines Elements am Ende des Containers.
• Entfernen eines Elements vom Anfang des Containers.
• Entfernen eines Artikels aus der Mitte des Containers.
• Entfernen eines Elements vom Ende des Containers.

Die Klassifizierung ist derzeit unvollständig und funktioniert auch in dieser Liste nicht richtig. Zum Beispiel klassifiziert der Einfügevorgang, selbst wenn er zu Beginn ausgeführt wird, den Einsteiger als Einfügen in die Mitte, obwohl dies tatsächlich überhaupt nicht der Fall ist.

Bekämpfung von Fehlalarmen

Bei jeder statischen Analyse sind falsch positive Ergebnisse die Hauptprobleme. Wenn es zu viele davon gibt, gehen nützliche Nachrichten im Müll verloren. Daher müssen Sie in diesem Fall sehr konservativ handeln und Warnungen nur dann ausgeben, wenn wir wirklich zuversichtlich in unsere Diagnose sind und durchaus sagen können, dass an einer Stelle im Code wirklich etwas nicht stimmt.

Wenn wir über Compiler-Optimierung sprechen, ist es dort immer noch trauriger - eine ordnungsgemäße Optimierung kann das Verhalten des Programms gemäß dem C ++ - Standard nicht ändern (andernfalls ist ein solcher Optimierer wertlos). Und Optimierung sollte auch keine Pessimisierung einführen :) Hier müssen Sie also bei Ihren Entscheidungen viel vorsichtiger sein.

In diesem Analysator führte dieser Kampf dazu, dass die Analyse für diesen Container deaktiviert wird, wenn der Analysator feststellt, dass gerade eine nicht unterstützte Operation ausgeführt wird.

Nachteile und mögliche Lösungen

Bei dieser Methode gibt es mehrere Probleme.

Das erste Problem ist, dass für den Analysator im Moment alle Zweige des Codes gleich wahrscheinlich sind. Genauer gesagt kennt er nicht einmal verschiedene Zweige der Codeausführung.
Dies führt zu Problemen bei der Analyse für so etwas wie diesen Code:

 void foo(int* ptr, std::vector<int>& v) { if(ptr == nullptr) { v.insert(v.begin(), 42); } else { v.push_back(84); } } 

In unserer Anwendung haben diese Codezweige höchstwahrscheinlich nicht die gleichen Ausführungswahrscheinlichkeiten, da in der realen Welt ein Zeiger normalerweise etwas Normales anzeigt und nicht nullptr. In derselben LLVM gibt es statische Heuristiken für diese Punktzahl. Beispielsweise wird der obige Fall beim Vergleichen von Zeigern mit nullptr und beim Vergleichen der Gleichheit von Werten zweier Variablen mit einem Gleitkomma und einiger anderer interessanter Fälle berücksichtigt. Dies ähnelt jedoch immer mehr Krücken, und aus meiner Sicht besteht die eigentliche Lösung für dieses Problem darin, dynamische Analysen oder Instrumente hinzuzufügen.

Das zweite Problem ist die mangelnde Unterstützung für benutzerdefinierte Container. Wir leben in der Welt von C ++, sie fahren gerne hier (lassen wir die Diskussion über die Gründe für dieses nicht immer schlechte Phänomen außerhalb des Rahmens dieses Artikels) alles, einschließlich unserer Container. Beispiele sind das gleiche LLVM, LibreOffice und viele andere. In diesem Zusammenhang stellt sich die Frage, wie Container analysiert werden sollen, die nicht aus der STL-Bibliothek stammen. Schließlich möchte ich die Analyse für so viele Container wie möglich einbeziehen.

Es gibt verschiedene Möglichkeiten, das Problem zu lösen.

Das erste ist, dass der Benutzer seine Container auf irgendeine Weise kommentiert (eine spezielle Art von Kommentar, C ++ - Attribute, etwas anderes). Das Problem bei dieser Methode ist, dass wir verstehen müssen, wie man im Allgemeinen kommentiert, welche Informationen wir für eine qualitative Analyse benötigen. Ein weiteres Problem kann die Codeänderung der Container selbst sein, die nicht immer möglich ist.

Die zweite Methode bietet dem Benutzer einen Mechanismus zum Schreiben eigener Regeln. Im Moment sind die Regeln im Analysator in den Quellcode des Analysators selbst eingenäht. Wenn der Benutzer seine eigenen Regeln hinzufügen möchte, muss er den Quellcode des Analysators herunterladen, zusammenstellen, herausfinden, wie Schecks geschrieben, geschrieben, neu erstellt usw. werden. Sie können dem Benutzer eine Möglichkeit bieten, seine Überprüfungen für DSL festzulegen, wobei der Benutzer nur Überprüfungen für seine Container schreibt und der Analysator an der gesamten Routine beteiligt ist. Ich halte diese Methode für vielversprechender als die vorherige.

Der automatische Austausch von Containern wird ebenfalls nicht unterstützt, da diese Funktionalität nicht in der CSA enthalten ist (sondern in Clang Tidy). In schwierigen Fällen ist die Durchführung der automatischen Korrektur jedoch nicht immer eine triviale Aufgabe, und der Analysator arbeitet eher im halbmanuellen Modus.

Mögliche Anwendungen

Ich sehe mehrere Anwendungen für diese Art der Analyse:

1. Wie ein statischer Analysator. Hier ist alles einfach - ein weiterer Test der statischen Analyse, den Sie nach Herzenslust durchführen (mit Ihren Händen, in der IDE automatisch während der Entwicklung, auf CI usw.), wo Sie wahrscheinlich einen Hinweis erhalten, dass Sie irgendwo könnten nimm einen Behälter und besser.
2. Wie die Optimierung im Compiler. In einigen Fällen können wir garantieren, dass das Ersetzen des Containers die Leistung definitiv nicht beeinträchtigt. Ersetzen Sie beispielsweise std :: vector für kleine Größen, die zur Kompilierungszeit bekannt sind, durch std :: array oder ersetzen Sie std :: list durch std :: forward_list, wenn wir keine doppelte Verbindung benötigen und die Größe nicht aus der Liste übernehmen. Der Compiler könnte ohne unser Wissen Container durch optimalere ersetzen, wie dies bereits für eine sehr große Anzahl von Dingen der Fall ist.
3. Wie ein dynamischer Analysator. Dies ist die Richtung, die mir für diese Art der Analyse am vielversprechendsten erscheint. In der Tat können wir mit Hilfe des Wissens über das Programmausführungsprofil beispielsweise so wichtige Informationen für uns erhalten, wie die Wahrscheinlichkeiten jeder Ausführung von Codezweigen. Und dies ist für eine genauere Beurteilung notwendig. Und mit einer solchen Analyse können Sie bereits in Richtung Integration mit PGO denken ...

Es ist auch erwähnenswert, dass diese Methode natürlich nicht nur für C ++ - Programme anwendbar ist. Ich würde diese Art der statischen Analyse / Optimierung wirklich gerne im Compiler und für andere Programmiersprachen sehen. Zum Beispiel weiß der SAP Static Analyzer für ABAP bereits, wie man eine statische Optimalitätsanalyse auf einer grundlegenden Ebene durchführt, was eine gute Nachricht ist. Wenn Sie ähnliche Projekte für andere Programmiersprachen kennen - schreiben Sie in die Kommentare und ich werde den Artikel ergänzen!

Arbeiten Sie in ähnliche Richtungen

Für die C ++ - Welt habe ich solche Analysatoren nirgendwo gefunden. Für die ABAP-Welt habe ich oben den Analysator erwähnt, der für einen Teil der Standardcontainer ineffiziente Operationen finden kann, aber soweit ich weiß, wird dort eine sehr einfache statische Analyse implementiert.

Eine viel interessantere Arbeit ist Chameleon - ein dynamischer Analysator für Java, der sehr geschickt gemacht wird. Sie haben die JVM ein wenig optimiert und während des Betriebs verschiedene Statistiken über die Verwendung von Containern gesammelt. Abhängig vom aktuellen Lastprofil wählen sie bestimmte Container aus und ersetzen sie automatisch während des Betriebs. Leider sind die Quellen geschlossen und es gibt keine Chance, sie zu bekommen (ich habe es versucht).

Ich empfehle auch, verschiedene Werke (es gibt viele) auf SETL anzuschauen . In ihnen stellten die Autoren auch häufig Fragen zur automatischen Auswahl des Containers.

Referenzen

1. Aktuelle Implementierung auf Github
2. C ++ Russland 2017: Yuri Efimochev, ordentlich: eine Reise in den abstrakten C ++ - Syntaxbaum
3. Chamäleon: Adaptive Auswahl von Sammlungen
4. Clang Static Analyzer Guide
5. Russischsprachiger Chat zur Entwicklung von Compilern im Telegramm. Wenn Sie interessiert sind, kommen Sie herein, es ist dort sehr interessant. Sei einfach vorsichtig mit der Flut - sie werden ihn sofort bestrafen :)

Anstelle einer Schlussfolgerung möchte ich mich auf die Tatsache konzentrieren, dass es sich bisher nur um einen Prototyp handelt und zu viele „Lücken“ in der Implementierung aufweisen. In diesem Artikel möchte ich Ihnen nur die Idee einer solchen Analyse und ihre Popularisierung mitteilen. Nun, vielleicht interessiert sich jemand für dieses Thema und es besteht der Wunsch, sich mit dem Projekt zu verbinden - ich werde nur glücklich sein! Darüber hinaus können Sie diesen Analysator jederzeit an Ihrem eigenen Ort sammeln, um ihn an Ihren Testbeispielen zu testen.

Wenn Sie etwas zur Ergänzung des Materials haben, auf ein ähnliches Problem gestoßen sind oder einfach einige Informationen haben, die zu diesem Thema nützlich sein können, zögern Sie bitte nicht, diese Informationen in den Kommentaren zu teilen.

Vielen Dank für Ihre Aufmerksamkeit!