Tout programmeur bénéficiera d'une compréhension des différentes
structures de données et de la manière d'analyser leurs performances. Mais dans la pratique, je n'ai jamais été utile pour
les arbres AVL, les arbres rouge-noir, les arbres préfixes ,
les listes à sauter , etc. J'utilise certaines structures de données pour un seul algorithme spécifique et rien de plus (par exemple, des
tas pour implémenter une
file d'attente prioritaire dans
l'algorithme de recherche de chemin A * ).
Dans le travail quotidien, je fais habituellement avec étonnamment peu de structures de données. Le plus souvent, ils me sont utiles:
- Matrices de données partagées (données en masse) - un moyen de stocker efficacement un grand nombre d'objets.
- Références (ou poignées ) faibles - un moyen d'accéder aux objets dans les données en masse sans que le programme se bloque si l'objet est supprimé.
- Les index sont un moyen d'accéder rapidement à des sous-ensembles individuels dans des données en masse.
- Les tableaux de tableaux sont un moyen de stocker des objets de données en vrac avec des tailles dynamiques.
Je vais consacrer plusieurs articles à la façon dont j'implémente habituellement toutes ces structures. Commençons par les données en vrac les plus simples et les plus utiles.
Données en masse
Il n'y a pas de terme commun pour ce concept (ou je ne le connais pas). J'appelle une «
masse de données » toute grande collection d'objets similaires. Par exemple, cela pourrait être:
- Toutes les balles du jeu.
- Tous les arbres du jeu.
- Toutes les pièces du jeu.
Ou, si vous écrivez du code à un niveau d'abstraction plus élevé, cela pourrait être:
- Toutes les entités du jeu.
- Toutes les mailles du jeu.
- Tous les sons du jeu.
En règle générale, chaque système (rendu, son, animation, physique, etc.) d'un jeu a deux types d'objets différents qu'il doit suivre. Par exemple, pour un système audio, cela pourrait être:
- Toutes les ressources sonores qui peuvent être jouées.
- Tous les sons en cours de lecture.
- Tous les effets (atténuation, changements de tonalité, etc.) appliqués aux sons.
Dans le cas de données en masse, je supposerai ce qui suit:
Bien sûr, vous pouvez trouver des situations dans lesquelles l'ordre est
important . Par exemple, si les objets désignent des éléments pour le rendu, avant le rendu, nous devrons peut-être les trier d'avant en arrière pour réduire la quantité de
redessin .
Cependant, je pense que dans la plupart des cas, il est préférable de trier les données
telles qu’elles sont utilisées , plutôt que de les stocker dans un conteneur trié, comme
des arbres rouge-noir ou des
arbres B. Par exemple, nous pouvons trier les objets rendus d'avant en arrière avant de les transmettre au moteur de rendu, ou trier les fichiers par ordre alphabétique avant de les afficher à l'écran sous forme de liste. Le tri des données dans chaque trame peut sembler coûteux, mais dans de nombreux cas, cela se fait en
O (n) en utilisant le
tri radix .
Comme j'utilise uniquement des structures de données simples, je préfère les objets C ++ aux objets C ++, car il est plus facile de comprendre ce qui se passe en mémoire et d'évaluer leurs performances. Cependant, il existe des situations où vous devez stocker dans des données en vrac quelque chose qui n'a pas de taille fixe. par exemple, le nom ou la liste des objets enfants. Je parlerai de ces cas dans un article séparé, où nous examinerons les «tableaux de tableaux». Pour l'instant, supposons que tous les objets sont de simples structures de données de taille fixe.
Par exemple, voici à quoi ressembleront les structures de données en vrac pour notre système de son hypothétique:
typedef struct { resource_t *resource;
Lorsque nous envisageons des moyens de stocker des données en masse, nous devons considérer deux objectifs:
- L'ajout et la suppression d'objets doivent être rapides.
- Les données doivent être placées sous une forme pratique pour la mise en cache , afin que vous puissiez rapidement les parcourir pour mettre à jour le système.
- Il doit prendre en charge le mécanisme de liaison - il doit exister un moyen de transmettre des informations sur des objets spécifiques dans des données en masse. Dans l'exemple ci-dessus, le fondu devrait pouvoir spécifier le son atténué. Dans l'exemple, j'ai écrit les liens sous forme de pointeurs, mais leur implémentation dépend de la façon dont les données en masse sont organisées.
- Les données doivent être conviviales pour les allocateurs - elles doivent utiliser plusieurs allocations de mémoire importantes et ne pas allouer d’objets individuels sur le tas.
Les deux façons les plus simples de représenter des données en masse sont un tableau statique ou un vecteur C ++:
Travailler avec un tableau est extrêmement simple, et cela peut très bien fonctionner pour vous si vous savez exactement combien d'objets sont nécessaires dans l'application. Si vous ne le
savez pas , alors gaspillez votre mémoire ou vous manquerez d'objets.
Le vecteur
std::vector est également une solution très digne et simple, mais ici, vous devez considérer certains aspects:
- L'implémentation standard de
std::vector de Visual Studio est lente en mode débogage en raison du débogage des itérateurs. Ils doivent être définis sur _ITERATOR_DEBUG_LEVEL = 0 . - Pour créer et détruire des objets,
std::vector utilise des constructeurs et des destructeurs, et dans certains cas, ils peuvent être beaucoup plus lents que memcpy() . std::vector beaucoup plus difficile à analyser que l'implémentation d'un simple "tampon extensible" .
De plus, sans mesures supplémentaires, ni les tableaux réguliers ni les vecteurs ne prennent en charge les références aux objets individuels. Examinons ce sujet, ainsi que d'autres décisions de conception importantes impliquées dans la création du système de données en masse.
Stratégie de suppression
La première décision importante: que faire lors de la suppression de l'objet
a[i] . Voici trois options principales:
- Vous pouvez déplacer tous les éléments suivants
a[i+1] → a[i] , a[i+2] → a[i+1] , etc., pour fermer un emplacement vide. - Vous pouvez déplacer le dernier élément du tableau vers un emplacement vide:
a[i] = a[n-1] . - Ou vous pouvez laisser l'emplacement vide en créant un trou dans le tableau. Ce trou peut ensuite être utilisé pour placer un nouvel objet.
La première option est terrible -
O (n) est dépensé pour le mouvement de tous ces éléments. Le seul avantage de la première méthode est que si le tableau est trié, son ordre est préservé. Mais comme mentionné ci-dessus, la commande ne nous dérange pas. Notez que si vous utilisez
a.erase() pour supprimer l'élément
std::vector , c'est exactement ce qui se passera!
La deuxième option est souvent appelée «swap-and-pop». Pourquoi? Parce que si vous utilisez un vecteur C ++, cette option est généralement implémentée en remplaçant (permutant) l'élément que vous souhaitez supprimer par le dernier, puis en supprimant ou en éclatant le dernier élément:
std::swap(a[i], a[a.size() - 1]); a.pop_back();
Pourquoi tout cela est-il nécessaire? En C ++, si nous
affectons a[i] = a[n-1] , nous devons d'abord supprimer
a[i] en appelant son destructeur, puis appeler le constructeur de copie pour créer une copie d'
a[n-1] à la position
i et enfin, nous appelons le destructeur
a[n-1] lors du décalage du vecteur. Si le constructeur de copie alloue de la mémoire et copie des données, cela peut être assez mauvais. Si nous utilisons
std::swap au lieu d'affectation, alors nous ne pouvons faire qu'avec le déplacement des constructeurs et ne devons pas allouer de mémoire.
Encore une fois, c'est pourquoi C ++ je préfère les structures de données simples et les opérations C. C ++ a de nombreux pièges de performances dans lesquels vous pouvez tomber si vous ne savez pas ce qui se passe à l'intérieur. En C, l'opération de swap-effacement sera très simple:
a.data[i] = a.data[--an];
Lors de l'utilisation de swap-and-pop, les objets restent bien emballés. Pour placer un nouvel objet, attachez-le simplement à la fin du tableau.
Si nous utilisons l'option «avec trous» I, lors du placement d'un nouvel objet, nous devons d'abord vérifier s'il existe des «trous» libres qui peuvent être utilisés. Cela vaut la peine d'augmenter la taille du tableau uniquement lorsqu'il n'y a pas de «trous» libres. Sinon, dans le processus de suppression et de création d'objets, il se développera indéfiniment.
Vous pouvez utiliser un
std::vector<uint32_t> pour suivre les positions des trous, mais il existe une meilleure solution qui ne nécessite pas de mémoire supplémentaire.
Étant donné que les données de l'objet dans le «trou» ne sont utilisées pour rien, vous pouvez l'utiliser pour stocker un pointeur sur le trou libre suivant. Ainsi, tous les trous du tableau forment une
liste simplement connectée , et si nécessaire, nous pouvons en ajouter et en supprimer des éléments.
Ce type de structure de données, dans lequel la mémoire inutilisée est utilisée pour lier des éléments libres, est généralement appelé
une liste libre .
Dans une liste chaînée traditionnelle, un
élément d'en-tête de liste spécial pointe vers le premier nœud de la liste et le dernier élément de la liste pointe vers NULL, ce qui signifie la fin de la liste. Au lieu de cela, je préfère utiliser une
liste liée circulaire , dans laquelle l'en-tête n'est qu'un élément de liste spécial, et le dernier élément de liste pointe vers un élément de titre:
Listes traditionnelles et chaînées.L'avantage de cette approche est que le code devient beaucoup plus simple en réduisant le nombre de cas spéciaux au début et à la fin de la liste.
Notez que si vous utilisez
std::vector pour stocker des objets, les pointeurs vers les objets changeront à chaque redistribution du vecteur. Cela signifie que nous ne pouvons pas utiliser de pointeurs réguliers vers une liste liée, car les pointeurs changent constamment. Pour contourner ce problème, vous pouvez utiliser des index comme «pointeurs» vers la liste liée, car l'index pointe constamment vers un emplacement spécifique même lors de la redistribution du tableau. Nous parlerons davantage de réaffectation dans la section suivante.
Vous pouvez allouer de l'espace pour un élément spécial du titre de la liste en le stockant toujours dans l'emplacement de tableau 0.
Le code ressemblera à ceci:
Quelle est la meilleure stratégie de suppression? Déplacer le dernier élément dans un emplacement vide, assurer un emballage serré du tableau ou garder tous les éléments à leur place avec la création de «trous» dans le tableau à la place de l'élément supprimé?
Lors de la prise de décision, deux aspects doivent être pris en compte:
- L'itération sur une matrice dense est plus rapide car nous contournons moins de mémoire et nous n'avons pas à passer trop de temps à ignorer les emplacements vides.
- Si nous utilisons un tableau compact, les éléments se déplaceront. Cela signifie que nous ne pouvons pas utiliser l'index d'un élément comme identificateur constant pour les références externes aux éléments. Nous devrons attribuer un identifiant différent à chaque élément et utiliser la table de recherche pour faire correspondre ces ID constants avec les indices d'objet actuels. Cette table de recherche peut être une table de hachage ou un
std::vector avec des trous, comme décrit ci-dessus (la deuxième option est plus rapide). Quoi qu'il en soit, nous aurons besoin de mémoire supplémentaire pour cette table et d'une étape indirecte supplémentaire pour les identifiants.
Le choix de la meilleure option dépend de votre projet.
Vous pouvez dire que le stockage d'un tableau dense est préférable, car les itérations sur tous les éléments (pour mettre à jour le système) se produisent plus souvent que la correspondance de liens externes. D'un autre côté, nous pouvons dire que les performances d'une «matrice avec trous» ne sont pires que dans le cas d'un grand nombre de trous, et dans le développement de jeux, nous nous soucions généralement des performances dans les
pires cas (nous voulons avoir une fréquence d'images de 60 Hz, même lorsque les opérations maximales sont effectuées dans le jeu) . Dans le pire des cas, nous avons le nombre maximum d'objets réels, et dans ce cas,
il n'y aura pas de trous dans le tableau. Les trous se produisent uniquement lorsque le nombre d'objets diminue, lorsque nous supprimons certains de ces objets.
Il existe également des stratégies qui peuvent être utilisées pour accélérer le traitement des tableaux avec de nombreux trous. Par exemple, nous pouvons suivre les longueurs de séquences continues de trous pour ignorer des séquences entières de trous à la fois, plutôt qu'élément par élément. Étant donné que ces données ne sont nécessaires que pour les "trous", et non pour les éléments ordinaires, vous pouvez les stocker avec le pointeur de la liste des versions dans la mémoire non allouée des objets et ne pas gaspiller de mémoire supplémentaire.
À mon avis, si vous n'avez pas besoin d'optimiser le code pour des itérations rapides, il est probablement préférable d'utiliser l'option «tableau avec trous». C'est plus simple, ne nécessite pas de structures de recherche supplémentaires et vous pouvez utiliser l'index de l'objet comme ID, ce qui est très pratique. De plus, le manque d'objets en mouvement élimine les éventuels bugs.
Stratégies de suppression de données en masse.Pointeurs faibles
À titre de remarque, je dirai qu'il est facile d'implémenter la prise en charge des «pointeurs faibles» ou des «descripteurs» pour les objets de données en masse.
Un pointeur faible est une référence à un objet qui peut en quelque sorte déterminer que l'objet auquel il se réfère a été supprimé. Pratique dans les pointeurs faibles, ils vous permettent de supprimer des objets sans vous soucier de qui peut les référencer. Sans pointeurs faibles pour supprimer un objet, nous aurions besoin de rechercher chaque lien individuel et de le déclarer invalide. Cela peut être particulièrement difficile si les liens sont stockés dans du code de script, sur d'autres ordinateurs du réseau, etc.
N'oubliez pas que nous avons déjà un identifiant qui identifie de manière unique
les objets
existants . Dans l'option "avec trous", cet ID est simplement l'index de l'élément (car les éléments ne bougent jamais). Dans le cas de tableaux densément compressés, cet index d'objet est un enregistrement dans le
tableau de recherche .
L'ID lui-même ne peut pas être utilisé comme pointeur faible, car les ID peuvent être réutilisés. Si un élément est supprimé et qu'un nouvel élément est créé dans le même emplacement, nous ne serons pas en mesure de le déterminer par l'ID seul. Pour obtenir un pointeur faible, vous devez combiner l'ID avec le champ de
generation :
typedef struct { uint32_t id; uint32_t generation; } weak_pointer_t;
Le champ de
generation est un champ dans la structure de l'objet qui suit le nombre de fois où le slot du tableau de données en vrac a été réutilisé. (Dans le cas d'un emballage serré, il garde une trace du nombre de fois où l'emplacement a été réutilisé dans le tableau de
recherche .)
Lorsque vous supprimez un élément, nous augmentons le nombre de génération dans son emplacement. Pour vérifier si le pointeur faible est toujours valide, nous vérifions si la
generation dans la structure du pointeur faible correspond à la génération du slot indiqué par son
id . S'ils correspondent, alors l'objet source que nous référençons existe toujours. Sinon, cela signifie qu'il est supprimé et que l'emplacement est soit sur la liste des versions, soit a été réutilisé.
Gardez à l'esprit que puisque le champ de
generation est nécessaire pour les trous et les objets existants, vous devez le stocker en dehors de l'union:
typedef struct { uint32_t generation; union { object_t; freelist_item_t; }; } item_t;
Stratégie de distribution
Si vous utilisez
std::vector pour stocker les données des éléments, alors lorsque le tableau est plein et doit être augmenté, l'ensemble du tableau des éléments sera redistribué. Les éléments existants sont copiés dans le nouveau tableau.
std::vector croît
géométriquement . Cela signifie que chaque fois qu'un vecteur doit augmenter, le nombre d'éléments distribués est multiplié par un certain facteur (généralement par × 2). La croissance géométrique (exponentielle) est importante car elle maintient les coûts d'augmentation de la matrice constants.
Lors de la redistribution du tableau, nous devons déplacer tous les éléments, ce qui nécessite
O (n) . Cependant, à mesure que le tableau grandit, nous ajoutons de l'espace pour
n autres éléments, car nous doublons la taille. Cela signifie que nous n'aurons plus besoin d'augmenter le tableau jusqu'à ce que nous y ajoutions
n éléments supplémentaires. Autrement dit, les coûts d'augmentation sont égaux à
O (n) , mais nous ne les exécutons que * O (n) * pour la nième fois d'écriture dans le tableau, c'est-à-dire qu'en moyenne, le coût d'écriture d'un élément est
O (n) / O (n) = O (1) .
Le coût d'enregistrement d'un élément est appelé la
constante amortie , car si vous calculez la moyenne de tous les enregistrements en cours d'exécution, les coûts seront fixes. Cependant, il ne faut pas oublier qu'avant de faire la moyenne, les coûts s'avèrent très spasmodiques. Après chaque enregistrement
O (n) , nous obtenons un pic de hauteur
O (n) :
Le coût d'écriture dans std::vector .Voyons également ce qui se passe si nous n'utilisons pas de croissance géométrique. Supposons qu'au lieu de doubler la mémoire pendant la croissance, nous allons simplement ajouter 128 autres emplacements. Le déplacement des anciennes données nous coûte toujours
O (n) , mais maintenant nous devons le faire tous les 128 éléments que nous ajoutons, c'est-à-dire que les coûts moyens seront désormais
O (n) / O (128) = O (n) . Le coût d'écriture d'un élément dans un tableau est proportionnel à la taille du tableau, donc lorsque le tableau devient grand, il commence à fonctionner à la vitesse d'une tortue. Oups!
La stratégie de distribution
std::vector est une bonne option standard, fonctionnant bien dans la plupart des cas, mais elle a quelques problèmes:
- Amortized Constant n'est pas bien adapté aux logiciels en temps réel. Si vous disposez d'un très grand tableau, disons, des centaines de millions d'éléments, l'augmentation de ce tableau et le déplacement de tous les éléments peuvent entraîner un ralentissement notable de la fréquence d'images. Ceci est problématique pour la même raison que la récupération de place est problématique dans les jeux. Peu importe à quel point les coûts moyens sont faibles, si dans certains cadres, les coûts peuvent augmenter, provoquant des problèmes de jeu.
- De même, cette stratégie d'allocation dans le cas de grands tableaux peut gaspiller beaucoup de mémoire. Disons que nous avons un tableau de 16 millions d'éléments et que nous devons en écrire un autre. Cela fera passer la gamme à 32 millions. Nous avons maintenant 16 millions d'éléments dans le tableau que nous n'utilisons pas. Pour une plateforme à faible mémoire, c'est beaucoup.
- Enfin, la réallocation déplace les objets en mémoire, invalidant tous les pointeurs vers les objets. Cela peut être une source de bugs difficiles à suivre.
Le code ci-dessous est un exemple de bogues pouvant survenir lors du déplacement d'objets:
Le problème ici est que la fonction
item_2 allocate_slot() peut avoir besoin de redistribuer le tableau pour créer de l'espace pour
item_2 . Dans ce cas, l'
item_1 sera déplacé en mémoire et le pointeur vers l'
item_1 cessera d'être valide. Dans ce cas particulier, nous pouvons éliminer l'erreur en déplaçant l'
item_1 affectation_1, mais des bogues similaires peuvent apparaître plus imperceptiblement. Personnellement, ils m'ont mordu plusieurs fois.
Une telle situation est perfide par le fait que le bogue ne sortira que lorsque le tableau sera redistribué exactement au moment où
slot_2 . Le programme peut fonctionner correctement pendant longtemps jusqu'à ce que quelque chose change le modèle de distribution, après quoi le bogue fonctionnera.
Tous ces problèmes peuvent être résolus en utilisant une stratégie de distribution différente. Voici quelques options:
- : 16, 32, 64, …, . , 16 , 32 , .… ,
std::vector . - , . , . . , O(n)
push() , . - , , , , .
, . , - , , . , , .
, — ? , . , 16 , 16 , . , , 50 %. .
,
, , . *16 K * n*,
n — bulk data , , ( ).
. -, ,
blocks\[i / elements_per_block\][i % elements_per_block] . -, , (heap allocator), .
, « », -
std::vector , , . , , .
, , ID . , , . , 64 , 32 (4 — ).
(Array of Structures, AoS)
(Structure of Arrays, SoA). . , , , , :
typedef struct { float t; vec3_t pos; vec3_t vel; vec3_t col; } particle_t;
struct . « ». :
uint32_t num_particles; particle_t *particles;
, .
(SoA) struct:
uint32_t num_particles; typedef struct { float *t; vec3_t *pos; vec3_t *vel; vec3_t *col; } particles;
, ,
vec3_t struct:
uint32_t num_particles; typedef struct { float *t; float *pos_x; float *pos_y; float *pos_z; float *vel_x; float *vel_y; float *vel_z; float *col_r; float *col_g; float *col_b; } particles;
, AoS, ? :
- . ,
tick() t . simulate_physics() pos vel . SoA struct. ( ), . , tick() 1/10 , , 10 . - SoA SIMD . , FPU . AVX float , 8 .
,
tick() 80 ? Non. 10 , , , SIMD .
SoA:
- .
- , .
particle_t * , . .- ,
- ( ), . , .
, , struct , VM ( ). - 10 struct . 8- -, , . !
— SIMD. :
uint32_t num_particles; typedef struct { float t[8]; float position_x[8]; float position_y[8]; float position_z[8]; float velocity_x[8]; float velocity_y[8]; float velocity_z[8]; float color_r[8]; float color_g[8]; float color_b[8]; } eight_particles_t; eight_particles_t *particles;
- SIMD- , -, . , .
tick() 32 , 288 , 32 .. , 10- ,
t . -, - 64 , , , 5 . , , -, 100% .
, . ,
[16] , float - . , , , :
AoS SoA., SoA — « », SIMD , ( «»).
SIMD- «» , , , «» . , ,
, .
next , SIMD- . struct.
, , , struct . , , .
AoS SoA, , . «» AoS SoA , SIMD-, , . .
— AoS SoA - . , AoS SoA, , AoS ( ). , , .
, « ». 16- , SoA, . scratch buffer 16 .
Conclusion
, « » bulk data :
«» , VM ( ), ( 16 , ).
, :
, 8 SIMD VM .
.