Ich baue eine AVL-Tree-Klasse, die eine feste maximale Anzahl von Items haben wird. Also dachte ich mir, anstatt jedes Element selbst zuzuteilen, würde ich einfach den gesamten Chunk auf einmal zuweisen und eine Bitmap verwenden, um bei Bedarf neuen Speicher zuzuweisen.
Mein Zuweisungs- / Freigabe-Code:
%Vor%Um standard new / delete zu verwenden, muss ich den Baum mit numitems == 0 konstruieren. Um meinen eigenen Allokator zu verwenden, gebe ich einfach die Anzahl der Items ein. Alle Funktionen sind für maximale Leistung inline.
Das ist alles gut und schön, aber mein eigener Allokator ist um 20% langsamer als neu / delete. Nun, ich weiß, wie komplex Speicherzuordner sind, es gibt keine Möglichkeit, dass Code schneller ausgeführt werden kann als ein Array-Lookup + ein Bit gesetzt, aber genau das ist hier der Fall. Was ist schlimmer: mein Deallocator ist langsamer, auch wenn ich den gesamten Code daraus entferne?!?
Wenn ich die Assembly-Ausgabe überprüfe, wird der Code-Pfad meines Zuordners mit QWORD PTR-Anweisungen gereist, die sich mit bitmap, avltree oder avlnode befassen. Es scheint nicht viel anders für den neuen / Löschpfad zu sein.
Beispiel: Assembly-Ausgabe von avltree :: newnode:
%Vor%Ich habe die Ausgabe der Kompilierung mehrfach überprüft, wenn ich meinen avltree mit dem Standard / benutzerdefinierten Zuordner konstruiere, und er bleibt in dieser bestimmten Code-Region gleich. Ich habe versucht, alle relevanten Teile zu entfernen / zu ersetzen, um keinen bedeutenden Effekt zu haben.
Um ehrlich zu sein, habe ich erwartet, dass der Compiler all dies inline macht, da es nur wenige Variablen gibt. Ich habe gehofft, dass alles außer den avlnode-Objekten selbst in Registern platziert wird, aber das scheint nicht der Fall zu sein.
Der Geschwindigkeitsunterschied ist jedoch eindeutig messbar. Ich rufe nicht 3 Sekunden pro 10 Millionen Knoten langsam eingefügt, aber ich erwartet, dass mein Code schneller, nicht langsamer als generische Allokator (2,5 Sekunden). Das gilt insbesondere für den langsameren Deallocator, der selbst dann langsamer ist, wenn der gesamte Code entfernt wurde.
Warum ist es langsamer?
Bearbeiten : Ich danke Ihnen allen für die ausgezeichneten Gedanken dazu. Aber ich möchte noch einmal betonen, dass das Problem nicht so sehr in meiner Zuteilungsmethode liegt, sondern in der suboptimalen Verwendung der Variablen: Die gesamte Klasse avltree enthält nur 4 UINT64-Variablen, die Bitliste nur 3.
Trotzdem optimiert der Compiler das nicht in Registern. Es besteht auf QWORD PTR-Anweisungen, die um Größenordnungen langsamer sind. Ist das, weil ich Klassen benutze? Soll ich zu C / plain-Variablen wechseln? Scratch das. Ich Idiot. Ich habe auch den ganzen Avltree Code drin, Dinge können nicht in Registern sein.
Außerdem bin ich total verloren, weshalb mein Deallocator immer noch langsamer wäre, selbst wenn ich ALLEN Code daraus lösche. Aber QueryPerformanceCounter sagt mir genau das. Es ist wahnsinnig, das zu denken: Derselbe Deallocator wird auch für den neuen / löschenden Codepfad aufgerufen und er muss den Knoten löschen ... Er muss nichts für meinen benutzerdefinierten Zuordner tun (wenn ich den Code entziehe).
Bearbeiten2: Ich habe jetzt die Bitliste komplett entfernt und die Freiraumverfolgung über eine einfach verknüpfte Liste implementiert. Die avltree :: newnode-Funktion ist jetzt viel kompakter (21 Anweisungen für meinen benutzerdefinierten Zuweisungsweg, 7 davon sind QWORD PTR-Operationen, die sich mit avltree befassen, und 4 werden für den Konstruktor von avlnode verwendet). Das Endergebnis (Zeit) sank von ~ 3 Sekunden auf ~ 2,95 Sekunden für 10 Millionen Zuweisungen.
Bearbeiten3: Ich habe auch den gesamten Code so umgeschrieben, dass jetzt alles von der einfach verlinkten Liste abgearbeitet wird. Jetzt hat die Klasse avltree nur zwei relevante Mitglieder: root und first_free. Die Geschwindigkeitsdifferenz bleibt erhalten.
Bearbeiten4: Code neu anordnen und Leistungszahlen betrachten, diese Dinge helfen am meisten:
#pragma pack(1) vor der Strukturdeklaration verringerte die Ausführungszeit um weitere 20% (2,5 Sekunden - & gt; 2 Sekunden) Bearbeiten Sie 5:
Da diese Frage sehr populär zu sein scheint, habe ich den endgültigen vollständigen Code als Antwort unten gepostet. Ich bin ziemlich zufrieden mit seiner Leistung.
Ihre Methode ordnet nur den Rohspeicher in einem Chunk zu und muss dann für jedes Element ein neues Placement erstellen. Kombinieren Sie das mit all dem Overhead in Ihrer Bitmap und es ist nicht zu verwunderlich, dass die standardmäßige new -Zuordnung bei leerem Heap Ihren Platz unterschreitet.
Um die größte Geschwindigkeitsverbesserung bei der Zuweisung zu erreichen, können Sie das gesamte Objekt in einem großen Array zuweisen und dann von dort aus zuweisen. Wenn Sie einen sehr einfachen und konstruierten Benchmark betrachten:
%Vor% Mit diesem Code auf MSVC ++ 2013 mit 50 Millionen Zuordnungen TestBucket() übertrifft TestNew() um einen Faktor von x16 (130 vs 2080 ms). Selbst wenn Sie ein std::bitset<> hinzufügen, um Zuordnungen zu verfolgen, ist es immer noch x4 schneller (400 ms).
Es ist wichtig, sich an new zu erinnern, dass die Zeit, die für die Zuweisung eines Objekts benötigt wird, im Allgemeinen vom Zustand des Heapspeichers abhängt. Ein leerer Heap ist in der Lage, eine Menge Objekte mit konstanter Größe wie diese relativ schnell zuzuordnen, was wahrscheinlich ein Grund dafür ist, dass Ihr Code langsamer als new erscheint. Wenn Sie ein Programm haben, das eine Weile läuft und eine große Anzahl von unterschiedlich großen Objekten zuweist, kann der Heap fragmentiert werden und das Zuweisen von Objekten kann viel (viel) länger dauern.
Als Beispiel hat ein Programm, das ich geschrieben habe, eine 200MB-Datei mit Millionen von Datensätzen geladen ... viele unterschiedlich große Zuweisungen. Beim ersten Laden dauerte es ~ 15 Sekunden, aber wenn ich diese Datei löschte und versuchte, sie erneut zu laden, brauchte sie etwas länger als x10-x20. Dies war ausschließlich auf die Speicherzuweisung zurückzuführen und der Wechsel zu einem einfachen Bucket / Arena-Allokator behob das Problem. Also, dieser konstruierte Benchmark, der eine x16-Beschleunigung zeigt, könnte tatsächlich einen deutlich größeren Unterschied mit einem fragmentierten Heap zeigen.
Es wird noch komplizierter, wenn Sie feststellen, dass verschiedene Systeme / Plattformen unterschiedliche Speicherzuweisungsschemata verwenden können, sodass die Benchmark-Ergebnisse auf einem System sich von denen eines anderen unterscheiden können.
Um dies in ein paar kurze Punkte zu destillieren:
Hinweis - Benchmarks wie diese sollen nicht realistisch sein, sind aber nützlich, um die Obergrenze dafür zu bestimmen, wie schnell etwas sein kann. Es kann zusammen mit dem Profil / Benchmark Ihres tatsächlichen Codes verwendet werden, um zu bestimmen, was optimiert werden sollte / sollte.
Aktualisieren - Ich kann Ihre Ergebnisse nicht in MSVC ++ 2013 in meinem Code replizieren. Wenn Sie dieselbe Struktur wie avlnode verwenden und ein Placement new ausprobieren, erhalten Sie dieselbe Geschwindigkeit wie bei meine Nicht-Placement-Bucket-Allokator-Tests (Platzierung neu war eigentlich ein bisschen schneller). Die Verwendung einer Klasse, die Ihrem avltree ähnlich ist, hat keinen großen Einfluss auf den Benchmark. Mit 10 Millionen Zuweisungen / Freigaben erhalte ich ~ 800 ms für die new / delete und ~ 200ms für den benutzerdefinierten Zuordner (sowohl mit als auch ohne Placement new ). Während ich mir keine Gedanken über den Unterschied in absoluten Zeiten mache, scheint der relative Zeitunterschied seltsam zu sein.
Ich würde vorschlagen, dass Sie sich Ihren Benchmark genauer ansehen und sicherstellen, dass Sie messen, was Sie für Sie halten. Wenn der Code in einer größeren Codebasis existiert, erstellen Sie einen minimalen Testfall, um ihn zu benchmarken. Stellen Sie sicher, dass Ihr Compileroptimierer nicht etwas tut, das den Benchmark ungültig machen würde (das passiert heutzutage zu einfach).
Beachten Sie, dass es viel einfacher wäre, Ihre Frage zu beantworten, wenn Sie sie auf ein minimales Beispiel reduziert und den vollständigen Code in die Frage aufgenommen hätten, einschließlich des Benchmark-Codes. Benchmarking ist eines der Dinge, die einfach scheinen, aber es gibt viele "gotchas" darin.
Update 2 - Beinhaltet die grundlegende Zuweisungsklasse und den Benchmark-Code, den ich verwende, damit andere versuchen können, meine Ergebnisse zu duplizieren. Beachten Sie, dass dies nur für Testzwecke gilt und weit vom tatsächlichen Arbeits- / Produktionscode entfernt ist. Es ist viel einfacher als Ihr Code, weshalb wir möglicherweise unterschiedliche Ergebnisse erzielen.
%Vor% Momentan bekomme ich ~ 800ms für TestNew() und TestClass(0) und unter 200ms für TestClass(NUM_ALLOCS + 10) . Der benutzerdefinierte Zuordner ist ziemlich schnell, da er auf dem Speicher in einer vollständig linearen Weise arbeitet, die es dem Speichercache erlaubt, seine Magie zu wirken. Ich verwende auch GetTickCount() zur Vereinfachung und es ist genau genug, solange Zeiten über ~ 100ms sind.
Nun, ich weiß, wie komplex Speicherzuordner sind, es gibt keine Möglichkeit, dass Code schneller ausgeführt werden kann als ein Array-Lookup + ein Bit gesetzt, aber genau das ist hier der Fall.
Das ist nicht annähernd richtig. Ein anständiger Bucket-Heap mit niedriger Fragmentierung ist O (1) mit einer sehr niedrigen konstanten Zeit (und effektiv null zusätzlichen Platz-Overhead). Ich habe eine Version gesehen, die vorher auf ~ 18 Asm-Anweisungen (mit einem Zweig) kam. Das ist viel weniger als dein Code. Denken Sie daran, dass Haufen insgesamt sehr komplex sein können, aber der schnelle Weg durch sie kann wirklich sehr schnell sein.
Nur zu Referenzzwecken war der folgende Code der leistungsfähigste für das vorliegende Problem.
Es ist nur eine einfache Implementierung von avltree, aber es erreicht 1,7 Sekunden für 10 Millionen Einsätze und 1,4 Sekunden für die gleiche Anzahl von Löschvorgängen auf meinem 2600K @ 4,6 GHz.
%Vor%Tags und Links c++ performance memory-management allocator