3. Diskussion ueber vector Speicherausrichtung (Split von uint8_t vector/uint32_t)

Diskussion ueber vector Speicherausrichtung (Split von uint8_t vector/uint32_t)

  • *

    @Columbo sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

    Ein kurzer Beispiel für C++11 und neuer, weshalb man eben aus dem Alignment eines news nicht darauf schließen darf, dass ein Zeiger oder ein Vector das passende Alignment aufweist, denn für Subtypes ist alignof(std::max_align_t) nicht gültig!

    Beispiel für LittleEndian Maschien mit alignof(std::max_align_t) == 16

    #include <iostream>
#include <initializer_list>
#include <cstddef>
#include <cstdlib>
#include <cstdint>

struct SmallVector {
	uint8_t flag_size;
	uint8_t data[31];
};

struct LargeVector {
	uint8_t* data;
	size_t	size;
	size_t	capacity;
};

union UnionVector {SmallVector sv; LargeVector lv;};

class vector {
public:
	UnionVector v;

	vector () {
		v.sv.flag_size = 1;
	}
	~vector() {
		if (!(uint8_t(1) & v.sv.flag_size)) delete[] v.lv.data;
	}

	vector (std::initializer_list<uint8_t>& il) {
		size_t s = il.size();
		if (s > 31) {
			v.lv.data = new uint8_t[s];
			v.lv.size = s;
			v.lv.capacity = s;

			size_t i = 0;
			for (auto it = il.begin(), en = il.end(); it != en; ++it) {
				v.lv.data[i++] = *it;
			}
		} else {
			uint8_t i = 0;

			for (auto it = il.begin(), en = il.end(); it != en; ++it) {
				v.sv.data[i++] = *it;
			}
			s = s << 1;
			s += 1;
			v.sv.flag_size = s;
		}
	}

	uint8_t* data() {
		if (uint8_t(1) & v.sv.flag_size) return &(v.sv.data[0]);
		return v.lv.data;
	}
};

std::ostream&
operator<< (std::ostream& o, vector& vec) {
	if (uint8_t(1) & vec.v.sv.flag_size) {
		std::cout << "small vector\n";
		uint8_t s = vec.v.sv.flag_size >> 1;

		for (uint8_t i = 0; i < s; ++i) {
			o << "[" << uint16_t(i) << "] = " << uint16_t(vec.v.sv.data[i]) << "\n";
		}
	} else {
		std::cout << "large vector\n";
		for (size_t i = 0; i < vec.v.lv.size; ++i) {
			o << "[" << i << "] = " << uint16_t(vec.v.lv.data[i]) << "\n";
		}
	}

	return o;	
}

