C++ Performance von C++ - aktueller Stand?

[antred]

Also ich bekomme erst bei 100.000 Elementen einen Geschwindigkeitsvorteil des Arrays um 1 ms. Bei 1.000.000 sind es immerhin schon 9 ms Vorsprung für das Array, allerdings möchte ich damit nicht arbeiten.

#define MEM_SIZE 100000

void FillVector( Stopwatch &s, vector<int> &r ) { s.Start(); for( int i = 0; i < MEM_SIZE; i++ ) r.push_back( 0 ); s.Stop(); }
void FillArray( Stopwatch &s, int *r ) { s.Start(); for( int i = 0; i < MEM_SIZE; i++ ) r[i] = 0; s.Stop(); }

int main()
{
  Stopwatch s;

  vector<int> v;
  int *a = new int[MEM_SIZE];

  FillVector( s, v ); cout << "std::vector took " << s.Difference() << " ms" << endl;
  FillArray( s, a );  cout << "array took " << s.Difference() << " ms" << endl;

  system( "pause" );

  return 0;
}

So "langsam" ist ein vector also nicht und die STL gibt es ja nun schon einige Jahre und es wurde bestimmt auch daran optimiert.

Ich bin bezüglich vector-Performance auf deiner Seite, aber ich würde mit solchen künstlichen Benchmarks sehr vorsichtig sein, da derart trivialer Code selten repräsentativ für tatsächlich produktiv eingesetzten Code ist.

Obendrein wundert es mich sogar, daß in deinem Beispiel der vector nahezu genau so schnell wie das Array ist, denn du hast den vector etwas ungünstig eingesetzt.

Normalerweise würde man, wenn bei einem vector schon von vorneherein weiß, mit wie vielen Elementen er bestückt werden soll, gleich dafür sorgen, daß er auf die nötige Kapazität hat ... also r.reserve( MEM_SIZE );

Sonst würde der vector nämlich mehrmals seinen internen Speicher vergrößern müssen - also größeres Array allokieren, Inhalt des alten in das neue, größere Kopieren und dann altes Array löschen. Und da wäre meine Erwartungshaltung dann schon, daß der vector im Vergleich zum Array etwas langsamer wäre.

 

[Yuuri]

Ich bin bezüglich vector-Performance auf deiner Seite, aber ich würde mit solchen künstlichen Benchmarks sehr vorsichtig sein, da derart trivialer Code selten repräsentativ für tatsächlich produktiv eingesetzten Code ist.

Klar kann man es nicht nehmen, aber für einen kleinen Performancevergleich reicht es alle male aus, nur um zu sehen, wie schnell Variante a zu b ist. Nichtsdestotrotz ändert das alles (du kannst ja nur Werte hinzufügen, was anderes wäre sinnlos) im Prinzip nichts an der Performance. Hier fehlt natürlich die sämtliche Logik drumherum, welche allerdings nichts an der Performance des Zuweisens/Hinzufügens selbst ändert würde.

Obendrein wundert es mich sogar, daß in deinem Beispiel der vector nahezu genau so schnell wie das Array ist, denn du hast den vector etwas ungünstig eingesetzt.

Normalerweise würde man, wenn bei einem vector schon von vorneherein weiß, mit wie vielen Elementen er bestückt werden soll, gleich dafür sorgen, daß er auf die nötige Kapazität hat ... also r.reserve( MEM_SIZE );

Wieder was dazugelernt. Mit dem .reserve() ist der Unterschied wieder bei 0 ms (mit 0-Zuweisung) bei 100.000 Elementen. Bei 1 Mio sind 3 ms Unterschied. Also theoretisch zu vernachlässigen, außer man braucht die Performance woanders.

Übrigens sehr nett finde ich den Unterschied von x86 und x64.

10 Mio Elemente, 0-Zuweisung, x86:
vector: 44 ms
array: 16 ms

10 Mio Elemente, 0-Zuweisung, x64:
vector: 34 ms
array: 14 ms

