dynamische Speicherplatzbeschaffung

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.

LordJaxom

Artchi schrieb:

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.

Das stimmt auffallend - #define _SECURE_SCL 0 (#undef _SECURE_SCL funzt komischerweise nicht) an den Anfang der Datei und die Laufzeiten sind wieder identisch.

Artchi

LordJaxom schrieb:

Das stimmt auffallend - #define _SECURE_SCL 0 (#undef _SECURE_SCL funzt komischerweise nicht) an den Anfang der Datei und die Laufzeiten sind wieder identisch.

virtuell Realisticer

Das ist sogar auf Release auf 1? Das ist aber strange, dachte das waere nur
bei Debug der Fall. Naja ein Define macht den Baeren auch nicht dicker.

gruss
v R

Artchi

Naja, das _SECURE_SCL hat mit debug weniger was zu tun. Wurde von MS halt einfach eingeführt, um wirklich produktiven Code sicherer zu machen. Auch die gesamte C-Library ist davon betroffen, wie strcpy usw. Ist eigentlich keine schlechte Aktion von MS, wie ich persönlich finde. Wer es nicht haben will (weil z.B. die ca. 15% stören), kann es aber ohne Probleme abschalten.

tntnet

Meiner Ansicht nach ist die Bereichsüberprüfung durchaus konform mit dem Standard. Der Standard sagt nichts aus, was geschehen soll, wenn ausserhalb des Bereiches zugegriffen wird. Daher ist von Absturz über Exceptions bis Rechner runterfahren alles erlaubt. Es ist einfach undefiniert. Ich finde noch nicht mal etwas über std::vector::at.

Immer wieder kommt hier die Aussage, std::vector::at würde eine Exception werfen und operator[] nicht. Kann jemand mal die Stelle im Standard nennen, wo das so spezifiziert ist?

Auch wird nicht explizit definiert, daß std::vector genauso schnell, wie ein Array sein muß. Es ist allerdings naheliegend, daß eine Implementierung sich so verhält. Ich habe nicht behauptet, daß beide genauso schnell sind, sondern wiederspreche lediglich der Aussge, daß es definitiv nicht so ist.

CStoll

tntnet schrieb:

Meiner Ansicht nach ist die Bereichsüberprüfung durchaus konform mit dem Standard. Der Standard sagt nichts aus, was geschehen soll, wenn ausserhalb des Bereiches zugegriffen wird. Daher ist von Absturz über Exceptions bis Rechner runterfahren alles erlaubt. Es ist einfach undefiniert. Ich finde noch nicht mal etwas über std::vector::at.

Immer wieder kommt hier die Aussage, std::vector::at würde eine Exception werfen und operator[] nicht. Kann jemand mal die Stelle im Standard nennen, wo das so spezifiziert ist?

Den Standard habe ich leider nicht vorliegen, aber laut Jossutis führt vector::at() eine Bereichsüberprüfung durch und wirft bei Fehlern eine out_of_range Exception. Was vector::op[] bei Bereichsüberschreitungen macht, liegt im persönlichen Ermessen des Compilers.

Auch wird nicht explizit definiert, daß std::vector genauso schnell, wie ein Array sein muß. Es ist allerdings naheliegend, daß eine Implementierung sich so verhält. Ich habe nicht behauptet, daß beide genauso schnell sind, sondern wiederspreche lediglich der Aussge, daß es definitiv nicht so ist.

OK, das stimmt. Der ANSI-Standard gibt keine absoluten Geschwindigkeitsvorgaben der Art "Zugriff auf vector-Elemente ist genauso schnell wie Zugriff auf C-Arrays", sondern nur Vorgaben der Größenordnung (z.B. "Zugriff auf vector-Elemente erfolgt in konstanter Zeit (O(1))"). Allerdings kann man aus diesen Anforderungen normalerweise schon herauslesen, was für ein Design das Standard-Kommitee im Auge hatte.

Braunstein

Hallo,

Zum Standard
aus 23.1.1 13

The member function at() provides bounds-checked access to container elements. at() throws out_of_range if n >= a.size().

über op[] habe ich nichts weiter gefunden.

asc

Ich kann hierzu jetzt auch nur das sagen was ich aus einem C++ Buch habe (glaube entweder ein Scott Meyer oder ein Herb Sutter Buch, leider weiß ich grad nicht welches).

Danach muß at eine Bereichsprüfung (mit Exception) machen, [] darf eine machen, muss es aber nicht (Compilerspezifisch).

Wie gesagt ist das jetzt nur die Erinnerung an einen Abschnitt aus einem Buch.

cu André

Artchi

Der Zugriff auf ein Array geschiet in konstanter Zeit, richtig? Und die Vorgabe für den Vector lautet (wie richtig gesagt) "kostante Zeit" und "die Elemenete müssen hintereinander im Speicher liegen" (letzteres ist ab C++2009 eine explizite Vorgabe!). Naja, wie sollte man das ganze sonst implementieren? Natürlich ist die Aussage "so schnell wie ein Array" nicht im Standard definiert, aber seien wir ehrlich: wer würde eine Std-Lib benutzen, die einen Vector implementiert, der zwar konstante Zeiten anbietet aber doppelt so langsam als ein Array ist?

Wegen der Exception:

C++0x Working Draft $23.1.1 schrieb:

13 The member function at() provides bounds-checked access to container elements. at() throws out_of_range if n >= a.size().

Steht aber auch im aktuellen Standard. Und auch im Bjarness Stroustrups Buch. Und kann man auch in jeder C++-Online-Reference nachlesen.

Artchi schrieb:

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!

Woher weisst Du das?

Oder stellst Du nur so eine Behauptung auf? :p

Artchi schrieb:

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