dynamische Speicherplatzbeschaffung

Artchi

VerbalKint schrieb:

Die Vermutung basiert auf der Meinung von meinen Arbeitskollegen, die vectoren bei großen Datenmengen ablehnen, weil aufgrund des Listenaufbaus die Suche nach bestimmten Daten zu lange dauern würde.

Dann solltest du in Zukunft auf solche Meinungen (Meinungen, sie scheinen keine Fakten zu liefern) kritisch hinterfragen! Haben sie Performancetests gemacht? Nein! Haben sie sich den ISO-C++-Standard bzgl. std::vector durchgelesen? Nein! haben sie sich die Implementierung ihrer vector-Implementierung angeschaut? Nein!

Und dann stellen die so eine Behauptung auf? Einfach nur unprofessionell.

Lass dir gesagt sein, das ein Vector 100% die gleiche Performance wie ein rohes Array hat. Warum? Weil das der ISO-C++-Standard vorgibt. Lediglich eine nicht ISO-konforme Implementierung könnte hier langsamer sein. Aber das ist in der heutigen Zeit eher unwahrscheinlich, da ich mal davon ausgehe, das ihr eine vernünftige C++-Compiler-Suite einsetzt.

David_pb

Artchi schrieb:

Dann solltest du in Zukunft auf solche Meinungen (Meinungen, sie scheinen keine Fakten zu liefern) kritisch hinterfragen! Haben sie Performancetests gemacht? Nein! Haben sie sich den ISO-C++-Standard bzgl. std::vector durchgelesen? Nein! haben sie sich die Implementierung ihrer vector-Implementierung angeschaut? Nein!

Ist mir irgendwie schon oft aufgefallen, grad bezüglich der STL, das dieser extremes Ausbremsen der Programme vorgeworfen wird. Und jedesmal ohne wirkliche Fakten zu nennen!

VerbalKint

Okay, ich danke Euch für die Aufklärung! Wieder was dazu gelernt

asc

VerbalKint schrieb:

Die Vermutung basiert auf der Meinung von meinen Arbeitskollegen, die vectoren bei großen Datenmengen ablehnen, weil aufgrund des Listenaufbaus die Suche nach bestimmten Daten zu lange dauern würde.

Vom Suchverhalten sind beide genauso schlecht. Für eine Suche ist weder ein Array noch ein Vector (ist eigentlich immer ein Array, kümmert sich aber selbstständig um Speicherallokierung...) bei großen Datenmengen zu empfehlen. Dafür gibt es andere Container.

thordk

asc schrieb:

VerbalKint schrieb:

Die Vermutung basiert auf der Meinung von meinen Arbeitskollegen, die vectoren bei großen Datenmengen ablehnen, weil aufgrund des Listenaufbaus die Suche nach bestimmten Daten zu lange dauern würde.

Vom Suchverhalten sind beide genauso schlecht. Für eine Suche ist weder ein Array noch ein Vector (ist eigentlich immer ein Array, kümmert sich aber selbstständig um Speicherallokierung...) bei großen Datenmengen zu empfehlen. Dafür gibt es andere Container.

du nimmst mir die worte aus dem mund

Simon2

BorisDieKlinge schrieb:

ein array ist ein array und keine liste!

... und ein std::vector auch (hat zumindestens dessen Zugriffszeit).

Gruß,

Simon2.

Simon2

Artchi schrieb:

...
Dann solltest du in Zukunft auf solche Meinungen (Meinungen, sie scheinen keine Fakten zu liefern) kritisch hinterfragen! Haben sie Performancetests gemacht? Nein! Haben sie sich den ISO-C++-Standard bzgl. std::vector durchgelesen? Nein! haben sie sich die Implementierung ihrer vector-Implementierung angeschaut? Nein!...

Ja - gaaanz so hart würde ich nicht mit ihm ins Gericht gehen. Immerhin hat er ganz klar hervorgehoben, dass es sich um eine Vermutung und eine Meinung (eines Kollegen) handelt. Das ist schon deutlich kritischer als einige Andere hier (Euch natürlich alle ausgenommen) auftreten und das alles als "FAKT" ( ) darstellen.