Alles übrigens mit dem MSVC2010 Compiler, einen anderen habe ich momentan nicht auf dem PC.

 

[antred]

Release oder debug build? Für maximale Performance empfiehlt es sich auch, mit -D_SCL_SECURE=0 zu übersetzen. Damit werden weiter Debugfeatures deaktiviert, und der Unterschied zum Array könnte noch geringer ausfallen.

 

[ghorst]

Das sollte keinen nennenswerten Unterschied mehr machen, da push_back() zwangsläufig langsamer als [] ist.
Das liegt daran, dass "a.push_back(x)" in Code umgesetzt, wenn man den Rückgabewert nicht beachtet, in etwa so aussieht:

if (size>=capacity)
 internes_array_vergrößern();
internes_array[size++]=x;

wohingegen a[x] nur a[x] ausführt.

Man bekommt also bei push_back() im Verhältnis zu a[x] immer das Wachsen des internen Zählers und die Überprüfung der Kapazität dazu. Das kann der Compiler auch nur verhindern, wenn man ihn darauf hinweist, dass die Daten in dem Bereich _nicht_ von Parallelverarbeitung betroffen sein kann. Dann kann er Aufrufe auf size und capacity in einem zusammenfassen.
Hingegen sind folgende Zugriffe:

std::vector<my_type> vec;
my_type* arr;
vec[i] und arr[i] absolut identisch.

 

[Yuuri]

Release oder debug build?

Release natürlich. Im Debug Build stinkt der Vektor natürlich vollends ab - 2939 ms gegen 33 ms (Array). Im x64-Debug-Build sind es immerhin noch 1009 ms.

Das sollte keinen nennenswerten Unterschied mehr machen, da push_back() zwangsläufig langsamer als [] ist.
Das liegt daran, dass "a.push_back(x)" in Code umgesetzt, wenn man den Rückgabewert nicht beachtet, in etwa so aussieht:

Hast Recht, aber einen minimalen Performancevorteil hat das Array bei 10 Mio Einträgen natürlich noch. Bei ergibt sich jetz 3 ms Vorteil zugunsten des Arrays (bei 10 Mio Elementen).

 

[ghorst]

Ich hoffe du hast nicht einfach auf den mit reserve() reservierten Bereich geschrieben... Das hebt den Wert von size() nicht an und führt bei Objekten dazu, dass diese nicht zerstört werden. Desweiteren schreibst dann auch mittels des assignment operators und nicht des placement new (habe ich in meinem Code vorher auch ziemlich ungeschickt geschrieben, was da steht, galt nur für POV. Da verhalten sich die beiden gleich.). Das ist ein ganz böse Idee.

Wenn du Startwerte in einem vector festlegen willst, benutzt man am sinnvollsten dafür den Contructor oder die bei späteren Werten die Funktion assign. Das spart sinnloses initialisieren und kopieren.

Eine wichtige Quelle für den Unterschied zwischen my_object[fix_size] und std::vector<my_object> bei kleinen Größen ist, dass das Array auf dem Stack angelegt wird und somit dessen Reservierung sich darauf beschränkt den Stackcounter zu erhöhen, wobei der std::vector im Normalfall (Leute, die Spaß an seltsamen Debug-Sessions haben, können natürlich auch einen Stackallocator benutzen...) die dynamische Speicherreservierung nutzt. Die ist um diverse Größenordnungen langsamer.

Daher kann ich mir gut vorstellen, dass wenn man std::vector als Ersatz für kleine statische Array benutzt, es hinbekommt, dass der std::vector-Code um den Faktor 10 langsamer ist. Schuld ist aber dann nicht std::vector sondern der Programmierer, der den falschen Container gewählt hat. Statische C-Arrays sollte man auch durch genau solche statischen Konstrukte ersetzen. Also entweder std::tr1::array oder in C++0x std::array bzw. das boost::array. MFC hat wenn ich mich dumpf erinnere auch einen solchen Container dabei.

 

