Was beeinflusst die Geschwindigkeit von C++-Programmen und wie erreicht man sie auf einer hohen Codeebene? Der leitende Entwickler der CatBoost-Bibliothek Evgeniy Petrov beantwortete diese Fragen anhand von Beispielen und Illustrationen aus seiner Erfahrung mit CatBoost für x86_64.
Videobericht
- Hallo zusammen. Ich optimiere die CatBoost-Bibliothek für maschinelles Lernen für die CPU. Der Hauptteil unserer Bibliothek ist in C++ geschrieben. Heute erzähle ich Ihnen, wie wir mit einfachen Mitteln Geschwindigkeit erreichen.
Die Berechnungsgeschwindigkeit besteht aus zwei Teilen. Der erste Teil ist der Algorithmus. Wenn wir bei der Auswahl eines Algorithmus einen Fehler machen, können wir ihn nicht schnell zum Laufen bringen. Der zweite Teil ist, wie optimiert unser Algorithmus für das Computersystem ist, das wir haben, mit seiner Leistung und seinem Durchsatz.
Datenaustausch und Berechnungen müssen aufgrund der großen Geschwindigkeitsunterschiede gesondert betrachtet werden. Wenn wir die Geschwindigkeit des Gedächtnisses als die Geschwindigkeit eines Fußgängers betrachten, dann entspricht die Rechengeschwindigkeit ungefähr der Reisegeschwindigkeit eines Passagierflugzeugs.
Um diesen Unterschied auszugleichen, verfügt die Architektur über mehrere Caching-Ebenen. Der schnellste und kleinste ist der L1-Cache. Dann gibt es einen größeren und langsameren Second-Level-Cache. Und es gibt einen sehr großen Cache, der mehrere zehn Megabyte groß sein kann, einen Cache der dritten Ebene, aber er ist der langsamste.
Aufgrund der unterschiedlichen Geschwindigkeit des Datenaustauschs von Berechnungen wird der Rechencode in zwei Klassen eingeteilt. Eine Klasse ist durch die Bandbreite, also die Geschwindigkeit des Datenaustauschs, begrenzt. Die zweite Klasse ist durch die Geschwindigkeit des Prozessors begrenzt. Die Grenze zwischen ihnen wird abhängig von der Anzahl der Operationen festgelegt, die mit einem Datenbyte ausgeführt werden. Dies ist normalerweise eine codespezifische Konstante.
Der Großteil des rechenintensiven Codes wurde schon vor langer Zeit geschrieben, ist sehr gut optimiert und es gibt eine große Anzahl an Bibliotheken. Daher ist es sinnvoll, nach einer Bibliothek zu suchen, die dazu in der Lage ist, wenn Sie in Ihrem Code rechenintensiv sind es für dich.
Im Übrigen können Compiler nicht alles tun, da nur ein sehr begrenzter Prozentsatz der Ressourcen für ihre Entwicklung aufgewendet wird. Welche von ihnen entwickeln sich heute mehr oder weniger aktiv weiter, das heißt, sie unterstützen Standards und versuchen, diese zu überwachen? Hierbei handelt es sich um ein Frontend-EDG, das in verschiedenen Derivaten verwendet wird, beispielsweise im Intel-Compiler. LLVM; GNU und Frontend Microsoft.
Da es nur wenige davon gibt, unterstützen Compiler nur Frequenzkontrollmuster und Datenabhängigkeiten. Betrachten wir die Steuerung, dann handelt es sich um lineare Abschnitte und einfache Zyklen, also eine Abfolge von Anweisungen und Wiederholungen. Sie lernen Häufigkeitsabhängigkeiten aus Daten der Reduktion, wenn wir beispielsweise viele Elemente zu einem zusammenfassen, reduzieren und Element-für-Element-Operationen an einem oder mehreren Arrays durchführen.
Was bleibt den Entwicklern übrig? Dies lässt sich grob in vier Teile unterteilen. Das erste ist die Anwendungsarchitektur; Compiler können sie einfach nicht für uns entwickeln.
Parallelisierung ist auch für Compiler eine schwierige Sache. Die Arbeit mit dem Speicher ist wirklich schwierig: Sie müssen die Architektur, die Parallelisierung und alles zusammen berücksichtigen. Darüber hinaus wissen Compiler nicht, wie sie die Qualität der Optimierung und die Geschwindigkeit des Codes richtig bewerten können. Auch wir Entwickler müssen dies tun, eine Entscheidung treffen – weiter optimieren oder aufhören.
Auf der Architekturseite schauen wir uns die Amortisierung des Overheads, der virtuellen Aufrufe, an, auf denen ein Großteil der Architektur basiert.
Lassen wir die Parallelisierung aus der Gleichung heraus. Was die Nutzung des Speichers betrifft: Dies ist gewissermaßen auch die Abwertung und korrekte Arbeit mit Daten, deren korrekte Platzierung im Speicher. Im Hinblick auf die Effizienzbewertung sprechen wir über Profiling und die Suche nach Engpässen im Code.
Die Verwendung von Schnittstellen und abstrakten Datentypen ist eine der grundlegenden Entwurfstechniken. Schauen wir uns einen ähnlichen Rechencode aus dem maschinellen Lernen an. Dies ist ein bedingter Code, der die Prognose mithilfe einer Gradientenmethode aktualisiert.
Wenn wir ein wenig nach innen schauen und versuchen zu verstehen, was im Inneren passiert, haben wir eine IDerCalcer-Schnittstelle zum Berechnen von Ableitungen der Verlustfunktion und eine Funktion, die die Prognose (unsere Vorhersage) entsprechend dem Gradienten der Verlustfunktion verschiebt.
Auf der rechten Seite der Folie sehen Sie, was das für den zweidimensionalen Fall bedeutet. Und beim maschinellen Lernen beträgt die Größe der Prognose nicht zwei oder drei, sondern Millionen, Dutzende Millionen Elemente. Sehen wir uns an, wie gut dieser Code für einen Vektor mit etwa 10 Millionen Elementen ist.
Nehmen wir die Standardabweichung als Zielfunktion und messen wir, wie sie funktioniert und wie lange es dauern wird, diese Prognose zu verschieben. Die Ableitung dieser Zielfunktion ist auf der Folie dargestellt. Die Betriebszeit auf einer bedingten Maschine, die dann fest bleibt, beträgt 40 ms.
Versuchen wir zu verstehen, was hier falsch ist. Das erste, was Aufmerksamkeit erregt, sind virtuelle Anrufe. Schaut man sich den Profiler an, sieht man, dass es sich je nach Anzahl der Parameter um etwa fünf bis zehn Anweisungen handelt. Und wenn, wie in unserem Fall, die Berechnung der Ableitung selbst nur aus zwei arithmetischen Operationen besteht, kann dies leicht zu einem erheblichen Mehraufwand führen. Für einen großen Körper beträgt dieser bei der Berechnung von Derivaten ca. Für einen Short-Körper, der die Ableitung berechnet – sagen wir nicht einmal 500 Anweisungen, sondern 20, 50 oder noch weniger – wird dies bereits ein erheblicher Prozentsatz in der Zeit sein. Was zu tun? Versuchen wir, den virtuellen Funktionsaufruf durch eine Änderung der Schnittstelle zu amortisieren.
Zunächst haben wir die Ableitungen punktweise für jedes Element des Vektors separat berechnet. Gehen wir von der Element-für-Element-Verarbeitung zur Vektorverarbeitung über. Nehmen wir eine Standard-C++-Vorlage, die es Ihnen ermöglicht, mit einer Ansicht auf einem Vektor zu arbeiten. Wenn Ihr Compiler den neuesten Standard nicht unterstützt, können Sie auch eine einfache hausgemachte Klasse verwenden, die einen Zeiger auf die Daten und die Größe speichert. Wie wird sich der Code ändern? Uns bleibt nur ein Aufruf, der die Ableitungen berechnet, und dann müssen wir eine Schleife hinzufügen, die die Prognose tatsächlich aktualisiert.
Zusätzlich zum Hinzufügen eines Zyklus müssen wir uns die Daten ein zweites Mal ansehen, d. h. den Prognosevektor selbst und den gerade berechneten Gradientenvektor ein zweites Mal lesen.
Versuchen wir es noch einmal auf derselben Maschine und stellen Sie fest, dass es schlimmer geworden ist, etwas ist schief gelaufen. Lassen Sie uns herausfinden, was mit dem Code passiert ist.
Es macht keinen Sinn, den Zyklus irgendetwas zu vermuten, da dies genau das gleiche Frequenzmuster ist, das Compiler gut erkennen und optimieren. Die Anzahl der Operationen pro Datenelement wird dort geringer sein als die Kosten eines virtuellen Anrufs.
Wenn Sie jedoch einen großen Vektor erstellen und ihn wiederholt durchlaufen, sollten Sie hier ein Problem vermuten. Um zu verstehen, warum das schlecht ist und langsamer wird, müssen Sie sich vorstellen, was im Speicher passiert, wenn der Code, den wir auf der Folie rechts sehen, ausgeführt wird.
Bei der Berechnung des Ableitungsvektors kommt es zu einer Schleife, die die Prognose verschiebt. Vor diesem Zyklus verbleibt nur ein sehr kleiner Teil der Daten im schnellen LXNUMX-Cache, der mit Prozessorgeschwindigkeit läuft. Auf der Folie ist es an einer Ampel grün. Die verbleibenden Daten werden aus dem Cache in den Speicher verschoben, und wenn der Zyklus mit der Aktualisierung der Prognosen beginnt, müssen die Daten ein zweites Mal aus dem Speicher gelesen werden. Aber bei uns funktioniert es im Allgemeinen sehr langsam, im Schritttempo.
Wenn wir eine Prognose aktualisieren, müssen wir nicht alle Derivate auf einmal lesen. Es reicht aus, sie in großen Paketen zu zählen, um virtuelle Anrufe aufzunehmen. Daher ist es sinnvoll, die Berechnung der Derivate und die Aktualisierung der Prognose in kleine Blöcke aufzuteilen und diese beiden Aktionen zu vermischen. Wozu führt das, wenn wir uns ansehen, woher die Daten gelesen werden?
Dies führt dazu, dass wir ständig Daten erfassen und dass die Daten im L1-Cache verbleiben und keine Zeit haben, in den langsamen Speicher zu gelangen. Und dann müssen wir verstehen, wer uns diese Blockgröße verrät.
Es ist logisch, dies dem Ableitungsrechner selbst anzuvertrauen, denn nur dieser weiß, wie viel Cache er benötigt. Als nächstes müssen wir die Schleife neu schreiben, die das Array durchsucht hat. Es muss in zwei Teile geteilt werden. Die äußere Schleife durchläuft die Blöcke und im Inneren durchlaufen wir die Elemente des Blocks zweimal.
Hier ist es, extern in Blöcken.
Und hier ist die interne für die Elemente des Blocks.
Wir berücksichtigen, dass der letzte Block möglicherweise unvollständig ist.
Mal sehen, was dabei herauskommt. Wir sehen, dass wir richtig geraten, richtig verstanden haben, was vor sich ging, und auf Kosten recht kleiner Änderungen im Code die Betriebszeit um acht Prozent reduziert haben. Aber wir können noch mehr tun. Wir müssen noch einmal kritisch hinterfragen, was wir geschrieben haben. Schauen Sie sich die Funktion an, die für uns Ableitungen berechnet. Es gibt uns einen Vektor von Derivaten zurück, auf deren Elemente in ungünstigen Situationen nur langsam zugegriffen werden kann.
Hier gibt es zwei Gründe. Platzieren Sie zunächst den Vektor auf dem Heap. Die Wahrscheinlichkeit ist hoch, dass dieser Vektor viele Male erstellt und zerstört wird. Der zweite Nachteil in Bezug auf die Geschwindigkeit besteht darin, dass wir jedes Mal Speicher erhalten, wahrscheinlich an einer neuen Adresse. Dieser Speicher ist aus Cache-Sicht „kalt“, was bedeutet, dass der Prozessor vor dem Schreiben in ihn einen Hilfslesevorgang durchführt, um die Daten im Cache zu initialisieren.
Um dies zu beheben, müssen Sie die Zuordnung aus der Schleife nehmen. Dazu müssen wir die Schnittstelle erneut ändern, die Rückgabe von Vektoren stoppen und damit beginnen, Ableitungen in den Speicher zu schreiben, die wir vom aufrufenden Code erhalten.
Dies ist eine Standardtechnik, bei der alle Manipulationen mit Ressourcen aus Engpässen im Rechencode entfernt werden. Fügen wir der CalcDer-Methode einen weiteren Parameter hinzu, nämlich die Ansicht des Vektors, wohin die Ableitungen gehen sollen.
Der Code wird sich auch auf offensichtliche Weise ändern. Der Ableitungsvektor ist außerhalb aller Schleifen eins, und der Methode wird einfach ein neuer Parameter hinzugefügt.
Mal sehen. Es stellt sich heraus, dass wir im Vergleich zur Vorgängerversion rund acht Prozent und im Vergleich zur Basisversion bereits 15 % mehr gewonnen haben.
Es ist klar, dass sich Optimierungen nicht auf die Amortisierung von Gemeinkosten beschränken, sondern dass es auch andere Arten von Engpässen gibt.
Um zu veranschaulichen, wie man nach Engpässen sucht, benötigen wir einen weiteren einfachen Testcode. Ich habe zum Beispiel die Matrixtransponierung genommen. Wir haben eine Matrix approx und eine Matrix approxByCol, in die wir die transponierten Daten einfügen müssen. Und ein einfaches Nest aus zwei Schleifen. Hier gibt es keine virtuellen Aufrufe oder Vektorerstellung. Es werden lediglich Daten übertragen. Die Schleife ist relativ Compiler-freundlich.
Lassen Sie uns messen, wie dieser Code auf einer ziemlich großen Matrix und auf einer bestimmten Maschine funktioniert.
Ich habe beispielsweise die Anzahl der Zeilen mit 1000 und die Anzahl der Spalten mit 100 angenommen. Die Maschine ist ein Intel-Server mit einem Kern. Beim Speicher verhält es sich genau so, das ist uns wichtig, denn alle Arbeiten mit dem Speicher und der Geschwindigkeit hängen von der Geschwindigkeit des Speichers ab. Wir haben es gemessen und 000 s erhalten. Ist es viel oder wenig? Was schaffen wir in dieser Zeit?
Wir schaffen es, 800 Megabyte zu lesen, das ist keine transponierte Matrix, sondern das Original. Und auch 1,6 GB lesen und schreiben, das ist schon eine transponierte Matrix. Der Prozessor führt vor dem Schreiben einen Hilfslesevorgang durch, um die Daten im Cache zu initialisieren.
Berechnen wir, wie viel Bandbreite wir sinnvoll genutzt haben. Es stellte sich heraus, dass der Durchsatz unseres Codes 1,7 GB/s betrug.
Dies war eine theoretische Berechnung. Als nächstes können Sie einen Profiler verwenden, der die Geschwindigkeit der Arbeit mit dem Speicher messen kann. Ich habe VTune genommen. Mal sehen, was er zeigt. Zeigt eine ähnliche Zahl - 1,8 GB. Im Prinzip stimmt es gut, denn bei unserer Berechnung haben wir nicht berücksichtigt, dass wir die Zeilenadressen und Spaltenadressen lesen müssen. Außerdem protokolliert VTune Hintergrundaktivitäten im Betriebssystem. Daher stimmt unser Modell mit der Realität überein.
Um zu verstehen, ob 1,7 GB viel oder wenig sind, müssen wir herausfinden, welche maximale Bandbreite uns zur Verfügung steht.
Dazu müssen Sie die Prozessorspezifikationen lesen. Es gibt eine spezielle Website ark.intel.com, auf der Sie alles über jeden Prozessor erfahren können. Wenn wir uns unseren Server genauer ansehen, sehen wir, dass er über acht Kerne verfügt und der schnellste unterstützte DDR3-Speicher in der Lage ist, etwa 60 GB/s in eine Richtung zu übertragen.
Hier müssen wir jedoch berücksichtigen, dass wir nur einen Kern verwenden und unser Speicher langsamer ist, das heißt, wir müssen diese 60 GB im Verhältnis zur Anzahl der Kerne und der Speicherfrequenz an unsere Verhältnisse skalieren.
Es stellt sich heraus, dass unser Code in eine Richtung 5,3 GB verbrauchen könnte. Und da man parallel lesen und schreiben kann, würden wir im Idealfall 10,6 erreichen, wenn wir einfach Daten von Ort zu Ort kopieren würden. Da wir zwei Lesevorgänge und einen Schreibvorgang durchführen, sollten es ungefähr 8 GB/s sein. Wir erinnern uns, dass wir 1,7 erreicht haben. Das heißt, wir haben etwa 20 % verbraucht.
Warum passiert das? Auch hier müssen Sie die Architektur verstehen. Tatsache ist, dass Daten zwischen Speicher und Cache nicht in beliebigen Paketen übertragen werden, sondern in genau 64 Bytes, nicht mehr und nicht weniger. Dies ist die erste Überlegung.
Die zweite Überlegung besteht darin, dass wir transponierte Daten nicht sequentiell, sondern zufällig schreiben, da die Zeilen der Matrix auf unvorhersehbare Weise im Speicher liegen.
Es stellt sich heraus, dass wir vor dem Schreiben einer reellen Zahl 64 Datenbytes lesen müssen. Wenn wir die Größe der Matrix mit N bezeichnen, erhalten wir anstelle der optimalen Betriebszeit (N/5,3 + N/10,6) (8*N/5,3 + N/10,6). Irgendwo vier- bis fünfmal mehr, was diesen Wirkungsgrad von 20 % erklärt.
Was tun dagegen? Sie müssen aufhören, Daten spaltenweise zu schreiben, und mit dem Schreiben so vieler Spalten beginnen, wie in eine Cache-Zeile (64 Byte) passen. Dazu teilen wir die Schleife entlang der Spalten in eine Schleife über Cache-Zeilen und eine verschachtelte Schleife über Cache-Zeilenelemente auf.
Hier sind sie, Iterationen entlang der Cache-Zeilen.
Und hier sind sie, Iterationen innerhalb der Cache-Zeile. Der Einfachheit halber gehen wir hier davon aus, dass die Daten an der Cache-Zeilengrenze ausgerichtet sind. Schauen wir uns nun an, was mit VTune passiert.
Wir sehen, dass das Ergebnis nahe an den berechneten acht Gigabyte pro Sekunde liegt – 7,6. Aber es ist keine Tatsache, dass all diese 7,6 nützliche Arbeiten sind. Vielleicht sind einige davon über Kopf.
Um zu verstehen, welchen Nutzen wir erzielt haben, messen wir die Betriebszeit nach der Optimierung. Es stellt sich heraus, dass es auf derselben Maschine 0,5 s dauert. Die Bandbreite aufgrund der Transposition selbst beträgt 4,8 GB/s. Es ist zu erkennen, dass es immer noch eine Reserve gibt, die wir nicht ausgewählt haben, aber dennoch haben wir ab 20 Prozent Wirkungsgrad 60 Prozent erreicht.
Mit dem Profiler können wir herausfinden, warum wir nicht 80 % oder 95 % erreicht haben.
Tatsache ist, dass wir Matrizen als Vektoren von Vektoren speichern, das heißt, wir verwenden den Speicherzugriff mit doppelter Indirektion.
Mithilfe von VTune können Sie sehen, welche Anweisungen für den Zugriff auf Array-Elemente generiert werden. Anweisungen, die die Adressen der Spalten der transponierten Matrix lesen, sind links gelb hervorgehoben. Und das sind erstens zusätzliche Anweisungen und zweitens zusätzliche Datenübertragungen. Aber wir werden nicht weiter optimieren, lassen Sie uns innehalten und zusammenfassen.
Was habe ich dir heute erzählt? Ein nützlicher Tipp für die Arbeit mit Computercode ist die blockweise Verarbeitung, um beispielsweise den Overhead zu amortisieren, der mit virtuellen Aufrufen verbunden ist. Außerdem verbessert sich durch die Blockierung die Datenlokalität und wir erhalten höhere Zugriffsgeschwindigkeiten.
Das Entfernen von Zuweisungen aus Engpässen ist auch deren Amortisation. Außerdem wird die Zugriffsgeschwindigkeit erhöht, indem temporäre Puffer im Speicher repariert werden.
Apropos Profiling. Erstens ist Profiling eine nützliche Technik, um „im Allgemeinen“ Engpässe zu finden. Zweitens ermöglicht es uns, die Effizienz des Codes zu bewerten, zu entscheiden, ob wir mit der Geschwindigkeit zufrieden sind oder weiter optimieren möchten, und zeigt uns, in welche Richtung wir uns bewegen müssen.
Das ist alles für mich. Wenn Sie CatBoost verwenden oder zum ersten Mal davon gehört haben und wissen möchten, was es ist, lesen Sie , besuchen Sie uns unter , schreiben Sie an . Vielen Dank für eure Aufmerksamkeit.
Source: habr.com
