[C++] Die Suche nach einem passenden Sequence-Container

[Lachsen]

Das ist keine Spielerei, sondern eine bewährte Strategie und wird zum Beispiel so in der Referenzbibliothek Loki implementiert.

...

Joa, ok. Wenn es um maximale Performance geht ist im endeffekt alles erlaubt. In so einem Fall muss man sich dennoch recht stark auf die implementieren der Struktur an sich konzentieren, weil man bei solchen Optimierungen doch auch schnell Fehler machen kann. Das ist genauso als ob man std::vector selbst implementiert. Da gibt es genug Kleinigkeiten, die man falsch machen kann. Aus dem Grund finde ich eine einfache Kombination aus Standard Containern die besser Wahl um auf der sicheren Seite zu sein.
Aber ja, "Spielereien" ist der falsche Begriff an dieser Stelle.

Dass du über die Spielobjekte im ersten Vektor iterieren willst, kann ich irgendwie nicht ganz nachvollziehen, da du immer auch über alle nicht belegten Stellen iterieren würdest.

...

Den overhead hast du als trade-off für schnelles einfügen und entfernen von Einträgen. Iterieren musst du auf jedenfall. Hm.. man kann auch über die beschleunigte Struktur iterieren, das stimmt.

Verwende weak references.

...

In C/C++? Soweit ich weiß gibt es dort keine einfache Implementierung dafür. In std sicher nicht, wahrscheinlich in boost. Ich habe weak pointers aber in der Praxis noch nicht erlebt in CPP und das hat wahrscheinlich seinen Grund...

[DFYX]

In C/C++? Soweit ich weiß gibt es dort keine einfache Implementierung dafür. In std sicher nicht, wahrscheinlich in boost. Ich habe weak pointers aber in der Praxis noch nicht erlebt in CPP und das hat wahrscheinlich seinen Grund...

...

In boost und seit C++11 auch in std.

[Kyuu]

Ich habe weak pointers aber in der Praxis noch nicht erlebt in CPP und das hat wahrscheinlich seinen Grund...

...

Ja, den Grund, dass du sie noch nicht in C++ (bewusst) erlebt hast.

Weak references sind sehr wichtig und überall dort wo reference cycles auftreten können, unverzichtbar. Im Prinzip stellen Indizes in deinen ersten Vektor auch (naive) weak references dar.

[Lachsen]

Ja, den Grund, dass du sie noch nicht in C++ (bewusst) erlebt hast.

Weak references sind sehr wichtig und überall dort wo reference cycles auftreten können, unverzichtbar. Im Prinzip stellen Indizes in deinen ersten Vektor auch (naive) weak references dar.

...

Ich habe nochmal nachgeschlagen und der Grund warum bei uns weak pointer noch nicht zum Einsatz kamen ist der, dass sie auf shared_ptr basieren, die wiederum einen overhead gegenüber normalen pointern verursachen, da der object counter dynamisch zusätzlich zum objekt allokiert wird. Wir verwenden hauptsächlich intrusive_ptr und da funktionieren die weak_ptr aus boost und std nicht, wenn ich das richtig verstehe.

Man braucht nicht weak pointer um reference cycles aufzuheben. Raw pointer und etwas vorsicht tun es auch. Ich schätze mal shared und weak ptr sind die sichere Methode, wenn man den Overhead in Kauf nehmen kann.

[Kyuu]

Ich habe nochmal nachgeschlagen und der Grund warum bei uns weak pointer noch nicht zum Einsatz kamen ist der, dass sie auf shared_ptr basieren, die wiederum einen overhead gegenüber normalen pointern verursachen, da der object counter dynamisch zusätzlich zum objekt allokiert wird. Wir verwenden hauptsächlich intrusive_ptr [...]

...