Und ehrlich gesagt: Ich schlage auch nicht alles selbst in Std nach, was camper, CStoll und Du hier posten. :p
=> Ich vertraue auch Meinungen Anderer (meistens solcher, denen ich mehr KnowHow zutraue) - und Ihr bestimmt auch hier und da.

Gruß,

Simon2.

RHBaum

Naja, auf der anderen Seite muss man auch "den Arbeitskollegen" verstehen, zumindest versuchen

Das Hauptproblem was zu der "angeblichen Inperformance" der STL fuehrt, ist doch das c-programmierer, oder C++ im C-Stil programmierer mit der STL "konfrontiert" werden und kaum Gelegenheit haben hinter die kulissen zu schauen. Und die Literatur oder andere sogenannte "Experten" tun ihr uebriges.
Wo wird denn schon unterschieden, ob nen C-array dynamisch oder statisch ist um es von nem Vector ersetzen zu lassen ? Neee wenn, dann wird gleich alles ersetzt, obwohl nen vector beim erzeugen nie die performance eines statischen arrays erreichen kann. Besonders bei den strings gilt das halt ... std::string mag zwar modern sein, aber gegen einen buffer fester groesse wie in C oft verwendet wird hat er keine chance.
Bestes beispiel aus der Praxis, der Performance Test der entwicklungsumgebungen in der CT damals, wo .Net gegen JavaRT und STL angetreten sind. Letzter Platz eindeutig - die STL. Jeder der bisserl von C++ und STL ahnung hatte brauchte sich ned wundern, weil so wie der Autor die STL verwendet hatte, tun das maximal blutige Umsteiger bei ihren ersten Gehversuchen
Auf die Kritik folgte dann halt der die Verteidigung, das durchaus da optimierungspotential vorhanden waer, aber man eben darauf Wert gelegt haette die Tools so zu verwenden wie man es in der Praxis meist taete
Naja dann brauchen wir uns doch nicht zu wundern ...

Ciao ...

Artchi schrieb:

Lass dir gesagt sein, das ein Vector 100% die gleiche Performance wie ein rohes Array hat. Warum? Weil das der ISO-C++-Standard vorgibt. Lediglich eine nicht ISO-konforme Implementierung könnte hier langsamer sein. Aber das ist in der heutigen Zeit eher unwahrscheinlich, da ich mal davon ausgehe, das ihr eine vernünftige C++-Compiler-Suite einsetzt.

Ziemlicher Unfug wird hier behauptet. Was der ISO-C++-Standard vorgibt und was technisch möglich ist sind zwei verschiedene paar Schuhe. Die Indexprüfung entfällt beim Zugriff auf ein rohes Array. Implizit findet eine Indexprüfung beim Zugriff auf einen Vector statt. Letzere Operation kostet Zeit. Es ist deshalb weder technisch und obendrein aus rein logischen Gründen unmöglich, dass man auf Vektordaten 100% genau so schnell zugreifen kann wie auf Arraydaten.
Es sei denn jemandem fällt eine Möglichkeit ein, mit der die implizite Indexprüfung NULL Taktzyklen dauert. Technisch unmöglich, und deshalb ist es unerheblich, was der ISO-C++-Standard in dieser Sache (angeblich) vorgibt.
Die Herren, die den ISO-C++-Standard erfunden haben, haben aber zweifellos genügend Ahnung von technischer Informatik. Folgerung: Es gibt eine solche Vorschrift im ISO-C++ Standard deshalb nicht. Es sei denn Phantasten wie Artchie hätten in dem Gremium das Sagen.

LordJaxom

TechnischerFreak schrieb:

Implizit findet eine Indexprüfung beim Zugriff auf einen Vector statt.

Nein.

queer_boy

genauer: die indexprüfung findet nur statt, wenn man statt operator[] die elementfunktion at verwendet.

LordJaxom schrieb:

TechnischerFreak schrieb:

Implizit findet eine Indexprüfung beim Zugriff auf einen Vector statt.