[Hancock]

@ghost:
Du hast es verstanden, bei kleinen Werten zieht halt die dynamische Speicherallokierung und der Konstruktor rein (ich hab auch was von 10 Elementen geschrieben, bei dem Fall waren is im Schnitt sogar nur 2).
Ich habs dann auch geändert, nachdem ich es bemerkt hatte und dann wars auch flott .

tr1::array kannte ich noch gar nicht, aber das ist eine nette Sache (aber ist auch nicht dynamisch (in VS2008)).

 

[badday]

In der Tat bietet tr1 viele interessante Sachen, etwa das unordered_set als hashtable.

Es gibt natürlich immer diverse Verbesserungen und Optimierungen, aber man muss sich halt immer überlegen, inwieweit der Code dann noch gut lesbar und überschaubar ist. Manchmal können ja kleine Sachen wie ++iter statt iter++ schon große Sachen bewirken


Gruß,

badday

 

[ghorst]

@ghost:
(aber ist auch nicht dynamisch (in VS2008)).

Das ist nirgendwo dynamisch. Steht im TR1 zumindest so drin und ist darum ein Ersatz für statische c-Arrays.

btw. Da ist ein "r" in meinem Nutzernamen. ;-)

@badday Mein Lieblingskonstrukt bzgl. sinnlosen Postinkrement :

for(irgendwas;irgendwas;iter++)

Das findet man lustigerweise in einer Reihe von Tutorials, Vorlesungen und Büchern.

 

[badday]

Das findet man lustigerweise in einer Reihe von Tutorials, Vorlesungen und Büchern.

In der Tat. Das interessante ist, dass viele, auch wenn man sie darauf aufmerksam macht, immer noch der festen Meinung sind, ihr Compiler würde das 100% optimieren

 

[Hancock]

@ghorst:
Ist mir gar nicht aufgefallen
wenns zur Erstellzeit dynamisch wäre, wärs ein echt mächtiges Konstrukt, was ist aber dann der Vorteil gegenüber einem "foo a[10]={};"? Nur dass man es kopieren kann und es ein paar Daten mehr speichert (size...)?

@postincrement:
Bei einer int sollte das auch wegoptimiert werden. Bei einem iterator wirds nicht ganz funktionieren...
Ich hab mir das präinkrementieren angewöhnt.

 

[ghorst]

wenns zur Erstellzeit dynamisch wäre, wärs ein echt mächtiges Konstrukt,

Du meinst ein Stack alloziertes statisches Array? Das kannst du mittels eines Stack-Allocators und valarray haben. Einfach als zweiten Templateparameter den anderen Allocator angeben. Den Stackallocator kannst du mittels alloca schreiben, so du eine Plattform hast, auf der das Ding zuverlässig arbeitet. Aber wie ich schon an anderer Stelle schrieb: Stackallocatoren können für echt coole Debugsessions sorgen.

was ist aber dann der Vorteil gegenüber einem "foo a[10]={};"? Nur dass man es kopieren kann und es ein paar Daten mehr speichert (size...)?

Size wird nicht gespeichert, sondern als Templateargument genutzt. Weiß also nur der Compiler etwas von. Da auch kein vtable von Nöten ist, sollte ein std::tr1::array<char,10> genauso groß und schnell sein wie char[10].

Was es bietet: Ein hübscheres Interface mit einer Nomenklatur wie die anderen Container. Ansonsten nimmt es sich nichts.

@postincrement:
Bei einer int sollte das auch wegoptimiert werden. Bei einem iterator wirds nicht ganz funktionieren...

It depends. Eine Reihe von iteratoren wird die Mehrheit der Compiler noch klein bekommen. Schwierig wird es, wenn der iterator mehr als nur trivialen Code enthält. Unmöglich wird es, wenn der Compiler den Code des operator++(int) und operator++() nicht "sehen" kann oder wenn er die nötigen Copy-Konstruktoren dahinter nicht sehen kann.