Discussion :

[BioKore]

Bonjour à tous,

Au cours de mes "exercices", je me suis posé la problématique suivante : "Comment découper un vecteur (ou mieux, une plage mémoire donnée) de données contigües en plusieurs vecteurs différents, SANS perdre pour autant la contiguïté de la plage de données initiale ?"
Je ne le cacherais pas, l'objectif derrière tout ça est de pouvoir manipuler des portions de la mémoire allouée initialement de manière indépendante, et permettre une itération sur l'ensemble des données initiales, le tout sur une plage de données contiguës.

Dans un premier temps, je considère que, lors de l'ajout d'un élément d'un "sous_vecteur", l'ensemble des données suivantes sont simplement poussées les unes après les autres.

Pour ce premier aspect, je visualise plutôt bien les choses. Là où ça se gâte, c'est comment m'assurer que l'ensemble des vecteurs liés à la "Base" (le block de mémoire contenant l'ensemble des éléments) sont bien systématiquement décalés ?

Pour réaliser ça, j'ai tenté de procéder de deux manières différentes :
- en manipulant des pointeurs bruts... Méthode classique (ou presque)
- en manipulant des vecteurs (std::vector).

J'ai donc réussi à peu près à atteindre l'objectif, mais les implémentations générées ne me plaisent pas du tout, le système pondu semble à la fois fragile et hyper rigide à l'utilisation, bref, je dois refondre le code de A à Z.
Je suis très surpris de me retrouver à buter sur un tel sujet qui me semble, dans l'idée en tout cas, très simple....

Mes questions sont donc les suivantes :
- Que pensez-vous des méthodes proposées ?
- connaissez-vous des méthodes alternatives plus simples à mettre en œuvre ?
- Sauriez-vous m’orienter vers des sources d'inspiration pour implémenter un tel système ?

Bref, toute aide est la bien-venue... Pour aider un peu la compréhension, voici, in fine, comment je vois l'utilisation de cet outil :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
global_memory<int> base;
sub_vector<int> v1 = base.generate_vector(); // renvoie un vecteur(ou un simple tableau, peu importe) pointant uniquement sur une portion de "base"
sub_vector<int> v2 = base.generate_vector(); // typiquement, v2.begin() == v1.end() == &base[v1.size()]
 
v1.push_back(3);	// ici, v1.size() augmente, donc, v1.end() aussi, donc, v2.begin() aussi !
v2.push_back(5);	// ici, seul v2 est affecté, car v1 a été initialisé avant... 
 
sub_vector<int> v3 = base.generate_vector();	// là aussi, v3.begin() == v2.end() == &base[v1.size() + v2.size()]

Espérant trouver une solution aisée à mettre en œuvre...

[jo_link_noir]

En fait ce que tu veux, c'est une vue mutable. Généralement, une vue sur une séquence ne change pas la taille, mais agrandir la séquence d'origine invalide la vue lorsqu'il y a une nouvelle allocation, car la vue ne modifie pas sa plage de valeur et reste donc avec l'ancienne (qui est supprimée). Faire une synchronisation avec les vues et le segment d'origine complexifie grandement le problème.

Une manière de faire, et c'est peut-être celle que tu as choisie, consiste à avoir l'ensemble des vues à l'intérieur du l'objet global et les sub_vector contiendrait 2 pointeurs: un sur la position de la vue, l'autre sur l'objet global. Comme ça lorsque l'objet global ajoute des éléments, il peut actualiser chaque intervalle des sub_vector.

Après il y a toute une problématique de durée de vie des sub_vector et comment ils doivent se comporter lorsqu'ils sont détruits dans le désordre si cela est autorisé. En plus, la synchronisation prend probablement plus de temps qu'un simple ajout et concaténer tous les vecteurs peut s'avérer plus efficace. Je pense que pour avoir quelque chose qui fonctionne bien il faudrait savoir exactement quelle est la problématique et quelles sont les contraintes.

Par exemple, si le but et parcourir plusieurs conteneurs comme un seul, alors la solution est un itérateur spécialisé. Si le nombre de vue est connue, le problème est simplifié. Idem si le nombre d'élément total est connu. Permettre la synchronisation post-insertion sera plus efficace que le faire pour chaque insertion. Etc

[BioKore]

Bonjour, et merci beaucoup pour ce retour, qui tombe justement.... Au moment où je viens d'arriver à faire une implémentation potable et fonctionnelle (mais qui reste à finaliser et à refaire au propre... c'est plus un "proof of concept" pour le moment) !

