(gelöst)[C++] std::vector, nur leichter

[Krishty]

Miep!

Ich nutze im Augenblick ein paar std::vectors für Zwischenergebnisse größerer Berechnungen, nur haben die zu viel Overhead. Insbesondere die Default-Initialisierung des Speichers bei resize() macht mir zu schaffen. Dabei sind meine Ansprüche wirklich nicht hoch:

• ein Mal reservieren, nie mehr vergrößern oder verkleinern
• die Länge ist aus anderer Quelle bekannt (kein size() oder end() nötig)
• keine Initialisierung

Mein Vorgänger schrieb an der Stelle immer eines von den beiden:

  auto_ptr<T> data(new T[length]);

  boost::scoped_array<T> data(new T[length]);

Aber das eine ist lange obsolet und das andere … ich hab’s noch nicht gesagt, aber kein boost.

Bietet C++’11, ’14, ’21 oder ’73 was, das mich davon abhält, meinen eigenen Typ zu schreiben?

[dot]

Code: Alles auswählen

auto data = std::make_unique<T[]>(length);

;)

[Krishty]

Zumindest unter VS wird das zu

  return (unique_ptr<_Ty>(new _Elem[_Size]()));

… und ruft damit den Standardkonstruktor auf :(

Habe eben schnell VirtualAlloc() eingesetzt, und der Algorithmus ist von 138 auf 107 ms runter. Bin aber weiter an einer STL-Lösung interessiert, um nicht den Rest der Nacht mit Copy-Konstruktoren und std::move()-Überladungen verbringen zu müssen …

[dot]

Ok, d.h. dein T ist also irgendein Class-Type mit non-trivial Default C'tor!? Denn ansonsten sollte die Default-Initialization der Arrayelemente eine NOP sein. In dem Fall ist mir aber unklar inwiefern die "Lösungen" deines Vorgängers nicht das gleiche Problem haben...

Hast du schon versucht, statt resize() und dann Elementzugriff, einen leeren std::vector zu machen, per reserve den notwendigen Platz zu holen und dann per push_back() deine Daten einzufüllen? Rein prinzipiell ist das Problem halt, dass so etwas wie ein "Array von nichtkonstruierten T Objekten" rein semantisch keinen Sinn macht. Wenn du einen Haufen T Objekte haben willst, um mit denen was zu machen, brauchst du erstmal einen Haufen T Objekte. Du kannst uninitialisiertem Speicher nicht einfach einen T-Wert zuweisen, sowas würde dem Konzept "Typ" an sich widersprechen; du kannst nur einem T-Wert einen neuen T-Wert zuweisen, sofern der Typ T eine solche Zuweisung definiert. Was du machen kannst, ist in uninitialisiertem Speicher ein T zu konstruieren. Das ist konzeptionell aber etwas völlig anderes da dabei neue Objekte erzeugt werden und nicht vorhandene modifiziert.

Edit: Ah OK, der Standard schreibt also tatsächlich vor dass std::make_unique() Arrays value-initialized, war mir nicht bewusst; aber gut zu wissen, muss ich einiges an eigenem Code anpassen...dann also:

Code: Alles auswählen

template <typename T>
inline auto make_default(std::enable_if_t<std::is_array_v<T> && std::extent_v<T> == 0, std::size_t> N)
{
  return std::unique_ptr<T> { new std::remove_extent_t<T>[N] };
}

// ...

auto data = make_default<T[]>(size);

[Krishty]

Danke!

reserve() und push_back() funktioniert normalerweise ganz gut, geht aber an dieser Stelle nicht, weil das Array durch Worker Threads befüllt wird und dann unnötige Synchronisation fällig wäre. Und ein Haufen von nicht-konstruierten Objekten macht halt *doch* Sinn, wenn es sich um POD handelt :)

[dot]

Und ein Haufen von nicht-konstruierten Objekten macht halt *doch* Sinn, wenn es sich um POD handelt :)

Nö, ein Haufen von nicht-konstruierten POD Objekten macht genauso keinen Sinn, denn nicht-konstruierte Objekte existieren per Definition nicht, egal wie P oder O der T auch noch sein mag... :P

Im Fall von POD Objekten siehe Edit oben... ;)

[xq]

