C++Guns – RoboBlog blogging the bot

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

Es ist ja so, dass ein Befehl auf der CPU nicht nur ausgeführt wird, er muss auch aus dem Speicher geladen und dekodiert werden. Heutige CPUs dekodieren schonmal den nächsten Befehl, wärend der aktuelle noch ausgeführt wird. Und der übernächste wird zeitgleich aus dem Speicher geholt. Das nennt man Prozessor-Pipeline [1] und das ist cool.

Uncool wird es allerdings, wenn der CPU Befehle vorbereitet hat, die dann doch garnicht ausgeführt werden. Das passiert zum Beispiel bei Sprüngen, wenn auf einmal der Code woanders weiter geht als die Pipeline es erwartet hat. Da gibt es auch wieder eine Menge Techniken um die Sprungvorhersage gut zu machen. Aber das will ich nicht weiter vertiefen.

Betrachten wir lieber folgendes Beispiel:

int min(int a, int b) {
  if (b < a)
    return b;
  return a;
}

Hier kann die Sprungvorhersage nichts tun. Was ist wahrscheinlicher, dass a kleiner ist als b oder doch nicht? Die Wahrscheinlichkeit liegt bei 50%. Wäre es nicht cool, wenn man die kleinere Zahl ausrechnen könnte? Dann braucht man keine Verzweigung im Programmpath und die Pipeline kann wunderschön arbeiten.

Man kann. Es gibt eine Seite mit lauter Bit Twiddling Hacks [2]. Und da gibt es noch viel mehr:

Compute the sign of an integer

Detect if two integers have opposite signs

Compute the integer absolute value (abs) without branching

Compute the minimum (min) or maximum (max) of two integers without branching

Determining if an integer is a power of 2

Um das Minimum zweier Interger Zahlen zu berechnen, kann man also folgende Formel verwenden:

int x;  // we want to find the minimum of x and y
int y;   
int r;  // the result goes here 

r = y ^ ((x ^ y) & -(x < y)); // min(x, y)

Um das ganze mal zu testen habe ich mir ein kleines Programm geschrieben, welches die kleinere von zwei Zufallszahlen bestimmt. Leider, oder zum Glück, wird die Funktion std::min() weg optimiert, so dass man keine Aussage mehr treffen kann, ob die Sprungvorhersage greift oder nicht. Also habe ich meine eigne min() Funktion geschrieben. Einmal mit einer if() und einmal mit der Rechnung.
Valgrind [3] bringt ein branch-prediction Profiler mit. Die Bedienung ist einfach und das Ergebnis eindeutig. Da ich euch nicht langweilen will, hier gleich das Ergebnis:

Die Details meines Tests werde ich das nächste Mal posten. Muss das erst etwas aufarbeiten.

[1] http://de.wikipedia.org/wiki/Pipeline_%28Prozessor%29
[2] http://www-graphics.stanford.edu/~seander/bithacks.html
[3] http://valgrind.org/docs/manual/cg-manual.html

Tach und Willkommen beim fünften Teil von Faster Code. Heute geht es um huge page. Eine Page ist normal 4kb groß. Eine hugepage hat 2MB, 4MB oder nocht viel mehr. Hoch zu 1GB. Je nach System, CPU u.s.w.
Die Größe ermittelt man so:

$ grep Huge /proc/meminfo 
HugePages_Total:      46
HugePages_Free:       46
HugePages_Rsvd:        0
HugePages_Surp:        0
Hugepagesize:       4096 kB

Wir haben also 4MB hugepage und es wurde 46 pages schon erstellt. Man kann sie so vom System anfordern:

# echo 46 > /sys/kernel/mm/hugepages/hugepages-4096kB/nr_hugepages

Es kann sein, dass man danach doch nicht 46 freie hugepages hat, da das System durch RAM Fragmentierung den angeforderten Speicher nicht am Stück liefern kann. Hier hilft es den Befehl mehrmals auszuführen oder neu zu starten.

Und wozu brauch man das nun?
Na um Translation Lookaside Buffer (TLB) misses zu verringern. Der TLB mappt eine virtuelle Adresse in eine physikalische Adresse um. Also so eine Art Cache der aber nur sehr sehr wenige Einträge halten kann (dafür ist er aber sehr schnell). Wenn man nun auf viele Adresse zugreift, die in Pages liegen die nah beinander liegen, dann läuft der TLB schnell zu und bereits vorhandenen Einträge werden überschrieben. Fehlende Einträge aus einem anderen Cache holen kostet Zeit und das wollen wir nicht.
Wenn wir nun die Page größer machen, liegen mehr Variablen in einer Page und der TLB muss sich weniger merken. Einleuchtend, nicht wahr? ;)