int main () {
	static_assert (alignof(std::max_align_t) == 16);

	std::cout << "sizeof(SmallVector): " << sizeof(SmallVector) << "\n";
	std::cout << "sizeof(LargeVector): " << sizeof(LargeVector) << "\n";
	std::cout << "sizeof(vector):      " << sizeof(vector) << "\n";

	std::initializer_list<uint8_t> il1 =
		{ 0,  1, 2,   3,  4,  5,  6,  7,  8,  9,
		 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
		 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
		 30
		};
	std::initializer_list<uint8_t> il2 =
		{ 0,  1, 2,   3,  4,  5,  6,  7,  8,  9,
         10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
         20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
         30, 31, 32, 33, 34, 35, 36, 37, 38, 39
		};

	vector v1(il1);
	vector v2(il2);

	std::cout << "uint8_t* v1.data " << static_cast<void*>(v1.data()) << "\n";
	std::cout << "uint8_t* v2.data " << static_cast<void*>(v2.data()) << "\n\n";

	std::cout << v1 << "\n";
	std::cout << v2 << "\n";
}
    0
  • Mod

    @john-0 Auch wenn small-buffer optimizations von vector<> durchgefuehrt werden, gilt immer noch die as-if rule. Die Tatsache, dass deine Implementierung den internen Speicher (demonstrativ um des Arguments willen.....) falsch ausrichtet, heisst, dass sie nicht konform ist.

    Waerst Du auch drauf gekommen, bevor Du 100 Zeilen Code schreibst, wenn Du mal 2 Minuten nachdenkst.

    -1
    *
     1 Antwort
  • *

    @Columbo sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

    @john-0 Auch wenn small-buffer optimizations von vector<> durchgefuehrt werden, gilt immer noch die as-if rule.

    Dir ist hoffentlich bewusst, dass die std::string Klassen der Compiler sich nicht daran halten? Es gibt mehrere Vorträge von den CppCon Tagungen rund um dieses Thema. Auf x86-64 ist alignof(max_align_t) == 16, aber die std::string Klassen nutzen intern nur 8. D.h. wenn ich da auf long double oder SSE Vektor caste kann es zu Problemen kommen. Wenn es eine Einschränkung für die Implementierung von Container gibt, wäre ein Hinweis auf die Stelle in der Norm angebracht, und nicht Mutmaßungen es müsse so sein. Der ganze Thread dreht sich darum, dass hier Mutmaßungen über das Speicherlayout gemacht werden.

    Was jedenfalls falsifiziert ist, dass man uint8_t* problemlos in ein uint32_t* casten kann. Denn ein Struct

    struct Foo {
    char a, b;
    uint8_t field[4];
};

    ist legal, und darf so auch im Code verwendet werden. In einer Funktion die ein uint8_t*als Argument übernimmt, darf ich daher nicht annehmen, dass das Feld so ausgerichtet ist, dass ich den Cast durchführen darf.

    Die Tatsache, dass deine Implementierung den internen Speicher (demonstrativ um des Arguments willen.....) falsch ausrichtet, heisst, dass sie nicht konform ist.

    Wie wäre es, die Stelle in der Norm anzuführen wo das steht?

    0
  • Mod

    Vorab: Fuer vector<> duerfen Implementierungen sowieso keine small-buffer optimization durchfuehren, siehe [container.requirements.general]:

    The expression a.swap(b), for containers a and b of a standard container type other than array, shall exchange the values of a and b without invoking any move, copy, or swap operations on the individual container elements. [..] Every iterator referring to an element in one container before the swap shall refer to the same
    element in the other container after the swap.

    (Der Leser darf sich hier selber zusammenreimen, warum das SBO verunmöglicht.)
    Das galt damals sogar fuer basic_string, wobei hier ein DR und entsprechendes Paper N3107 Abhilfe verschafft haben, um SSO zu erlauben.

    Ich bin übrigens auch kein Fan davon, von irgendwelchen abstrusen alignment Bedingungen interner Speicher abhängig zu sein, weshalb ich einfach memcpy anwenden würde, wie bereits erwaehnt. Aber die gesamte Diskussion basiert auf einem schwach definierten Problem. Allzuviel Intellekt zu verschwenden ist hier nicht angezeigt.

    @john-0 sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

    @Columbo sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

    @john-0 Auch wenn small-buffer optimizations von vector<> durchgefuehrt werden, gilt immer noch die as-if rule.

    Dir ist hoffentlich bewusst, dass die std::string Klassen der Compiler sich nicht daran halten?

    Theoretisch: string::capacity() ergibt die Laenge des allozierten Speichers. Gleichzeitig repräsentiert capacity() die Zahl von Elementen, die ohne reallocation aufgenommen werden können (das ist fuer basic_string nicht explizit, aber analog zur vector::capacity Definition zu verstehen). Folglich steht das erste Element an Position 0 des allozierten Speichers, der wie oben erwaehnt das strictest fundamental alignment haben muss.

    In der Realitaet befolgen die Autoren der stdlib diese Schlussfolgerung (und auch Exegese) nicht. Ueberhaupt ist diese Diskussion realitaetsfern, weil niemand den Speicher von std::string fuer andere Objekte zweckentfremdet.

    Was jedenfalls falsifiziert ist, dass man uint8_t* problemlos in ein uint32_t* casten kann.

    Diese Pauschalaussage hat niemand gemacht. Vielleicht hast Du Dir ausgedacht, dass sie hier jemand gemacht hat, damit Du allen erklaeren darfst, dass sie falsch ist?

    0
    *
     1 Antwort
  • *

    @Columbo sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

    (Der Leser darf sich hier selber zusammenreimen, warum das SBO verunmöglicht.)

    Das leidige Thema swap und move bei Standard Container, das in der Norm fehlerhaft festgelegt wurde, weil es mit erlaubten Allokatoren, die sich nicht so wie der std::allokator<T> verhalten, zu UB führt, wenn man swap auf dem Container ausführt.

    Das erzwingt eine Allokation auf dem Heap, aber das erfordert noch immer nicht, dass das Datenfeld entsprechend ausgerichtet sein muss. Wenn man size und capacity in den Heap legt, und nur den Pointer und den Allokator in die eigentliche Datenstruktur, fängt die Datenstruktur auf dem Heap nicht mehr mit dem ersten Element des Feldes an. Und bitte nicht vergessen, die Norm erlaubt es explizit, dass man für diese beiden Datentypen nicht size_t verwendet, sondern etwas kleineres, so dass dann hier trotzdem ein Problem mit der Ausrichtung bekommt.

    Nicht vergessen Garantien sind mehr als nur eine Gewissheit, dass etwas vermutlich funktioniert. In C++98 durfte man bei einem std::vector<T> noch Löcher zwischen den Elementen haben (und es gab meines Wissens nie eine Implementation, die das umgesetzt hätte), das wurde auch erst später repariert, so dass ein Cast auf die Datenelemente auch garantiert funktionierte.

    0 1 Antwort
  • Mod

    @john-0 sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

    Das leidige Thema swap und move bei Standard Container, das in der Norm fehlerhaft festgelegt wurde, weil es mit erlaubten Allokatoren, die sich nicht so wie der std::allokator<T> verhalten, zu UB führt, wenn man swap auf dem Container ausführt.

    Aehh... ich meinte die Tatsache, dass es unmöglich ist, die Iteratoren wie gefordert gültig zu lassen, wenn man die Elemente in-place im vector (bzw. Allokator) speichert. Deine Erklaerung ist irgendwie nichtssagend.

    Wenn man size und capacity in den Heap legt, und nur den Pointer und den Allokator in die eigentliche Datenstruktur, fängt die Datenstruktur auf dem Heap nicht mehr mit dem ersten Element des Feldes an.

    Das ist Schwachsinn, da

    • ...std::allocator<T>::allocate ein T[] Array erschafft, dessen Elemente noch nicht am Leben sind. Dort Objekte frermden Typs zu speichern wuerde das Array zerstoeren (siehe [intro.object]), was in der Folge zu UB fuehrt.
    • ...der Default Konstruktor von vector quasi noexcept ist (vorbehaltlich der noexcept-ness des Allokator ctors), ein allocate Aufruf aber potenziell std::bad_alloc wirft.

    Wenn Du jetzt behaupten willst, der vector koennte seine Elemente ja ab Position 1 des allozierten Arrays speichern... 🙄

    Nicht vergessen Garantien sind mehr als nur eine Gewissheit, dass etwas vermutlich funktioniert.

    Deshalb habe ich ja oben auch explizit erklaert, was meine Einstellung zu diesem Thema ist.

    0
    *
     1 Antwort
  • *

    @Columbo sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

    Aehh... ich meinte die Tatsache, dass es unmöglich ist, die Iteratoren wie gefordert gültig zu lassen, wenn man die Elemente in-place im vector (bzw. Allokator) speichert. Deine Erklaerung ist irgendwie nichtssagend.

    Das ist schon klar. Das ist aber mit bestimmten konformen Allokatoren nicht erfüllbar, und führt zu UB. Die Norm ist an dieser Stelle defekt, die Anforderungen an die Container sind nur dann erfüllbar, wenn für den Allokator entweder std::allocator_traits<Allocator<T>>::is_alway_equal oder std::allocator_traits<Allocator<T>>::propagate_on_container_swap erfüllt ist. Sonst knall es, wie man mit real existierenden Implementationen leicht sehen kann.

    Das ist Schwachsinn, da

    Du musst schon bei einer Argumentationslinie bleiben, wenn Du nun hier behauptest, dass man den mit dem Allokator allokierten Speicher nicht auf einen anderen Typen casten kann, dann kann man erst recht nicht std::vector<uint8_t> auf uint32_t casten. Wenn man das doch kann, dann kann man in das Feld auch vorher etwas hineinkopieren.

    0 1 Antwort
  • Mod

    @john-0 sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

    Du musst schon bei einer Argumentationslinie bleiben, wenn Du nun hier behauptest, dass man den mit dem Allokator allokierten Speicher nicht auf einen anderen Typen casten kann, dann kann man erst recht nicht std::vector<uint8_t> auf uint32_t casten. Wenn man das doch kann, dann kann man in das Feld auch vorher etwas hineinkopieren.

    Ich muss gar nichts, weil ich den Unterschied zwischen type punning und object lifetime verstehe. Wenn T != unsigned char/char/std::byte/std::size_t, also fast immer, konstruierst Du im Speicher ein neues Objekt, welches kein Subobjekt des Arrays sein kann, und deshalb als neues Objekt im gleichen Speicher das alte Objekt zwingend zerstoert. Siehe [basic.life].
    Im anderen Fall, unter der Annahme dass uint8_t == unsigned char/char, wird unter den neuen object lifetime Regeln ein Objekt vom Typ uint32_t automatisch erzeugt, welches in dem char Array 'nested' ist. Sowohl das char Array als auch das uint32_t Objekt koexistieren im gleichen Speicher.

    Das ist aber mit bestimmten konformen Allokatoren nicht erfüllbar, und führt zu UB.

    Ein Allokator der bei validen Operationen zu UB fuehrt ist per Definition nicht konform. Ausserdem ist dieser Paragraph trivial zu implementieren, wenn man einfach keine SBO einsetzt.

    Sonst knall es, wie man mit real existierenden Implementationen leicht sehen kann.

    Demonstration bitte. Duerfte der Diskussion auch helfen.

    0
    *
     1 Antwort
  • *

    @Columbo sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

    Ich muss gar nichts, weil ich den Unterschied zwischen type punning und object lifetime verstehe.

    Du verstehst hier an der Sache vieles nicht. Die Allokation des Allokators konstruiert keinerlei Objekte! Die Konstruktion muss anschließend separat ausgeführt werden in dem man explizit std::allocator_traits<Allocator<T>>::construct für jedes Objekt aufruft und genauso muss man es per std::allocator_traits<Allocator<T>>::destroy explizit wieder zerstören. Ein Allokator ist kein fancy new.

    Ein Allokator der bei validen Operationen zu UB fuehrt ist per Definition nicht konform.

    Die Operation ist wie sie durchgeführt wird eben nicht valide.

    Die Norm erlaubt für Allokatoren explizit dieses Verhalten, und solche Allokatoren sind auch sehr sinnvoll, da es Speicheranforderungen gibt, die die speziellen Anforderungen von Container an swapund move gar nicht erfüllen können, da es sich hier um Optimierungen in Spezialfällen handelt, die eben nicht immer durchgeführt werden können.

    Bleiben wir mal bei dem Fall swap. Man erwartet, dass der Befehl swap die Inhalte der beiden Container miteinander austauscht. Wenn man eine unified memory system hat, kann man hier optimieren und einfach die Zeiger in den beiden Container austauschen. Allerdings gibt es eben nicht nur UMA-Systeme sondern auch NUMA-Systeme, und bei denen läuft das ganze nun einmal anders ab. Liegen beide Container auf demselben NUMA-Knoten, dann läuft das ab wie bei UMA-System. Ist das aber nicht der Fall, sollen trotzdem die Inhalte der beiden Container vertauscht werden, und das geht nur mit Kopieren, weil sonst eben nicht die Daten die Knoten wechseln.

    Die Allokatoren in C++ sind dafür geeignet, dieses Problem korrekt abzubilden. Aber eben nicht die Standardcontainer. Irgend ein Dödel hat es vergessen das korrekt für die Container zu formulieren.

    Demonstration bitte. Duerfte der Diskussion auch helfen.

    Ich habe dafür Testcode und auch einen Testallokator (nicht so robust wie er sein könnte, aber für Test- bzw. Demofälle reicht er aus), der simuliert wie sich ein NUMA-System verhält.

    Fangen wir mit dem std::allocator<T> an. Wichtig sind hier vier Eigenschaften eines Allokators, die man mit std::allocator_traits testet. Das sind IAE, POCCA, POCMA und POCS. Die vier Abkürzungen werden auch in der Literatur oftmals genutzt und stehen für: is_always_equal, propagate_on_container_copy_assignment, propagate_on_container_move_assignment und propagate_on_container_swap.

    Für std::allocator<T> ergibt sich somit folgende Ausgabe. Die Vektoren sind absichtlich gleich groß, weil so Allokationen wegen unterschiedlichen Vektorgrößen vermieden werden. Das ganze wurde mit gcc 11.3.0 unter Linux übersetzt.

    POCCA false
