new und delete-Operatoren

[out]

Du brauchst new, wenn du ein Objekt über den Scope hinaus am Leben erhalten musst, aus welchen Gründen auch immer, z.B. weil du das Objekt nicht kopieren darfst, und deswegen Zeiger hin und her reichst.

[dot]

Die Frage ist genau so sinnvoll wie "wann muss man den + Operator verwenden?". Wenn du ein Beispiel zum Üben brauchst: Schreib z.B. ein Programm in das der Benutzer so lange verschiedene Wörter eingeben kann, bis er einen . eingibt und danach dein Programm fragen kann, ob ein bestimmtes Wort unter den zuvor eingegebenen Wörter vorkommt oder nicht.

[cooky451]

Ist deine Frage wozu man Freispeicher allgmein braucht oder warum man new/delete malloc/free gegenüber bevorzugen sollte?

[Nathan]

SeppJ schrieb:

Willst du denn unbedingt alle polymorphen Objekte einzeln auf den Heap legen?

Ich sag nicht, dass das nicht auch mal richtig sein kann, aber es gibt auch andere Methoden. Du brauchst schließlich nur Zeiger/Referenzen, was nicht zwangsläufig new/delete bedeutet.

Ja, klar.
Aber wenn man die Anzahl vorher nicht kennt, muss man es.
Und das meinte ich auch.

[Stechus Kaktus]

out schrieb:

Jetzt gibt es doch wirklich keine Fällt mehr, wo du new brauchst [...]

Mir fällt jetzt auch kein Beispiel ein, wann ich zuletzt eine pure new-delete-Kombination verwandt habe. Es ist der Vollständigkeit willen aufgeführt. Defensive Consulting sozusagen.

Ave

[SeppJ]

Nathan schrieb:

Ja, klar.
Aber wenn man die Anzahl vorher nicht kennt, muss man es.
Und das meinte ich auch.

vector und andere Container?

vector<derived_1> derived_1s;
vector<derived_2> derived_2s;

// Erzeuge so viele derived_1 und 2 wie nötig

vector<base*> foo; // Enthält passende Zeiger auf Elemente in derived_1s und derived_2s

[CreativeLabs]

SeppJ schrieb:

Nathan schrieb:

Ja, klar.
Aber wenn man die Anzahl vorher nicht kennt, muss man es.
Und das meinte ich auch.

vector und andere Container?

vector<derived_1> derived_1s;
vector<derived_2> derived_2s;

// Erzeuge so viele derived_1 und 2 wie nötig

vector<base*> foo; // Enthält passende Zeiger auf Elemente in derived_1s und derived_2s

Also foo soll Zeiger in dieser Form enthalten?

foo.push_back(&derived_1s[x]);

Ja schön und gut, nur können die ungültig werden, wenn man derived_1s weitere Elemente hinzufügt und der vector umkopieren muss.

Ich finde, die sich hier breitmachende Angst vor jedem new, nimmt Bizarre Formen an. V.a. in Kombination mit Smart-Pointern kann ich nicht ganz nachvollziehen, warum man krampfhaft jedes new vermeiden will.

[SeppJ]

CreativeLabs schrieb:

Ja schön und gut, nur können die ungültig werden, wenn man derived_1s weitere Elemente hinzufügt und der vector umkopieren muss.

1. Dann nimm eben nicht vector
2. Du weißt als Programmierer genau, wann die Elemente ungültig werden. vector ist in dieser Hinsicht absolut deterministisch.
3. Dazu sind komplexe Datentypen da: Fass alles zusammen. Einfügen mit Reallokation führt zu Aktualisierung der Liste.

Ich finde, die sich hier breitmachende Angst vor jedem new, nimmt Bizarre Formen an. V.a. in Kombination mit Smart-Pointern kann ich nicht ganz nachvollziehen, warum man krampfhaft jedes new vermeiden will.

