Warum akkumuliert sich schneller als ein einfacher Zyklus?

8

Ich habe Algorithmen getestet und bin in dieses seltsame Verhalten geraten, wenn std::accumulate schneller ist als ein einfacher for -Zyklus.

Wenn ich mir den generierten Assembler anschaue, bin ich nicht viel klüger :-) Es scheint, dass der for -Zyklus in MMX-Anweisungen optimiert ist, während sich accumulate zu einer Schleife erweitert.

Dies ist der Code. Das Verhalten wird mit -O3 optimization level, gcc 4.7.1

, angezeigt %Vor%     
Let_Me_Be 06.11.2012, 01:54
quelle

3 Antworten

9

Wenn Sie das 0 übergeben, um es zu akkumulieren, machen Sie es mit einem int statt mit einem langen long akkumulieren.

Wenn Sie Ihre manuelle Schleife so kodieren, wird es gleichwertig sein:

%Vor%

oder Sie können sich wie folgt ansammeln:

%Vor%     
Vaughn Cato 06.11.2012, 02:52
quelle
5

Ich habe verschiedene Ergebnisse mit Visual Studio 2012

%Vor%

Beachten Sie, dass der ursprüngliche std::accumulate -Code nicht der for -Schleife entspricht, da der dritte Parameter für std::accumulate ein int 0-Wert ist. Er führt die Summierung mit int durch und speichert das Ergebnis erst am Ende in long long . Wenn Sie den dritten Parameter in 0LL ändern, wird der Algorithmus gezwungen, einen long long -Akkumulator zu verwenden und führt zu folgenden Zeiten.

%Vor%

Da das Endergebnis in ein int passt, habe ich suma und std::accumulate wieder auf die Verwendung von int -Werten zurückgesetzt. Nach dieser Änderung war der MSVC 2012-Compiler in der Lage, die for -Schleife automatisch zu vektorisieren und führte zu den folgenden Zeiten.

%Vor%     
Blastfurnace 06.11.2012 02:58
quelle
1

Nach der Behebung des Problems mit dem Akkumulieren haben andere festgestellt, dass ich sowohl mit Visual Studio 2008 & amp; 2010 und akkumulieren war in der Tat schneller als die manuelle Schleife.

Als ich die Disassemblierung betrachtete, sah ich, dass einige zusätzliche Iteratoren in der manuellen Schleife überprüft wurden, also wechselte ich zu einem rohen Array, um es zu eliminieren.

Hier ist, was ich am Ende getestet habe:

%Vor%

Mit diesem Code schlägt die manuelle Schleife leicht an. Der große Unterschied ist, dass der Compiler die manuelle Schleife 4 Mal entrollt hat, ansonsten ist der generierte Code fast identisch.

    
Retired Ninja 06.11.2012 03:22
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Erzwingen des Überlaufmenüs in Actionbar mit Actionbarsherlock auf 4.0-Geräten [duplizieren]