{"id":4347,"date":"2019-06-01T09:29:36","date_gmt":"2019-06-01T08:29:36","guid":{"rendered":"http:\/\/roboblog.fatal-fury.de\/?p=4347"},"modified":"2019-06-01T09:29:36","modified_gmt":"2019-06-01T08:29:36","slug":"cguns-re-c-core-guidelines-stdarray-und-stdvector-sind-die-erste-wahl","status":"publish","type":"post","link":"http:\/\/roboblog.fatal-fury.de\/?p=4347","title":{"rendered":"C++Guns: RE: C++ Core Guidelines: std::array und std::vector sind die erste Wahl"},"content":{"rendered":"

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 <\/a> 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.<\/p>\n

Nat\u00fcrlich hat sich der C++ Gr\u00fcndervater Bjarne Stroustrup schon seit Jahren (Jahrzehnten?) mit dem Thema besch\u00e4ftigt. Es lohnt sich nachzulesen in Are lists evil?<\/a><\/p>\n

Zuallererst: Benchmarks sind super schwer und keiner kann sie richtig machen. Daher werde ich im ersten Schritt
\nnur versuchen die Ergebnisse auf meinem Laptop nachzuvollziehen. Und im zweiten Schritt die Datenmenge oder die
\nAnzahl Zugriffe erh\u00f6hen, da eine Laufzeit von 0.07 Sekunden doch sehr gering ist. Da Linux ein Multiuser\/Multithread
\nBetriebssystem ist, passiert allerlei Nebenbei. Und diese \"St\u00f6rungen\" versuche ich durch eine l\u00e4ngere Messzeit
\nzu auszublenden.<\/p>\n

1) Reproduzieren
\n1.a) Erster Versuch
\nBeispiel Code runter laden, compilieren, starten, \"Killed\".<\/p>\n

1.b)
\nIch habe nicht genug RAM oder der RAM ist zugem\u00fcllt -_- Im Beispiel Code werden 100 Millionen Integer a 4 Byte
\nals Nutzdaten angegeben. Das ergibt ein Speicherverbrauch von _mindestens_ 400MB. std::vector und std::deque
\nfunktionieren noch. Bei std::list steigt das Programm aus.
\nDer Grund ist einfach. W\u00e4hrend std::vector einfach 400MB am St\u00fcck allokiert, passiert bei std::list schon mehr.
\nIch wage zu behaupten, dass f\u00fcr jedes neu eingef\u00fcgte Element einmal extra Speicher auf dem Heap allokiert wird.
\nDamit ist der Speicher Overhead nat\u00fcrlich gigantisch und das Programm steigt aus. <\/p>\n

1.c)
\nEin kurzer Blick in den Systemmonitor Zeigt, dass das Programm Firefox nat\u00fcrlich einige GB im RAM belegt. Also das Programm
\nbeenden und schon zeigen sich 20 Instanzen von mysql die jeweils 170MB belegen. Wozu brauche ich eine Datenbank?
\nWusste gar nicht, dass so etwas installiert ist. Also mysqld Server deinstallieren und beenden.<\/p>\n

1.d) Zweiter Versuch
\nImmerhin l\u00e4uft std::list jetzt durch, aber bei std::forward_list bricht das Programm mit der Fehlermeldung ab:
\n*** Error in `.\/a.out': free(): invalid pointer: 0x00000000464a1320 ***
\nDas weitere beenden von Programmen welche viel Speicher verbrauchen f\u00fchre zu einem Absturz des Systems...<\/p>\n

1.e) Dritter Versuch
\nNach einem Neustart werden \"nur\" 832 von 7680MB als belegt angezeigt. Diesmal hat es funktioniert!<\/p>\n

std::vector
\ntime: 0.0352953930
\nres: 4999774274<\/p>\n

std::deque
\ntime: 0.0827120400
\nres: 4999774274<\/p>\n

std::list
\ntime: 0.2975692830
\nres: 4999774274<\/p>\n

std::forward_list
\ntime: 0.3002444010
\nres: 4999774274<\/p><\/blockquote>\n

Damit kann ich die Werte reproduzieren. std::vector ist wie zu erwarten am schnellsten. Und std::forward_list ist langsamer als std::list.<\/p>\n

2) L\u00e4ngere Laufzeit
\nDie Datenmenge zu erh\u00f6hen w\u00fcrde kein Sinn machen. Also werde ich die Summe statt nur einmal, gleich 100 mal bilden.
\nDie zu erwartende Laufzeit liegt damit von 4 bis 30 Sekunden.
\nUm einen Vergleich anzustellen wie die Laufzeiten der Container sich relativ zu std::vector verhalten:<\/p>\n

1.000 std::ector
\n0.427 std::deque
\n0.119 std::list
\n0.118 std::forward_list<\/p>\n

std::vector
\ntime: 3.4487668950
\nres: 499993166900<\/p>\n

std::deque
\ntime: 7.2533651530
\nres: 499993166900<\/p>\n

std::list
\ntime: 28.2407733910
\nres: 499993166900<\/p>\n

std::forward_list
\ntime: 30.5225665430
\nres: 499993166900<\/p><\/blockquote>\n

Hier die neuen relativen Werte:
\n1.000 std::vector
\n0.475 std::deque
\n0.122 std::list
\n0.113 std::forward_list<\/p>\n

Also std::forward_list ist _wirklich_ langsamer als std::list. Es bleibt ein R\u00e4tsel.<\/p>\n","protected":false},"excerpt":{"rendered":"

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\u00fcrlich hat sich der C++ Gr\u00fcndervater Bjarne Stroustrup […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[17],"class_list":["post-4347","post","type-post","status-publish","format-standard","hentry","category-allgemein","tag-cpp"],"_links":{"self":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/4347","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4347"}],"version-history":[{"count":5,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/4347\/revisions"}],"predecessor-version":[{"id":4352,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/4347\/revisions\/4352"}],"wp:attachment":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4347"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4347"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4347"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}