Nein.

Es finden noch viel abenteuerliche Dinge als eine Indexprüfung statt. (Automatische) Speicheranforderung, wenn man außerhalb der Vectorgrenzen zugreifen möchte ist da nur ein Beispiel. Ganz ohne das Zutun und oft auch ohne das Wissen des Programmierers.

Aber jeder kann gerne ein geeignetes kleines Testprogramm, einmal mit dyn. Array- und alternativ mit Vector- Datenbehälter schreiben, in dem 100.000 mal eingefügt und 100.000 mal gelesen wird, und das stoppen. (ohne es jetzt probiert zu haben, aber mit dem Vector dauern diese Operationen dreimal so lange). Etwas Geduld, ...

queer_boy

so ein blödsinn. willste mal eine implementation von operator[] sehen?

reference
vector::operator[](size_type __n)
{ return *(begin() + __n); }

wo ist da auch nur ein check, der die performance beeinflusst? richtig: es gibt keinen.

hustbaer

TechnischerFreak schrieb:

Artchi schrieb:

Lass dir gesagt sein, das ein Vector 100% die gleiche Performance wie ein rohes Array hat. Warum? Weil das der ISO-C++-Standard vorgibt. Lediglich eine nicht ISO-konforme Implementierung könnte hier langsamer sein. Aber das ist in der heutigen Zeit eher unwahrscheinlich, da ich mal davon ausgehe, das ihr eine vernünftige C++-Compiler-Suite einsetzt.

Ziemlicher Unfug wird hier behauptet. Was der ISO-C++-Standard vorgibt und was technisch möglich ist sind zwei verschiedene paar Schuhe. Die Indexprüfung entfällt beim Zugriff auf ein rohes Array. Implizit findet eine Indexprüfung beim Zugriff auf einen Vector statt.

Nein

Letzere Operation kostet Zeit. Es ist deshalb weder technisch und obendrein aus rein logischen Gründen unmöglich, dass man auf Vektordaten 100% genau so schnell zugreifen kann wie auf Arraydaten.
Es sei denn jemandem fällt eine Möglichkeit ein, mit der die implizite Indexprüfung NULL Taktzyklen dauert. Technisch unmöglich, und deshalb ist es unerheblich, was der ISO-C++-Standard in dieser Sache (angeblich) vorgibt.
Die Herren, die den ISO-C++-Standard erfunden haben, haben aber zweifellos genügend Ahnung von technischer Informatik.

Nein

Folgerung: Es gibt eine solche Vorschrift im ISO-C++ Standard deshalb nicht. Es sei denn Phantasten wie Artchie hätten in dem Gremium das Sagen.

Koffer

LordJaxom

techfreak schrieb:

Es finden noch viel abenteuerliche Dinge als eine Indexprüfung statt. (Automatische) Speicheranforderung, wenn man außerhalb der Vectorgrenzen zugreifen möchte ist da nur ein Beispiel. Ganz ohne das Zutun und oft auch ohne das Wissen des Programmierers.

Diese Behauptung ist in der Tat der Brüller des Tages!

Simon2

"TechnischerFreak" und "techfreak" sind ziemlich gute Beispiele für "Andere" im Sinne von:

Simon2 schrieb:

...Immerhin hat er [VerbalKint AnmdVerf] ganz klar hervorgehoben, dass es sich um eine Vermutung und eine Meinung (eines Kollegen) handelt. Das ist schon deutlich kritischer als einige Andere hier (Euch natürlich alle ausgenommen) auftreten und das alles als "FAKT" ( ) darstellen...

Also von mir nochmal ein explizites Lob an VerbalKint, der weiß und klar äußert, wo er Ahnung hat und wo nicht.

Gruß,

Simon2.

tntnet

techfreak schrieb:

LordJaxom schrieb:

TechnischerFreak schrieb:

Implizit findet eine Indexprüfung beim Zugriff auf einen Vector statt.

Nein.

