Boost.Intrusive

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

[KaJenDro]

Danke krümelkacker!!!

[tarmin]

Eine schöne Einführung und Erklärung von Intrusiven Datenstrukturen mit Erklärungen, warum das so gut ist findet sich bei www.codefarms.com (möglicherweise der Erfinder) hier:
http://www.codefarms.com/publications/intrusiv/Intrusive.pdf

Gruß, Stephan.