Dann hast du meine Botschaft nicht verstanden. Es ging mir nicht um new/delete, sondern darum, Nathan ein paar neue Denkanstöße zu geben. Denn: Die Elemente alle gemeinsam im Speicher zu halten ist effizienter.

Indirekt ist das natürlich auch ein Punkt gegen new/delete für Einzelobjekte, da es eben diese Art von Speicherzerhackstückelung fördert. Das gilt aber auch für einige der Container wie z.B. list, die ansonsten kaum Vorteile bieten, die diesen Nachteil zu rechtfertigen.

[Nathan]

SeppJ schrieb:

Dann hast du meine Botschaft nicht verstanden. Es ging mir nicht um new/delete, sondern darum, Nathan ein paar neue Denkanstöße zu geben. Denn: Die Elemente alle gemeinsam im Speicher zu halten ist effizienter.

Und das ist dir gelungen.
Ich hatte so etwas gar nicht auf dem Plan, schon allein, weil mir das zu viel Arbeit wäre.
Da hätte ich doch tatsächlich so etwas in der Art in einen Allokator gepackt...

[SeppJ]

Nathan schrieb:

Ich hatte so etwas gar nicht auf dem Plan, schon allein, weil mir das zu viel Arbeit wäre.
Da hätte ich doch tatsächlich so etwas in der Art in einen Allokator gepackt...

Kommt ungefähr auf gleiche raus, aber ich fände meine Methode weniger Arbeit.

[vectorsucks]

SeppJ schrieb:

Kommt ungefähr auf gleiche raus, aber ich fände meine Methode weniger Arbeit.

Deine Methode ist sogar kontraproduktiv.

vector<unique_ptr<base> > foo;

for (int i=0; i<howmany; ++i) {
    foo.push_back(unique_ptr<base>(new derived_1()));
    foo.push_back(unique_ptr<base>(new derived_2()));
}

int sum = 0;
for (int i=0; i<howoften; ++i) {
    for (auto& b : foo) {
        sum += b->foo();
  }
}

http://ideone.com/SV16dd
0.87s

vector<derived_1> derived_1s;
vector<derived_2> derived_2s;

for (int i=0; i<howmany; ++i)
    derived_1s.push_back(derived_1());
for (int i=0; i<howmany; ++i)
    derived_2s.push_back(derived_2());

vector<base*> foo;

for (int i=0; i<howmany; ++i) {
    foo.push_back(&derived_1s[i]);
    foo.push_back(&derived_2s[i]);
}

int sum = 0;
for (int i=0; i<howoften; ++i) {
    for (base* b : foo) {
        sum += b->foo();
  }
}

http://ideone.com/s48f7X
1.60s

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

for (int i=0; i<howmany; ++i)
    derived_1s.push_back(derived_1());
for (int i=0; i<howmany; ++i)
    derived_2s.push_back(derived_2());

vector<base*> foo;

for (int i=0; i<howmany; ++i) {
    foo.push_back(&derived_1s[i]);
    foo.push_back(&derived_2s[i]);
}

int sum = 0;
for (int i=0; i<howoften; ++i) {
    for (base* b : foo) {
        sum += b->foo();
  }
}

http://ideone.com/Tr7dlD
0.83s

[SeppJ]

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?

[vectorsucks]

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. Es geht um deinen "Trick", die Sachen "kompakt" zu speichern.

[Nathan]

SeppJ schrieb:

Nathan schrieb:

Ich hatte so etwas gar nicht auf dem Plan, schon allein, weil mir das zu viel Arbeit wäre.
Da hätte ich doch tatsächlich so etwas in der Art in einen Allokator gepackt...

Kommt ungefähr auf gleiche raus, aber ich fände meine Methode weniger Arbeit.

Naja, ich finde einmal Arbeit und initialisieren und dann keinen Mehraufwand, vs Mehraufwand beim Einfügen (jetzt rein codetechnisch) da das erste besser. (Toller Satz)

[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.

[vectorsucks]

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.

[vectorsucks]

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.