Und wie nutzt man huge pages?
Es gibt verschiedene Methoden. Über das hugepagefs was ich aber umständlich finde, weil man von Hand ein Filesystem noch mountern muss. Dann gibt es seit Kernel 2.6.38 die Transparent Huge Pages (THP). Hier wird der ganze Aufwand im Hintergrund gehalten und man bekommt als User garnichts mehr mit. Man muss auch nicht sein Code änderen.
Ob das System THP benutzt kann man kann man so erfahren

$ cat /sys/kernel/mm/transparent_hugepage/enabled 
always madvise [never]

In meinem Fall also nie. Wenn man sein Speicher normal über malloc/new anfordert, sollte man die Variable auf always stellen. Bei madvise muss noch irgendwo ein Flag übergeben werden. Hab vergessen wo.

Die dritte Möglichkeit ist seinen Speicher per mmap() zu bestellen. Das find ich am besten. Man hat dann mehr Kontrolle was in hugepages landet und was nicht. Hier ein Beispiel:

  #include < sys/mman.h >

  /* Only ia64 requires this */ 
  #ifdef __ia64__
  #define ADDR (void *)(0x8000000000000000UL)
  #define FLAGS (MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB | MAP_FIXED)
  #else
  #define ADDR (void *)(0x0UL)
  #define FLAGS (MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB)
  #endif

  // versuche speicher per mmap zu holen. wenn das fehlschlaegt nimm new oder valloc
  void *addr = mmap(ADDR, anzKnoten * sizeof(t_knoten_minimal), PROT_READ | PROT_WRITE, FLAGS, 0, 0);
  if (addr == MAP_FAILED) {
    perror("mmap");
    knoten_minimal = new t_knoten_minimal[anzKnoten];
  } else {
    knoten_minimal = new (addr) t_knoten_minimal[anzKnoten];
  }

Und hats was gebracht?
Jein, ehr nein. Ich hatte kein Testfall wo der TLB der Flaschenhals ist. Ich hab immer recht schnell neue Daten aus dem RAM geholt und wenig mit ihnen gerechnet. Die Leitung zum RAM ist natürlich sehr viel langsamer als der TLB seine neuen Adressen bekommt. Darum gab es so gut wie kein Speedup.
Aber ich werde in meinem nächsten Code die Möglichkeit bereitstellen hugepages einfach zu nutzen.

Wie ich im letzten Post erwähnt habe, ist es gut wenn Variablen im RAM ausgerichtet vorliegen. Nun muss man aber
noch bedenken, dass nicht einzelne Variablen aus dem RAM geladen werden, sondern ganze Cache-Zeilen. Nun wäre es doch auch cool, wenn Arrays auf eine Seitenbreite ausgerichtet sind.
Man stelle sich nur mal vor, zwei Threads die auf zwei CPU Kerne laufen, schreiben in Variablen die in der selben Seite/Cache-Zeile liegt. Nun muss doch die Seite/Zeile gegenseitig ausgetauscht werden. Das macht die Sache langsamer.

Um die Seitengröße in Byte festzustellen, gibt es die Funktion int getpagesize (void). Sie beträgt nochmal 4096Byte.
Um eine Adresse die auf eine Seitenbreite ausgerichtet ist zu bekommen, kann man einfach valloc nutzen [1].

  int *a = (int*)valloc(sizeof(int) *1);
  multipleOf(a);

21e0000 multiple of 2  4  8  16  32  4096 

Natürlich ist die Adresse auch auf 64 128 u.s.w. ausgerichtet, aber ich habe mir nicht die Mühe gemacht das rauszuschreiben.

Vielleich denken sich jetzt einige: "Schade, dass new von C++ sowas nicht kann". Aber keine Sorge. Es gibt ein Trick, der nennt sich "placement new" [2]
Man kann new einfach einen schon allokierten Speicher übergeben und es wird wie gewohnt ctors etc. ausgerufen.

  class narf {
    public:
      narf() {cout << "narf()\n";}
      ~narf() {cout << "~narf()\n";}
  };

  narf* a = (narf*)valloc(sizeof(narf) *1);
  multipleOf(a);
  a = new (a) narf();
  a->~narf();
  free(a);