POCMA true
POCS  false
IAE   true


POCCA: Propagate On Container Copy Assignment
va: p = 0x23322c0, [0] = 0, [1] = 1, [2] = 2, [3] = 3
vb: p = 0x23322e0, [0] = 4, [1] = 5, [2] = 6, [3] = 7
copy assigment va = vb
va: p = 0x23322c0, [0] = 0, [1] = 1, [2] = 2, [3] = 3
vb: p = 0x23322e0, [0] = 0, [1] = 1, [2] = 2, [3] = 3


POCMA: Propagate On Container Move Assignment
va: p = 0x23322c0, [0] = 0, [1] = 1, [2] = 2, [3] = 3
vb: p = 0x23322e0, [0] = 4, [1] = 5, [2] = 6, [3] = 7
vb = move(va)
va: p = 0
vb: p = 0x23322c0, [0] = 0, [1] = 1, [2] = 2, [3] = 3


POCS: Propagate on Container Swap
va: p = 0x23322c0, [0] = 0, [1] = 1, [2] = 2, [3] = 3
vb: p = 0x23322e0, [0] = 4, [1] = 5, [2] = 6, [3] = 7
swap(va, vb)
va: p = 0x23322e0, [0] = 4, [1] = 5, [2] = 6, [3] = 7
vb: p = 0x23322c0, [0] = 0, [1] = 1, [2] = 2, [3] = 3

    Was sehen wir hier?
    POCCA: Die Elemente von va werden nach vb elementweise kopiert. Die Allokationen und Zeiger in beiden Vektoren werden nicht angerührt.

    POCMA: Die Allokation des Ziels wird gelöscht, der Zeiger von der Quelle ins Ziel transferiert und die Quelle auf nullptr gesetzt.

    POCS: Die beiden Zeiger werden vertauscht. Da IAE true ist, ist das auch valide.

    Das ganze nun für meinen NUMA-Allokatorsimulator

    POCCA false
