new und delete-Operatoren

SeppJ

vectorsucks schrieb:

SeppJ schrieb:

Und, war es schwierig, einen Benchmark so zu manipulieren, dass er genau den einen kleinen Nachteil von vector gegenüber deque übermäßig hervorhebt, ohne dass die Nachteile der deque zum Vorschein kommen?

Wovon redest du?
Die Allokationszeit ist in diesem Benchmark völlig nebensächlich.

Die ist es, die du hauptsächlich misst. Mach mal richtig Arbeit mit den Objekten:

const int howmany  = 100*1000;
  const int howoften = 100*1000;

Zack! Schon zieht der vector gegenüber new/delete davon. Bloß die deque hält immer noch mit (oder führt sogar!), da sie hier in diesem Benchmark keinen Zugriffsnachteil gegenüber dem vector hat (da alles über Zeiger geht), aber dafür schneller allokiert. Ich revidiere leicht meine Empfehlung:

deque<derived_1> derived_1s;
deque<derived_2> derived_2s;

// Erzeuge super-schnell so viele derived_1 und 2 wie nötig

vector<base*> foo; // Enthält passende Zeiger auf Elemente in derived_1s und derived_2s und hat vectorschnellen Zugriff auf ziemlich lokalisierte Objekte.

Falls man jedoch eher selten Allokationen hat, ist die deque hier aber eher als Mikoroptimierung für Klugscheißer zu sehen. Immerhin hat sie aber keine Nachteile und sollte daher genommen werden.

SeppJ schrieb:

vector<base*> foo; // Enthält passende Zeiger auf Elemente in derived_1s und derived_2s und hat vectorschnellen Zugriff auf ziemlich lokalisierte Objekte.[/code]Falls man jedoch eher selten Allokationen hat, ist die deque hier aber eher als Mikoroptimierung für Klugscheißer zu sehen. Immerhin hat sie aber keine Nachteile und sollte daher genommen werden.

Du hast es immer noch nicht ganz kapiert.

Hier der gleiche Benchmark, bei dem ausschliesslich die Zugriffszeiten gemessen wurden:
deque: 3.48s
vector: 6.58s
new/delete: 4.98s

SeppJ

Erstaunlich. Bloß, dass bei mir was komplett anderes rauskommt. Letzteres finde ich wiederum nicht erstaunlich, sondern ist genau das was ich bei einem Beitrag von dir erwartet hätte.

SeppJ schrieb:

Erstaunlich. Bloß, dass bei mir was komplett anderes rauskommt. Letzteres finde ich wiederum nicht erstaunlich, sondern ist genau das was ich bei einem Beitrag von dir erwartet hätte.

Was soll das heissen?

-Ofast -march=native

int howmany, howoften; cin >> howmany >> howoften;

Eingabe "20000 20000"
sowie

auto start = clock();

  int sum = 0;
  for (int i=0; i<howoften; ++i) {
    for (base* b : foo) {
      sum += b->foo();
    }
  }
  auto end = clock();
  std::cout << setprecision(10) << static_cast<double>(end - start) / CLOCKS_PER_SEC << "s"\n";

Das kann nicht gefälscht sein.

krümelkacker

vectorsucks schrieb:

Hier der gleiche Benchmark, bei dem ausschliesslich die Zugriffszeiten gemessen wurden:
deque: 3.48s
vector: 6.58s
new/delete: 4.98s

Interessante Ergebnisse. Aber repräsentativ? Ich denke eher nicht. Ich denke, es ist eher zu künstlich (das Programm tut nichts anderes) und speziell (Allozierungsreihenfolge).