Krishty, warum nicht einfach das Array mit malloc alloizieren und mit placement new initialisieren? das ganze packst du in einen unique_ptr mit delete[] oder free als deleter und jut.

[Spiele Programmierer]

Naja, eine Anforderung für POD ist halt auch dass es einen Trivial Default Constructor hat - in anderen Worten: Einen Konstruktor der nichts macht.
cppreference.com schreibt außerdem: "it can be created with std::malloc"
Mit anderen Worten, POD Objekte muss man tatsächlich nicht konstruieren/initialisieren, denn std::malloc initialisiert ebenfalls nicht.

Und selbst falls es sich nicht um POD Objekte handelt, kann man sie nachträglich mit Placement New erzeugen. Nichts anderes macht std::vector.
Das ganze ausnahmesicher hinzubekommen ist zwar ein wenig trickreich, aber absolut möglich.

Ich verstehe bloß noch nicht ganz das Problem mit dem new[]. Eigentlich sollte das für trivialle Konstruktoren (also auch jedem POD) ebenfalls keinen Konstruktor aufrufen. Falls es dir um das VirtualAlloc geht, aber du eine C++ Lösung willst:

Code: Alles auswählen

class VirtualFreeDeleter
{
    void operator()(void* Ptr) noexcept { VirtualFree(Ptr, 0, MEM_RELEASE); } 
};
template<typename T>
std::unique_ptr<T[], VirtualFreeDeleter> MakeVirtualAlloc(size_t Count)
{
    void* Ptr = VirtualAlloc(nullptr, sizeof(T) * Count, MEM_RESERVE | MEM_COMMIT, PAGE_READWRITE);
    if (!Ptr)
        throw std::bad_alloc();
    return std::unique_ptr<T[], VirtualFreeDeleter>(reinterpret_cast<T*>(Ptr));
}

void Test()
{
    auto SomeVirtualMemory = MakeVirtualAlloc<int>(65536);
    SomeVirtualMemory[1024] = 10; //Speicher verwenden...
} 

Gleiches kann man auch mit malloc oder jeden anderen Allokator machen.
Ich persönlich nutze das oft, weil ich die Semantik von new[] fürcherlich finde.
Ich bin auch ein Freund von std:realloc ... ;)

[Krishty]

Ich glaube, da habt ihr was missverstanden: dots spätere Lösung funktioniert bereits. Ich kann aber die Standardlösung mit unique_ptr nicht nutzen, weil sie (gemäß Standard) new _Elem[_Size]() aufruft statt new _Elem[_Size]. Die Klammern bewirken Default-Konstruktion, und das bedeutet bei POD Nullen des Speichers, und das bedeutet viel Overhead.

VirtualAlloc() hatte ich nur als erstbesten Kandidaten zum Testen eingebaut, bis die Funktionierende Lösung klar war. Und die wäre, wie von dot gepostet:

Code: Alles auswählen

template <typename T>
inline auto make_default(std::enable_if_t<std::is_array_v<T> && std::extent_v<T> == 0, std::size_t> N)
{
  return std::unique_ptr<T> { new std::remove_extent_t<T>[N] };
}

// ...

auto data = make_default<T[]>(size);

[Spiele Programmierer]

Ok, das habe ich wirklich völlig missverstanden.

