Verschachtelung von std::vector oder std::array

Hallo,
interessehalber interessiert es mich, ob die Elemente hintereinander oder zerstückelt im Speicher liegen, wenn man std::vector oder std::array verschachtelt.

vector< vector<vector<int>> > vec(5000);

Zerstückelt oder am Stück?

vector< array<array<int,50>,50> > vec(5000);

Zerstückelt oder am Stück?

array< array<array<int,50>,50>, 5000> ar;

Zerstückelt oder am Stück?

Was hat es überhaupt für Auswirkungen/Nachteile, wenn die Elemente nicht hintereinander im Speicher liegen? Nur, dass sich die Zugriffszeiten auf Elemente erhöhen, oder ist da noch mehr?

Danke im Voraus.

rüdiger

In allen Fällen zerstückelt. Man sollte lieber einen vector/array nehmen und dann über y*width+x auf die Elemente zugreifen. Oder man nimmt boost multiarray oder bastelt sich was eigene, dass das einfach im Hintergrund macht.

314159265358979

rüdiger schrieb:

In allen Fällen zerstückelt. Man sollte lieber einen vector/array nehmen und dann über y*width+x auf die Elemente zugreifen. Oder man nimmt boost multiarray oder bastelt sich was eigene, dass das einfach im Hintergrund macht.

Falsch. In den Fällen 2 und 3 am Stück. In 1 zerstückelt.

unskilled

314159265358979 schrieb:

rüdiger schrieb:

In allen Fällen zerstückelt. Man sollte lieber einen vector/array nehmen und dann über y*width+x auf die Elemente zugreifen. Oder man nimmt boost multiarray oder bastelt sich was eigene, dass das einfach im Hintergrund macht.

Falsch. In den Fällen 2 und 3 am Stück. In 1 zerstückelt.

das es bei vector zerstückelt ist, ist ja klar.
aber bei array habe ich keine garantie gefunden.

rüdiger

314159265358979 schrieb:

rüdiger schrieb:

In allen Fällen zerstückelt. Man sollte lieber einen vector/array nehmen und dann über y*width+x auf die Elemente zugreifen. Oder man nimmt boost multiarray oder bastelt sich was eigene, dass das einfach im Hintergrund macht.

Falsch. In den Fällen 2 und 3 am Stück. In 1 zerstückelt.

Zumindest bei Boost hat array früher new benutzt. Das ist vom Standard her auch nicht verboten. Also bei 2 und 3 ist es dann wohl Implementationsabhängig.

Michael E.

unskilled schrieb:

aber bei array habe ich keine garantie gefunden.

Abschnitt 23.3.2.1.2 sagt, dass std::array ein aggregate gemäß Paragraph 8.5.1 ist. Also hat std::array keinen user-provided constructor, sodass insbesondere kein new-Aufruf benutzt werden kann, sodass der Speicher innerhalb des Objekts liegen muss.

Nexus

Selbst wenn std::array<T, N> ein purer Wrapper um ein C-Array T[N] ist, dürfte der Compiler Padding am Ende der Klasse einfügen, oder?

Michael E.

Ich denke schon. Nichtsdestotrotz bleibt die Cachelokalität gewahrt.

hustbaer

Nexus schrieb:

Selbst wenn std::array<T, N> ein purer Wrapper um ein C-Array T[N] ist, dürfte der Compiler Padding am Ende der Klasse einfügen, oder?

Wenn std::array als einziges non-static data member das Array enthält und keine virtuellen Funktionen, Basisklassen oder dergleichen hat ist zumindest zu erwarten dass es kein Padding gibt.
Ob es garantiert ist weiss ich nicht.

So lange es nur um Cachelokalität und nicht-Verschwendung von Speicher geht würde ich mich einfach mal blind darauf verlassen.
Wenn es für das Funktionieren des Programms notwendig ist würde ich einfach std::vector<T> verwenden, und die Indexberechnung selbst machen.

Danke für eure Antworten :-). Auf meine zweite Frage wurde noch nicht so richtig eingegangen. Kann da noch jemand etwas sagen? --> Und welche Nachteile hat so ein zerstückelter Speicher nun?

(Stark) Erhöhte Zugriffszeit.

Nexus

Bei zerstückeltem Memory-Layout ist die Cache-Lokalität schlechter, was sich vor allem beim Iterieren auswirkt. Zudem hast du im Falle von std::vector noch dynamische Allokationen und Deallokationen für jeden inneren vector , die einmalig Rechenzeit und Memory-Overhead kosten. Der Zugriff ist auch minimal langsamer, weil zwei Additionen und Dereferenzierungen stattfinden (bei std::array können die Operationen zusammengefasst werden).

hustbaer

Cache-Lokalität wurde ja schon zur Genüge erwähnt.

Weiters hast du mehr Allokationen, und mehr Allokationen heisst wieder "dauert längen beim Anfordern + Freigeben". Und mehr Allokationen heisst auch mehr Heap-Fragmentierung.

Und in dem Fall heisst mehr Allokationen auch mehr Indirections, was wieder Geschwindigkeit kostet.

Dafür werden die Stücke bei mehr Allokationen natürlich kleiner, was wiederum heisst dass das Programm mit weniger zusammenhängendem freien Adressraum auskommt. Was bei 32 Bit - je nach Gesamtgrösse des Blocks - durchaus ein Thema sein könnte. Bei 64 Bit eher weniger.

pumuckl

hustbaer schrieb:

Nexus schrieb:

Selbst wenn std::array<T, N> ein purer Wrapper um ein C-Array T[N] ist, dürfte der Compiler Padding am Ende der Klasse einfügen, oder?

Wenn std::array als einziges non-static data member das Array enthält und keine virtuellen Funktionen, Basisklassen oder dergleichen hat ist zumindest zu erwarten dass es kein Padding gibt.
Ob es garantiert ist weiss ich nicht.

std::array<T, N> ist garantiert layout-kompatibel zu T[N] - allerdings liegen z.B. die einzelnen Elemente von hinterinanderliegenden Arrays auch nicht garantiert "dicht" im Speicher, z.B. dürften in array<array<char,3>, 2> padding-bytes zwischen den array<char, 3> liegen.

SeppJ

pumuckl schrieb:

std::array<T, N> ist garantiert layout-kompatibel zu T[N] - allerdings liegen z.B. die einzelnen Elemente von hinterinanderliegenden Arrays auch nicht garantiert "dicht" im Speicher, z.B. dürften in array<array<char,3>, 2> padding-bytes zwischen den array<char, 3> liegen.

Was dann jedoch egal ist, solange man nicht anfängt, manuell Indizes zu errechnen.