Warum ist dieser C ++ - Code schneller als meine handgeschriebene Assembly zum Testen der Collatz-Vermutung?
Ich schrieb diese zwei Lösungen für Projekt Euler F14, in Assembler und in C++. Sie sind die gleichen brute-force-Ansatz für die Prüfung der Collatz-Vermutung. Die Montage-Lösung wurde montiert mit
nasm -felf64 p14.asm && gcc p14.o -o p14
C++ kompiliert wurde mit
g++ p14.cpp -o p14
Montage p14.asm
section .data
fmt db "%d", 10, 0
global main
extern printf
section .text
main:
mov rcx, 1000000
xor rdi, rdi ; max i
xor rsi, rsi ; i
l1:
dec rcx
xor r10, r10 ; count
mov rax, rcx
l2:
test rax, 1
jpe even
mov rbx, 3
mul rbx
inc rax
jmp c1
even:
mov rbx, 2
xor rdx, rdx
div rbx
c1:
inc r10
cmp rax, 1
jne l2
cmp rdi, r10
cmovl rdi, r10
cmovl rsi, rcx
cmp rcx, 2
jne l1
mov rdi, fmt
xor rax, rax
call printf
ret
C++, p14.cpp
#include <iostream>
using namespace std;
int sequence(long n) {
int count = 1;
while (n != 1) {
if (n % 2 == 0)
n /= 2;
else
n = n*3 + 1;
++count;
}
return count;
}
int main() {
int max = 0, maxi;
for (int i = 999999; i > 0; --i) {
int s = sequence(i);
if (s > max) {
max = s;
maxi = i;
}
}
cout << maxi << endl;
}
Weiß ich über die compiler-Optimierungen zur Verbesserung der Geschwindigkeit und alles, aber ich sehe nicht viele Möglichkeiten zur Optimierung meiner Montage-Lösung weiter (sprechen programmatisch nicht mathematisch).
Den C++ - code Modul-jeder Begriff und jeder division auch Begriff, wo die Montage ist nur eine division pro sogar Begriff.
Aber die assembly ist, die durchschnittlich 1 Sekunde länger als die C++ - Lösung. Warum ist das so? Ich Frage aus vor allem Neugier.
Ausführungszeiten
Mein system: 64-bit-Linux auf 1.4 GHz Intel Celeron 2955U (Haswell-Mikroarchitektur).
-
g++
(nicht optimierten): avg 1272 ms -
g++ -O3
avg 578 ms -
original asm (div) avg 2650 ms
-
Asm (shr)
avg 679 ms -
@johnfound asm, montiert mit nasm avg 501 ms
-
@hidefromkgb asm avg 200 ms
-
@Veedrac C++ avg 81 ms mit
-O3
, 305 ms mit-O0
-S
, um die assembly, die der compiler generiert. Der compiler ist schlau genug zu erkennen, dass der E-Modul hat die division an der gleichen Zeit. InformationsquelleAutor der Frage jeffer son | 2016-11-01
Du musst angemeldet sein, um einen Kommentar abzugeben.
Wenn Sie denken, dass ein 64-bit-DIV-Anweisung ist eine gute Möglichkeit, um durch zwei teilen, dann kein Wunder, dass der compiler asm Ausgabe schlagen Sie Ihre hand-code geschrieben, sogar mit
-O0
(compile schnell, keine extra Optimierung", und speichern/laden Speicher nach/vor jeder C-Anweisung, so dass ein debugger können Variablen ändern).Sehen Agner Fog ist die Optimierung von Montage-Anleitung zu lernen, wie zu schreiben effiziente asm. Er hat auch Anweisung Tabellen und microarch guide für spezifische details für bestimmte CPUs. Siehe auch die x86 - tag wiki für mehr perf links.
Siehe auch dieser mehr Allgemeinen Frage, schlagen Sie den compiler mit der hand geschrieben asm: Ist inline-Assembler langsamer als nativer C++ - code?. TL:DR: ja, wenn Sie es falsch machen (wie bei dieser Frage).
In der Regel sind in Ordnung, ließ der compiler seine Sache tun, vor allem, wenn Sie versuchen C++ zu schreiben, kompilieren können effizient. Siehe auch ist die Montage schneller als kompilierte Sprachen?. Eine der Antworten, die links zu diese nette Dias, die zeigen, wie verschiedene C-Compiler optimieren einige wirklich einfache Funktionen mit coolen tricks.
Auf Intel Haswell,
div r64
ist 36 uops, mit einem Latenz von 32-96 Zyklen, und einen Durchsatz von einem pro 21-74 Zyklen. (Plus die 2 uops einrichten, RBX und null-RDX, aber out-of-order-Ausführung kann die früh -). High-uop-count Anweisungen, wie DIV sind microcoded, das kann auch zu front-end-Engpässe. In diesem Fall ist die Latenz der meisten relevanten Faktor, weil es ein Teil von einer Schleife getragen Abhängigkeit Kette.shr rax, 1
hat den gleichen unsigned-division: Es ist 1 uop, mit 1c Latenz, und kann ausführen 2 pro Takt.Zum Vergleich, 32-bit-division ist schneller, aber immer noch schrecklich vs. verschiebt.
idiv r32
9 uops, 22-29c Latenz, und eine pro 8-11c Durchsatz auf Haswell.Wie Sie sehen können aus der Betrachtung gcc
-O0
asm-Ausgabe (Godbolt compiler explorer), verwendet es nur Verschiebungen Anweisungen. clang-O0
nicht kompilieren naiv wie Sie dachte, auch mit 64-bit-IDIV zweimal. (Wenn die Optimierung, die Compiler verwenden, werden beide Ausgänge des IDIV, wenn die Quelle eine division und modulus mit den gleichen Operanden, wenn Sie IDIV)GCC nicht ganz-naiv-Modus; es verwandelt immer durch GIMPLE, was bedeutet, dass einige "Optimierungen" kann nicht deaktiviert werden. Dies beinhaltet die Erkennung division-by-Konstante und mit Verschiebungen (Potenz von 2) oder ein fester Punkt multiplikative inverse (non power of 2) zu vermeiden, IDIV (siehe
div_by_13
im obigen godbolt link).gcc -Os
(optimize for size) hat Verwendung IDIV für non-power-of-2-division,leider auch in Fällen, in denen das multiplikative inverse code ist nur geringfügig größer, aber viel langsamer.
Hilft der compiler
(Zusammenfassung für diesen Fall: verwenden Sie
uint64_t n
)Erste von allen, es ist nur interessant zu schauen, optimierte compiler-Ausgaben. (
-O3
).-O0
- Geschwindigkeit ist im Grunde bedeutungslos.Blick auf Ihre asm-Ausgabe (auf Godbolt, oder sehen Zum entfernen von "Rauschen" von GCC/clang Montage-Ausgang?). Wenn der compiler nicht optimal code: Schreiben Sie Ihre C/C++ - Quelldatei, in einer Weise, die führt den compiler in eine bessere code ist in der Regel der beste Ansatz. Sie haben, um zu wissen, asm, und wissen, was ist effizient, aber Sie wenden dieses wissen indirekt. Compiler sind auch eine gute Quelle von Ideen: manchmal klappern tun Sie etwas kühl, und Sie können hand-hold-gcc zu tun, die gleiche Sache: siehe diese Antwort und was habe ich mit den nicht-ent loop in @Veedrac code unten).
Dieser Ansatz ist tragbar, und in 20 Jahren einige zukünftige compiler kompilieren können es zu was auch immer ist effizient auf zukünftige hardware (x86-oder nicht), vielleicht mit neuen ISA-Erweiterung oder auto-Vektorisieren. Hand-geschrieben, x86-64 asm von 15 Jahren würden in der Regel nicht optimal abgestimmt für Skylake. z.B. vergleichen&branch makro-fusion damals nicht existierte. Was ist optimal jetzt für handgefertigte asm für eine Mikroarchitektur, die möglicherweise nicht optimal für andere aktuelle und zukünftige CPUs. Kommentare zu @johnfound Antwort diskutieren die wesentlichen Unterschiede zwischen AMD Bulldozer und Intel Haswell, die eine große Wirkung haben auf diesen code. Aber in der Theorie
g++ -O3 -march=bdver3
undg++ -O3 -march=skylake
wird das richtige tun. (Oder-march=native
.) Oder-mtune=...
nur Melodie, ohne Verwendung von Anweisungen, die anderen CPUs unterstützen möglicherweise nicht.Mein Gefühl ist, dass die Führung der compiler asm das ist gut für eine aktuelle CPU, die Sie kümmern sollte kein problem sein für die Zukunft-Compiler. Sie sind hoffentlich besser als die derzeitigen Compiler bei der Suche nach Möglichkeiten, um zu transformieren-code, und kann einen Weg finden, das funktioniert für zukünftige CPUs. Unabhängig davon, zukünftige x86 wohl nicht schrecklich sein, auf alles, was sich gut auf x86, und die Zukunft compiler keine asm-spezifische Fallstricke bei der Implementierung von so etwas wie dem verschieben der Daten von der C-Quelle, wenn es nicht sieht, etwas besser.
Hand geschriebene asm ist eine black-box für den Optimierer, also Konstanten-propagation funktioniert nicht beim inlining macht eine Eingabe einer compile-Zeit-Konstante. Andere Optimierungen sind ebenfalls betroffen. Lesen https://gcc.gnu.org/wiki/DontUseInlineAsm vor der Verwendung von asm. (Und vermeiden Sie die MSVC-style inline-asm: Eingänge/Ausgänge gehen durch den Speicher die fügt overhead.)
In diesem Fall: Ihre
n
eine signierte geben, und gcc verwendet das SAR/SHR/HINZUFÜGEN, Reihenfolge gibt die richtige Rundung. (IDIV und Arithmetik-shift "Runde" anders als für negative Eingaben finden Sie in der SAR-insn set ref manuelle Eingabe). (IDK, wenn gcc versucht und sind gescheitert, um zu beweisen, dassn
nicht negativ sein kann, oder was. Signed-überlauf ist Undefiniertes Verhalten, so sollte es in der Lage gewesen.)Benutzt du
uint64_t n
, so kann es nur SHR. Und so ist es portable Systeme, in denenlong
ist nur die 32-bit - (z.B. x86-64 Windows).BTW, gcc optimiert asm-output sieht sehr gut aus (mit
unsigned long n
): die innere Schleife es inlines inmain()
tut:Die innere Schleife ist astfreie, und der kritische Pfad der Schleife durchgeführt Abhängigkeit Kette:
Insgesamt: 5 Zyklen pro iteration, Latenz-Flaschenhals. Out-of-order-Ausführung kümmert sich um alles anderes parallel dazu (in der Theorie: habe ich noch nicht getestet mit perf Counter um zu sehen, ob es wirklich läuft bei 5c/iter).
FLAGS-Eingang
cmov
(produziert von TEST) ist schneller zu produzieren als die RAX-Eingang (von LEA->MOV), so dass Sie nicht auf dem kritischen Pfad.Ähnlich, die MOV->SHR produziert CMOV s Fei Eingang aus ist der kritische Pfad, weil es auch schneller als die LEA. MOV auf IvyBridge und später hat zero Latenz (abgewickelt register-umbenennen-Zeit). (Es dauert noch eine uop, und ein Schlitz in der pipeline, so ist es nicht frei, nur null-Latenz). Die extra-MOV in der LEA-dep-Kette ist Teil des Engpasses auf anderen CPUs.
Cmp/jne ist auch nicht Teil des kritischen Pfades: es ist nicht loop-carried, weil die Kontrolle von Abhängigkeiten behandelt werden, die mit branch prediction + spekulative Ausführung, im Gegensatz zu Daten-Abhängigkeiten, die auf dem kritischen Pfad.
Schlagen der compiler
GCC hat einen ziemlich guten job hier. Es könnte sparen eine byte-code durch die Verwendung von
inc edx
stattadd edx, 1
, weil niemand kümmert sich um P4 und seinen falschen Abhängigkeiten für Teil-flag-Anweisungen ändern.Könnte es auch alle speichern die MOV-Anweisungen, und der TEST: SHR-sets CF= das bit verschoben, so können wir
cmovc
statttest
/cmovz
.Siehe @johnfound Antwort für einen anderen schlauen trick: entfernen Sie die CMP durch Verzweigung auf SHR-Flagge Ergebnis als auch mit es für CMOV: nur null, wenn n 1 (oder 0), um mit zu beginnen. (Fun fact: SHR mit count != 1 auf Nehalem oder früher verursacht einen stall, wenn Sie Lesen, die flag-Ergebnisse. Das ist, wie Sie es single-uop. Die shift-by-1 spezielle Codierung ist in Ordnung, obwohl.)
Vermeidung von MOV nicht helfen, die Wartezeit auf Haswell (Kann x86 - MOV wirklich "frei" sein? Warum kann ich nicht reproduzieren, überhaupt?). Es hilft deutlich auf CPUs wie Intel pre-IvB-und AMD-Bulldozer-Familie, wo MOV ist nicht null-Latenz. Der compiler ist verschwendet MOV-Anweisungen haben Auswirkungen auf den kritischen Pfad an. BD Komplex-LEA und CMOV geringer Latenz (2c und 1c jeweils), so dass es einen größeren Anteil der Latenz. Auch, Engpässe zu einem Problem werden, weil es nur zwei integer-ALU Rohren. Siehe @johnfound Antwort, wo hat er die timing-Ergebnisse von einer AMD CPU.
Sogar auf Haswell, diese version mag ein bisschen helfen, indem es einige Verzögerungen, wo eine nicht-kritische uop Stiehlt Ausführung-Anschluss von einem auf dem kritischen Pfad verzögert die Ausführung um 1 Zyklus. (Dies wird als eine Ressource-Konflikt). Es spart auch ein register, das helfen kann, wenn dabei mehrere
n
Werte parallel in einem interleaved-Schleife (siehe unten).LEA Wartezeit hängt von der Adressierungsart, auf Intel SnB-Familie CPUs. 3c, für 3 Komponenten (
[base+idx+const]
, die zwei separate fügt), aber nur 1c mit 2 oder weniger Komponenten (add). Einige CPUs (wie Core2) noch ein 3-Komponenten-LEA in einem einzigen Zyklus, aber SnB-Familie nicht. Schlimmer noch, Intel SnB-Familie standardisiert Latenzen, also gibt es keine 2c uops, sonst 3-Komponenten-LEA wäre nur 2c wie Bulldozer. (3-Komponenten-LEA ist langsamer auf AMD-als auch-nur nicht so viel).So
lea rcx, [rax + rax*2]
/inc rcx
ist nur 2c Wartezeit, schneller alslea rcx, [rax + rax*2 + 1]
auf Intel SnB-Familie CPUs wie Haswell. Break-even auf BD, und schlimmer noch auf Core2. Es kostet eine zusätzliche Upstream-Provider, die in der Regel nicht Wert speichern 1c latency, die Latenz ist jedoch das größte Hindernis ist hier und Haswell hat eine breit genug-pipeline zu handhaben, die extra uop Durchsatz.Weder gcc, icc, noch das Geräusch (auf godbolt) verwendet SHR CF-Ausgang, immer mit einem UND oder TEST. Dumme Compiler. 😛 Sie sind große Stücke von komplexen Maschinen, aber ein kluger Mensch kann sich oft schlagen Sie auf den kleinen Maßstab Probleme. (Tausend bis Millionen mal mehr darüber nachdenken, natürlich! Compiler verwenden nicht erschöpfend algorithmen zu suchen, die für jede mögliche Art und Weise, Dinge zu tun, denn das würde zu lange dauern bei der Optimierung eine Menge von inline-code, das ist, was Sie am besten können. Sie brauchen auch nicht das Modell der pipeline in der Ziel-Mikroarchitektur; Sie benutzen Sie einfach einige Heuristiken.)
Einfache loop-unrolling nicht helfen; diese Schleife Engpässen die Wartezeit von einer Schleife getragen Abhängigkeit Kette, nicht auf Schleifen-overhead /Durchsatz. Dies bedeutet, es würde gut tun mit hyperthreading (oder jede andere Art von SMT), da hat die CPU sehr viel Zeit, um interleave Anweisungen von zwei threads. Dies würde bedeuten, die Parallelisierung der Schleife in
main
, aber das ist gut, weil jeder thread kann nur überprüfen, eine Reihe vonn
Werte und produzieren ein paar von ganzen zahlen als Ergebnis.Interleaving von hand in einem einzigen thread könnte gangbar sein, auch. Vielleicht berechnen Sie die Sequenz, die für ein paar von zahlen parallel, da jeweils nur ein paar Register, und Sie können alle update die gleichen
max
/maxi
. Dies schafft mehr instruction-level-parallelism.Der trick ist zu entscheiden, ob zu warten, bis alle
n
Werte erreicht haben1
bevor man ein weiteres paar abn
Werte, oder ob Sie brechen heraus und Holen einen neuen Anfangspunkt für nur einen erreicht, dass die Ende-Bedingung, ohne Sie zu berühren die Register für die andere Sequenz. Wahrscheinlich ist es am besten, um jede Kette arbeiten auf nützliche Daten, sonst müsste man bedingt Inkrementieren Ihre Zähler.Könnten Sie vielleicht sogar tun dies mit SSE verpackt-vergleichen Sie Sachen bedingt, erhöht sich der Zähler für die vector-Elemente, wo
n
noch nicht erreicht1
noch. Und dann verstecken die noch längere Wartezeit von einer SIMD-bedingte-Inkrement-Implementierung, die Sie brauchen würde, halten mehr Vektorenn
Werte in der Luft. Vielleicht lohnt nur mit 256b Vektor (4xuint64_t
).Ich denke, die beste Strategie, um die Erkennung einer
1
"sticky" ist die Maske-Vektor, der alle-diejenigen, die Sie hinzufügen, erhöht sich der Zähler. So, nachdem Sie gesehen haben, ein1
in einem element, das Inkrement-Vektor eine null, und +=0 ist ein no-op.Ungetestete Idee für die manuelle Vektorisierung
Können Sie und setzen diese mit Interna, anstatt von hand geschrieben asm.
Algorithmische /Umsetzung Verbesserung:
Außer eben die Umsetzung der selben Logik mit effizienter asm, suchen Sie nach Möglichkeiten zur Vereinfachung der Logik, oder vermeiden Sie redundante Arbeit. z.B. memoize zu erkennen, die Häufig Endungen-Sequenzen. Oder noch besser, schauen Sie bei 8 nachgestellte bits auf einmal (gnasher Antwort)
@EOF weist darauf hin, dass
tzcnt
(oderbsf
) könnte verwendet werden, um mehreren/=2
Iterationen in einem Schritt. Das ist wahrscheinlich auch besser als SIMD Vektorisieren, da kein SSE oder AVX-Instruktion kann das tun. Es ist immer noch kompatibel mit multiple scalarn
s parallel in verschiedenen integer-Register, obwohl.So dass die Schleife könnte wie folgt Aussehen:
Kann dies tun, wesentlich weniger Iterationen, aber die Variablen-Anzahl Schichten langsam auf Intel SnB-Familie CPUs ohne BMI2. 3 uops, 2c Latenz. (Sie haben eine input-Abhängigkeit auf die FAHNEN, weil count=0 bedeutet, dass die flags nicht verändert. Sie behandeln diese als Daten-Abhängigkeit, und mehrere uops, da ein uop können nur 2 Eingänge (pre-HSW/BDW sowieso)). Dies ist die Art, die Leute beschweren sich über x86 ist verrückt-CISC-design bezogen werden. Es macht x86-CPUs langsamer, als Sie sein würde, wenn die ISA wurde von Grund auf neu entwickelt, noch heute in einer weitgehend ähnlichen Weise. (d.h. dieser Teil ist der "x86-Steuer", dass Kosten, Geschwindigkeit /Strom.) SHRX/SHLX/SARX (BMI2) sind ein großer Gewinn (1 uop /1c-Latenz).
Er stellt auch tzcnt (3c auf Haswell und später) auf dem kritischen Pfad, so dass es signifikant verlängert die Gesamt-Latenz der Schleife durchgeführt Abhängigkeit Kette. Tut es das Bedürfnis für ein CMOV, oder für die Vorbereitung eines Registers holding
n>>1
, obwohl. @Veedrac Antwort überwindet all dies durch zurückstellen des tzcnt/shift für mehrere Iterationen, die hoch wirksam ist (siehe unten).Sicher können wir BSF oder TZCNT austauschbar, weil
n
kann nie null sein. TZCNT Maschine-code dekodiert als ASF auf CPUs, die keine Unterstützung BMI1. (Sinnlos Präfixe werden ignoriert, also REP BSF läuft als BSF).TZCNT führt viel besser als ASF auf AMD-CPUs, die es unterstützen, so kann es eine gute Idee zu verwenden
REP BSF
, auch wenn Sie don ' T care über die Einstellung der ZF, wenn der Eingang null ist, anstatt die Ausgabe. Einige Compiler dies tun, wenn Sie__builtin_ctzll
auch mit-mno-bmi
.Führen Sie das gleiche auf Intel-CPUs, so speichern Sie einfach das byte, wenn das ist alles, was zählt. TZCNT auf Intel (pre-Skylake) hat immer noch eine falsche Abhängigkeit von der angeblich nur-schreiben-output-operand, wie BSF, zur Unterstützung des undokumentierten Verhalten, dass ASF mit input = 0 verlässt sein Ziel unverändert. So müssen Sie zu umgehen, es sei denn, die Optimierung nur für Skylake, also es gibt nichts zu gewinnen aus den zusätzlichen REP byte. (Intel geht oft über das hinaus, was die x86-ISA-Benutzerhandbuch erfordert, um zu vermeiden, bricht weit verbreiteten code, die davon abhängt, etwas, das es nicht, oder das ist rückwirkend nicht zulässig. z.B. Windows 9x ist übernimmt keine spekulativen prefetching der TLB-Einträge, was sicher war, wenn der code geschrieben wurde, bevor Intel aktualisiert die TLB-management-Regeln.)
Sowieso, LZCNT/TZCNT auf Haswell haben die gleichen falschen dep als POPCNT: siehe dieses Q&A. Dies ist der Grund, warum in gcc-asm-Ausgabe für @Veedrac code, sehen Sie es brechen Sie die dep-Kette mit xor-Nullung auf das register-es ist zu verwenden wie TZCNT Ziel, wenn es nicht in Gebrauch dst=src. Da TZCNT/LZCNT/POPCNT verlassen nie Ihr Ziel nicht definiert oder modifiziert werden, diese falsche Abhängigkeit von der Ausgabe, die auf Intel-CPUs ist rein performance-Fehler /eine Begrenzung. Vermutlich lohnt es sich, einige transistoren /macht zu haben, Sie Verhalten sich wie andere uops, gehen Sie zu der gleichen Einheit Testausführung. Die einzige software, die sichtbare Oberseite ist in der Interaktion mit anderen mikroarchitektonische Einschränkung: Sie können micro-fuse ein Speicher-operand mit einer indizierten Adressierung Modus auf Haswell, aber auf Skylake, wo Intel entfernt, die false-Abhängigkeit für LZCNT/TZCNT Sie "un-Laminat" indizierte Adressierungsarten, während POPCNT können noch micro-fuse jede addr-Modus.
Verbesserungen, Ideen /code aus den anderen Antworten:
@hidefromkgb Antwort hat eine schöne Beobachtung, dass Sie garantiert werden können, führen Sie einen rechts-shift nach einem 3n+1. Sie berechnen, dies, mehr, noch effektiver als nur das weglassen der Kontrollen zwischen den Schritten. Die asm-Implementierung in dieser Antwort ist gebrochen, obwohl (es hängt davon ab, was undefiniert ist, nachdem SHRD mit einem count > 1), und langsam:
ROR rdi,2
ist schneller alsSHRD rdi,rdi,2
, und mit zwei CMOV-Instruktionen die auf dem kritischen Pfad ist langsamer als eine zusätzliche PRÜFUNG, die parallel ausgeführt werden können.Legte ich aufgeräumt /verbesserte C (die guides der compiler besser zu produzieren asm), und getestet+funktioniert schneller asm (in den Kommentaren unter dem C) bis auf Godbolt: siehe den link in @hidefromkgb Antwort. (Diese Antwort trifft den 30k char beschränken, aus der großen Godbolt URLs, aber shortlinks können verrotten und waren zu lang für goo.gl anyway.)
Verbesserte sich auch die Ausgabe-drucken, konvertieren in einen string und machen ein
write()
anstelle des Schreibens einen char mit einem mal. Dies minimiert die Auswirkungen auf die timing-das ganze Programm mitperf stat ./collatz
(für die Aufzeichnung von performance Countern), und ich de-verschleiert, einige der nicht-kritischen asm.@Veedrac code
Habe ich eine sehr kleine Beschleunigung, die von rechts-Verschiebung, so viel wie wir wissen getan werden muss, und überprüfen, um weiterhin die Schleife. Von 7,5 s bei limit=1e8 unten, um 7.275 s, auf Core2Duo (Merom), mit einem abrollbar Faktor 16.
code + Kommentare Godbolt auf. Verwenden Sie nicht diese version mit clang; es ist etwas dummes mit dem verschieben-Schleife. Mit einem tmp-Zähler
k
und dann hinzufügen zucount
später ändert, was das Geräusch macht, aber das leicht weh tut gcc.Siehe Diskussion in den Kommentaren: Veedrac code ist ausgezeichnete auf CPUs mit BMI1 (also nicht Celeron/Pentium)
InformationsquelleAutor der Antwort Peter Cordes
Behauptet, dass der C++ compiler optimalen code produzieren mehr als eine zuständige Assembler-Programmierer, der ist ein sehr böser Fehler. Und besonders in diesem Fall. Das menschliche immer können den code besser, dass es der compiler, und diese Besondere situation ist eine gute illustration dieser Behauptung.
Der timing-Unterschied, den Sie sehen, ist, da der Assembler-code in der Frage ist sehr weit vom Optimum in den inneren Schleifen.
(Der code unten ist 32-bit, aber kann einfach umgerüstet werden, um 64-bit)
Z. B. die Sequenz-Funktion optimiert werden kann nur, 5 Hinweise:
Der gesamte code sieht wie folgt aus:
Um um diesen code zu kompilieren, FreshLib benötigt wird.
In meinen tests (1 GHz AMD A4-1200 Prozessor), der obige code ist etwa vier mal schneller als der C++ - code aus der Frage (bei der Kompilierung mit
-O0
: 430 ms vs. 1900 ms), und mehr als zwei mal schneller (430 ms vs. 830 ms), wenn der C++ - code kompiliert wird mit-O3
.Die Ausgabe der beiden Programme ist gleich: max sequence = 525 auf i = 837799.
InformationsquelleAutor der Antwort johnfound
Für mehr Leistung: Eine einfache änderung ist die Beobachtung, dass nach n = 3n+1, n ungerade, so können Sie durch 2 dividieren sofort. Und n nicht 1 sein, so brauchen Sie nicht zu testen. So könnten Sie sparen ein paar if-Anweisungen und schreiben:
Hier ein großen gewinnen: Wenn Sie sich auf die untersten 8 bits von n, alle die Schritte, bis Sie durch 2 geteilt acht mal sind ganz bestimmt von diesen acht bits. Zum Beispiel, wenn die letzten acht bits 0x01, das ist bei binäre Ihre Nummer ???? 0000 0001 dann die nächsten Schritte sind:
Also alle diese Schritte können vorausgesagt werden, und 256k + 1 ersetzt wird mit 81k + 1. Etwas ähnliches geschehen wird für alle Kombinationen. So können Sie eine Schleife mit einer großen switch-Anweisung:
Führen Sie die Schleife bis n ≤ 128, da zu diesem Zeitpunkt n werden könnte 1 mit weniger als acht Divisionen durch 2, und tun acht oder mehr Schritte auf ein mal machen würde, Sie verpassen den Punkt, wo Sie erreichen 1 für die erste Zeit. Dann weiter die "normalen" loop - oder haben eine Tabelle vorbereitet, die Ihnen sagt, wie viele Schritte brauchen, um zu erreichen 1.
PS. Ich vermute stark Peter Cordes' Vorschlag würde es noch schneller. Es werden keine bedingten Verzweigungen in alle außer einem, und die wird richtig vorhergesagt, außer wenn die Schleife endet. So würde der code so etwas wie
In der Praxis, Sie wäre zu Messen, ob die Verarbeitung der letzten 9, 10, 11, 12 bits von n in einer Zeit schneller gehen würde. Für jedes bit, die Anzahl der Einträge in der Tabelle verdoppeln würde, und ich excect eine Verlangsamung, wenn die Tabellen nicht passen in den L1-cache nicht mehr.
PPS. Wenn Sie brauchen, um die Anzahl der Vorgänge: In jeder iteration wir haben genau acht Divisionen durch zwei, und eine variable Anzahl von (3n + 1) Operationen, so dass eine offensichtliche Methode, um die Anzahl der Operationen würde ein anderes array. Aber wir können tatsächlich berechnen der Anzahl von Schritten (basierend auf der Anzahl der Iterationen der Schleife).
Konnten wir neu definieren Sie das problem leicht: Ersetzen Sie n durch (3n + 1) /2, wenn Sie ungerade, und ersetzen n durch n /2 wenn auch. Dann ist jeder iteration wird genau das tun, 8 Schritte, aber Sie könnten auch mogeln 🙂 Also angenommen es wurden r-Operationen n <- 3n+1 und N Operationen n <- n/2. Das Ergebnis wird ziemlich genau in n' = n * 3^r /2^N, da n <- 3n+1 für n <- 3n * (1 + 1/3n). Unter dem Logarithmus finden wir r = (N + log2 (n' /n)) /log2 (3).
Wenn wir die Schleife bis n ≤ 1.000.000 und eine vorausberechnete Tabelle, wie viele Iterationen erforderlich sind, von jedem Startpunkt n ≤ 1.000.000 ist dann die Berechnung der r wie oben, gerundet auf die nächste Ganzzahl, die für das richtige Ergebnis, es sei denn, s ist wirklich groß.
InformationsquelleAutor der Antwort gnasher729
Auf einem eher beziehungslosen Hinweis: mehr Leistung hacks!
[die ersten «Vermutungen» wurde schließlich entlarvt durch @ShreevatsaR; entfernt]
Beim Durchlaufen der Sequenz, die wir nur bekommen können 3 mögliche Fälle, die in die 2-Nachbarschaft des aktuellen Elements
N
(als erstes angezeigt):Sprung vorbei diese 2 Elemente bedeutet, dass zur Berechnung
(N >> 1) + N + 1
,((N << 1) + N + 1) >> 1
undN >> 2
bzw.Lassen Sie uns beweisen, dass für die beiden Fälle (1) und (2) ist es möglich, auf die erste Formel,
(N >> 1) + N + 1
.Fall (1) ist offensichtlich. Fall (2) bedeutet
(N & 1) == 1
, also, wenn wir davon ausgehen (ohne Verlust der Allgemeinheit) , N ist 2 bit lang und seine bits sindba
von den meisten - zu mindestens-eine Bedeutung hat, danna = 1
, und die gilt:wo
B = !b
. Rechts-Verschiebung der ersten Ergebnis gibt uns genau das, was wir wollen.Q. E. D.:
(N & 1) == 1 ⇒ (N >> 1) + N + 1 == ((N << 1) + N + 1) >> 1
.Als erwiesen an, wir können Durchlaufen der Sequenz 2 Elemente gleichzeitig, mit einem einzigen ternären Betrieb. Weitere 2× Zeit-Reduktion.
Der resultierende Algorithmus sieht wie folgt aus:
Hier vergleichen wir
n > 2
da der Prozess möglicherweise stoppen zu 2 anstelle von 1, wenn die gesamte Länge der Sequenz ungerade ist.[EDIT:]
Let ' s übersetzen diese in Montage!
Verwenden Sie diese Befehle zum kompilieren:
Finden Sie in der C und eine verbesserte/fehlerbereinigte version des asm Peter Cordes Godbolt auf. (Anmerkung der Redaktion: Entschuldigung, wenn ich meine Sachen in deine Antwort, aber meine Antwort trifft den 30k char limit von Godbolt links + text!)
InformationsquelleAutor der Antwort hidefromkgb
C++ Programme übersetzt werden Assembler-Programme bei der Erzeugung von Maschinencode aus dem Quelltext. Es wäre geradezu falsch, zu sagen-assembly ist langsamer als C++. Darüber hinaus Binär-code erzeugt, unterscheidet sich von compiler zu compiler. So eine intelligente C++ - compiler kann produzieren binary code optimieren und effizienter als eine dumme assembler-code.
Aber ich glaube, dass Ihre profiling-Methode hat gewisse Mängel. Die folgenden sind Allgemeine Richtlinien, die für die Profilerstellung:
InformationsquelleAutor der Antwort Mangu Singh Rajpurohit
Kommentare:
Viele zahlen es wird nicht überlauf.
Wenn es wird überlauf - für eines jener unglücklichen ersten Samen, die überflogen Zahl wird sehr wahrscheinlich konvergieren gegen 1, ohne dass ein anderes überlauf.
Immer noch dabei stellt sich die interessante Frage, gibt es ein überlauf-zyklische Anzahl Samen?
Einfache abschließenden konvergierenden Serie beginnt mit der Kraft der zwei Wert (klar genug?).
2^64 überlauf zu null, das ist undefiniert Endlosschleife nach Algorithmus (endet nur mit 1), aber die optimale Lösung in der Antwort zu beenden wegen
shr rax
produziert ZF=1.Können wir produzieren 2^64? Wenn die startnummer ist
0x5555555555555555
es ungerade Zahl, die nächste Zahl ist dann 3n+1, das ist0xFFFFFFFFFFFFFFFF + 1
=0
. Theoretisch im undefinierten Zustand des Algorithmus, sondern die optimierte Antwort von johnfound wird sich erholen, indem man auf ZF=1 ist. Diecmp rax,1
von Peter Cordes endet in einer Endlosschleife (QED Variante 1, "cheapo" durch Undefinierte0
Anzahl).Wie über einige weitere komplexe Zahl, die schaffen Zyklus ohne
0
?Ehrlich gesagt, ich bin mir nicht sicher, meine Mathe-Theorie ist zu diesig, um eine ernsthafte Idee, wie man sich damit in schwerwiegender Weise. Aber intuitiv würde ich sagen, die Serie wird zusammen mit 1 für jede Zahl : 0 < Zahl 3n+1-Formel wird sich langsam verwandeln jedes nicht-2 prime-Faktor der ursprünglichen Zahl (oder intermediate) in eine Potenz von 2 ist, früher oder später. So brauchen wir nicht zu befürchten, Endlosschleife für die original-Serie, nur überlauf behindern uns.
So, ich Stelle gerade paar zahlen in Blatt und warf einen Blick auf 8 bit abgeschnitten zahlen.
Gibt es drei Werte überlaufen zu
0
:227
,170
und85
(85
direkt0
, die beiden anderen voran in Richtung85
).Aber es gibt keinen Wert erzeugen zyklischer überlauf Samen.
Lustigerweise habe ich ein check, das ist die erste Zahl unter 8 bit abschneiden, und schon
27
betroffen ist! Es tut reach-Wert9232
im richtigen nicht-abgeschnitten-Serie (erste abgeschnittene Wert ist322
im 12. Schritt) und der maximale Wert erreicht für jede der 2-255 Eingabe von zahlen in nicht-abgeschnitten Weise ist13120
(für die255
selbst), die maximale Anzahl der Schritte zu laufen Sie zu1
ist über128
(+-2, nicht sicher, ob die "1" zu zählen, etc...).Interessanterweise (für mich) die Anzahl
9232
ist maximal für vielen anderen Quelle zu zahlen, was ist daran so besonders? :-O9232
=0x2410
... hmmm.. keine Ahnung.Leider kann ich nicht bekommen keine tiefen Griff dieser Serie, warum wird es konvergieren und welche Auswirkungen Sie abzuschneiden, um k bits, aber mit
cmp number,1
abschließende Bedingung ist es sicherlich möglich, den Algorithmus in Endlosschleife mit bestimmten Eingangswert Ende als0
nach dem abschneiden.Aber der Wert
27
überquellenden für 8-bit-Fall ist die Art der Alarmierung, das sieht aus wie wenn Sie zählen die Anzahl der Schritte zu erreichen Wert1
erhalten Sie falsche Ergebnis für die Mehrheit der zahlen von den Gesamt-k-bit-Ganzzahlen im Bereich. Für die 8-bit-Ganzzahlen, die die 146 Nummern von 256 betroffenen Serie von abschneiden (einige von Ihnen können noch immer treffen Sie die richtige Anzahl von Schritten, die durch einen Unfall, vielleicht-ich bin zu faul zu schauen).InformationsquelleAutor der Antwort Ped7g
Hast du nicht nach dem code, der vom compiler generiert, so dass es' einige Vermutungen hier, aber auch ohne es gesehen, kann man sagen, dass dies:
... hat eine chance von 50% mispredicting der Zweig, und das wird teuer kommen.
Den compiler fast sicher beide Berechnungen (die Kosten neglegibly mehr, da die div/mod ist schon Recht lange Latenzzeit, also die multiply-add "frei") und folgt mit einem CMOV. Die, natürlich, hat eine null Prozent chance, mispredicted.
InformationsquelleAutor der Antwort Damon
Auch ohne Blick auf die Montage, der offensichtlichste Grund ist, dass
/= 2
ist wohl optimiert>>=1
und viele Prozessoren verfügen über eine sehr schnelle shift-operation. Aber selbst wenn ein Prozessor nicht über eine shift-operation, die integer-division ist schneller als Fließkomma-division.Edit: Ihre Laufleistung variieren, auf das "integer-division ist schneller als Fließkomma-division" Aussage oben. Die Kommentare unten zeigen, dass die modernen Prozessoren haben Priorität Optimierung fp division über integer-division. Also, wenn jemand gesucht, der wahrscheinlichste Grund für die Beschleunigung, die diesem thread-Frage, fragt nach, dann die compiler-Optimierung
/=2
als>>=1
wäre die beste 1. Platz zu sehen.Auf eine unabhängigen Hinweis, wenn
n
ungerade ist, wird der Ausdruckn*3+1
immer noch. So gibt es keine Notwendigkeit zu prüfen. Sie können ändern, die Filiale zuAlso ist die ganze Aussage wäre dann
InformationsquelleAutor der Antwort Dmitry Rubanovich
Als eine Allgemeine Antwort, die nicht speziell gerichtet an diese Aufgabe: In vielen Fällen erheblich beschleunigen kann jedes Programm durch Verbesserungen auf einem hohen Niveau. Wie die Ermittlung von Daten, die einmal und nicht mehrere Male, Vermeidung unnötiger arbeiten, komplett, mit caches in der besten Weise, und so weiter. Diese Dinge sind viel einfacher zu tun, in einer high-level Sprache.
Schreiben von assembler-code, ist es möglich zu verbessern, was eine Optimierung der compiler tut, aber es ist harte Arbeit. Und sobald es fertig ist, dein code ist viel schwieriger zu ändern, so dass es weitaus schwieriger ist die Beurteilung der algorithmischen Verbesserungen. Manchmal wird der Prozessor verfügt über Funktionen, die Sie nicht verwenden können, die von high-level-Sprache, inline-Montage ist es oft hilfreich, in diesen Fällen und noch ermöglicht es Ihnen, eine high-level-Sprache.
In der Euler-Probleme, die meisten der Zeit, die Sie erfolgreich, etwas zu bauen, zu finden, warum es langsam ist, bauen etwas besser, Suche nach, warum es langsam ist, und so weiter und so weiter. Das ist sehr, sehr schwer mit assembler. Ein besserer Algorithmus bei der Hälfte der möglichen Geschwindigkeit wird in der Regel schlagen ein schlechter Algorithmus, der bei voller Drehzahl, und immer die volle Geschwindigkeit in assembler ist nicht trivial.
InformationsquelleAutor der Antwort gnasher729
Für das Collatz-problem, Sie können eine erhebliche Steigerung der Leistung durch Zwischenspeichern der "Schwänze". Dies ist eine Zeit - /memory-trade-off. Siehe: memoization
(https://en.wikipedia.org/wiki/Memoization). Sie konnten auch einen Blick in die dynamische Programmierung Lösungen für andere Zeit - /memory-trade-offs.
Beispiel python-Implementierung:
InformationsquelleAutor der Antwort Emanuel Landeholm
Die einfache Antwort:
tun, eine MOV RBX, 3 und MUL RBX ist teuer; nur HINZUFÜGEN, RBX, RBX zweimal
HINZUFÜGEN 1 ist wahrscheinlich schneller als INC hier
MOV 2 und DIV ist sehr teuer; nur eine Verschiebung nach rechts
64-bit-code ist in der Regel deutlich langsamer als die 32-bit-code und die Anpassung Probleme werden komplizierter; mit kleinen Programme wie dieses haben Sie, pack Sie, so dass Sie tun, parallele Berechnung zu haben, jede chance, schneller als 32-bit-code
Wenn Sie generiert die Liste der assembly für Ihre C++ - Programm, können Sie sehen, wie er sich aus Ihrer Montage.
InformationsquelleAutor der Antwort Tyler Durden