C++ vektor

[Youka]

Die Leistung der STL hängt nicht wenig von der Implementation ab, so ist sie in älteren Compiler-Bibliotheken in vielen Fällen schlechter als in neueren.
Desweiteren sind STL-Klassen oftmals überladen, was in C++11 durch schlankere Alternativen verbessert wurde.
Ein neuerer Compiler und der Nutzen von std::array wäre eine Überlegung wert.

Zu beachten sei auch das Speichermodell eines STL Vektors und deiner Vorwärts-Liste:
Ein Vektor ist ein Wrapper um ein dynamisches Array. Mit neuen Elementen findet auch eine Reallokierung statt, dies macht das Erweitern von Vektoren teuer, das Löschen kann ungenutzen Speicher zur Folge haben. Jedoch ist der Zugriff wegen des aneinander liegenden Speichers schnell.
Deine Liste ist ein durch Zeiger zusammengehaltenes Speicherkonstrukt. Hinzufügen oder entfernen von Elementen ist günstig, jedoch der Zugriff auf ein bestimmtes Element teuer, weil erst durch die Liste durchgegangen werden muss.

Zusammenfassend ließe sich sagen, dass Vektoren gut sind, wenn es um schnellen Zugriff auf ein bereits fertiges Datenkonstrukt geht, wohingegen Listen empfehlenswerter für das Gegenteil sind, also noch einiges an Daten hinzugefügt oder entfernt werden muss.

[Fuchs aus dem Wald]

Hab ich schon ... es ist einfach genau so schnell wie der andere scheiß. Nur das ich halt bestimmt 15 Zeilen mehr habe.

[glühbirne]

Die nehmen im Ernst eine verkettete Liste, weil std::vector langsam ist? Sag denen mal, dass dynamische Speicheranforderung pro Element viel teurer als pro Array ist, und dass man die Daten cache-unfreundlich im RAM verteilt hat.

Youka: vector ist fast immer schneller als list. Und was meinst du mit "STL-Klassen sind oftmals überladen"? Die Anzahl der Funktionen hat keinen Einfluss auf die Performance... Und besonders viele Datenmember gibts üblicherweise auch nicht.

<>

[glühbirne]

Fuchs aus dem Wald schrieb:

Hab ich schon ... es ist einfach genau so schnell wie der andere scheiß.

Niemals ist std::vector gleich schnell wie die verkettete Liste. Du misst bestimmt falsch.

<>

[jokurt]

Youka schrieb:

Desweiteren sind STL-Klassen oftmals überladen, was in C++11 durch schlankere Alternativen verbessert wurde.
Ein neuerer Compiler und der Nutzen von std::array wäre eine Überlegung wert.

Die einzige überladene STL-Klasse ist std::array. Es gibt wirklich keinen Grund, das zu benutzen.

@Fuchs aus dem Wald: Wenn nicht mal eine Messung diese Leute vom Gegenteil überzeugt (lass auch ruhig mal die messen), kommst du mit rationalen Begründungen auch nicht weit.

[Fuchs aus dem Wald]

ScottZhang schrieb:

Miss doch einfach die Performance mal, und die wirst die ganz schnell davon überzeugen das std::vector sau schnell ist.

Hab ich schon ... es ist einfach genau so schnell wie der andere scheiß. Nur das ich halt bestimmt 15 Zeilen mehr habe.

formanz schrieb:

Was du nicht machen darfst, ist das col-Array durch einen Vektor ersetzen.

Nein leider darf ich das nicht ...

Youka schrieb:

Die Leistung der STL hängt nicht wenig von der Implementation ab, so ist sie in älteren Compiler-Bibliotheken in vielen Fällen schlechter als in neueren.
Desweiteren sind STL-Klassen oftmals überladen, was in C++11 durch schlankere Alternativen verbessert wurde.
Ein neuerer Compiler und der Nutzen von std::array wäre eine Überlegung wert.

Zu beachten sei auch das Speichermodell eines STL Vektors und deiner Vorwärts-Liste:
Ein Vektor ist ein Wrapper um ein dynamisches Array. Mit neuen Elementen findet auch eine Reallokierung statt, dies macht das Erweitern von Vektoren teuer, das Löschen kann ungenutzen Speicher zur Folge haben. Jedoch ist der Zugriff wegen des aneinander liegenden Speichers schnell.
Deine Liste ist ein durch Zeiger zusammengehaltenes Speicherkonstrukt. Hinzufügen oder entfernen von Elementen ist günstig, jedoch der Zugriff auf ein bestimmtes Element teuer, weil erst durch die Liste durchgegangen werden muss.

Zusammenfassend ließe sich sagen, dass Vektoren gut sind, wenn es um schnellen Zugriff auf ein bereits fertiges Datenkonstrukt geht, wohingegen Listen empfehlenswerter für das Gegenteil sind, also noch einiges an Daten hinzugefügt oder entfernt werden muss.

Danke so sehe ich das auch. Und da bei mir nichts mehr im nachhinein hin zu kommt oder entfernt werden muss ...

glühbirne schrieb:

Fuchs aus dem Wald schrieb:

Hab ich schon ... es ist einfach genau so schnell wie der andere scheiß.

Niemals ist std::vector gleich schnell wie die verkettete Liste. Du misst bestimmt falsch.

<>

Ich konnte nicht feststellen das mein Programm dadurch langsamer wird(Vektor) aber auch nicht schneller ...

[formanz]

Fuchs aus dem Wald schrieb:

formanz schrieb:

Was du nicht machen darfst, ist das col-Array durch einen Vektor ersetzen.

Nein leider darf ich das nicht ...

Ich meinte: Aus Performanz-Gründen darfst du auf keinen Fall das col-Array durch einen Vektor ersetzen. Wenn das Array eine fixe Länge (<1Mrd) hat, ist ein statisches Array IMMER* besser als std::vector.

Btw: Wie misst du? Mit der Stoppuhr in der Hand neben dem Computer?

Ansonsten würde ich isoliert von der Anwendung an einem Minimalbeispiel zeigen, dass std::vector schneller ist. Bei einem kleinen übersichtlichen Programm mit Vector vs. Intrusive-List können die sich auch schlecht rausreden.

*gut, gibt exotische Ausnahmen wie move-Operationen.

[Fuchs aus dem Wald]

Also ob ich hier per Hand messe ...

timeval start, end;///debugg
  gettimeofday(&start, 0);
  /*
   * code
   */
  gettimeofday(&end, 0);///debugg
  std::cout << start.tv_sec << ':' << start.tv_usec << std::endl;///debugg
  std::cout << end.tv_sec << ':' << end.tv_usec << std::endl;///debugg

[glühbirne]

jokurt schrieb:

Die einzige überladene STL-Klasse ist std::array. Es gibt wirklich keinen Grund, das zu benutzen.

Genau andersherum: Mit std::array gibt es keinen Grund mehr, C-Arrays zu nutzen. Man hat nur fehlende Sicherheit und Wertsemantik.

Fuchs: Mach ein minimales Programm mit dem Benchmark und poste die Ergebnisse. Ich bezweifle nach wie vor, dass beides gleich schnell ist.

<>

[formanz]

glühbirne schrieb:

fehlende Sicherheit

Sicherheit hat man nur im Debug-Build. Und da können auch Array-Zugriffe überprüft werden, sonst hat man die falschen Tools.

glühbirne schrieb:

Wertsemantik.

Praktisch immer ein Fehler. Arrays zu kopieren sollte man vermeiden oder zumindest syntaktisch kenntzeichnen. C-Arrays unterstützen einen dabei.

.begin(), .end(), .size() sollte man sowieso durch std::begin, std::end, ::size ersetzen, C-Arrays unterstützen einen dabei.

C-Arrays können auch automatisch ihre Größe herausfinden, bei std::array besteht immer die Gefahr, sich um eins verzählt zu haben.

<>

[camper]

Bei einem 256-Byte großen Element dürfte die Containerwahl relativ unbedeutend für die Performance sein (bei einfachen iterativen Algorithmen). Der Vorteil von vector in Bezug auf bessere Cachlokalität ist dann einfach kaum noch gegeben, und der Speicheroverhead von Node-basierten Containern ist auch unbedeutend.

[Fuchs aus dem Wald]

glühbirne schrieb:

Fuchs: Mach ein minimales Programm mit dem Benchmark und poste die Ergebnisse. Ich bezweifle nach wie vor, dass beides gleich schnell ist.

<>

Liste:
START: 1370425812:811620
ENDE: 1370425812:811626
hier sind es 6 Mikrosekunden
Vektor:
START: 1370426056:420174
ENDE: 1370426056:420196
Hier sind es 22 Mikrosekunden

Ok es ist mit dem Vektor wirklich langsamer. Ich hatte das auf dem gesamten Durchlauf getestet jetzt nur auf den einzel Part. Und dann auch nur grob gerechnet.

[camper]

formanz schrieb:

glühbirne schrieb:

Wertsemantik.

Praktisch immer ein Fehler. Arrays zu kopieren sollte man vermeiden oder zumindest syntaktisch kenntzeichnen. C-Arrays unterstützen einen dabei.

Warum?

formanz schrieb:

C-Arrays können auch automatisch ihre Größe herausfinden, bei std::array besteht immer die Gefahr, sich um eins verzählt zu haben.

Nicht relevant in diesem Thread, schließlich geht es hier nicht um automatische oder statische Arrays, die ihre Größe aus einem Initialisierer ermitteln können.

[formanz]

@Fuchs:

formanz schrieb:

Wenn die Messung richtig gefaked ist, ist

std::vector<COLOR> colors;

langsamer, dann nimm

std::deque<COLOR> colors;

Das ist garantiert schneller.

Beachte, dass du auch auf die Member zugreifst.

camper schrieb:

formanz schrieb:

glühbirne schrieb:

Wertsemantik.

Praktisch immer ein Fehler. Arrays zu kopieren sollte man vermeiden oder zumindest syntaktisch kenntzeichnen. C-Arrays unterstützen einen dabei.

Warum?

