Ich habe einige kritische Verzweigungskodes innerhalb einer Schleife, die etwa 2 ^ 26 mal ausgeführt wird. Die Verzweigungsvorhersage ist nicht optimal, da m zufällig ist. Wie würde ich die Verzweigung entfernen, möglicherweise mit bitweisen Operatoren?
Und hier ist die relevante Assembly, die von gcc -O3 :
Der Zweigstellen-freie modulo konnte nützlich sein, aber das Testen zeigt, dass es in der Praxis nicht so ist.
%Vor%Testfall:
%Vor%Genau das Timing mit einem Testprogramm:
%Vor% (Hinweis: Es gibt keine srand , daher sind die Ergebnisse deterministisch.)
Meine ursprüngliche Antwort: 5.3s
Der Code in der Frage: 4.8s
Nachschlagetabelle: 4.5s ( static unsigned lookup[2][k+1]; )
Nachschlagetabelle: 4.3s ( static unsigned lookup[k+1][2]; )
Erics Antwort: 4.2s
Diese Version: 4.0s
Der schnellste, den ich gefunden habe, ist jetzt die Tabellenimplementierung
Timings, die ich bekommen habe (UPDATED für neuen Messcode)
HVD zuletzt: 9.2s
Tischversion: 7.4s (mit k = 693)
Tabellenerstellungscode:
%Vor%Tabellenlaufzeitschleife:
%Vor%Mit dem Messcode von HVD sah ich, dass die Kosten von rand () die Laufzeit dominierten, so dass die Laufzeit für eine zellenlose Version in etwa dem Bereich dieser Lösungen entsprach. Ich habe den Messcode auf diesen Wert geändert (UPDATED, um die zufällige Verzweigungsreihenfolge beizubehalten und zufällige Werte vorzurechnen, um zu verhindern, dass rand () usw. den Cache verwirft)
%Vor%Hinzufügen zu Animonys Neufassung:
%Vor%sieht wie ein Anstieg mit Umbruch aus. Sie können dies als
schreiben %Vor%was natürlich nur Sinn macht, wenn Divisionen tatsächlich schneller sind als Zweige.
Nicht sicher über den anderen; zu faul, um darüber nachzudenken, was (~ 0)% k sein wird.
Tags und Links optimization c++ bit-manipulation