Im Falle von new/delete hast du wahrscheinlich das Glück, dass die allozierten Objekte alle in mehr oder weniger in derselben Reihenfolge hintereinander im Speicher stehen, wie du sie hinterher besuchst. Das verwundert nicht besonders, wenn das Program sonst nichts anderes macht. Lass es länger laufen, hier und da mal was löschen, hier und da mal wieder etwas hinzufügen, noch anderen Kram den Heap benutzen lassen und irgendwann stehen die Objekte relativ willkürlich im Speicher und auf einmal wird's wieder ganz langsam, weil der Cache das Zugriffsmuster nicht mehr erkennen kann und dementsprechend keinen vernünftigen Prefetch machen kann.

Ist sicher mal interessant, sich anzuschauen, wie die Objekte im Speicher stehen; denn ich denke, dass das hauptausschlaggebend bzgl Laufzeit ist.

Das könnte hier z.B. so aussehen:

dx = das x-te derived1-objekt
ex = das x-te derived2-objekt

deque     : d0 d1 d2 d3   e0 e1 e2 e3   d4 d5 d6 d7   e4 e5 e6 e7   d8 d9 ...

vector    : d0 d1 d2 d3 d4 d5 d6 d7 d8 d9 ...   e0 e1 e2 e3 e4 e5 e6 e7 e8 ...

new/delete: d0  e0  d1  e1  d2  e2  d3  e3  d4  e4  d5  e5  d6  e6  d7  e7 ...

Also: bei den deques wechsseln sich die Blöcke von derived1 und derived2 Objekten ab. Warum? Weil der Heap komplett frei war, die Heap-Zuteilung hintereinander liegende Blöcke rausgegeben hat und dequeue so ähnlich wie vector<vector<>> funzt, wobei die inneren Vektoren eine feste Blockgröße haben und vielleicht noch verlinkt sind, damit das Iterieren schneller geht.

Jetzt könnte man noch vector<pair<derived_1,derived_2>> testen.

SeppJ

vectorsucks schrieb:

Das kann nicht gefälscht sein.

Was glaubst du, habe ich wohl gemacht? Nimm's nicht persönlich, aber ich vertraue meinen Ergebnissen mehr als deinen. Doch, nimm es persönlich. Denn genau das ist es und ich traue dir bei keiner einzigen deiner Zahlen.

SeppJ schrieb:

vectorsucks schrieb:

Das kann nicht gefälscht sein.

Was glaubst du, habe ich wohl gemacht?

Einfach mal angenommen, meine Ergebnisse wären falsch und geschrieben, sie würden nicht stimmen.
Es kann Unterschiede geben, wenn deine libc ein schrottiges malloc verwendet. Aber die "ungefälschten Zeiten" von deinem System posten, das erwarte ich von dir schon.

SeppJ

vectorsucks schrieb:

Es kann Unterschiede geben, wenn deine libc ein schrottiges malloc verwendet.

So? Erklär mal! Meinst du, krümelkacker hätte 100% Recht (hat er auch!) und dein Benchmark wäre manipuliert?

Trotzdem geht der vector/deque ab:
100,000 Elemente, 10,000 Mal iteriert:
new: 14 Sekunden
deque: 9.1 Sekunden
vector: 11 Sekunden

Wieso 100,000 Elemente? Damit nicht einfach alles im L1-Cache des Prozessors liegt! Du weißt schon^*: So wie bei einem normalen Programm. Sollen wir auch noch probieren, was bei > 1,000,000 Elementen passiert (d.h. > L2-Cache)? Also dann, wenn es wirklich auf Performance ankommt, weil es nicht mehr um Sekundenbruchteile, sondern um Stunden geht?

^*: Oder wohl eher nicht.

krümelkacker

Ich habe mal ein bisschen das Speicherlayout getestet

Windows7 64 Bit
g++ (tdm64-1) 4.6.1

sizeof(derived_1) -> 16
sizeof(derived_2) -> 16

Fall vector<unique_ptr<base>>, jedes Objekt einzeln per new angelegt:
Aufeinanderfolgend besuchte Objekte liegen hier meist nur 32 Byte auseinander (mit Ausreißern). die 16-Byte-Lücken gehen sicherlich für die Heap-Verwaltung drauf.

