Aktualisiert , ursprüngliche Frage unter der Zeile:
Ich muss einen Median berechnen und möchte den O (N) Quickselect-Algorithmus verwenden. Es stellt sich jedoch heraus, dass die Laufzeit nicht länger mit O (N) skaliert, wenn das Array nicht länger ein flaches Array von Doppelpunkten ist, sondern ein Array von Strukturen (von denen ein Element das für die Medianberechnung zu verwendende Element ist).
Die folgende Flat-Array-Version hat annähernd lineare Laufzeit:
%Vor%Gibt:
%Vor%Die folgende Version mit Strukturen hat jedoch nicht lineare Laufzeit:
%Vor%Gibt:
%Vor%Beide Versionen wurden mit gcc -O2 kompiliert (aber -O0 gibt die gleiche Skalierung).
Woher kommt diese Änderung der Skalierung und wie kann sie behoben werden?
Beachten Sie, dass ich zwar die Struktur ändern kann, aber nicht nur den Median y , weil ich auch die anderen Parameter kennen muss, die dem Medianpunkt entsprechen.
Zusätzlich benötige ich das Quickselect-Verhalten für das resultierende Array (z. B. a.y <= m.y für alle a links von m und b.y > m.y für alle b rechts von m ).
Ich muss einen Median berechnen und möchte den O (N) Quickselect-Algorithmus verwenden. Es stellt sich jedoch heraus, dass die Laufzeit nicht länger mit O (N) skaliert, wenn das Array nicht länger ein flaches Array von Doppelpunkten ist, sondern ein Array von Strukturen (von denen ein Element das für die Medianberechnung zu verwendende Element ist).
Ich benutze die folgende Implementierung:
%Vor% mit -O2 die Struktur ist weg optimiert (ich denke, zumindest die Skalierung sieht genauso aus wie bei einem einfachen Array) und die Skalierung ist linear.
Wenn Sie jedoch die anderen Komponenten der Struktur auskommentieren, ist die Skalierung nicht länger linear.
Wie kann das sein?
Und wie kann das behoben werden?
Beachten Sie, dass ich zwar die Struktur ändern kann, aber nicht nur den Median y , weil ich auch die anderen Parameter kennen muss, die dem Medianpunkt entsprechen.
Zusätzlich benötige ich das Quickselect-Verhalten für das resultierende Array (z. B. a.y <= m.y für alle a links von m und b.y > m.y für alle b rechts von m ).
Ich denke, Memory-Cache-Mishits erklären das nichtlineare Wachstum der Ausführungszeit. In meinem x86_64-Architektur-PC (Linux + gcc) ist sizeof(double) 8 und sizeof(point_t) ist 32, so dass weniger Elemente in den Cache-Speicher passen. Größerer Grund für das nichtlineare Wachstum ist jedoch, dass Speicherzugriffe auf die point_t -Strukturen durch das Pointer-Array in Ihrem Code schnell stark randomisiert werden und mehr und mehr Cache-Misses auftreten, weil ...
Ich habe den Code wie folgt geändert:
%Vor%und das Wachstum der Ausführungszeit ist linearer.
Original quicselect() mit double array:
Original quickselect() mit point_t * array:
Genau das gleiche quickselect() mit point_t * -Array wie oben, aber sicherstellen, dass die Zeiger im Array in folgerichtiger Reihenfolge sind, bevor% code_de% aufgerufen wird, indem das obige Patch angewendet wird:
Beachten Sie, dass selbst wenn die geänderte Version die zusätzliche Sortierung in der Timing-Schleife durchführt, sie immer noch schneller ist.
Ich betreibe 3,2 GHz Pentium (R) Dual-Core-CPU E6700, 64-Bit-Linux, gcc 4.6, Optimierung quickselect() . (Meine Maschine ist nicht untätig, so dass meine Benchmark-Zahlen einige Fluktuationen haben - ich würde auch -O2 für erhöhte Genauigkeit im Linux-System verwenden, wenn ich ernsthaftere Benchmarks für die Berechnung des Zeitpunkts erstelle, an dem der Kernel den Benchmarked-Prozess nicht plant run.)
UPDATE: Beispielsweise kann clock_gettime(CLOCK_PROCESS_CPUTIME_ID, ...) (falls von Ihrer Plattform unterstützt) verwendet werden, um die Auswirkungen der Cache-Treffer zu analysieren. Ich modifizierte das Programm, um zwei Argumente zu nehmen, die Array-Größe (entsprechend den Elementen des Arrays valgrind ) und die Testzahl (entsprechend N[] ). Ausführungszeiten ohne ntest , wobei valgrind im Wesentlichen das unmodifizierte Programm ist, das in der Frage aufgelistet ist, und test2 ist die modifizierte Version, die das Array test4 neu anordnet, bevor die Funktion ap[] aufgerufen wird:
Hier ist das Ergebnis der Ausführung von quickselect() mit dem cachegrind-Tool:
und
%Vor%Siehe Valgrind-Handbuch , um diese Statistiken zu lesen. Ein wesentlicher Punkt ist: "Auf einer modernen Maschine kostet ein L1-Fehlversuch in der Regel etwa 10 Zyklen, ein LL-Fehler kann bis zu 200 Zyklen kosten" . Das Berechnen von LLd ( Lastlevel-Daten -Cache) führt zu einem Kostenunterschied zwischen den beiden Fällen (jede Differenz in Fehltreffern multipliziert mit den angenommenen 200 Zyklen pro 3,2e9 Zyklen / Sekunde für 3,2 GHz CPU) ergibt
%Vor%Die D1-Fehlschläge tragen hier ziemlich wenig bei (insgesamt 91 Sekunden vorausgesetzt, wenn die Kosten für D1-Fehltritte unabhängig von den LLd-Fehlkosten sind); Mit all unseren Ungenauigkeiten (vor allem über die tatsächlichen Kosten von LLD Misshit in diesem Computer) können die D1-Fehler einfach ignoriert werden.
Die Laufzeitunterschiede für valgrind und test2 kommen auf ungefähr 106 Sekunden, was ziemlich nah an den oben genannten 86 Sekunden liegt . Dies alles könnte genauer gemacht werden, aber dies scheint bereits den Effekt von Cache-Misses in der Testanordnung zu demonstrieren.
P.S. test4 schreibt eine Protokolldatei, in der ich überprüfen konnte, ob die Größen und Typen der L2- und L1-Caches korrekt zu erkennen sind.
Es sieht so aus, als würden Sie die tatsächlichen Strukturen sortieren und austauschen, was bedeutet, dass Sie viel mehr Dinge bewegen. Sie sollten versuchen, mit einem Array von Zeigern zu den Strukturen zu sortieren und diese zu tauschen.
Also würde Ihre Median-Funktion einen Prototyp haben von:
%Vor%Und dann müssten Sie die Strukturen zuweisen und freigeben und ihre Zeiger in das Array einfügen, bevor Sie sie aufrufen, anstatt die Elemente des Arrays direkt mit der Struktur zu füllen.
Tags und Links optimization c