POCMA false
POCS  false
IAE   false


POCCA: Propagate On Container Copy Assignment
MemoryPool::allocate   node=0 size=16 aligned_size=16 p=0x7f14697ac010
MemoryPool::allocate   node=1 size=16 aligned_size=16 p=0x7f14297ab010
va: p = 0x7f14697ac010, [0] = 0, [1] = 1, [2] = 2, [3] = 3
vb: p = 0x7f14297ab010, [0] = 4, [1] = 5, [2] = 6, [3] = 7
copy assigment va = vb
va: p = 0x7f14697ac010, [0] = 0, [1] = 1, [2] = 2, [3] = 3
vb: p = 0x7f14297ab010, [0] = 0, [1] = 1, [2] = 2, [3] = 3
MemoryPool::deallocate node=1 size=16 aligned_size=16 p=0x7f14297ab010
MemoryPool::deallocate node=0 size=16 aligned_size=16 p=0x7f14697ac010


POCMA: Propagate On Container Move Assignment
MemoryPool::allocate   node=0 size=16 aligned_size=16 p=0x7f14697ac010
MemoryPool::allocate   node=1 size=16 aligned_size=16 p=0x7f14297ab010
va: p = 0x7f14697ac010, [0] = 0, [1] = 1, [2] = 2, [3] = 3
vb: p = 0x7f14297ab010, [0] = 4, [1] = 5, [2] = 6, [3] = 7
vb = move(va)
va: p = 0x7f14697ac010
vb: p = 0x7f14297ab010, [0] = 0, [1] = 1, [2] = 2, [3] = 3
MemoryPool::deallocate node=1 size=16 aligned_size=16 p=0x7f14297ab010
MemoryPool::deallocate node=0 size=16 aligned_size=16 p=0x7f14697ac010


POCS: Propagate on Container Swap
MemoryPool::allocate   node=0 size=16 aligned_size=16 p=0x7f14697ac010
MemoryPool::allocate   node=1 size=16 aligned_size=16 p=0x7f14297ab010
va: p = 0x7f14697ac010, [0] = 0, [1] = 1, [2] = 2, [3] = 3
vb: p = 0x7f14297ab010, [0] = 4, [1] = 5, [2] = 6, [3] = 7
swap(va, vb)
va: p = 0x7f14297ab010, [0] = 4, [1] = 5, [2] = 6, [3] = 7
vb: p = 0x7f14697ac010, [0] = 0, [1] = 1, [2] = 2, [3] = 3
MemoryPool::deallocate node=1 size=16 aligned_size=16 p=0x7f14697ac010
terminate called after throwing an instance of 'std::runtime_error'
  what():  Node::deallocation failed
Abgebrochen (Speicherabzug geschrieben)

    POCCA: Es gibt keinen Unterschied.

    POCMA: Das funktioniert auch, und die Daten werden sogar kopiert. Das hätte man gar nicht erwartet. Die Allokation in der Quelle wird nicht gelöscht, aber der Container als leer makiert. Eigentlich hält der Compiler hier die Auflagen der Norm für Container nicht ein, aber erhält sich an die Vorgaben des Allokators.

    POCS: Hier wird es nun ganz wild. Es werden einfach die Zeiger vertauscht, obwohl genau das der Container gar nicht tun darf, da der Allocator weder IAE noch POCS als true definiert.

    //
// NUMA-AllocatorSimulator.h
//

#ifndef NUMA_alloc_sim_H_
#define NUMA_alloc_sim_H_

#include <algorithm>
#include <iostream>
#include <memory>
#include <vector>
#include <iterator>
#include <cstddef>
#include <cstdlib>
#include <new>
#include <boost/core/noncopyable.hpp>

/// Chunks are used to store all informations for each allocation.
struct Chunk {
	size_t	size_;
	void*	p_;

	/// @param [in] s Size of memory [chunk](@ref Chunk).
	/// @param [in] pointer The pointer to the memory [chunk](@ref Chunk).
	Chunk (const size_t s, void* const pointer) : size_(s), p_(pointer) {}
};

bool operator< (const Chunk& ck1, const Chunk& ck2);

/// @brief This function compares [Chunks](@ref Chunk) by their stored pointer address.
/// @param [in] ck1 Chunk
/// @param [in] ck2 Chunk
/// @return ck1.p_ < ck2.p_
bool operator< (const Chunk& ck1, const Chunk& ck2) {
	return (ck1.p_ < ck2.p_);
}

