Versuchen Sie Folgendes:
%Vor% Mit clang und -o3 wird dies in ungefähr 0,5 s kompiliert und läuft in null Zeit für %code% . Ihr "konventioneller" Ansatz kompiliert in etwa 0,4 Sekunden und läuft in 0,8 Sekunden. Nur zur Überprüfung, das Ergebnis ist %code% right?
Als ich Ihre eigene %code% -Lösung ausprobiert habe, habe ich den Compiler ein paar Minuten lang laufen lassen und dann gestoppt, weil anscheinend der Speicher voll war (der Computer begann zu frieren). Der Compiler hat versucht, das Endergebnis zu berechnen, und Ihre Implementierung ist extrem ineffizient, um zur Kompilierzeit verwendet zu werden.
Bei dieser Lösung werden Template-Instanziierungen bei %code% , %code% bei der Instanziierung von %code% wiederverwendet. Daher ist %code% zur Kompilierzeit tatsächlich als Wert bekannt, und zur Laufzeit gibt es nichts zu tun. Dies ist ein dynamischer Programmieransatz und natürlich können Sie das auch zur Laufzeit tun, wenn Sie alle Werte bei %code% bis %code% speichern, bevor Sie bei %code% rechnen.
Mit Ihrer Lösung kann der Compiler %code% zur Kompilierzeit auswerten, ist aber nicht erforderlich für . In Ihrem Fall bleibt die gesamte oder ein Teil der Berechnung für die Laufzeit übrig. In meinem Fall wird die gesamte Berechnung zur Kompilierungszeit versucht und daher nie beendet.
Der Grund ist, dass Ihre Runtime-Lösung nicht optimal ist. Für jede Knotennummer werden Funktionen mehrmals aufgerufen. Die Fibonacci-Sequenz hat überlappende Teilprobleme, also zum Beispiel %code% ruft %code% auf, und %code% ruft auch %code% auf.
Der auf Vorlagen basierende Ansatz verwendet (unabsichtlich) einen Ansatz der dynamischen Programmierung, was bedeutet, dass er Werte für zuvor berechnete Zahlen speichert, um Wiederholungen zu vermeiden. Wenn also %code% %code% aufruft, wurde die Anzahl bereits berechnet, wenn %code% dies tat.
Ich empfehle, nach "dynamic programming fibonacci" zu suchen und versuche das, es sollte die Dinge dramatisch beschleunigen.
Vielleicht verwenden Sie einfach einen effizienteren Algorithmus?
%Vor%Mein Code basiert auf einer Idee, die D. Knuth im ersten Teil seiner "The Art of Computer Programming" beschrieben hat. Ich kann mich nicht an den genauen Ort in diesem Buch erinnern, aber ich bin sicher, dass der Algorithmus dort beschrieben wurde.
Wenn Sie -0 (oder höher) zu GCC4.8.1 hinzufügen, wird fibonacci & lt; 40 & gt; () eine Kompilierzeitkonstante und der gesamte vorlagengenerierte Code wird aus Ihrer Assembly verschwinden. Der folgende Code
%Vor%führt zur Assembly-Ausgabe
%Vor%Dies bietet die beste Laufzeitleistung.
Es sieht jedoch so aus, als würden Sie ohne Optimierungen (-O0) bauen, so dass Sie etwas ganz anderes bekommen. Die Assembly-Ausgabe für jede der 40 Fibonacci-Funktionen sieht grundsätzlich identisch aus (mit Ausnahme der Fälle 0 und 1)
%Vor%Das ist einfach, es richtet den Stapel ein, ruft die beiden anderen Fibonacci-Funktionen auf, addiert den Wert, reißt den Stapel herunter und kehrt zurück. Keine Verzweigung und keine Vergleiche.
Vergleichen Sie das nun mit der Baugruppe aus dem konventionellen Ansatz
%Vor%Jedes Mal, wenn die Funktion aufgerufen wird, muss überprüft werden, ob N 0 oder 1 ist und entsprechend handeln. Dieser Vergleich wird in der Template-Version nicht benötigt, da er über die Magie von Templates in die Funktion eingebaut ist. Meine Vermutung ist, dass die unoptimierte Version des Vorlagencodes schneller ist, weil Sie diese Vergleiche vermeiden und auch keine verpassten Verzweigungsvorhersagen haben.
Versuchen Sie Folgendes:
%Vor% Mit clang und -Os wird dies in ungefähr 0,5 s kompiliert und läuft in null Zeit für N=40 . Ihr "konventioneller" Ansatz kompiliert in etwa 0,4 Sekunden und läuft in 0,8 Sekunden. Nur zur Überprüfung, das Ergebnis ist 102334155 right?
Als ich Ihre eigene constexpr -Lösung ausprobiert habe, habe ich den Compiler ein paar Minuten lang laufen lassen und dann gestoppt, weil anscheinend der Speicher voll war (der Computer begann zu frieren). Der Compiler hat versucht, das Endergebnis zu berechnen, und Ihre Implementierung ist extrem ineffizient, um zur Kompilierzeit verwendet zu werden.
Bei dieser Lösung werden Template-Instanziierungen bei N-2 , N-1 bei der Instanziierung von N wiederverwendet. Daher ist fibonacci<40> zur Kompilierzeit tatsächlich als Wert bekannt, und zur Laufzeit gibt es nichts zu tun. Dies ist ein dynamischer Programmieransatz und natürlich können Sie das auch zur Laufzeit tun, wenn Sie alle Werte bei 0 bis N-1 speichern, bevor Sie bei N rechnen.
Mit Ihrer Lösung kann der Compiler fibonacci<N>() zur Kompilierzeit auswerten, ist aber nicht erforderlich für . In Ihrem Fall bleibt die gesamte oder ein Teil der Berechnung für die Laufzeit übrig. In meinem Fall wird die gesamte Berechnung zur Kompilierungszeit versucht und daher nie beendet.
Der Grund ist, dass Ihre Runtime-Lösung nicht optimal ist. Für jede Knotennummer werden Funktionen mehrmals aufgerufen. Die Fibonacci-Sequenz hat überlappende Teilprobleme, also zum Beispiel fib(6) ruft fib(4) auf, und fib(5) ruft auch fib(4) auf.
Der auf Vorlagen basierende Ansatz verwendet (unabsichtlich) einen Ansatz der dynamischen Programmierung, was bedeutet, dass er Werte für zuvor berechnete Zahlen speichert, um Wiederholungen zu vermeiden. Wenn also fib(5) fib(4) aufruft, wurde die Anzahl bereits berechnet, wenn fib(6) dies tat.
Ich empfehle, nach "dynamic programming fibonacci" zu suchen und versuche das, es sollte die Dinge dramatisch beschleunigen.
Wenn Sie -0 (oder höher) zu GCC4.8.1 hinzufügen, wird fibonacci & lt; 40 & gt; () eine Kompilierzeitkonstante und der gesamte vorlagengenerierte Code wird aus Ihrer Assembly verschwinden. Der folgende Code
%Vor%führt zur Assembly-Ausgabe
%Vor%Dies bietet die beste Laufzeitleistung.
Es sieht jedoch so aus, als würden Sie ohne Optimierungen (-O0) bauen, so dass Sie etwas ganz anderes bekommen. Die Assembly-Ausgabe für jede der 40 Fibonacci-Funktionen sieht grundsätzlich identisch aus (mit Ausnahme der Fälle 0 und 1)
%Vor%Das ist einfach, es richtet den Stapel ein, ruft die beiden anderen Fibonacci-Funktionen auf, addiert den Wert, reißt den Stapel herunter und kehrt zurück. Keine Verzweigung und keine Vergleiche.
Vergleichen Sie das nun mit der Baugruppe aus dem konventionellen Ansatz
%Vor%Jedes Mal, wenn die Funktion aufgerufen wird, muss überprüft werden, ob N 0 oder 1 ist und entsprechend handeln. Dieser Vergleich wird in der Template-Version nicht benötigt, da er über die Magie von Templates in die Funktion eingebaut ist. Meine Vermutung ist, dass die unoptimierte Version des Vorlagencodes schneller ist, weil Sie diese Vergleiche vermeiden und auch keine verpassten Verzweigungsvorhersagen haben.
Vielleicht verwenden Sie einfach einen effizienteren Algorithmus?
%Vor%Mein Code basiert auf einer Idee, die D. Knuth im ersten Teil seiner "The Art of Computer Programming" beschrieben hat. Ich kann mich nicht an den genauen Ort in diesem Buch erinnern, aber ich bin sicher, dass der Algorithmus dort beschrieben wurde.