Ich habe nicht gewusst das make_unique PODs mit 0 initialisiert.
Halte ich ehrlich gesagt für eine sehr sehr fragwürdige Entscheidung.
Von "What you don’t use, you don’t pay for" rückt man wohl ab. :(

[Krishty]

Lange schon. Ich hab’s schon bei std::vector nicht verstanden.

Zu dir als Freund von malloc(): Ich nutze gern HeapAlloc() und VirtualAlloc(). Wenn man genullten Speicher haben will, kommen die kostenlos ran (virtueller Speicher startet bei Windows immer genullt, schon aus Sicherheitsgründen). Ich verstehe nicht, warum die STL dann unbedingt erzwingen muss, dass nochmal genullt wird – und das Element- statt Blockweise. Für die Leute, die ihre eigenen Allokatoren schreiben? Zum Kotzen, das alles.

[Spiele Programmierer]

Meinst du beim std::vector, dass eine Memberfunktion fehlt um die Größe zu ändern ohne ihn mit einem Referenzobjekt zu füllen?

Ich nutzte wegen Linux meistens malloc.
Für genullten Speicher calloc. Ich nehme an, dass das bei genügend großen Anfragen den fertig genullten Speicher vom OS nimmt?

EDIT;
An der Stelle noch eine Lobeshymne auf Rusts Typen die reallocable sind und eine effizentere Vector Implementierung zulassen.
C++ Move-Konstruktoren zu schreiben ist nebenbei die größte Zeitverschwendung überhaupt direkt nach der mit dem Schreiben von Headern.

[Krishty]

Ich habe nun noch doch meinen eigenen vector für POD geschrieben:

1. keine Default-Initialisierung
2. realloc() beim Wachsen statt neuem Speicherblock

Die Leistungsverbesserung liegt bei 2,5 % (1 GiB Arbeitssatz) bis 4,5 % (4 GiB Arbeitssatz). Dabei scheint realloc() fast nichts zu bringen; ich vermute, dass Windows intern jedes Mal einen neuen Block sucht (Low Fragmentation Heap?).

(Nur damit wir mal Zahlen aus der echten Welt haben.)

[Spiele Programmierer]

Für große Allokationen greift "malloc" direkt auf "VirtualAlloc" zurück.
Es gibt aber leider, leider kein "VirtualRealloc"...
Obwohl das mit Paging ja sehr effizient möglich wäre! Sogar Linux hat "mremap".
Ich würde mir auch wirklich wünschen es gäbe ein "VirtualRealloc".

Je nach Anwendungsfall kommt vielleicht eine Art Unrolled Linked List als Alternative in Frage.
Also unabhänige kontinuerliche Speicherblöcke von jeweils ein paar MB.

[Krishty]

Naja; eigentlich nutze ich nicht malloc() und realloc() sondern HeapAlloc() und HeapRealloc() der WinAPI (ich wollt’s nur allgemeinverständlich halten). Die greifen für große Allokationen ebenfalls auf VirtualAlloc() zurück.

Ich hatte mir davon eine Reduzierung des Arbeitssatzes erhofft, weil das Commit erst bei tatsächlicher Nutzung eintritt (und nicht, wenn der scheiß std::vector() alles nullt), aber zumindest in meinem Szenario sind die Speicherzugriffe zu breit verteilt.

Threoretisch könnte man Blöcke mit VirtualAlloc() verbinden, sofern der Speicher dazwischen noch nicht zugewiesen ist (man kann ja eine Adresse angeben). Beim Schrumpfen könnte man ebenfalls einfach die letzten Pages wieder freigeben. Ob sie das praktisch machen, keine Ahnung. Der Großteil meiner Daten ist eh in Blöcken < 100 B untergebracht und bei den wirklich großen Blöcken sind die Zugriffe zu verstreut, siehe oben.

[dot]

Man könnte übrigens per custom allocator auch std::vector dazu bringen, zu default-initen statt zu value-initen... ;)

[Krishty]

a.allocate(n) – allocates storage suitable for n objects of type T, but does not construct them. May throw exceptions.

Ich habe das so interpretiert, dass der Allocator sowieso nichts mit Konstruktion am Hut hat und diese vom vector übernommen wird. War ich da auf der falschen Fährte?

[Spiele Programmierer]

a.construct(xptr, args) - Constructs an object of type X in previously-allocated storage at the address pointed to by xptr, using args as the constructor arguments

Allokatoren sind sehr seltsam in C++.

[Krishty]

Uuuuh, danke. Habe ich drei Mal überlesen …

… ein std::vector mit eigenem Allocator und Memory Pool war übrigens ebenfalls im Bau, aber ein paar Architekturprobleme kamen dazwischen. Von dem Pool hatte ich mir erhofft, die Millionen einzelnen Freigaben zu sparen. Später vielleicht.

[dot]

Wobei man erwähnen sollte, dass Allocator::construct() deprecated ist und man besser einfach std::allocator_traits spezialisiert... ;)

[dot]

a.construct(xptr, args) - Constructs an object of type X in previously-allocated storage at the address pointed to by xptr, using args as the constructor arguments

Allokatoren sind sehr seltsam in C++.

[youtube]LIb3L4vKZ7U[/youtube]

;)