$ valgrind  ./a.out 

223c000 multiple of 2  4  8  16  32  4096 
narf()
~narf()

==5788== HEAP SUMMARY:
==5788==     in use at exit: 0 bytes in 0 blocks
==5788==   total heap usage: 1 allocs, 1 frees, 1 bytes allocated
==5788== 
==5788== All heap blocks were freed -- no leaks are possible

Nicht vergessen den dtor von Hand aufzurufen!

[1] http://www.gnu.org/software/libc/manual/html_node/Aligned-Memory-Blocks.html#Aligned-Memory-Blocks
[2] http://www.parashift.com/c++-faq-lite/dtors.html#faq-11.10

Variablen deren Adressen ein vielfaches von 4Byte (oder 8Byte auf 64Bit???) sind, können schneller aus dem RAM geladen werden. Man sollte also bei oft benutzen Variablen darauf achten und nicht nur blind der Compiler Optimierung vertrauen. Gerade bei Sachen wie SSE ist es gut, wenn die Array Elemente auf 16Byte ausgerichtet sind, da ein SSE Register 128Bit breit ist.

Der GNU Compiler hat ein spezielles Attribut für Variablen [1].

Hier die Funktion die anzeigt, auf wieviel Byte eine Variable ausgerichtet ist:

void multipleOf(void* p) {
  cout << (size_t)p << " multiple of";
  if((size_t)p % 2 == 0)
    cout << " 2 ";
  if((size_t)p % 4 == 0)
    cout << " 4 ";
  if((size_t)p % 8 == 0)
    cout << " 8 ";
  if((size_t)p % 16 == 0)
    cout << " 16 ";
  if((size_t)p % 32 == 0)
    cout << " 32 ";
  cout << endl;
}

Und hier ein paar Beispiele.

  char unalign;
  char __attribute__ ((aligned (4))) align;
  multipleOf(&unalign);
  multipleOf(&align);

140736773522255 multiple of
140736773522252 multiple of 2  4 

Die erste Zahl ist immer die Adresse der Variable in Dezimal, damit man besser Kopfrechnen kann. Wie man sieht hat die Variable unalign eine ungerade Adresse -> nicht gut. Aber mit dem aligned Attribut kann man das schnell ändern :).

Soweit ich weiß haben int, long, float, double u.s.w. immer mindestens ein align von 4.

Aber wie sieht das mit den Adressen einzelner Arrayelemente aus?

  struct  Point {
  float x, y, z;
  };

  cout << "sizeof Point " << sizeof(Point) << endl;
  Point p[4];
  multipleOf(p);
  multipleOf(p+1);
  multipleOf(p+2);
  multipleOf(p+3);

sizeof Point 12
140733340474464 multiple of 2  4  8  16  32 
140733340474476 multiple of 2  4 
140733340474488 multiple of 2  4  8 
140733340474500 multiple of 2  4 

Das nächste Array Element ist immer 12Byte weiter. So ist die Sache zwar noch auf 4Byte ausgerichtet, aber nicht auf 16Byte wie das für SSE schön wäre. Hier die Lösung:

  struct  __attribute__ ((aligned (32))) Point {
  float x, y, z;
  };

sizeof Point 16
140736307878992 multiple of 2  4  8  16 
140736307879008 multiple of 2  4  8  16  32 
140736307879024 multiple of 2  4  8  16 
140736307879040 multiple of 2  4  8  16  32 

In diesem Fall hätte man auch einfach eine vierte Variable "w" in das Strukt einfügen können. Aber ich denke die Ausrichtung in Bytes manuell angeben ist besser. Es steht nämlich niergends geschrieben, dass ein float auch 4Byte hat. Zum Beispiel hat ein int auf einer 64Bit Maschine unter Linux noch 32Bit aber unter Windows 64Bit. Das gibt böse Fehler.

[1] http://gcc.gnu.org/onlinedocs/gcc/Type-Attributes.html

Es geht um std::vector

Das i-te Element von vector<> a kann statt mit a[i] e?zienter mit
T::iterator ai = a.begin();
T element = *(ai + i);
dereferenziert werden. Dies entspricht der internen Arbeitsweise des Indexoperators, jedoch
erzeugt dieser bei jedem Elementzugri? einen Iterator auf den Anfang des Containers. Gerade
in Schleifen, in denen große Datenströme Element für Element durchlaufen werden, emp?ehlt
es sich, einen Iterator einmalig vor der Schleife anzulegen und als Basisadresse zu verwenden.
Dadurch verdoppelt sich die Performance im Cache und im Speicher können etwa 20 %
Geschwindigkeitszuwachs gemessen werden.