struct ChunkIndex {
	size_t	size_;
	size_t	index_;
};

bool operator< (const ChunkIndex& ci1, const ChunkIndex& ci2);

/// @brief This function compares [ChunkIndexes](@ref ChunkIndex) by their stored sizes.
/// @param [in] ci1 ChunkIndex
/// @param [in] ci2 ChunkIndex
/// @return ci1.size_ < ci2.size_
bool operator< (const ChunkIndex& ci1, const ChunkIndex& ci2) {
	return ci1.size_ < ci2.size_;
}

namespace {
	using IT = std::vector<Chunk>::iterator;
}

/// @brief The class Node manages the allocations for a simulated NUMA node.
///
///        Each Node allocates a big block of memory, and manages simulated
///        NUMA allocations by itself. Each NUMA allocation is stored in
///        a [chunk](@ref Chunk), which contains the address and the size of
///        the NUMA allocation. Each used [chunk](@ref Chunk) is stored in the
///        vector used_, and each freed [chunk](@ref Chunk) ist stored in the
///        vector free_.
///
class Node : private boost::noncopyable {
	/// The size of the simulated NUMA node memory.
	size_t size_;

	std::vector<Chunk> free_;
	std::vector<Chunk> used_;

	/// The pointer to the allocated simulated NUMA memory.
	std::unique_ptr<char, decltype (&free)> p_;
public:
	/// The MemoryPool class allocates a array of Nodes, so we cannot initialize
	/// the instances of class Node directly via the constructor.
	/// @post Both vectors are default constructed, size_ is set to zero and p_ is a nullptr.
	/// 
	Node () : size_(0), free_({}), used_({}), p_(nullptr, free) {}

	/// @brief Allocates the memory for the simulated NUMA node.
	/// @param [in] size Size of the simulated NUMA memory space.
	/// @pre size_ is zero and p_ is a nullptr.
	/// @post The memory is allocated and setup of Node is completed.
	/// @exception If size is zero, or [node](@ref Node) is allready
	///            initialized, or if the memory block is to large, then
	///            std::bad_alloc is thrown.
	/// If the init function is called a second time, std::runtime_error is thrown.
	void init (const size_t size) {
		void* temp_pointer = nullptr;

		// check the pre conditions and if the malloc is successfull
		if (0 != size_ || 0 == size) throw std::bad_alloc();
		if (nullptr == (temp_pointer = malloc(size))) throw std::bad_alloc();

		// store pointer and other stuff to meet post conditions
		this->p_ = std::unique_ptr<char, decltype (&free)> (static_cast<char*>(temp_pointer), free);
		size_ = size;

		Chunk ck (size, temp_pointer);
		this->free_.push_back(ck);
	}

	/// \brief Helper function which calculates a new pointer.
	/// \param [in] pointer The pointer to the allocated memory block.
	/// \param [in] size Size if allocated memory block.
	/// \return New pointer, which points to p+s.
	[[nodiscard]] void* generate_pointer_with_offset (void* const pointer, const size_t size) noexcept {
		// We have to cast to char*, because void* does not allow to do pointer arithmetics.
		char* new_pointer = static_cast<char*> (pointer);
		new_pointer += size;
		return static_cast<void*> (new_pointer);
	}

	[[nodiscard]] void* calculate_base_pointer (void* const pointer, const size_t size) noexcept {
		char* base_pointer = static_cast<char*> (pointer);
		base_pointer -= size;

		return static_cast<void*> (base_pointer);
	}

	/// @brief This is a special allocation function.
	/// @param [in] size of the allocation
	/// @pre   free_ is sorted by size of chunk.size_ 
	/// @post  todo
	[[nodiscard]] void* allocate (const size_t size) {
		if (0 == size) return nullptr;
		if (size_ < size) throw std::bad_alloc();

		void* new_pointer = nullptr;
		bool found = false;
		const size_t end = free_.size();
		std::vector<Chunk>::size_type pos = 0;

		std::vector<ChunkIndex> freeIndex(free_.size());
		for (size_t i = 0; i < end; ++i) {
			freeIndex[i] = {free_[i].size_, i};
		}
		sort (freeIndex.begin(), freeIndex.end());

		for (size_t i = 0; i < end; ++i) {
			if (freeIndex[i].size_ >= size) {
				pos = i;
				found = true;
				break;
			} 
		}

		if (!found) throw std::bad_alloc();

		IT it = free_.begin() + std::vector<Chunk>::difference_type (pos);
		new_pointer = it->p_;
		Chunk ck {size, new_pointer};
		it->p_     = generate_pointer_with_offset (it->p_, size);
		it->size_ -= size;

		IT position = upper_bound (used_.begin(), used_.end(), ck);
		used_.insert (position, ck);
		if (0 == it->size_) free_.erase(it);

		std::cout << " p=" << new_pointer << "\n";

		return new_pointer;
	}

	/// @brief Deallocation function
	/// @param [in,out] pointer memory to be free
	/// @param [in] size and the size
	/// @pre The pointer p must be poiting to memory allocated for node \p node. I.e. p must be in the nodes_.used_ vector.
	/// @post Test
	void deallocate (void* pointer, const size_t size) {
		if (nullptr == pointer) return;

		Chunk ck = {size, pointer};
		std::pair<IT,IT> pair = std::equal_range (used_.begin(), used_.end(), ck);

		if (pair.first == used_.end()) {
			throw std::runtime_error ("Node::deallocation failed");
		}

		used_.erase(pair.first);

		IT position = std::upper_bound (free_.begin(), free_.end(), ck);

		free_.insert (position, ck);

		// searching for Chunks which can be merged with this chunk
		recycle();
	}

