3. Reference-Counted Array variabler Länge mit minimalem Overhead (shared_ptr, o.ä.)

Reference-Counted Array variabler Länge mit minimalem Overhead (shared_ptr, o.ä.)

  • F

    Hallo zusammen!

    ich suche nach weiteren Lösungsansätzen für ein Problem bei dem ich vermeiden möchte, die Lösung "zu Fuß" zu implementieren und bei dem mir gerade die Ideen ausgehen.

    Vielleicht fällt euch ja etwas ein?

    Problem:

    Ich möchte ein Array oder eine vergleichbare Datenstruktur variabler Länge möglichst effizient mittels Reference Counting verwalten.
    Die Länge der Arrays ist erst zur Laufzeit bekannt, und soll auch veränderbar sein. Im Prinzip suche ich so etwas:

    T* a = new T[N];
...
delete [] a;
a = new T[M];

    ... nur dass das Array eben über einen shared_ptr oder etwas Vergleichbarem verwaltet wird.
    Ferner gibt es noch folgende Anforderung, welche viele naheliegende Lösungen nicht praktikabel macht:

    Minimaler Overhead: Mit Ausnahme der atomaren Operationen und den zusätzlichen Speicher für das Reference Counting soll die Datenstruktur die selben Ausführungs- und Speicherzugriffscharakteristiken haben wie o.g. new / delete -Konstrukt haben.
    Insbesondere: Keine zusätzlichen Allokationen und Cache-freudlicher Zugriff auf die Elemente (d.h. keine load-Operationen auf Speicherbereiche in deren Nachbarschaft keine Array-Elemente liegen).

    Bisherige Ansätze:

    1.

    std::shared_ptr<std::vector<T>>

    Leider ungeeignet, da der Zugriff auf die Elemente eine zusätzliche Dereferenzierung erfordert.
    std::shared_ptr und std::vector sind meines wissens so oder ähnlich implementiert:

    class shared_ptr
{
   ...
   T* object;
   ...
}

class vector
{
   ...
   T* elements;
   ...
}

    d.h. um auf ein Element von vector zuzugreifen muss zunächst object und dann elements dereferenziert werden, es wird also oft eine Cache-Line geladen um lediglich an den elements -Pointer zu gelangen (und eventuell die Länge des Vektors), ohne dass ich beim Zugriff auf die eigentlichen Elemente davon weiter profitieren könnte. Zugegeben, beim Durchlaufen besonders langer Arrays wird sich das zusätzliche Dereferenzieren wahrscheinlich amortisieren, ich suche aber nach einer Lösung die diesen Overhead dennoch vermeidet.

    2.

    std::shared_ptr<std::array<T, N>>

    Ungeeignet, da die Länge des Arrays während des Kompilierens bekannt sein muss und diese Teil des Typs ist (soll zugewiesen werden können, auch wenn linke und rechte Seite der Zuweisung unterschiedliche Array-Längen haben)

    3. std::shared_ptr<T> mit Custom-Deleter:

    std::shared_ptr<T> a(new T[N], std::default_delete<T[]>());

    ... sieht nach einer guten Lösung aus, benötigt aber 2 Allokationen ( new T[N] und Kontrollblock von shared_ptr , Exception-safety erstmal außen vor) und der Kontrollblock ist im Speicher nicht mit den Elementen den benachbart.
    std::make_shared wäre die ideale Lösung, unterstützt allerdings leider nicht die Konstruktion von Arrays in der o.g. Form 😞

    Falls jemand mit so etwas schonmal Erfahrungen gesammelt hat, und einen guten Lösungsansatz hat, wäre ich dankbar. Das per Hand zu implementieren ist ein ziemlicher Schlepp den ich gerne vermeiden würde 😃

    Gruss,
    Finnegan

    0
  • N

    Evtl. könntest du mit allocate_shared tricksen.

    0
  • ?

    Was ist mit http://www.boost.org/doc/libs/1_57_0/libs/smart_ptr/intrusive_ptr.html ?

    0

  • @Intr Usoff
    Intrusive-Pointer sollten eine gute Möglichkeit sein, wenn die Array-Elemente immer PODs sind.
    Mit nicht-POD Typen wüsste ich auf die Schnelle aber nicht wie man das anstellen soll. Ausser halt wieder viel Code selbst zu schreiben.

    0
  • ?

    Finnegan schrieb:

    Zugegeben, beim Durchlaufen besonders langer Arrays wird sich das zusätzliche Dereferenzieren wahrscheinlich amortisieren, ich suche aber nach einer Lösung die diesen Overhead dennoch vermeidet.

    Wäre SmallVector eine Option? Also immer Speicher für ca. 16 Elemente bereithalten und wenn das überschritten wird, dynamisch Speicher anfordern. Nicht maximal effizient, aber dafür einfach.

    0
  • F

    Nathan schrieb:

    Evtl. könntest du mit allocate_shared tricksen.

    Intr Usoff schrieb:

    Was ist mit http://www.boost.org/doc/libs/1_57_0/libs/smart_ptr/intrusive_ptr.html ?

    Hey! Boost und allocate_shared waren die richtigen Stichworte, die mich auf die richtige Fährte gebracht haben (aus Boost 1.57-Doku):

    template<class U> 
    shared_ptr<U> make_shared(size_t size);
template<class U, class A> 
    shared_ptr<U> allocate_shared(const A& allocator, size_t size);

    Returns: A shared_ptr to a value-initialized object of type T[size].

    Remarks: These overloads shall only participate in overload resolution when U is of the form T[].

    Examples:

        boost::shared_ptr<int[]> a1 = boost::make_shared<int[]>(size);
        boost::shared_ptr<int[][2]> a2 = boost::make_shared<int[][2]>(size);

    Scheint so, als könne der boost::shared_ptr genau das was ich beim std::shared_ptr vermisst habe! Jetzt, wo so vieles aus Boost Einzug in die Standard Library gehalten hat, bin ich gar nicht mehr drauf gekommen, dass Boost auch einen shared_ptr hat. Ich werd's mal damit probieren 😃
    Vielen Dank jedenfalls!

    Finnegan

    P.S.: Jetzt ist es mir schon ein bisschen peinlich, dass ich das nicht vorher gefunden habe - diese Lösung habe ich sogar in den Suchmaschinenergebnissen übersehen 🙄 (Schande über mich, LMGTFY lasst grüssen). Sorry!
    BTW: Scheint sogar mit N3641 ein Standard-Proposal zu geben, in dem vorgeschlagen wird, das auch in std aufzunehmen. Könnte also sein, das sowas demnächst von Haus aus unterstützt wird.

    0
Anmelden zum Antworten