Es finden noch viel abenteuerliche Dinge als eine Indexprüfung statt. (Automatische) Speicheranforderung, wenn man außerhalb der Vectorgrenzen zugreifen möchte ist da nur ein Beispiel. Ganz ohne das Zutun und oft auch ohne das Wissen des Programmierers.

Aber jeder kann gerne ein geeignetes kleines Testprogramm, einmal mit dyn. Array- und alternativ mit Vector- Datenbehälter schreiben, in dem 100.000 mal eingefügt und 100.000 mal gelesen wird, und das stoppen. (ohne es jetzt probiert zu haben, aber mit dem Vector dauern diese Operationen dreimal so lange). Etwas Geduld, ...

Du solltest mal 2 Dinge tun: zum einen den Standard lesen und zum anderen genau das, was Du vorschlägst.

Der opertor[] von std::vector macht keine Indexprüfung und vergrössert auch nicht automatisch den Speicher. Das macht die std::map. Das hast Du vielleicht verwechselt.

Der vollständigkeit halber habe ich 2 kleine Testprogramme geschrieben. Das Ergebnis ist, daß der std::vector genausso schnell ist, wie das array. Hier meine Programme (und immer schön mit -O2 übersetzen, wenn Geschwindigkeit getestet wird):

#include <iostream>

const unsigned N = 1000000;

int main(int argc, char* argv[])
{
  try
  {
    int a[N];
    for (unsigned n = 0; n < 10; ++n)
    {
      for (int i = 0; i < N; ++i)
        a[i] = i;
      int sum = 0;
      for (int i = 0; i < N; ++i)
        sum += a[i];
      std::cout << sum << std::endl;
    }
  }
  catch (const std::exception& e)
  {
    std::cerr << e.what() << std::endl;
  }
}

#include <iostream>
#include <vector>

const unsigned N = 1000000;

int main(int argc, char* argv[])
{
  try
  {
    std::vector<int> a(N);
    for (unsigned n = 0; n < 10; ++n)
    {
      for (int i = 0; i < N; ++i)
        a[i] = i;
      int sum = 0;
      for (int i = 0; i < N; ++i)
        sum += a[i];
      std::cout << sum << std::endl;
    }
  }
  catch (const std::exception& e)
  {
    std::cerr << e.what() << std::endl;
  }
}

PS: man kann es natürlich auch so ausdrücken, wie LordJaxom

LordJaxom

Nochmal zu tntnet's Testprogrammen:

Mit dem GCC 4.1 (-O3) auf Linux kann ich seine Beobachtung bestätigen. Da sind die beiden Testprogramme aber auf die Nanosekunde gleich schnell (über Durchschnitt natürlich).

Mit dem MSVC++ 8.0 (Release) ist die Vector-Implementierung im Schnitt 15% langsamer als die Array-Implementierung. Von Faktor zwei oder gar drei ist hier jedoch überhaupt nichts zu sehen.

David_pb

Das is doch mal super cool!

techfreak, TechnischerFreak: Ha(s|b)t du/ihr schonmal die fixe Idee gehabt erstmal eure Behauptung auf Korrektheit zu überprüfen bevor ihr sie so überaus überzeugt verkündet und andere als "Phantasten" hinstellt?

Artchi

LordJaxom schrieb:

Mit dem MSVC++ 8.0 (Release) ist die Vector-Implementierung im Schnitt 15% langsamer als die Array-Implementierung. Von Faktor zwei oder gar drei ist hier jedoch überhaupt nichts zu sehen.

Ich habe leider hier im Büro keinen MSVC, werde es erst heute abend zu Hause ausprobieren können. Aber hast du auch _SECURE_SCL auf 0 gesetzt? Da standardmäßig _SECURE_SCL=1 ist und somit ALLES indexgeprüft, selbst die Iteratoren. Und das ist nicht ISO-konform. Bin mir sicher, das dann auch der MSVC++ 8.0 in dem Test 0% Unterschied sein wird.

http://msdn2.microsoft.com/en-us/library/aa985965.aspx

_SECURE_SCL=1 ist von MS aber gut gemeint. Muß man denen ja lassen.