Inwiefern spielt der overhead beim Allozieren des reference counters für euch eine Rolle? Solange ihr nicht in einer kritischen Schleife die Objekte immer wieder erzeugt, ist dieser zusätzliche overhead vernachlässigbar, da mit ihm nur bei der Objekterzeugung zu rechnen ist. Intrusive reference counting aus dem Grund zu wählen, weil es den overhead beim Allozieren des reference counters vermeidet ist fragwürdig, ich hoffe das ist nur deine Interpretation. Intrusive reference counting ist praktisch etwa wenn reference counting über Programm/Bibliothek-Grenzen hinweg funktionieren soll, oder wenn die Objekte in memory pools alloziert werden.

Man braucht nicht weak pointer um reference cycles aufzuheben. Raw pointer und etwas vorsicht tun es auch.

...

Ich kann mir Situationen vorstellen, in denen raw pointer nicht reichen würden.

----------------------

Übrigens fällt mir gerade ein Problem bei deiner Struktur weiter oben ein. Dein Argument war, dass du null zurückgeben kannst, wenn ein Objekt gelöscht wurde. Dem entnehme ich, dass bei dir Situationen eintreten können, in denen Objekte referenziert werden, die bereits gelöscht wurden. Was nun, wenn ein Objekt gelöscht wird und die Stelle im Vektor durch ein neues ersetzt wird, noch bevor der Code, der das gelöschte Objekt referenziert, realisiert, dass das referenzierte Objekt nicht mehr existiert?

[Lachsen]

Inwiefern spielt der overhead beim Allozieren des reference counters für euch eine Rolle? Solange ihr nicht in einer kritischen Schleife die Objekte immer wieder erzeugt, ist dieser zusätzliche overhead vernachlässigbar, da mit ihm nur bei der Objekterzeugung zu rechnen ist. Intrusive reference counting aus dem Grund zu wählen, weil es den overhead beim Allozieren des reference counters vermeidet ist fragwürdig, ich hoffe das ist nur deine Interpretation. Intrusive reference counting ist praktisch etwa wenn reference counting über Programm/Bibliothek-Grenzen hinweg funktionieren soll, oder wenn die Objekte in memory pools alloziert werden.

...

Ich empfinde die Optimierung durch das auslassen von shared_ptr ähnlich fragwürdig was das weg-optimieren des 2. Vektors der auf freie Felder speichert. Allokation ist eine teure operation, das könnte einen Unterschied machen wenn viele Objekte neu erstellt und entfernt werden (bei partikeln etwa?). Dazu kommt auch, dass dein shared_ptr zwei sachen referenziert (counter und pointer) und damit doppelt so groß ist. Wenn du also über einen Array mit shared_pointern itereierst kannst du genauso gut über eine Vektor doppelter größe mit raw-pointer iterieren. (vergleichbar mit dem Overhead, wenn man bei meiner Struktur über 0 pointer iteriert)

Im übrigen ist fast alles was wir hier diskutieren premature optimization. Just sayin'.

Ich kann mir Situationen vorstellen, in denen raw pointer nicht reichen würden.

...

Care to share? Ich kann mir keine solche Situation vorstellen, die man nicht genauso gut mit einer Routine im Destuktor lösen kann.

Übrigens fällt mir gerade ein Problem bei deiner Struktur weiter oben ein. Dein Argument war, dass du null zurückgeben kannst, wenn ein Objekt gelöscht wurde. Dem entnehme ich, dass bei dir Situationen eintreten können, in denen Objekte referenziert werden, die bereits gelöscht wurden. Was nun, wenn ein Objekt gelöscht wird und die Stelle im Vektor durch ein neues ersetzt wird, noch bevor der Code, der das gelöschte Objekt referenziert, realisiert, dass das referenzierte Objekt nicht mehr existiert?

...

Da hast du recht. In dem Fall verhält sich das System fehlerhaft.
Also ich vermute mal das Argument mit sicheren zugriff per id zieht nicht wirklich.
Es ist also lediglich eine Struktur in der man schnell einfügen und entfernen kann, direkten zugriff hat und bei der auch iteration funktioniert. (mit einem gewissen overhead)
Naja, es funktioniert für meine Anwendungen gut genug.