Pour la problématique, c'est simplement dans la continuité de mon passe-temps actuel qui se résume à faire un ECS adaptable au besoin. J'ai bien conscience que la solution que je propose ici n'en est qu'une parmi tant d'autres qui peuvent probablement être plus simples, mais dans toutes les versions d'ECS que j'ai réalisé, je me trouvais finalement à devoir ajouter un composant à une entité juste pour pouvoir déterminer son type, et finalement devoir itérer sur le type plutôt que sur les composants réellement importants. Par exemple, pour reprendre l'exercice de javaquarium, si je souhaite n'afficher que le nom des poissons et non des algues, je me retrouve à devoir itérer sur le type, puis sur le nom, ce que je trouve idiot (et encore plus si on ne souhaite afficher que les poissons qui ont un nom précis, un sexe précis, un age précis etc...).
Avec la solution proposée ici, je pourrais itérer, soit sur tous les noms de la base de données, soit uniquement sur les noms des poissons, soit uniquement sur les noms des algues... Et dans tous les cas, les données sont continues ce qui limite les cache-misses, et malgré tout l'outil reste utilisable comme les ECS standard que j'ai réalisé jusqu'à présent si c'est ce que l'on souhaite.

En fait, comme tu dis, j'ai réalisé un tableau dynamique basique (en gros, j'ai ré-implémenté une sorte de std::vector mais avec le strict minimum nécessaire), qui contiens aussi un tableau de mini-structures contenant uniquement un offset (de type T*) et une taille.
Compte tenu du fait que les "sous_vecteur" sont nécessairement reliés à un tableau global (baptisé "memory" dans mon implémentation actuelle), alors c'est cette classe "memory" qui va attribuer un id unique aux sous_vecteurs, id qui sera en réalité l'index correspondant du tableau de mini structures.

en gros :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
40
41
42
43
44
45
46
47
template<typename T>
class sub_vector
{
 
private:
 
	std::size_t idx;
	memory<T>* mem;
 
public:
	sub_vector(std::size_t const & id, memory<T>* m_): idx{id}, mem{m_} {}
 
};
 
template<typename T>
struct frame
{
	T* offset;
	std::size_t size_;
};
 
template<typename T>
class memory
{
private:
 
	T* values_;
	std::size_t capacity_;
	std::size_t size_;
 
	std::vector<frame<T> > frame_;
 
public:
 
	memory(std::size_t const & new_capacity): values_{m_alloc().allocate(new_capacity)}, 
											capacity_{new_capacity}, size_{0}
	{
	}
 
	sub_vector<T> create_vector()
	{
		frame_.push_back(frame<T>{end(), 0});
 
		return sub_vector<T>{frame_.size()-1, this};
	}
 
};

Je mettrais un code complet quand je l'aurais refait au propre, mais les quelques lignes ci-dessus illustrent à peu près les interactions entre ces classes.

Concernant l'ajout d'éléments, le code reste là aussi très simple, et consiste à "swap" les éléments de début et de fin de chaque frame jusqu'à ce que l'élément appartienne à la bonne frame :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void push(std::size_t const & id, T const & val)
{
	assert(is_valid_table(id) && "no created id");
 
	values_[size_] = val;
	size_++;
 
	for(auto i = frame_.size()-1; i != id; --i)
	{
		swap(end(i), begin(i));
		frame_[i].offset_ = ++;
	}
 
	frame_[id].size_++;
}

A savoir, les méthodes begin() et end() sont surchargées de manière à retourner respectivement le début et la fin de chaque frame.

En fin, à l'utilisation, je retrouve le code suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
int main()
{
	memory<int> global;
	//global.push(0, 5);  // peut aussi être utilisé en dirrect
 
	sub_vector<int> mv = global.create_vector();
	mv.push(12);
	mv.push(87);
 
	sub_vector<int> cv = global.create_vector();
	cv.push(128);
	cv.push(692);
 
	mv.push(57);
	mv.push(36);
 
	cv.push(458);
 
	for(auto it {mv.begin()}; it != mv.end(); ++it)
	{
		std::cout << *it << std::endl;
	}
 
	std::cout << std::endl;
	for(auto it {cv.begin()}; it != cv.end(); ++it)
	{
		std::cout << *it << std::endl;
	}
 
	std::cout << std::endl;
	for(auto it {global.begin()}; it != global.end(); ++it)
	{
		std::cout << *it << std::endl;
	}
 
 
	return 0;
}

