Dynarray Implementation

Shade Of Mine

TyRoXx schrieb:

Spricht etwas gegen erase , clear oder shrink_to_fit ?

Ja.
Das Dynarray ist per Definition immer voll.

krümelkacker

TyRoXx schrieb:

Spricht etwas gegen erase , clear oder shrink_to_fit ?

DynArray ist als VLA-Ersatz gedacht.

knivil

Sone schrieb:

Was ich meinte ist, dass es keine sinnvolle Verwendung für null-sized Dynarrays gibt, weil man damit nichts machen kann.
Es geht nicht darum, dass es die Größe Null nicht annehmen darf - das ist ja schon gegeben.
Ich meinte, das man ihn nicht so erzeugen darf.
Und das lässt du ja...

Also wenn Arrays (Multi)Mengen repraesentieren, dann sollte auch eine Moeglichkeit bestehen, die leere Menge zu repraesentieren. Siehe Haskell [] | [a] vs. Maybe. Meine Algorithmen akzeptieren meist leere Mengen und ich spare mir eine seperate Fehlerabfrage.

TyRoXx

Shade Of Mine schrieb:

TyRoXx schrieb:

Spricht etwas gegen erase , clear oder shrink_to_fit ?

Ja.
Das Dynarray ist per Definition immer voll.

Was soll das bedeuten?

krümelkacker schrieb:

TyRoXx schrieb:

Spricht etwas gegen erase , clear oder shrink_to_fit ?

DynArray ist als VLA-Ersatz gedacht.

Und das heißt?

Es ist ja nicht so als würde Dynarray diese Operationen im jetzigen Zustand verhindern. Ein freies erase ist bloß unnötig ineffizient.

template <class T, class A>
void erase(Dynarray<T, A> &a, typename Dynarray<T, A>::iterator begin, typename Dynarray<T, A>::iterator end)
{
	Dynarray<T, A> remaining(a.size() - std::distance(begin, end));
	std::move(a.begin(), begin, remaining.begin());
	std::move(end, a.end(), remaining.begin() + std::distance(a.begin(), begin));
	a = std::move(remaining);
}

EDIT: Besser, aber noch nicht so gut wie eine Methode.

clear als Methode würde den Speicher noch nicht freigeben (äquivalent zu .erase(begin(), end()) ). So kann man in einen Nullzustand gelangen, ohne sofort eine teure Deallokation machen zu müssen.

EDIT 2: Warum sagt mir denn niemand, dass ein Allocator beim Freigeben die Größe verlangt? So ist günstiges Verkleinern wie bei vector natürlich nicht möglich.

krümelkacker

TyRoXx schrieb:

krümelkacker schrieb:

DynArray ist als VLA-Ersatz gedacht.

Und das heißt?

Wann will, dass sich

void foo(int x) {
  DynArray<double> da(x);
  ...
}

so ähnlich verhält wie

void foo(int x) {
  double da[x]; // C99 VLA feature
  ...
}

ohne, dass man am Sprachkern noch rumfummeln muss und damit auf die C99-Regeln verzichten kann

camper

krümelkacker schrieb:

TyRoXx schrieb:

krümelkacker schrieb:

DynArray ist als VLA-Ersatz gedacht.

Und das heißt?

Wann will, dass sich
void foo(int x) {
  DynArray<double> da(x);
  ...
}
so ähnlich verhält wie
void foo(int x) {
  double da[x]; // C99 VLA feature
  ...
}
ohne, dass man am Sprachkern noch rumfummeln muss und damit auf die C99-Regeln verzichten kann

Also braucht man noch einen entsprechenden Allokator. Wobei ich keine Ahnung habe, wie dann move unterstützt werden könnte.

krümelkacker

Im ursprünglichen Proposal steht auch nichts von Allokatoren oder Move-Operationen. Die Stack-Allokation wäre dann QoI/Compiler-Magie. Und ich würde das wahrscheinlich auch so basteln, dass, falls der Stack schon "recht voll" ist oder die geforderte Größe eine gewisse Grenze überschreitet, trotzdem auf den Freispeicher ausgewichen wird.

Ein Move könnte man trotzdem noch zulassen. Allerdings muss dann im Konstruktor geprüft werden, woher das Quellobjekt den Speicher herbekommen hat und ggf doch einfach kopieren, wenn es Stack-Speicher war.

Die Stack-Optimierung könnte so aussehen, dass der dynarray-Klasse noch einen besonderern, privaten Konstruktor bekommt, der dann ggf automatisch aufgerufen wird und worüber der allozierte Stack-Speicher empfangen werden kann.

camper

Hat jemand mal demonstriert, dass ein alloca-basiertes Array signifikant schneller ist als z.B. ein Array basierend auf einem thread-lokalen Pool (im Prinzip ist der Stack ja nichts anderes)?

ungefähr so (ungestest, wahrscheinlich auch nicht ganz korrekt)

struct tl_pool
{
    thread_local unique_ptr<char[]> pool;
    thread_local char* pool_ptr;

    static const std::size_t align = 8;
};

thread_local unique_ptr<char[]> tl_pool::pool(new char[1024*1024]);
thread_local char* tl_pool::pool_ptr = pool;

template <typename T>
struct tl_pool_alloc
{
    typedef T value_type;

    T* allocate(std:size_t n)
    {
        T* result = reinterpret_cast<T*>(pool_ptr);
        pool_ptr += ( n * sizeof(T) + ( align - 1 ) ) / align * align;
        return result;
    }

    void deallocate(T* p, std:size_t)
    {
        pool_ptr = p;
    }
};

Shade Of Mine

krümelkacker schrieb:

Die Stack-Optimierung könnte so aussehen, dass der dynarray-Klasse noch einen besonderern, privaten Konstruktor bekommt, der dann ggf automatisch aufgerufen wird und worüber der allozierte Stack-Speicher empfangen werden kann.

Wieso nicht über den allocator gehen? Dazu sind die ja da.

Aber Stack allokation ist tricky, weil du nicht mehr moven kannst, da wenn du selber out of scope gehst, ja auch dein Speicher out of scope geht...

Hier bräuchte man halt intelligente allocatoren - was die C++ allocatoren leider nicht sind.

@camper:
alloca ist einfach zu gefährlich um relevant verwendet werden zu können. insofern würde ich in 99% aller Situationen einen thread local pool bevorzugen.

hustbaer

krümelkacker schrieb:

Im ursprünglichen Proposal steht auch nichts von Allokatoren oder Move-Operationen. Die Stack-Allokation wäre dann QoI/Compiler-Magie. Und ich würde das wahrscheinlich auch so basteln, dass, falls der Stack schon "recht voll" ist oder die geforderte Größe eine gewisse Grenze überschreitet, trotzdem auf den Freispeicher ausgewichen wird.

Siehe mein Beitrag auf Seite 5 (der im übrigen komplett ignoriert wurde).

hustbaer

camper schrieb:

Hat jemand mal demonstriert, dass ein alloca-basiertes Array signifikant schneller ist als z.B. ein Array basierend auf einem thread-lokalen Pool (im Prinzip ist der Stack ja nichts anderes)?

Die Geschwindigkeit hab ich noch nicht verglichen - könnte man ruhig mal machen.
Aber was ist mit dem Grundsätlichen Problem eines solchen Allocators: man muss verdammt aufpassen dass man damit keinen Mist baut.
Speziell wenn der Container dann noch so "gefährliche" Funktionen wie move anbietet.