C++Guns – RoboBlog

27.03.2012

Faster Code - Part 2

Filed under: Allgemein — Tags: , , , — Thomas @ 10:03

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.

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