C++Guns – RoboBlog blogging the bot

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