Wertsemantik ist hauptsächlich sinnvoll als Member und da ist die Wertsemantik gegeben.

Nicht relevant in diesem Thread:
Rückgabewert -> Referenz auf Parameter (falls man Pech bei RVO hat)
Parameter -> const-Referenz oder Iteratoren

[Fuchs aus dem Wald]

Ich glaub um so mehr ich hier lese um so mehr muss ich leider sagen hier wird absoluter mist gecoeded ...
Also hier bei mir

[Youka]

Fuchs aus dem Wald schrieb:

Liste:
START: 1370425812:811620
ENDE: 1370425812:811626
hier sind es 6 Mikrosekunden
Vektor:
START: 1370426056:420174
ENDE: 1370426056:420196
Hier sind es 22 Mikrosekunden

Ok es ist mit dem Vektor wirklich langsamer.

Mit Erstellung des Vektors muss ein größerer Speicherbereich reserviert werden, was mehr Zeit kostet, als die wenigen kleinen Speicherbereiche deiner Liste. Das war's dann aber auch mit der Erstellung, folgend muss auch auf den Speicher zugegriffen werden und da punktet der Vektor ganz klar!

[Fuchs aus dem Wald]

Youka schrieb:

Mit Erstellung des Vektors muss ein größerer Speicherbereich reserviert werden, was mehr Zeit kostet, als die wenigen kleinen Speicherbereiche deiner Liste. Das war's dann aber auch mit der Erstellung, folgend muss auch auf den Speicher zugegriffen werden und da punktet der Vektor ganz klar!

Jop der Zugriff kommt erst später... ach ja das beste hab ich noch gar nicht erzählt.
Ich muss alle Daten von der liste in ein Array packen damit ich es überhaupt verschicken kann.
Jetzt fragt ihr euch sicher warum nicht gleich Array ... naja ich kenne die endgültige Größe ja nicht.
Aber Vektor ist da ja sooooooo viel umständlicher.

[camper]

Fuchs aus dem Wald schrieb:

glühbirne schrieb:

Fuchs: Mach ein minimales Programm mit dem Benchmark und poste die Ergebnisse. Ich bezweifle nach wie vor, dass beides gleich schnell ist.

<>

Liste:
START: 1370425812:811620
ENDE: 1370425812:811626
hier sind es 6 Mikrosekunden
Vektor:
START: 1370426056:420174
ENDE: 1370426056:420196
Hier sind es 22 Mikrosekunden

Ok es ist mit dem Vektor wirklich langsamer. Ich hatte das auf dem gesamten Durchlauf getestet jetzt nur auf den einzel Part. Und dann auch nur grob gerechnet.

Das sagt nicht viel aus, ohne zu wissen, was genau da getestet wurde. Diese Zeiten entsprechen ungefähr dem theoretischen Ergebnis, wenn für den vector ein Wachstumsfaktor von 1.5 angenommen wird (ohne Reservierung), der Aufwand der eigentlichen Speicherallokation gering ist und nur das usprüngliche Befüllen der Container gemessen wurde (und dafür intressieren wir uns ja eigentlich nicht so sehr).
Ansonsten ist eher zu vermuten, das
- unpassende Compileroptionen verwendet wurde, oder
- unpassende debug Einstellungen verwendet wurde (die Performance von Debug-Container kann sich erheblich - auch was die Komplexität angeht - von denen normaler Container unterscheiden), oder
- eine unpassene Messmethode verwandt wurde

[Fuchs aus dem Wald]

Messmethode hab ich doch gepostet.

[Furble Wurble]

Wes Brot ich ess, des Lied ich sing.
Da musst Du wohl durch.
Und das öffentliche Gezicke gegen die eigene Firma würde ich sein lassen!

Naja, wo wir schon Code sehen:
Das mit der Geschwindigkeit lasse ich mal dahingestellt.
Aber bei so einem Firelefanz wie diesem hier geht mir der Hut hoch:

struct COLOR{
  char col[256];
  COLOR* next;
};

COLOR* curr;
COLOR* first;

Konstruktor(){ curr = NULL; first = NULL}

if(!first){
    first = new COLOR;
    curr = first;
  }else{
    curr->next = new COLOR;
    curr = curr->next;
  }
  curr->next=NULL;	
}

Wieso hat eine Farbe eine Eigenschaft next ? Und wenn ich schon meine eigene Liste schreibe (haben wir schließlich alle mal), warum dann nicht als Template, sondern für jeden Typ eine eigene? Das ist ganz übler Stil - irgendwas zwischen C, C with classes und C++ ohne STL.

Ich würde noch ein Stück weiter gehen als formanz und sogar das eigene struct entfernen

typedef std::array<char, 256> COLOR;
  std::forward_list<COLOR> colors;

(und um Ihn zu ärgern habe ich sogar ein std::array eingebaut )

Damit schrumpft Eure Codebasis erheblich - allerdings ist natürlich die Lernkurve der Standardbibliothek auch nicht ganz zu verachten...
Spannend wäre noch zu wissen, wie gut sich Eure container mit den Algorithmen der STL vertragen...