Boost.Intrusive

[Boost Newbie]

Hallo,

mal eine ganz allgemeine Frage.
Bisher habe ich primär mit der STL programmiert.
In der Boost.Intrusive befinden sich zahlreiche Container mit Spezifikation
des darunterliegenden Algorithmus.

In welchem Fall zieht ihr die STL und wann die Boost Library vor?
Welche Conteiner in Boost.Intrusive haltet ihr für besonders empfehlenswert,
welche eher nicht?

Danke,
Mark

[hustbaer]

Intrusive Collections sind hauptsächlich dann interessant, wenn es auf das letzte Bisschen Performance ankommt.
Speziell also bei Low-Level Dingen die - abgesehen von Collection-Code - sehr schnell arbeiten.

Beispiel: eine FIFO Queue oder Priority-Queue die Zeiger auf irgendwelche Dinge speichert. Etwas konkreter: vielleicht eine Queue für einen Thread-Pool Job-Scheduler der darauf optimiert ist sehr "kleine" Jobs zu verteilen. Oder ein MRU Cache der "einfache" Keys verwendet (z.B. Integers).

p.S.: am interessantesten ist vermutlich list. Danach die diversen Bäumchen. Welcher der Bäume hängt stark von der Verwendung ab.

[Boost Newbie]

Danke für deine Antwort hustbaer!

hustbaer schrieb:

p.S.: am interessantesten ist vermutlich list.

Das wundert mich etwas...
Denn strukturell kann ich mir keine so großen Unterschiede zwischen
list und der STL list vorstellen.
Was ist denn da der Unterschied?
Da du von Performance redest, vermute ich, dass die Anzahl der dynamischen
Speicher-Allokationen gering gehalten wird, indem Speicher
für mehrere Listenelemente gleichzeitig reserviert wird, die in einem
zusammenhängenden Block liegen.
Liege ich da richtig?

Gruß,
Mark

[brotbernd]

Die intrusiven Container sind wie schon gesagt auf Performance ausgelegt. Da man nie "frühzeitig optimiert" beginne ich immer mit der STL. Wenn man dann feststellt, dass eine std::list einen großen Anteil an unangenehmen Wartezeiten hat, kann man sie durch eine intrusive Liste ersetzen.
Etwas anderes sind Container, die tatsächliche Funktionserweiterungen darstellen, wie z.B. der boost multi index container. So etwas mit der STL nachzubauen, wäre viel zu aufwändig, da setzt man direkt auf die fertige Lösung.

[brotbernd]

Boost Newbie schrieb:

Was ist denn da der Unterschied?

Die Speicherverwaltung wird con dir übernommen, du speicherst z.B. alle Elemente in einem vector. Die intrusive list speichert selber goar nix, sie verwaltet nur die Zeiger nach vorne und hinten, die in den Elementen selber gespeichert sind. Da liegt dann auch der große Nachteil, du musst die Datentypen, die du speichern möchtest anpassen.

[krümelkacker]

"Intrusive and non-intrusive containers" sagt doch eigentlich alles.

Ich habe bisher für Boost.Intrusive keine Verwendung gehabt.

Was das Kopieren von Objekten bei STL-Containern angeht, so wird das in C++0x nicht mehr nötig sein. Man kann Objekte direkt in den Containern erzeugen. Beispiel:

class foo
{
public:
  foo(int n, std::string s)
  : cieffs_(n), name_(std::move(s))
  {}
  foo(int n, char const* p)
  : coeffs_(n), name_(p)
  {}
private:
  std::vector<double> coeffs_;
  std::string name_;
};

...

std::list<foo> fl;
fl.emplace_back(256,"yay!");

Der einzige praktische Unterschied zu einer "Intrusive List" ist dann, dass immer noch Speicher für die Elemente von std::list dynamisch reserviert und verwaltet wird, während Du bei einer "Intrusive List" Dich komplett selbst darum kümmern musst (Da werden nur Zeiger umgebogen, sonst nichts, keine Allozierung, keine Freigabe).

[volkard]

krümelkacker schrieb:

Ich habe bisher für Boost.Intrusive keine Verwendung gehabt.

Komisch.

krümelkacker schrieb:

Was das Kopieren von Objekten bei STL-Containern angeht, so wird das in C++0x nicht mehr nötig sein. Man kann Objekte direkt in den Containern erzeugen. Beispiel:

class foo
{
private:
  std::vector<double> coeffs_;
  ...
};

Ja, aber

class foo
{
private:
  std::tr1::array<double,10> coeffs_;
};

!

