C++Guns – RoboBlog

09.04.2012

Faster Code – Part 6 – Sprungvorhersage again

Filed under: Allgemein — Tags: , , , — Thomas @ 16:04

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

No Comments »

No comments yet.

RSS feed for comments on this post.

Leave a comment

You must be logged in to post a comment.

Powered by WordPress