Aus http://www.rrze.uni-erlangen.de/dienste/arbeiten-rechnen/hpc/Projekte/DA_Stengel_cppnuma.pdf Seite 34

Das geht aber wieder gegen die Compiler Optimierung. Leider habe ich mir nicht notiert, wo ich das gelesen habe. Aber wenn man den operator[] benutzt, dann weiß der Compiler, dass man nur durch das Array laufen will. Und nicht irgendwelche Pointerarithmetik.
// edit
Gilt das aber auch für den operator[] einer Klasse und nicht nur für ein RAW Array? Mist, wo hab ich das blos nur gelesen...

Ich habe mal etwas geforscht und folgendes gefunden: in der libstdc++-v3 die mit dem GNU C++ Compiler kommt, wird KEIN Iterator beim Aufruf vom operator[] erzeugt.
gcc-4.7-20120225/libstdc++-v3/include/bits/stl_vector Zeile 755

   // element access
      /**
       *  @brief  Subscript access to the data contained in the %vector.
       *  @param __n The index of the element for which data should be
       *  accessed.
       *  @return  Read/write reference to data.
       *
       *  This operator allows for easy, array-style, data access.
       *  Note that data access with this operator is unchecked and
       *  out_of_range lookups are not defined. (For checked lookups
       *  see at().)
       */
      reference
      operator[](size_type __n)
      { return *(this->_M_impl._M_start + __n); }

_M_start ist also nur ein Pointer der um __n Element weiter gezählt wird. Kein Iterator zu sehen. Das ist aber Pointer Arithmetik und das ärgert den Compiler. Kann man das nicht auch so machen?

 { return _M_impl._M_start[__n]); }

Das wäre dann der [] operator auf ein RAW Array.

Der benutze Compiler im obrigen Pdf ist der 64Bit Intel C/C++-Compiler Version 9.1.049. Und damit wäre der Gnu Compiler schneller. Zumindest in diesem Fall ;) GNU Rockt ;)

Ich habe auch noch ein Codestück von SGI gefunden wo ein Iterator benutzt wird.
http://www.sgi.com/tech/stl/download.html Datei stl_vector.h Zeile 224.

iterator begin() { return _M_start; }
reference operator[](size_type __n) { return *(begin() + __n); }

Der Iterator ist hier nur ein Funktion die ein Pointer zurück gibt. Dieser Funktionsaufruf wird bestimmt weg optimiert.

Micht interessiert wie Intel das implementiert hat.

Auf 64Bit Plattformen ist in der Regel ein Int 32Bit groß. Macht man damit Pointerarithmetik muss die 32Bit Zahl erst zu eine 64Bit zahl convertiert werden, bevor sie verrechnet wird. Pointer sind auf 64Bit Plattformen auch 64Bit groß.

Durch den Einsatz von size_t statt int und ptrdiff_t statt int* lässt sich das verhindern. Siehe http://www.viva64.com/en/a/0050/

Ich habe mit Valgrind mir die Anzahl der Instrktionen für die Testfunktion geben lassen und es stimmt. Es werden für dieses
Beispiel nur noch 5 statt 4 Instruktionen für ein Array Element benötigt.

Hier mein Testprogramm:

#include < iostream >
#include < stdlib.h >

void func(size_t arraySize, float array[] ) {
  for (size_t i = 0; i < arraySize / 2; i++)
  {
    float value = array[i];
    array[i] = array[arraySize - i - 1];
    array[arraySize - i - 1] = value;
  }
}

int main(int argc, char **argv) {
        unsigned int n = atoi(argv[1]);
        std::cout << n << std::endl;
        float *arr = new float[n];

        func(n, arr);

        std::cout << "ausgabe " << arr[0] << std::endl;
        delete[] arr;
        return 0;
}

g++ -O2  -Wall object.cpp
valgrind --tool=callgrind   --collect-systime=yes --callgrind-out-file=unsignedint.out ./a.out 100000000
callgrind_annotate unsignedint.out |grep func

array           Instruction count
lenght     unsigned int        size_t

1*10^8    500,000,007         400,000,007 
1*10^7     50,000,007          40,000,007
1*10^6      5,000,007           4,000,007  
1*10^5        500,007             400,007
1*10^4         50,007              40,007
1*10^3          5,007               4,007