Und selbst hier ist vector noch ok oder schneller. Aber wenn ich nicht nur so Objekte anlege und lösche, sondern auch von einem Container zum anderen bewege, könnten intrusive Listen fein sein.
shared_ptrs zu verwalten, ist für mich keine naheliegende Alternative. Es wäre nur ein (langsamer) Kunstgriff, während Elemente intrusiver Listen auf natürliche Weise umhängbar sind.

[hustbaer]

Ich hab nen wichtigen Punkt vergessen: no-throw Garantie.

Der einzige praktische Unterschied zu einer "Intrusive List" ist dann, dass immer noch Speicher für die Elemente von std::list dynamisch reserviert und verwaltet wird,

Und das macht nen RIESEN Unterschied wenn die Elemente z.B. gerade mal aus 4-8 Byte bestehen.

[krümelkacker]

volkard schrieb:

...
Ja, aber

class foo
{
private:
  std::tr1::array<double,10> coeffs_;
};

!

Was ist denn damit? Erklär mal...

volkard schrieb:

Und selbst hier ist vector noch ok oder schneller. Aber wenn ich nicht nur so Objekte anlege und lösche, sondern auch von einem Container zum anderen bewege, könnten intrusive Listen fein sein. ... während Elemente intrusiver Listen auf natürliche Weise umhängbar sind.

Das kann ich mit list<>::splice doch auch.

hustbaer schrieb:

Der einzige praktische Unterschied zu einer "Intrusive List" ist dann, dass immer noch Speicher für die Elemente von std::list dynamisch reserviert und verwaltet wird,

Und das macht nen RIESEN Unterschied wenn die Elemente z.B. gerade mal aus 4-8 Byte bestehen.

...kommt drauf an, wie und wo du die Dinger im Falle einer Intrusive List anlegst und was für einen Allocator Du im Falle von std::list verwendest.

[Boost Newbie]

Danke für die zahlreichen Antworten!

Ich lese weiterhin interessiert mit, auch wenn ich mich in die Dsikussion nicht einmischen kann

[volkard]

krümelkacker schrieb:

volkard schrieb:

...
Ja, aber

class foo
{
private:
  std::tr1::array<double,10> coeffs_;
};

!

Was ist denn damit? Erklär mal...

Da wird move stärend langsam.

[volkard]

krümelkacker schrieb:

...kommt drauf an, wie und wo du die Dinger im Falle einer Intrusive List anlegst und was für einen Allocator Du im Falle von std::list verwendest.

Oh, mit rebind war ich nie glücklich.

[krümelkacker]

volkard schrieb:

krümelkacker schrieb:

volkard schrieb:

...
Ja, aber

class foo
{
private:
  std::tr1::array<double,10> coeffs_;
};

!

Was ist denn damit? Erklär mal...

Da wird move stärend langsam.

Ich sehe jetzt hier keinen Zusammenhang. Was hat das denn mit std::list zu tun? Mit list<>::emplace kannst Du so ein Objekt direkt in der Liste erzeugen, ohne dass da etwas kopiert oder "bewegt" werden muss. Und list<>::splice stört das auch nicht, falls ein Typ nur aufwändig kopiert bzw "bewegt" werden kann.

[Shade Of Mine]

Du hast doch bei emplace() eine Allokation.
Die kannst du mit intrusive Listen sparen.

Im Prinzip verwende ich intrusive Container immer dann wenn ich diese Allokationen sparen will.

[krümelkacker]

Shade Of Mine schrieb:

Du hast doch bei emplace() eine Allokation.
Die kannst du mit intrusive Listen sparen.

Irgendwer muss irgendwo die Objekte erzeugen. Ob das jetzt std::list<> über den Allocator macht oder Du selbst macht ja nur dann einen Unterschied, wenn Du nicht extra für jedes Objekt new/malloc verwendest. Wenn Du nicht für jedes Objekt new/malloc verwenden willst, musst Du sie entweder im statischen Speicher anlegen, auf'm Stack (falls dadurch eine ausreichende Lebenszeit garantiert werden kann) oder Speicher für die Objekte in größeren Blöcken dynamisch anfordern. Letzteres ist aber auch das, was ein "small object allocator" macht.

Shade Of Mine schrieb:

Im Prinzip verwende ich intrusive Container immer dann wenn ich diese Allokationen sparen will.

Das sagst Du so, als wären std::list<> und boost::intrusive::list<> austauschbar. Wenn Du Allozierungen sparen willst, wie erzeugst Du dann Deine Objekte und wer "kümmert" sich darum? Bring doch mal ein konkretes Beispiel.

[Difference]

Der Unterschied liegt darin, dass du die Größe der abgeforderten Speicherressourcen
kalkulieren kannst!!!

[hustbaer]

@krümelkacker:
Auch ein wichtiger Punkt ist dass man mit intrusive Containern eine "no throw" Garantie umsetzen kann.