	/// \brief This function 
	void recycle() {
		if (free_.size() <= 1) return;

		std::vector<Chunk> fs (free_);
		std::sort(fs.begin(), fs.end());

		const size_t e = fs.size();

		///todo nachbesser mit der Recycle Funktion
		for (size_t i = (e - 2); i > 0; --i) {
			char* p = static_cast<char*> (fs[i].p_);
			char* q = p + fs[i].size_;

			if (q == fs[i+1].p_) {
				fs[i].size_ += fs[i+1].size_;
				IT it = next(fs.begin(), std::vector<Chunk>::difference_type(i+1));
				fs.erase(it);
			}
		}

		swap(fs, free_);
		sort(free_.begin(), free_.end());
	}
};

class MemoryPool : private boost::noncopyable {
private:
	int                     n_nodes_;
	std::unique_ptr<Node[]> nodes_;
public:
	~MemoryPool () = default;

	[[nodiscard]] constexpr size_t calculate_aligned_size (size_t const size) const {
		constexpr size_t alignment = alignof(max_align_t);
		size_t aligned_size = 0;

		if (0 == (size % alignment)) {
			aligned_size = size;
		} else {
			aligned_size = ((size / alignment) + 1) * alignment;
		}

		return aligned_size;
	}

	/// \brief This constructor 
	/// \param [in] number_nodes The number of NUMA nodes to simulate.
	/// \param [in] size The memory size of each simulated NUMA node. This size will be adjusted to multiples of align_of(std::max_aligned_t).
	MemoryPool (const int number_nodes, const size_t size) : n_nodes_(number_nodes), nodes_(new Node[size_t(number_nodes)]) {
		size_t aligned_size = calculate_aligned_size(size);

		for (int i = 0; i < n_nodes_; ++i) {
			this->nodes_[size_t(i)].init(aligned_size);
		}
	}

	/// \brief This function allocates @p n memory on simulated NUMA node @p node.
	/// \param [in] size The size of the allocation.
	/// \param [in] node On which simulated NUMA node the allocation should be done.
	/// \return Pointer to newly allocated memory.
	/// @exception If node does not reference an simulated NUMA node or
	[[nodiscard]] void* allocate (const size_t size, const int node) {
		std::cout << "MemoryPool::allocate   node=" << node << " size=" << size;
		if ((0 > node) || (n_nodes_ <= node)) throw std::runtime_error ("allocate failed; node number is incorrect");

		size_t aligned_size = calculate_aligned_size(size);
		std::cout << " aligned_size=" << aligned_size;

		return this->nodes_[size_t(node)].allocate (aligned_size);
	}

	/// \brief Special deallocation function.
	/// @param [in] pointer Pointer which should be freed.
	/// @param [in] size The size of the allocation.
	/// @param [in] node The node of allocation.
	void deallocate (void* pointer, const size_t size, const int node) {
		size_t aligned_size = calculate_aligned_size(size);
		std::cout << "MemoryPool::deallocate node=" << node << " size=" << size << " aligned_size=" << aligned_size << " p=" << pointer << std::endl;
		this->nodes_[size_t(node)].deallocate(pointer, aligned_size);
	}
};

/// \brief This allocator class simulates
/// \tparam T any possible type
template <typename T>
class NUMA_alloc_sim {
		int node_;
		std::shared_ptr<MemoryPool> smp_;
	public:
		using value_type 		= T;
		using size_type			= size_t;

		// The new approach for allocators is they do not define these values,
		// if they are false. So for testing purposes, these lines are present
		// but not used.
		//using propagate_on_container_copy_assignment = std::false_type;
		//using propagate_on_container_move_assignment = std::false_type;
		//using propagate_on_container_swap            = std::false_type;
		//using is_always_equal                        = std::false_type;

		~NUMA_alloc_sim() = default;
		/// @param [in] node ssss
		/// @param [in] smp A shared Memory Pool
		NUMA_alloc_sim (const int node, std::shared_ptr<MemoryPool> smp) noexcept : node_(node), smp_(smp) {}
		NUMA_alloc_sim () noexcept : node_(0), smp_(nullptr) {}
		NUMA_alloc_sim (const NUMA_alloc_sim& rhs) noexcept = default;
		template <class U> NUMA_alloc_sim (const NUMA_alloc_sim<U>& rhs) noexcept;
		NUMA_alloc_sim (NUMA_alloc_sim&&) = default;
		NUMA_alloc_sim& operator= (const NUMA_alloc_sim&) = default;
		NUMA_alloc_sim& operator= (NUMA_alloc_sim&&) = default;

		[[nodiscard]] inline T* allocate (const size_type n) {
			return static_cast<T*> (this->smp_->allocate(sizeof(T)*n, this->node_));
		}
		inline void deallocate (T* p, const size_type n) {
			this->smp_->deallocate(p, n*sizeof(T), this->node_);
		}
		template <typename U> friend bool operator== (const NUMA_alloc_sim<U>&, const NUMA_alloc_sim<U>&);
		template <typename U> friend bool operator!= (const NUMA_alloc_sim<U>&, const NUMA_alloc_sim<U>&);
		template <typename U, typename V> friend constexpr bool operator== (const NUMA_alloc_sim<U>& lhs, const NUMA_alloc_sim<V>& rhs);
		template <typename U, typename V> friend constexpr bool operator!= (const NUMA_alloc_sim<U>& lhs, const NUMA_alloc_sim<V>& rhs);
};

template <typename U>
bool operator== (const NUMA_alloc_sim<U>& lhs, const NUMA_alloc_sim<U>& rhs) {
	return (lhs.node_ == rhs.node_);
}

template <typename U>
bool operator!= (const NUMA_alloc_sim<U>& lhs, const NUMA_alloc_sim<U>& rhs) {
	return (lhs.node_ != rhs.node_);
}

template <class U, class V>
constexpr bool operator== (const NUMA_alloc_sim<U>& lhs [[maybe_unused]], const NUMA_alloc_sim<V>& rhs [[maybe_unused]]) {
	return false;
}

