Frage C ++ - Standardbibliothek vs Mortal Made Code + Wo finde ich die Quellen?


Zwei, vielleicht triviale Fragen:

 1. Warum kann ich die STD-Funktionen nicht schlagen?

Ja wirklich. Ich habe die letzten drei Tage damit verbracht, etwas schneller als std :: sort zu implementieren, nur um es zu tun. Es sollte ein Introsort sein, und ich vermute, dass es den Quicksort innerhalb der Single Pivot-Version verwendet. Episches Versagen. Meins war mindestens doppelt so langsam.

In meiner absoluten Verbitterung kopiere ich auch andere - erstklassige - Programmierer Code. Kein Erfolg. Ich bewertete auch meine anderen Algorithmen ... Meine binary search, und die oberen, unteren, unteren Versionen sind so reduziert, dass es nicht wirklich mit weniger Anweisungen gemacht werden könnte. Trotzdem sind sie ungefähr doppelt so langsam.

Ich frage, warum, warum, warum? Und das führt mich zu meiner nächsten Frage ...

2. Wo finde ich den Quellcode der STL-Bibliotheksfunktionen?

Natürlich möchte ich ihre Quellen sehen! Ist es überhaupt möglich, effizienteren Code zu schreiben, oder bin ich auf einer Abstraktionsebene mit meiner "einfachen" main.cpp, wo ich keine Optimierungen erreichen kann, die von der STL-Bibliothek genutzt werden?

Ich meine zum Beispiel ... Nehmen wir die Karten, die einfache assoziative Container sind. Die Dokumentation sagt, dass es mit einem rot-schwarzen Baum implementiert ist. Nun ... würde es sich lohnen, meinen eigenen rot-schwarzen Baum zu implementieren, oder sie nahmen diese Freude :-) von mir weg und ich sollte einfach alle Daten, die ich in die Hände bekomme, in den Kartencontainer werfen?

Ich hoffe, das macht Sinn. Wenn nicht, bitte vergib mir.



5
2017-09-09 21:17


Ursprung


Antworten:


Die kurze Antwort lautet: "Wenn es möglich wäre, schnelleren Code zu schreiben, der das Gleiche macht, dann hätte die Standardbibliothek es bereits getan".

Die Standard-Bibliothek wurde von cleveren Leuten entworfen, und der Grund, warum sie in C ++ aufgenommen wurde, ist, dass andere clevere Leute sie als clever erkannt haben. Und seitdem sind 15 Jahre vergangen, in denen andere Kluge Leute haben versucht, diese Spezifikationen zu übernehmen und den absolut effizientesten Code zu schreiben, um es zu implementieren.

Das ist eine Menge Klugheit, mit der du konkurrieren willst. ;)

Es gibt also keine Magie in der STL, sie betrügen nicht, oder verwenden Tricks, die für dich nicht verfügbar sind. Es ist nur sehr sorgfältig entwickelt, um die Leistung zu maximieren.

Die Sache mit C ++ ist, dass es keine schnelle Sprache als solche ist. Wenn Sie nicht vorsichtig sind, ist es leicht, alle möglichen Ineffizienzen einzuführen: virtuelle Funktionsaufrufe, Cache-Fehler, übermäßige Speicherzuweisungen, unnötiges Kopieren von Objekten, all dies kann die Leistung von C ++ - Code beeinträchtigen, wenn Sie nicht vorsichtig sind.

Mit Vorsicht können Sie Code schreiben, der ungefähr so ​​effizient ist wie die STL. Es ist nicht Das Besondere. Aber im Allgemeinen, der einzige Weg, den du bekommen wirst schneller Code ist, um die Anforderungen zu ändern. Die Standardbibliothek muss allgemein sein, um so gut wie möglich zu funktionieren alle Anwendungsfälle. Wenn Ihre Anforderung spezifischer ist, ist es manchmal möglich, spezialisierten Code zu schreiben, der diese spezifischen Fälle bevorzugt. Aber dann ist der Kompromiss, dass der Code entweder nicht funktioniert oder in anderen Fällen ineffizient sein wird.

Ein letzter Punkt ist, dass ein wesentlicher Teil des Grundes, warum die STL so clever ist, und warum sie in den Standard übernommen wurde, ist, dass es ziemlich Null ist. Die Standardbibliotheken in vielen Sprachen sind "schnell genug", aber nicht so schnell wie handgenerierter Code. Sie haben einen Sortieralgorithmus, aber es ist nicht ganz so schnell, als wenn Sie es selbst an Ort und Stelle geschrieben hätten. Es kann ein paar Umwandlungen von und zu einer gemeinsamen Basisklasse "object" verwenden oder Boxen für Werttypen verwenden. Die STL ist so konzipiert, dass so ziemlich alles vom Compiler inline geschrieben werden kann, was zu einem Code führt, der dem entspricht, wenn Sie es von Hand gerollt hätten. Es verwendet Vorlagen, um sich auf den von Ihnen verwendeten Typ zu spezialisieren, sodass kein Overhead für die Konvertierung in einen vom Container oder Algorithmus verstandenen Typ erforderlich ist.