[Kyuu]

Ich empfinde die Optimierung durch das auslassen von shared_ptr ähnlich fragwürdig was das weg-optimieren des 2. Vektors der auf freie Felder speichert. Allokation ist eine teure operation, das könnte einen Unterschied machen wenn viele Objekte neu erstellt und entfernt werden (bei partikeln etwa?).

...

Könnte, würde, müsste... Teste. Und wenn es sich herausstellt, dass die Allokation der Flaschenhals ist, würden sich memory pools als sinnvolle Lösung anbieten (auch für den reference counter).

Gerade bei Partikeln (und ähnlich kleinen Objekten) bieten sich memory pools an und um ehrlich zu sein, habe ich noch nie gesehen, dass Partikel einzeln auf dem Heap alloziert werden (obwohl es durchaus gute Gründe geben könnte, dies zu tun).

Aber ich gebe zu, mein Vorschlag den zweiten Vektor wegzuoptimieren ist nicht gerade einleuchtend. Aber um einen Performance-/Speichervorteil ging es mir dabei weniger, das hast du dann selbst hineininterpretiert. Ich habe gesehen, dass deine Sruktur Ähnlichkeiten mit einem memory pool hat und habe einen Ansatz vorgeschlagen, wie man den zweiten Vektor eliminieren könnte. Ob es in deinem Anwendungsfall sinnvoll wäre, musst du dann selbst entscheiden.

Dazu kommt auch, dass dein shared_ptr zwei sachen referenziert (counter und pointer) und damit doppelt so groß ist. Wenn du also über einen Array mit shared_pointern itereierst kannst du genauso gut über eine Vektor doppelter größe mit raw-pointer iterieren. (vergleichbar mit dem Overhead, wenn man bei meiner Struktur über 0 pointer iteriert)

...

Den Gedankengang kann nicht nicht ganz nachvollziehen. Willst du damit sagen, dass die Zeit, um über 50 acht Byte große Elemente zu iterieren, dieselbe ist, wie über 100 vier Byte große Elemente? Das Einzige, was hier wahrscheinlich gleich wäre, wäre das Cacheverhalten.

Übrigens könnte man, statt nur den reference counter zu allozieren, eine Struktur allozieren, die sowohl den reference counter, als auch den Objektzeiger enthält, womit der smart pointer nur noch die Größe eines Zeigers hätte. Ob das sinnvoll wäre, muss man wieder im Anwendungsfall genauer betrachten.

Im übrigen ist fast alles was wir hier diskutieren premature optimization. Just sayin'.

...

I beg to differ. (Hey, ich kann auch ein bisschen Englisch. ) Ich halte es nicht für premature optimization, sich ein paar Gedanken über die Implementierungsmöglichkeiten zu machen. Eine naive Implementierung könnte sich im Nachhinein als mindestens genauso problematisch erweisen, als eine mikrooptimierte, verworrene Implementierung mit einem effektiven Vorteil von 0.0001%. Dass die Leser hier sich ihre eigenen Gedanken machen und vor dem Implementieren abwägen, soviel möchte ich ihnen zutrauen.

Care to share? Ich kann mir keine solche Situation vorstellen, die man nicht genauso gut mit einer Routine im Destuktor lösen kann.

...

Zwei Objekte, A und B, beide reference counted und beide besitzen auf das jeweils andere Objekt eine Referenz. Um den reference cycle aufzuheben, machen wir As Zeiger auf B zu einem raw pointer. Wenn nun alle Referenzen auf B erlöschen, wird B gelöscht und As raw pointer wird zu einem dangling pointer.

Und As Zeiger auf B aus Bs Destruktor zu manipulieren werde ich nicht akzeptieren.