Et ça fonctionne bien. L’opérateur operator[] est bien entendu lui aussi intégré.


Il me reste à implémenter la partie "suppression" des éléments, et aussi, comme tu le soulignes, des sub_vector.
Pour le premier point, sans trop se casser la tète, ce qui me vient à l'esprit, c'est la même méthode que push() mais en fonctionnement inverse... Il me reste à réfléchir à ça, mais là comme ça, cela devrait marcher.
Pour supprimer une table et bien.... La aussi je dois y réfléchir, mais à mon avis, le but est de supprimer tous les éléments de la table un par un selon la méthode proposée ci-dessus (donc O(log(n)) malheureusement). Sinon, une méthode un peu plus brutale (surtout si on a beaucoup de sub_vectors et beaucoup d'éléments): une réallocation de toute la table globale...

Pour tes derniers points d'interrogation, tout doit être "dynamique" donc nombre de sub_vector non fixé, nombre d'éléments non fixés etc.... Pour cette raison, l'allocation initiale de base de la table "globale" doit être tout de même assez juste si on ne souhaite pas tout ré-allouer à la volée toutes les deux minutes.
Techniquement, pour les applications que j'imagine, je ne devrais pas avoir à supprimer de sub_vector très souvent. Je pourrais effectivement presque être capable de déterminer leur nombre à l'avance, mais j'aime autant que ce soit dynamique.


Selon vous, cette méthode semble-t-elle viable pour la suite ?

Merci.

[Bousk]

std::span, disponible en C++20.
Pour le moment, tu peux créer ton propre truc, c'est rien de plus que

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
template<class T, size_t size>
class VectorView
{
T* mData;
size_t mDataSize;
};

Mais bien sûr les push_back suivant peuvent invalider les pointeurs.
Si tu veux pouvoir créer ces vues puis push_back, préfère un

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
template<class T, size_t size>
class VectorView
{
public:
VectorView(vector<t>& vec, size_t first, size_t size);
T& operator[](size_t idx) { assert(idx >= mOffset && idx < mOffset + mDataSize); return mData[mOffset + idx];
private:
std::vector<T>& mData;
size_t mOffset;
size_t mDataSize;
};

[BioKore]

Bonjour,

Oui, ça ressemble effectivement beaucoup à std::span !

En ce qui concerne ta proposition d'implémentation, je suis justement en train de voir comment je peux faire avec des std::vector plutôt que des pointeurs bruts.
L'idée de l'opérateur [] directement dans le vectorView est bonne, cependant, lorsque l'on ajoute où supprime des éléments, des swap sont réalisés (j'ai ajouté la fonctionnalité de suppression hier soir btw). Il est donc nécessaire que l'accès aux éléments du vectorView soient indexés.

Dans le bout de code que j'ai présenté hier, j'ai donc dû ajouté un index aussi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
template<typename T>
	struct frame
	{
		std::size_t id_;
		T* data_;
		std::size_t size_;
 
		std::vector<std::size_t> index{};
	};

Ca marche, mais le code final au complet reste "moche" (ressemble beaucoup à de l'hybride C - C++, j'aime pas trop ça...).
Je vais voir ce que j'arrive à faire en ne me basant que sur des std::vector ; car au final, je ne vois rien qui justifie de conserver un tableau dynamique de type C.

Merci pour ce retour !



EDIT : je remarque aussi que dans la solution proposée, on se retrouve, dans le vectorView, avec une référence sur le vecteur complet. Ceci n'est-il pas trop gourmand au niveau de la RAM ?

---

Bon, j'ai refait l'ensemble du système, avec des std::vector cette fois ci.
J'y gagne un tout petit peu en terme de lisibilité, mais c'est tout de même bien améliorable. Je me demande si le code ne devrais pas être splité en plus de classes.
Pour le moment j'ai :

• une classe sector : celle qui gère l'allocation des secteurs en ram (les "grands" vecteurs principaux)
• une classe frame : la classe sector contiens un vecteur de frame. C'est en fait les "vectorView". Cette classe contiens aussi l'indexe des données qui lui sont liées
• une classe fragment : correspond à un fragment de chaque secteur. C'est ce que manipule l'utilisateur.

Quoi qu'on puisse dire de l'implémentation de tout ça, l'utilisation correspond à ce que je souhaitais :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
fragment<int> a_frag;	// création d'un fragment, relié à un secteur générique (statique)
a_frag.push(4);
a_frag.push(68);
// [...]
a_frag.pop(0)	// suppresion de l'élément 0 ; ici 4
 
fragment<int> a_bis;
a_bis.push(12);
 
assert(a_frag[0] != a_bis[0]);
 
sector<int> int_sec;	// création d'un nouveau secteur de int
fragment<int> b_frag(&int_sec);	// création d'un fragment, relié au secteur souhaité
b_frag.push(87);
b_frag.push(324);
 
sector<std::string> str_sec;
fragment<std::string> c_frag(&str_sec);
c_frag.push("un string");
c_frag.push("une autre");
c_frag.push("etc...");

En gros, quasiment comme un simple vecteur, à la différence que je peux itérer sur toutes les valeurs d'un secteur.

Je suis content du résultat, mais moins de la gueule du code.

Voici, par exemple, la classe "sector" (celle sur laquelle tout repose) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
template<typename T>
class sector
{
private:
 
	std::vector<T> data_;
	std::size_t size_;
 
	std::vector<frame<T> > frame_;
 
 
public:
 
	using iterator = typename std::vector<T>::iterator;
	using const_iterator = typename std::vector<T>::const_iterator;
 
	sector(std::size_t const & cap=500): size_{0} { data_.reserve(cap); }
 
	std::size_t create_frame()
	{
		frame_.push_back(frame<T>{frame_.size(), data_, size_, 0});
 
		return frame_.size()-1;
	}
 
	void push(std::size_t const & fid, T const & val)
	{
		data_.push_back(val);
 
		for(auto i = frame_.size()-1; i > fid; --i)
		{
			std::swap(*begin(i), *end(i));
			frame_[i].first_++;
			frame_[i].index_[0] = frame_[i].size_-1;
		}
 
		frame_[fid].add_index(frame_[fid].size_);
 
		frame_[fid].size_++;
		size_++;
	}
 
	void pop(std::size_t const & fid, std::size_t const & idx)
	{
		std::swap(frame_[fid][idx], *(end(fid)-1));
		frame_[fid].swap_indexes(frame_[fid].size_-1, idx);
		--frame_[fid].size_;
 
		for(auto i = fid+1; i != frame_.size(); ++i)
		{
			--frame_[i].first_;
			frame_[i].swap_indexes(frame_[i].size_-1, 0);
			std::swap(*begin(i), *end(i));
		}
 
		data_.erase(end()-1);
		frame_[fid].pop_index(idx);
 
		--size_;
	}
 
	T & get(std::size_t const & fid, std::size_t const & idx)
	{
		return frame_[fid][idx];
	}
 
 
 
	iterator begin()
	{
		return data_.begin();
	}
 
	iterator end()
	{
		return data_.end();
	}
 
	std::size_t const & size() const
	{
		return data_.size();
	}
 
	iterator begin(std::size_t const & id)
	{
		return begin() + frame_[id].first_;
	}
 
	iterator end(std::size_t const & id)
	{
		return begin(id) + frame_[id].size_;
	}
 
	std::size_t const & size_of_frame()
	{
		return frame_.size();
	}
};

J'aimerais rendre ça plus lisible, compréhensible, et surtout, simplifier ce qui peut l'être...
Peut-être avez-vous des idées à ce sujet ?
J'imagine qu'il n'est pas simple de comprendre ce code sans avoir les autres éléments, mais le post risque de prendre plus d'une page sinon. Je posterais les deux autres classes si vous le souhaitez...


Qu'en pensez-vous ?

[bacelar]

Je comprend pas trop la problématique dans une approche ECS.

Dans une approche ECS, chaque système maintient une liste d'élément ayant un nombre d'attribut FIXE, qui lui est nécessaire pour travailler (le système), triés selon un ordre qui permet d'avoir la meilleure performance du système.
Donc un système = une liste d'élément (peut-être finie) de taille FIXE (les éléments).
Dans les attributs des éléments, il y a l'id de l'entité ainsi qu'un flag pour savoir si l'élément est toujours valide.
Avec ce boolean "valide", il est possible de régulièrement compacter cette liste.

Il n'y pas de pointeur/références qui doivent se balader entre les systèmes.

Si vous devez passer des attributs d'un système à un autre, c'est toujours via des tables d'index d'indirection, donc le contenu sera à customiser en fonction des besoins.

La redondance de l'information n'est pas un problème.