Deshalb ist es schwer mit zu konkurrieren. Es ist eine lächerlich effiziente Bibliothek, und es musste sein. Mit der Mentalität eines durchschnittlichen C- oder C ++ - Programmierers, insbesondere vor 10-15 Jahren, Niemand würde jemals ein verwenden std::vector wenn es 5% langsamer war als ein RAW-Array. Niemand würde Iteratoren und Standardalgorithmen verwenden, wenn sie nicht so schnell wären, wie die Schleife selbst zu schreiben.

Deshalb hat die STL viele clevere C ++ - Tricks entwickelt, um genauso effizient zu werden wie handgeschriebener C-Code.


9
2017-09-09 22:27



Sie sind wahrscheinlich in hohem Maße optimiert. Solche Implementierungen berücksichtigen Speicherseitenfehler, Cache-Fehler usw.

Die Quelle dieser Implementierungen hängt vom Compiler ab, mit dem sie ausgeliefert werden. Ich denke, dass die meisten Compiler (sogar Microsoft) Ihnen erlauben werden, sie zu sehen.

Ich denke, die wichtigsten Dinge zu wissen sind die Architektur, die Sie kompilieren und das Betriebssystem (falls vorhanden), auf dem Ihr Programm läuft. Wenn Sie diese Dinge verstehen, können Sie die Hardware präzise anvisieren.

Es gibt auch unzählige Optimierungstechniken. Dies ist eine gute Zusammenfassung. Globale Optimierung ist auch eine ganze Wissenschaft, also gibt es sicherlich viele Dinge zu lernen.

Es gibt einige kluge Dinge auch auf dieser Seite. Sok sikert!


3
2017-09-09 21:23



Wenn Sie die disassemblierte Version Ihres Codes im Vergleich zu ihrem Code betrachten und vergleichen, erhalten Sie möglicherweise einige Einblicke, warum sie schneller sind als Ihre.

Es scheint, als wäre es ein Idiot, die Standard-Bibliotheksfunktionalität von Grund auf neu zu implementieren, um schnellere Versionen zu erstellen. Es wäre viel besser, wenn Sie versuchen würden, ihre Version zu modifizieren, um Ihre Ziele zu erreichen, obwohl Sie selbst dann die zugrundeliegende Plattform verstehen müssen, um den Wert der von Ihnen vorgenommenen Änderungen einschätzen zu können.

Ich würde vermuten, dass Sie Ihre Sortierroutine posten sollten, dass sie in wenigen Minuten auseinander gerissen würde und Sie verstehen würden, warum Ihre Version wesentlich langsamer ist als die Standardbibliotheksversion.


2
2017-09-09 21:35



Die meisten IDEs verfügen über einen Befehl zum Öffnen einer benannten Header-Datei mit den Suchpfaden des Compilers. Ich benutze das ziemlich oft und tendiere dazu, den Code zu behalten algorithm öffnen.

Für mich ist der Code, nach dem Sie suchen, in

/usr/include/c++/4.2.1/bits/stl_algo.h
/usr/include/c++/4.2.1/bits/stl_tree.h

Beachten Sie, dass eine Menge Leute ihre Thesen zum Sortieren und zum Baum-Balancing gemacht haben (Felder, von denen ich denke, dass sie bis auf die Knochen reichen, ich würde dort keine Forschung versuchen), und viele von ihnen sind wahrscheinlich entschlossener als Sie, GCCs Standard-Bibliothek zu erstellen schneller.

Allerdings gibt es immer die Möglichkeit, für Ihren Code spezifische Muster zu nutzen (einige Unterbereiche sind bereits sortiert, häufig verwendete spezifische kleine Sequenzgrößen usw.).


2
2017-09-09 21:49



Zwei Antworten, wahrscheinlich allgemein anwendbar:

  • Sie werden wahrscheinlich nicht in der Lage sein, effizientere Versionen von Algorithmen zu implementieren, die viele andere intelligente Leute viel mehr Zeit damit verbracht haben, zu optimieren. Aufgrund der Zeit und des Tests allein werden die STD-Algorithmen ziemlich gut sein.

  • Bei identischen Algorithmen ist die Optimierung bei allen aktuellen Hardware- und Konfigurationsvarianten "sehr schwierig". Um ein Beispiel zu geben, könnte der Hauptfaktor für die Algorithmusleistung auf einer bestimmten Plattform sein, auf welchen Cache-Ebenen die am häufigsten verwendeten Routinen gespeichert werden können, was im Allgemeinen nicht von Hand optimiert werden kann. Daher ist der Compiler im Allgemeinen viel mehr ein Faktor für die tatsächliche Algorithmusleistung als irgendein bestimmter Code, den Sie schreiben können.

Aber ja ... wenn Sie es wirklich ernst meinen mit der Optimierung, gehen Sie in die Baugruppe und vergleichen Sie. Mein Rat wäre jedoch, sich auf andere Dinge zu konzentrieren, es sei denn, es ist Ihre Aufgabe, Ihre Implementierung oder etwas zu optimieren. Nur meine 2c.


1
2017-09-09 21:48