Fall deque<derived_1>, deque<derived_2>, vector<base*>:
Die d1-Objekte liegen meist 16 Byte voneinander entfernt, mit Ausreißern. Ebenso die d2-Objekte. Allerdings springen wir natürlich zwischen den beiden deques hin und her beim Durchlaufen, da ja abwechselnd ein derived_1-Objekt und ein derived_2-Objekt angesprochen wird (genauso wie beim vector-Fall). Kleine Sprünge in den Adressen deuten darauf hin, dass die von mir verwendete deque jeweils 32 Elemente in einem Block zusammenfasst. Das sind dann also 512-Byte-Blöcke getrennt von 16 Byte Heap-verwaltungspoverhead.

Im new/delete Fall habe ich hier also einen Speicheroberhead von 100%. Upps.

Das Speichern von Adressen von Vector/Deque-Elementen ist aber mit Vorsicht zu genießen. Die können ja ungültig werden. vector<unique_ptr<base>> ist da natürlich einfacher zu händeln gerade wenn man zwischendurch auch mal etwas löschen will. Wenn man allerdings immer nur Objekte hinzufügt und keine löschen muss (außer alle am Schluss), kann man deque doch verwenden; denn auch nach einem push_back oder emplace_back bleiben alle Referenzen noch gültig (diese Garantie gilt nicht für Iteratoren). Ich denke, bevor man sich selbst um so etwas wie Pool-Allocators und Free-Lists rumschlägt, sollte man doch erst mal bei make_unique bleiben.

PHBU

Hallo nochmal!

Mensch, das wird ja hier eine richtige Großdiskussion .

Warum funktioniert folgender Code?

char * x;
	x = new CHR8 [100];
	x [103] = 'H';
	cout << x [103];
	delete [] x;

Was ich tun möchte:

1.: Variablen auf dem Heap ablegen (nicht auf Stack) (soll nur ein Versuch sein)
2.: Ich möchte, das man nicht mehr Daten dem char-Array zuweisen kann, als man zugewiesen hat (im Code kann ich dennoch das Array mit dem Wert 103 definieren, obwohl das Array nur 100 groß ist ).

Danke im Voraus!

MfG

Seikuassi

SeppJ

Undefiniertes Verhalten ist undefiniert. Unter anderem darf es auch unerwartet funktionieren.

Wenn du so etwas nicht möchtest, zitiere ich noch einmal die allererste Antwort aus dem Thread:

Nathan schrieb:

Seikuassi schrieb:

ich frage mich, in welchen Fällen man den new- bzw. delete-Operator braucht?

nie (na gut, fast nie).
Die Operatoren werden von der Standardbibliothek (indirekt) verwendet um dynamisch wachsende Arrays (std::vector), verkettete Listen (std::list) und alle anderen Container zu realisieren, aber als User sollte man mit denen nie (na gut, selten) in Kontakt kommen.

Die Container der Standardbibliothek könnten das.

PHBU

Hallo nochmal,

Die Container der Standardbibliothek könnten das.

Stimmt. Denn ich habe gerade 8589934591 Byte Speicher auf meinem Laptop mit gerade mal 2 GB RAM angefordert -> und ist dann abgestürzt .

Frage: Wie kann ich ein String-Literal an ein deque bestehend aus mehreren chars (ohne Pointer) übergeben?

Danke im Voraus!

MfG

Seikuassi

Nathan

Es gibt dafür std::string.

SeppJ

Seikuassi schrieb:

Frage: Wie kann ich ein String-Literal an ein deque bestehend aus mehreren chars (ohne Pointer) übergeben?

Wieso ohne Pointer? Dafür sind Pointer toll geeignet!

const char *foo = "Hallo Welt";

deque<char> bar(foo, foo + 10);

Ist das eine Art von Programmiermasochismus, zwanghaft die passendsten Mittel nicht zu benutzen?