template <class U, class V>
constexpr bool operator!= (const NUMA_alloc_sim<U>& lhs [[maybe_unused]], const NUMA_alloc_sim<V>& rhs [[maybe_unused]]) {
	return true;
}

#endif /* NUMA_alloc_sim_H_ */

    Und dann Testcode mit -DTEST kann man zwischen Standard Allokator und NUMA-Simulator Allokator umschalten.

    //
// test4.cc
//
#include <iostream>
#include <memory>
#include <vector>
#include <cstdlib>
#include <string>

#ifdef TEST
#include "NUMA-AllocatorSimulator.h"
#endif

void
print_vector (char const* const name, auto& v) {
	std::cout << name << ": p = " << static_cast<void*>(&(v[0]));
	auto s = v.size();
	for (size_t i = 0; i != s; ++i) {
		std::cout << ", [" << i << "] = " << v[i];
	}
	std::cout << "\n";
}

int main () {
#ifdef TEST
	constexpr size_t size = 1024L*1024L*1024L;

	using Allocator = NUMA_alloc_sim<int>;
	using vec = std::vector<int,Allocator>;

	std::shared_ptr<MemoryPool> smp = std::make_shared<MemoryPool> (2, size);
	Allocator na(0, smp), nb(1, smp);
#else
	using Allocator = std::allocator<int>;
	using vec = std::vector<int>;

	Allocator na, nb;
#endif
	std::cout << "\n\nPOCCA ";
	if constexpr (std::allocator_traits<Allocator>::propagate_on_container_copy_assignment::value) {std::cout << "true\n";} else {std::cout << "false\n";}
	std::cout << "POCMA ";
	if constexpr (std::allocator_traits<Allocator>::propagate_on_container_move_assignment::value) {std::cout << "true\n";} else {std::cout << "false\n";}
	std::cout << "POCS  ";
	if constexpr (std::allocator_traits<Allocator>::propagate_on_container_swap::value) {std::cout << "true\n";} else {std::cout << "false\n";}
	std::cout << "IAE   ";
	if constexpr (std::allocator_traits<Allocator>::is_always_equal::value) {std::cout << "true\n";} else {std::cout << "false\n";}
	std::cout << "\n\n";


	using size_type = std::allocator_traits<Allocator>::size_type;
	size_type m = 4;

	std::cout << "POCCA: Propagate On Container Copy Assignment\n";
	{
		vec va(m, na);
		vec vb(m, nb);

		for (size_type i = 0; i < m; ++i) {
			va[i] = vec::value_type(i);
			vb[i] = vec::value_type(m+i);
		}

		print_vector("va", va);
		print_vector("vb", vb);

		std::cout << "copy assigment va = vb" << std::endl;
		vb = va;

		print_vector("va", va);
		print_vector("vb", vb);
	}
	std::cout << "\n" << std::endl;


	std::cout << "POCMA: Propagate On Container Move Assignment\n";
	{
		vec va(m, na);
		vec vb(m, nb);

		for (size_type i = 0; i < m; ++i) {
			va[i] = vec::value_type(i);
			vb[i] = vec::value_type(m+i);
		}

		print_vector("va", va);
		print_vector("vb", vb);

		std::cout << "vb = move(va)" << std::endl;
		vb = move(va);

		print_vector("va", va);
		print_vector("vb", vb);
	}
	std::cout << "\n" << std::endl;

	std::cout << "POCS: Propagate on Container Swap\n";
	{
		vec va(m, na);
		vec vb(m, nb);

		for (size_type i = 0; i < m; ++i) {
			va[i] = vec::value_type(i);
			vb[i] = vec::value_type(m+i);
		}
		print_vector("va", va);
		print_vector("vb", vb);

		swap(va, vb);
		std::cout << "swap(va, vb)\n";

		print_vector("va", va);
		print_vector("vb", vb);
	}
	std::cout << std::endl;
}
    0

  • Könnt ihr euch zum Schwanzvergleich bitte woanders verabreden?

    Bei manchen eurer Diskussion nehme ich ja noch was Brauchbares mit, aber aus dem hier ... nicht.

    0
  • Mod

    @john-0 sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

    Du verstehst hier an der Sache vieles nicht.

    Lies http://eel.is/c++draft/default.allocator#allocator.members-5.sentence-2 (welches Deinen fettgedruckten Satz widerlegt) und ausserdem die Paragraphen, die erklaeren, dass Zeigerarithmetik mit einem Zeiger der nicht auf ein Array Element zeigt, undefiniert ist.

    Und dann realisierst Du vielleicht weshalb allocate ein Array Objekt kreiert. Oder vielleicht auch nicht. Weiter erklaeren ist, wie mein Vorposter wohl erkannt hat, zwecklos.

    Bei manchen eurer Diskussion nehme ich ja noch was Brauchbares mit, aber aus dem hier ... nicht.

    Es ist schwer, ihn zu ignorieren, wenn er mit voll aufgepumpten Selbstbewusstsein anfaengt, inkorrekte Tiraden ueber teils tangentiale Probleme zu posten. Das hat sogar gewisse Parallelen mit mir vor 10 Jahren (wahrscheinlich ist John auch Teenager). Und wer nach wiederholter Zurechtweisung immer noch Recht behalten will, provoziert auch.

    1 1 Antwort

  • Ja, es hat nen Grund warum ich manche Benutzer geblockt habe.
    Ein Vorteil davon kein Mod zu sein 🙂

    0 1 Antwort
  • Mod

    @hustbaer sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

    Ja, es hat nen Grund warum ich manche Benutzer geblockt habe.
    Ein Vorteil davon kein Mod zu sein 🙂

    Ohne Scherz, der größte Nachteil am Modsein 🙂

    0
  • Mod

    @hustbaer Der erste Tag, an dem NodeBB hellbans unterstuetzt........ 🕶

    @SeppJ Fuer mich persoenlich mehr, dass ich nicht wirklich verbalisieren darf, was ich von einigen Leuten halte.... wobei Volkard da auch eine andere Etiquette hatte....

    0

  • @Columbo sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

    Das hat sogar gewisse Parallelen mit mir vor 10 Jahren (wahrscheinlich ist John auch Teenager).

    Top Reflektion, Hut ab.

    0
  • *

    @DocShoe sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

    Könnt ihr euch zum Schwanzvergleich bitte woanders verabreden?

    Der Thread könnte schon lange beendet sein, wenn Columbo in der Lage wäre die Textstelle in der Norm zu nennen, die die angebliche oder tatsächliche Garantie widerspiegelt. Ich kenne sie nicht, und hätte gerne eine fundierte Aussage dazu. Leider ist er dazu nicht der Lage, und nennt irgend etwas anderes was nicht zutreffend ist.

    Bei manchen eurer Diskussion nehme ich ja noch was Brauchbares mit, aber aus dem hier ... nicht.

    Sorry, aber wenn ich etwas hier im Forum postet triggert das oftmals Columbo.

    @Columbo
    Mein lieber Columbo,
    jeder Mensch macht Fehler. Insbesondere macht man dann Fehler, wenn man so Texte wie die ISO Norm bzw. deren Drafts interpretiert. Mir geht es lediglich darum, ob ich eine Stelle in der Norm übersehen habe, in der ein spezielles Speicherlayout für einen z.B. std::vector<uint8_t> verboten wäre, und deshalb hätte ich halt gerne den Verweis auf die Stelle der Norm (und da wäre nicht der WIP Draft sinnvoll, sondern der letzte Draft vor der offiziellen Ausgabe der Norm für C++20 ist das N4861) an der steht, dass das nicht erlaubt ist.

    Das Nachfolgende in Pseudocode

    // N ist ein Vielfaches von alignof(max_align_t)