Ein konkretes Beispiel das ich schon erwähnt habe: ein Job-Scheduler.
Sagen wir du möchtest bestimmte Dinge gleichzeitig ausführen lassen, dann aber innerhalb der gleichen Funktion auf deren Abschluss warten.
Einsatzbereiche dafür gibt es genügend, z.B. parallelisierung von Algorithmen.

int DoStuffParallel(..., Scheduler& s) // no-throw
{
    // Wir erzeugen Futures am Stack, die Ausführung übernimmt der Scheduler
    InStackFuture<int> const& f1 = MakeInStackFuture(s, bind(&DoStuffParallel, ..., ref(s)));
    InStackFuture<int> const& f2 = MakeInStackFuture(s, bind(&DoStuffParallel, ..., ref(s)));
    // Wir warten darauf dass beide Futures "fertig" sind
    Wait(f1, f2);
    // Wir kombinieren das Ergebnis und geben es zurück
    return f1.Get() + f2.Get();
}

Sowas schreit geradezu nach einem intrusive Container im Scheduler.
Dadurch wird alles schneller, und anders wäre es kaum möglich zu garantieren dass nirgends Exceptions geworfen werden.

Anderes Beispiel: du willst ein GUI Framework basteln. Oder einen Scene-Graph. Natürlich kann man hier mit normalen Listen/Vektoren arbeiten, nur da jedes Objekt immer nur einen Parent haben darf, kann man genauso gut intrusive Listen verwenden.

emplace() fällt flach, da man die Objekte üblicherweise unabhängig vom Parent/Graphen erzeugen möchte, auch wieder rausnehmen können möchte etc. move() fällt flach, da die Objekte "identity" haben (=die Adresse sollte sich nicht ändern).

[KaJenDro]

krümelkacker schrieb:

class foo
{
public:
  foo(int n, std::string s)
//...
};
std::list<foo> fl;
fl.emplace_back(256,"yay!");

Wie funktioniert sowas denn? wie kann man einer dynamische Anzahl von Parametern
an den Konstruktor weitergeben?
Also wie wird soetwas intern realisiert?
Wie sieht die Funktionssignatur von emplace aus und wie wird
der Konstruktoraufruf durchgeführt?

Gruß,
Karsten

[krümelkacker]

KaJenDro schrieb:

Wie funktioniert sowas denn? wie kann man einer dynamische Anzahl von Parametern
an den Konstruktor weitergeben?
Also wie wird soetwas intern realisiert?

Stichwort: Variadic Templates + Perfect Forwarding (C++0x)

template<class T>
struct list_node
{
  list_node *prev;
  list_node *next;
  T value;

  template<class...Args>
  explicit list_node(Args&&...args)
  : prev(0), next(0),
    value(std::forward<Args>(args)...)
  {}
};

template<class T>
class list
{
public:
  ...

  template<class...Args>
  iterator emplace(iterator it, Args&&...args)
  {
    ...
    list_node<T> p = new list_node<T>(std::forward<Args>(args)...);
    ...
  }

private:
  ...
};

[Shade Of Mine]

krümelkacker schrieb:

Irgendwer muss irgendwo die Objekte erzeugen. Ob das jetzt std::list<> über den Allocator macht oder Du selbst macht ja nur dann einen Unterschied, wenn Du nicht extra für jedes Objekt new/malloc verwendest. Wenn Du nicht für jedes Objekt new/malloc verwenden willst, musst Du sie entweder im statischen Speicher anlegen, auf'm Stack (falls dadurch eine ausreichende Lebenszeit garantiert werden kann) oder Speicher für die Objekte in größeren Blöcken dynamisch anfordern. Letzteres ist aber auch das, was ein "small object allocator" macht.

Bedenke dass du bei jedem new locken musst. Du kannst keine allocatoren in der STL verwenden die nur thread lokal sind, denn dann könntest du ja nicht splicen und das ist wichtiger als alles andere.

deshalb ist der trick einfach ein großes alloc zu machen und so nur einmal zu locken.

natürlich könnte man einen nicht konformen allocator verwenden... dann bleibt immer noch das problem der kopie die man beim einfügen in die liste hat. und kopien können wieder allokieren. also brauchen wir move semantik dafür - nur leider ist move auch nicht immer das was man will (identity problem).

Letztens habe ich intrusive Listen bei caches verwendet. Caches haben eine fixe größe, also ist es einfach das in einem rutsch zu allokieren. und der schöne trick dabei war dann, dass es möglich war zeiger auf die einzelnen cache objekte zu speichern auch wenn die liste durchsortiert wurde (je nachdem ob man lfu oder lru verwenden wollte) da die zeiger ja nie ungültig wurden.

klar, intrusive container sind nichts was man dauernd braucht - aber ab und zu sind sie einfach perfekt.