C++Guns – RoboBlog

Ich finde es schade, dass der Artikel von Rainer Grimm bei heise.de C++ Core Guidelines: std::array und std::vector sind die erste Wahl so wenig Beachtung bekommt. Er wirft nicht nur ein paar interessante Fragen auf, sondern geht auf der Kernaussage von Performance ein: Don't think, use std::vector.

Natürlich hat sich der C++ Gründervater Bjarne Stroustrup schon seit Jahren (Jahrzehnten?) mit dem Thema beschäftigt. Es lohnt sich nachzulesen in Are lists evil?

Zuallererst: Benchmarks sind super schwer und keiner kann sie richtig machen. Daher werde ich im ersten Schritt
nur versuchen die Ergebnisse auf meinem Laptop nachzuvollziehen. Und im zweiten Schritt die Datenmenge oder die
Anzahl Zugriffe erhöhen, da eine Laufzeit von 0.07 Sekunden doch sehr gering ist. Da Linux ein Multiuser/Multithread
Betriebssystem ist, passiert allerlei Nebenbei. Und diese "Störungen" versuche ich durch eine längere Messzeit
zu auszublenden.

1) Reproduzieren
1.a) Erster Versuch
Beispiel Code runter laden, compilieren, starten, "Killed".

1.b)
Ich habe nicht genug RAM oder der RAM ist zugemüllt -_- Im Beispiel Code werden 100 Millionen Integer a 4 Byte
als Nutzdaten angegeben. Das ergibt ein Speicherverbrauch von _mindestens_ 400MB. std::vector und std::deque
funktionieren noch. Bei std::list steigt das Programm aus.
Der Grund ist einfach. Während std::vector einfach 400MB am Stück allokiert, passiert bei std::list schon mehr.
Ich wage zu behaupten, dass für jedes neu eingefügte Element einmal extra Speicher auf dem Heap allokiert wird.
Damit ist der Speicher Overhead natürlich gigantisch und das Programm steigt aus.

1.c)
Ein kurzer Blick in den Systemmonitor Zeigt, dass das Programm Firefox natürlich einige GB im RAM belegt. Also das Programm
beenden und schon zeigen sich 20 Instanzen von mysql die jeweils 170MB belegen. Wozu brauche ich eine Datenbank?
Wusste gar nicht, dass so etwas installiert ist. Also mysqld Server deinstallieren und beenden.

1.d) Zweiter Versuch
Immerhin läuft std::list jetzt durch, aber bei std::forward_list bricht das Programm mit der Fehlermeldung ab:
*** Error in `./a.out': free(): invalid pointer: 0x00000000464a1320 ***
Das weitere beenden von Programmen welche viel Speicher verbrauchen führe zu einem Absturz des Systems...

1.e) Dritter Versuch
Nach einem Neustart werden "nur" 832 von 7680MB als belegt angezeigt. Diesmal hat es funktioniert!

std::vector
time: 0.0352953930
res: 4999774274

std::deque
time: 0.0827120400
res: 4999774274

std::list
time: 0.2975692830
res: 4999774274

std::forward_list
time: 0.3002444010
res: 4999774274

Damit kann ich die Werte reproduzieren. std::vector ist wie zu erwarten am schnellsten. Und std::forward_list ist langsamer als std::list.

2) Längere Laufzeit
Die Datenmenge zu erhöhen würde kein Sinn machen. Also werde ich die Summe statt nur einmal, gleich 100 mal bilden.
Die zu erwartende Laufzeit liegt damit von 4 bis 30 Sekunden.
Um einen Vergleich anzustellen wie die Laufzeiten der Container sich relativ zu std::vector verhalten:

1.000 std::ector
0.427 std::deque
0.119 std::list
0.118 std::forward_list

std::vector
time: 3.4487668950
res: 499993166900

std::deque
time: 7.2533651530
res: 499993166900

std::list
time: 28.2407733910
res: 499993166900

std::forward_list
time: 30.5225665430
res: 499993166900

Hier die neuen relativen Werte:
1.000 std::vector
0.475 std::deque
0.122 std::list
0.113 std::forward_list

Also std::forward_list ist _wirklich_ langsamer als std::list. Es bleibt ein Rätsel.