struct MediumVector {
    uint16_t capacity;
    uint8_t data[N-4];
    uint16_t size;
};

template vector<typename T, template <typename> Allocator = std::allocator<T>> {
Allocator a;
T* data;
};

    Das Datenfeld für den vector<uint8_t> wird dann so interpretiert wie MediumVector, und natürlich geht das von der Zeigerarithmetik, und casten kann man das auch, weil das Alignment stimmt. Nur den Zeiger auf das erste Element ließe sich dann nicht auf uint32_t* casten. Die Frage war, gibt es eine Stelle in der Norm, die besagt, dass man so das Datenfeld nicht auslegen darf? Es steht außer Frage, dass man das normalerweise so nicht macht.

    Das hat sogar gewisse Parallelen mit mir vor 10 Jahren (wahrscheinlich ist John auch Teenager).

    Man merkt allen Deinen Antworten an, dass Du Dir wenig bis gar keine Mühe bei den Antworten machst. Weshalb das hier so offensichtlich ist. Du hättest mal nachschauen können seit wann ich Mitglied im Forum bin. Kurzform: ich bin 6 Jahre länger dabei als Du, kann ich dann ein Teenager sein?

    Und wer nach wiederholter Zurechtweisung immer noch Recht behalten will, provoziert auch.

    Das Forum dient zum Meinungsaustausch und die Aufgabe eines Mods ist es nicht bei inhaltlichen Differenzen Nutzer „zurecht zu weisen“. Wenn Du Dich dadurch provoziert fühlst, dass ich Dich fortlaufend darauf hinweisen muss, dass die von Dir gegebenen Antworten die ursprüngliche Fragestellung eben nicht hinreichend beantworten, ist das keine Provokation sondern Teil einer inhaltlich sachlichen Diskussion. Wenn von Deiner Seite kein Interesse an der Fortsetzung der Diskussion besteht, kann man diese auch sachlich beenden. Noch wirst Du von irgend jemanden hier im Forum dazu gezwungen mir überhaupt zu antworten.

    0
  • Mod

    Ich habe mal nach oben gescrollt, und tatsaechlich, ich habe ein einziges Mal die Aussage getroffen, die Ausrichtung waere so vom Standard gefordert. Und ich vermute, dass LWG kein Interesse daran hat, eine Aussage wie "vector places its elements into the first allocated byte" in den Standard zu schreiben. Weil niemand vector<> als char Array fuer andere Objekte zweckentfremdet und eine derartige Vorgabe anderweitig nicht wirklich relevant (und prinzipiell einschraenkend) ist. Deshalb lautet die Antwort, es ist nicht unmittelbar formal so vorgeschrieben, aber alles andere waere extrem pathologisch und wuerde bei Bedarf auch vom LWG verboten werden. Das war auch die Meinung die ich zu vertreten gesucht habe. Deine obige Skizze ist bspw. unnoetig ineffizient, weil jeder size() Aufruf einen Nulltest + add/indirection ausfuehren muss.

    Ich habe auch mindestens einmal klargestellt, dass ich ueberhaupt nicht dafuer plaediere davon abhaengig zu sein, bzw. suggeriert dass ich nicht vertraue, nach dem Hantieren mit Paragraphen irgendeine verlaessliche Abhaengigkeit bewiesen zu haben:

    Ich bin übrigens auch kein Fan davon, von irgendwelchen abstrusen alignment Bedingungen interner Speicher abhängig zu sein, weshalb ich einfach memcpy anwenden würde, wie bereits erwaehnt. [...]

    In der Realitaet befolgen die Autoren der stdlib diese Schlussfolgerung (und auch Exegese) nicht.

    Den Rest von Deinem passiv-aggressiven Traktat brauche ich gar nicht mehr durchzulesen. Edit: Joa, ich glaub der Ton ist unsachlich. Wir koennen zu machen.

    0
Anmelden zum Antworten