Wie im letzten Post angekündigt, gibt es jetzt die genauere Analyse meines Tests.
Hier erstmal das Programm:
int mymin(int a, int b) __attribute__ ((noinline));
int mymin(int a, int b)
{
asm ("");
if (b < a)
return b;
return a;
}
int mymin2(int a, int b) __attribute__ ((noinline));
int mymin2(int a, int b)
{
asm ("");
return b ^ ((a ^ b) & -(a < b)); // min(a, b)
}
int main()
{
int a = 0;
int b = 0;
int c = 0;
long sum = 0;
for(int i = 0; i < 1e7; i++) {
a = rand();
b = rand();
c = std::min(a,b);
// c = mymin1(a,b);
// c = mymin2(a,b);
sum+=c;
// cout << a << " " << b << " " << c << "\n";
}
return 0;
}
Wie man sieht, gibt es zwei Funktion die jeweils die kleinere Zahl bestimmen. Einmal durch eine einfache if() Verzweigung und einmal durch eine Rechnung. Die beiden Funktionen sind mit den Attribute noinline [1] und einem inline Assembler Befehl versehen, damit der Compiler sie nicht weg optimiert. Sonst hat valgrind nichts zum messen 
Es gibt drei Durchläuft. Einmal mit std::min um die "normale Version" zu vermessen.
Dann meine min Version mit If. Und zum Schluss die Version mit Rechnung.
Compiliert wird immer mit
g++ -O2 -g -Wall main.cpp
Bei Valgrind schalte ich die Cache Simulation ab, um die Ausführungszeit etwas zu verkürzen
valgrind --tool=cachegrind --branch-sim=yes --cache-sim=no ./a.out
Test 1
Mit std::min
==5210== I refs: 1,821,485,345
==5210==
==5210== Branches: 230,216,253 (210,213,194 cond + 20,003,059 ind)
==5210== Mispredicts: 657,699 ( 657,279 cond + 420 ind)
==5210== Mispred rate: 0.2% ( 0.3% + 0.0% )
--------------------------------------------------------------------------------
Ir Bc Bcm Bi Bim file:function
--------------------------------------------------------------------------------
880,000,000 80,000,000 645,163 0 0 /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/stdlib/random_r.c:random_r
353,545 54,035 3,217 0 0 /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/elf/dl-lookup.c:do_lookup_x
176,933 28,792 2,876 2,144 252 /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/elf/../sysdeps/i386/dl-machine.h:_dl_relocate_object
138,235 31,695 1,684 0 0 /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/string/strcmp.c:strcmp
562,727 63,616 1,366 0 0 /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/elf/dl-lookup.c:_dl_lookup_symbol_x
--------------------------------------------------------------------------------
-- Auto-annotated source: /home/kater/qtcode/plaintest/plaintest/main.cpp
--------------------------------------------------------------------------------
Ir Bc Bcm Bi Bim
-- line 13 ----------------------------------------
. . . . .
. . . . . int mymin2(const int& a, const int& b) __attribute__ ((noinline));
. . . . . int mymin2(const int& a, const int& b)
. . . . . {
. . . . . return b ^ ((a ^ b) & -(a < b)); // min(a, b)
. . . . . }
. . . . .
. . . . . int main()
7 0 0 0 0 {
. . . . . int a = 0;
. . . . . int b = 0;
. . . . . int c = 0;
. . . . . long sum = 0;
80,000,000 10,000,000 5 0 0 for(int i = 0; i < 1e7; i++) {
10,000,000 0 0 0 0 a = rand();
10,000,000 0 0 0 0 b = rand();
. . . . . c = std::min(a,b);
. . . . . //c = mymin(a,b);
. . . . . sum+=c;
. . . . . // cout << a << " " << b << " " << c << "\n";
. . . . . }
. . . . . return 0;
11 0 0 0 0 }
Interessant sind hier nur Conditional branches executed (Bc) and conditional branches mispredicted (Bcm).
Wir haben also 657,699 falsch vorhergesagte Sprünge und 645,163 gehen für die Random Funktion drauf. Der Rest verteilt sich auf diverse Systemfunktionen. Aber es gibt keine falschen Sprünge für std::min. Der Compiler ist gut
Fünf gehen für die For Schleife drauf. Hier erkennt die Sprungvorhersage schnell, dass es eine Schleife ist und nimmt immer den richtigen Weg.
Test 2
Mit mymin; if()
==10996== I refs: 1,946,482,984
==10996==
==10996== Branches: 240,216,256 (220,213,197 cond + 20,003,059 ind)
==10996== Mispredicts: 5,658,603 ( 5,658,183 cond + 420 ind)
==10996== Mispred rate: 2.3% ( 2.5% + 0.0% )
--------------------------------------------------------------------------------
Ir Bc Bcm Bi Bim file:function
--------------------------------------------------------------------------------
880,000,000 80,000,000 645,163 0 0 /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/stdlib/random_r.c:random_r
520,000,000 120,000,000 15 0 0 /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/stdlib/random.c:random
180,000,000 0 0 0 0 /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/stdlib/rand.c:rand
140,000,015 10,000,000 9 0 0 /home/kater/qtcode/plaintest/plaintest/main.cpp:main
120,001,144 0 0 0 0 /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/string/../sysdeps/i386/i686/multiarch/strcspn.S:???
84,997,627 10,000,000 5,000,895 0 0 /home/kater/qtcode/plaintest/plaintest/main.cpp:mymin(int, int)
--------------------------------------------------------------------------------
-- Auto-annotated source: /home/kater/qtcode/plaintest/plaintest/main.cpp
--------------------------------------------------------------------------------
Ir Bc Bcm Bi Bim
. . . . . #include
. . . . . #include
. . . . . using namespace std;
. . . . .
. . . . .
. . . . . int mymin(int a, int b) __attribute__ ((noinline));
. . . . . int mymin(int a, int b)
30,000,000 0 0 0 0 {
34,997,627 10,000,000 5,000,895 0 0 asm ("");
. . . . . if (b < a)
. . . . . return b;
. . . . . return a;
20,000,000 0 0 0 0 }
. . . . .
. . . . . int mymin2(int a, int b) __attribute__ ((noinline));
. . . . . int mymin2(int a, int b)
. . . . . {
. . . . . asm ("");
. . . . . return b ^ ((a ^ b) & -(a < b)); // min(a, b)
. . . . . }
. . . . .
. . . . . int main()
8 0 0 0 0 {
. . . . . int a = 0;
. . . . . int b = 0;
. . . . . int c = 0;
. . . . . long sum = 0;
80,000,000 10,000,000 9 0 0 for(int i = 0; i < 1e7; i++) {
20,000,000 0 0 0 0 a = rand();
10,000,000 0 0 0 0 b = rand();
. . . . . // c = std::min(a,b);
30,000,000 0 0 0 0 c = mymin(a,b);
. . . . . // c = mymin2(a,b);
. . . . . sum+=c;
. . . . . // cout << a << " " << b << " " << c << "\n";
. . . . . }
. . . . . return 0;
12 0 0 0 0 }
Jetzt sieht die Sache schon anders aus. Wir haben fünf Millionen falsch vorhergesagte Sprünge. Das macht 50%. Wie es zu erwarten war.
Test 3
Mit der Rechnung:
==11057== I refs: 1,991,485,357
==11057==
==11057== Branches: 230,216,256 (210,213,197 cond + 20,003,059 ind)
==11057== Mispredicts: 657,699 ( 657,279 cond + 420 ind)
==11057== Mispred rate: 0.2% ( 0.3% + 0.0% )
--------------------------------------------------------------------------------
Ir Bc Bcm Bi Bim file:function
--------------------------------------------------------------------------------
880,000,000 80,000,000 645,163 0 0 /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/stdlib/random_r.c:random_r
520,000,000 120,000,000 11 0 0 /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/stdlib/random.c:random
180,000,000 0 0 0 0 /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/stdlib/rand.c:rand
140,000,015 10,000,000 5 0 0 /home/kater/qtcode/plaintest/plaintest/main.cpp:main
130,000,000 0 0 0 0 /home/kater/qtcode/plaintest/plaintest/main.cpp:mymin2(int, int)
--------------------------------------------------------------------------------
-- Auto-annotated source: /home/kater/qtcode/plaintest/plaintest/main.cpp
--------------------------------------------------------------------------------
Ir Bc Bcm Bi Bim
-- line 9 ----------------------------------------
. . . . . asm ("");
. . . . . if (b < a)
. . . . . return b;
. . . . . return a;
. . . . . }
. . . . .
. . . . . int mymin2(int a, int b) __attribute__ ((noinline));
. . . . . int mymin2(int a, int b)
40,000,000 0 0 0 0 {
70,000,000 0 0 0 0 asm ("");
. . . . . return b ^ ((a ^ b) & -(a < b)); // min(a, b)
20,000,000 0 0 0 0 }
. . . . .
. . . . . int main()
8 0 0 0 0 {
. . . . . int a = 0;
. . . . . int b = 0;
. . . . . int c = 0;
. . . . . long sum = 0;
80,000,000 10,000,000 5 0 0 for(int i = 0; i < 1e7; i++) {
20,000,000 0 0 0 0 a = rand();
10,000,000 0 0 0 0 b = rand();
. . . . . // c = std::min(a,b);
. . . . . // c = mymin(a,b);
30,000,000 0 0 0 0 c = mymin2(a,b);
. . . . . sum+=c;
. . . . . // cout << a << " " << b << " " << c << "\n";
. . . . . }
. . . . . return 0;
12 0 0 0 0 }
Wie zu erwarten war gibt es keine fünf Millionen falsch vorhergesagten Sprünge. Wir sind so gut wie die Compiler Optimierung. Gebracht hats also nix
Man bräuchte mal ein realen Anwendungsfall.
Ach ein Nachteil hat die Methode zur Berechnung der kleinsten Zahl: Man kann keine Reference auf die kleinste Zahl zurück geben. Kein Plan wie der Compiler das macht. It's magic.
[1] http://gcc.gnu.org/onlinedocs/gcc/Function-Attributes.html#index-g_t_0040code_007bnoinline_007d-function-attribute-2561
