Listes chaînées augmentées : un guide essentiel

Comment fonctionne une liste chaînée ?

Une liste chaînée est une structure de données dans laquelle les champs de chaque donnée sont connectés par des pointeurs au lieu de décalages. Il se compose d'un élément principal qui stocke le premier et le dernier éléments, appelés éléments de nœud, contenant tous les champs utilisateur nécessaires (tels qu'un téléphone, un propriétaire, une entreprise, etc.) et un pointeur vers le nœud suivant. Le dernier élément est lié au champ NULL qui indique la fin de la liste.

Lorsqu'un nouvel élément est ajouté à la liste chaînée, le nœud principal doit mettre à jour le pointeur « queue » vers le nouveau nœud final, et le pointeur NULL précédent doit être mis à jour vers la nouvelle queue.

Cette structure de données permet un enregistrement efficace de nouvelles données sans redimensionner l'ensemble du tableau. Il s'agit d'une méthode efficace pour stocker des données en écriture seule et elle ne nécessite pas de connaître à l'avance la quantité d'éléments. Il s'agit d'une structure de données simple, et en mémoire, elle ressemble à ceci :

Liste liée pour les clés d'expulsion

Dans un article précédent, nous avons discuté de la nécessité d'un tampon pour analyser l'arborescence sans quitter l'arborescence après la suppression de chaque élément. Dans les langages avec GC, ce n'est pas un problème. Cependant, lorsque le code de l'application gère la mémoire, un buffer basé sur une liste chaînée contenant des éléments obsolètes peut être une solution.

Une liste chaînée permet l’ajout rapide d’éléments. Cependant, trouver quoi que ce soit dans la liste chaînée nécessite une analyse séquentielle, ce qui la rend impropre à une récupération rapide des clés. Il s'agit donc d'une solution efficace pour enregistrer des données, créer des tampons temporaires et organiser les données pour effectuer des lectures séquentielles à partir des nœuds principaux.

Trouver des éléments à préempter est un exemple d'une telle tâche. La préemption est souvent utilisée dans les différentes implémentations de cache. Le cache contient des données qui peuvent être restaurées à partir d'autres sources de mémoire avec une latence plus importante. Le cache est généralement stocké dans la mémoire principale. La mémoire principale est limitée et pour une utilisation efficace, seul un petit instantané des données peut être stocké dans la mémoire principale.

Cela nous oblige à utiliser la mémoire plus intelligemment, en évitant de l'utiliser pour des données rarement demandées et en supprimant ces données si elles deviennent trop rarement demandées.

Une méthode efficace pour supprimer des champs du cache est la méthode LRU (Les moins récemment utilisés). Voici la représentation LRU ci-dessous :

Dans ce cas, l'application comprend au moins une liste chaînée pour stocker les objets récemment utilisés et dispose d'autres structures de données (comme une table de hachage) pour une recherche rapide. Les nœuds sont interconnectés.

Lorsqu'un utilisateur récupère des données de la table de hachage, la liste chaînée actualise ces données en les déplaçant vers la queue. En conséquence, après plusieurs opérations, la queue contient les données récemment utilisées, tandis que la tête contient les données rarement demandées.

En cas de débordement de mémoire, l'application peut scanner les N premiers éléments pour libérer suffisamment de mémoire. Il s'agit d'une opération simple car la liste chaînée s'adapte aux analyses séquentielles. La mémoire contenant des données rarement utilisées sera libérée et de nouveaux nœuds plus fréquents pourront être stockés dans le cache.

 #include <stdlib.h> #include <stdio.h> typedef struct lnode_t { struct lnode_t *next; struct lnode_t *prev; void *ptr; } lnode_t; typedef struct list_t { lnode_t *head; lnode_t *tail; } list_t; lnode_t* lru_insert(list_t *list, char *ptr) { if (!list->head) { list->head = list->tail = calloc(1, sizeof(lnode_t)); list->head->ptr = ptr; return list->head; } lnode_t *saved_tail = list->tail; lnode_t *new = calloc(1, sizeof(sizeof(lnode_t))); new->ptr = ptr; saved_tail->next = new; new->prev = saved_tail; list->tail = new; return new; } void lru_update(list_t *list, lnode_t *lnode) { if (list->tail == lnode) { return; } lnode_t *saved_tail = list->tail; saved_tail->next = lnode; if (!lnode->prev) list->head = lnode->next; lnode->next = NULL; lnode->prev = saved_tail; list->tail = lnode; } void lru_evict(list_t *list, int items, void (*func)(void* arg, void *ptr), void* arg) { lnode_t *lnode = list->head; while(items-- && lnode) { func(arg, lnode->ptr); lnode_t *prev = lnode->prev; lnode_t *next = lnode->next; if (prev) prev->next = next; if (next) next->prev = prev; free(lnode); lnode = next; } if (!lnode) list->head = list->tail = NULL; } void print_deleted_obj(void *arg, void *ptr) { printf("evicted: %p\n", ptr); deleteThisInTheOtherStructure(arg, ptr); } int main() { list_t *list = calloc(1, sizeof(list_t)); lnode_t *test = lru_insert(list, "some data"); lru_insert(list, "another data"); lru_update(list, test); lru_evict(list, 1, print_deleted_obj, otherStructure); }

Une remarque : lorsque le nombre d'éléments utilisateurs diffère significativement en fréquence (par exemple, les 95% de requêtes réparties sur les 100 premières clés sur 1 million), le Splay Tree pourrait être plus adapté pour stocker le cache. Cet arbre est équilibré en fonction de la fréquence d'utilisation de chaque nœud.

L'idée principale du Splay Tree est à l'opposé de LRU : les éléments les plus utilisés sont situés près de la racine, ce qui rend cette structure de données idéale comme structure principale pour le cache.

L'expulsion peut être résolue de deux manières : en utilisant une liste chaînée interconnectée avec la structure principale, ou en modifiant un Splay Tree en Threaded Binary Tree. Les nœuds du Splay Tree sont déjà classés par fréquence d'utilisation. Bien que le threading supplémentaire des feuilles d’arbre puisse nécessiter plus de temps CPU, il peut donc économiser de la mémoire.

Pour mieux comprendre l'accélération des données récemment utilisées en mémoire, vous pouvez explorer un exemple de migration de VM en direct sur ce lien .

Améliorer la vitesse d'analyse de la liste liée

Comme mentionné précédemment, les listes chaînées offrent la solution la plus rapide pour écrire des données. Leur vitesse de numérisation est bonne, mais elle est plus lente que la vitesse de numérisation dans la baie.

J'ai décrit ce problème comme étant la localité des données dans l' article précédent. Cependant, comme elles sont similaires aux arbres binaires, les listes chaînées présentent un potentiel d'amélioration. Le déroulement des listes chaînées vous permet de stocker plus de données dans chaque nœud de la liste. Ainsi, cela permet d'économiser de la mémoire sur le nœud pointeur suivant, et parfois d'améliorer les performances, à condition que la taille de l'élément corresponde à la ligne de cache CPU :

L'idée principale reste inchangée, mais la représentation de la liste dans la mémoire sera modifiée.

Cela changera à bien des égards. Il y a 2 options ci-dessous :

Ces améliorations augmentent les performances des listes chaînées, mais ajoutent une certaine complexité au code. Pour les opérations sur disque avec une liste chaînée, un nœud déroulé peut avoir plus d'éléments. Un moyen simple de comprendre comment cela fonctionne est d’imaginer une liste chaînée de tableaux.

Dans le code, il faut modifier la description de la structure, et désormais lire ou écrire chaque élément du tableau de la structure :

 typedef struct lnode_t { struct lnode_t *next; struct lnode_t *prev; void *ptr[3]; } lnode_t;

Ignorer la liste

La liste de sauts est une méthode permettant d'améliorer les caractéristiques de vitesse des éléments de recherche dans une liste chaînée. Ce type de liste chaînée stocke une clé pour ordonner la liste chaînée et comprend des pointeurs supplémentaires pour localiser les nœuds plus efficacement qu'une simple opération d'analyse.

Les nœuds supplémentaires améliorent la vitesse de déplacement entre les nœuds dans une liste de sauts. Cela fonctionne comme une recherche binaire. Au contraire, l’ajout de nouveaux éléments prend plus de temps. Par conséquent, les listes de sauts doivent avoir une clé. Les applications peuvent créer n'importe quel nombre de niveaux pour améliorer les caractéristiques de vitesse. Dans la plupart des cas, un meilleur choix consiste à avoir des niveaux légèrement inférieurs ou à peu près identiques à la hauteur de l'arbre. (Regardez la photo ci-dessus)

Lors de la recherche, une application démarre au niveau le plus élevé, ce qui constitue le chemin le plus rapide. Lors de la détection de la clé proche, elle descend à un niveau inférieur jusqu'à ce que le nœud souhaité soit trouvé.

Ce processus aboutit à une complexité temporelle de O(log(n)). Par exemple, utiliser 4 niveaux pour une liste de sauts avec 16 nœuds, 20 niveaux pour 1 million de nœuds et 32 niveaux pour 4 milliards de nœuds offre une complexité temporelle similaire à celle de l'arbre RB.

La liste de sauts est préférable pour les raisons suivantes :

• Simplicité de mise en œuvre. Malgré ses caractéristiques similaires à celles de l’arbre RB, il est beaucoup plus facile à mettre en œuvre et à maintenir.

• Haute efficacité dans l’ajout de nouveaux nœuds à la fin de la liste de sauts.

• Créer une implémentation thread-safe de la liste de sauts est plus facile que l'arborescence.

Explorons la mise en œuvre de ce concept !

Nœuds de structure :

 typedef struct skip_node { uint64_t key; uint64_t value; struct skip_node **forward; } skip_node; typedef struct skip_t { uint64_t level; uint8_t max_level; skip_node *header; } skip_t;

Fonction pour créer des nœuds :

 skip_node* create_skip_node(uint64_t key, int value, int level) { skip_node *newskip_node = (skip_node*)malloc(sizeof(skip_node)); newskip_node->key = key; newskip_node->value = value; newskip_node->forward = malloc(sizeof(skip_node)*level); for (uint64_t i = 0; i < level; i++) { newskip_node->forward[i] = NULL; } return newskip_node; } skip_t* skip_new(uint8_t max_level) { skip_t *list = (skip_t*)malloc(sizeof(skip_t)); list->level = 0; list->max_level = max_level; skip_node *header = create_skip_node(0, 0, max_level); list->header = header; for (uint64_t i = 0; i < max_level; i++) { header->forward[i] = NULL; } return list; }

Lors de l'insertion, la tâche comprend la détection de l'emplacement correct pour stocker le nœud et la détermination du nombre de niveaux à connecter à ce nœud. L'utilisation d'une fonction aléatoire pour déterminer les niveaux permet de simplifier le processus pour chaque nouveau nœud. En moyenne, cette fonction attribue le deuxième niveau dans 50 % des cas, le troisième niveau dans 25 % des cas, et ainsi de suite. Cette méthode minimise le temps d'accès à la mémoire pour rééquilibrer les éléments.

 uint64_t random_level(uint8_t max_level) { uint64_t level = 1; while (rand() < RAND_MAX / 2 && level < max_level) { level++; } return level; } void skip_insert(skip_t *list, uint64_t key, int value) { skip_node *update[list->max_level]; skip_node *current = list->header; for (uint64_t i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->key < key) { current = current->forward[i]; } update[i] = current; } current = current->forward[0]; if (current == NULL || current->key != key) { uint64_t newLevel = random_level(list->max_level); if (newLevel > list->level) { for (uint64_t i = list->level; i < newLevel; i++) { update[i] = list->header; } list->level = newLevel; } skip_node *newskip_node = create_skip_node(key, value, newLevel); for (uint64_t i = 0; i < newLevel; i++) { newskip_node->forward[i] = update[i]->forward[i]; update[i]->forward[i] = newskip_node; } } }

Fonction pour rechercher des nœuds :

 skip_node* skip_search(skip_t *list, uint64_t key) { skip_node *current = list->header; for (uint64_t i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->key < key) { current = current->forward[i]; } } current = current->forward[0]; ++nodes_scan; if (current != NULL && current->key == key) return current; else return NULL; }

Une fonction de référence pour tester les performances d'une liste chaînée, d'une liste de sauts et de l'arborescence RB. Les valeurs, utilisées comme clés, sont définies sous forme de puissances de deux. La valeur à des fins de test n'a pas d'importance.

 skip_t *skipList = skip_new(atoi(argv[1])); list_t *llist = list_new(); tree_t *tree = calloc(1, sizeof(*tree)); size_t to_index = 50000000; struct timespec s_icalc; struct timespec e_icalc; struct timespec s_scalc; struct timespec e_scalc; clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) tree_insert(tree, i, i*2); clock_gettime(CLOCK_REALTIME, &e_icalc); count = 0; nodes_scan = 0; clock_gettime(CLOCK_REALTIME, &s_scalc); for (uint64_t i = 0; i < to_index; ++i) { node_t *node = tree_get(tree, i); } clock_gettime(CLOCK_REALTIME, &e_scalc); clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) skip_insert(skipList, i, i*2); clock_gettime(CLOCK_REALTIME, &e_icalc); count = 0; clock_gettime(CLOCK_REALTIME, &s_scalc); for (uint64_t i = 0; i < to_index; ++i) { skip_node* ret = skip_search(skipList, i); } clock_gettime(CLOCK_REALTIME, &e_scalc); clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) list_add(llist, NULL, NULL); clock_gettime(CLOCK_REALTIME, &e_icalc);

Résultats du test de ces structures de données sur les clés à croissance séquentielle :

C'est le meilleur moment pour insérer (si vous ne tenez pas compte d'une simple liste chaînée) et une méthode assez rapide pour rechercher des éléments.

Résultats du test de ces structures de données sur les clés décroissantes séquentiellement :

C'est facile à comprendre : cette implémentation d'une liste de sauts n'a qu'un pointeur principal vers le premier élément. L'ajout de nœuds à la fin est plus complexe. Pour changer cette approche, nous pouvons ajouter un deuxième pointeur (vers la queue) ou une liste de sauts inversés (la tête pointera vers les grandes valeurs). Cela signifie qu'une liste de sauts est une structure de données efficace pour les données de journal telles que les flux Kafka. Dans ce cas, il peut être au moins deux fois plus rapide que l’arborescence RB et plus facile à mettre en œuvre.

Skip List réduit la vitesse d'insertion de la liste chaînée, cependant, pour les données séquentielles, elle reste plus rapide que les autres structures de données avec un temps d'accès logarithmique aux éléments, en particulier lorsque les clés augmentent de manière séquentielle. Néanmoins, toute croissance séquentielle des clés complique les insertions dans l'arbre car elle provoque de nombreuses rotations pour maintenir l'équilibre de l'arbre.

Cela ne fonctionne efficacement que lorsque la valeur augmente (ou diminue) tout au long de la séquence. Par exemple, si nous randomisons les clés, les résultats seront différents :

Comme on le voit, la distribution entre les valeurs n'a pas d'impact significatif sur les caractéristiques de vitesse de l'arborescence RB, mais elle affecte notamment les performances de la liste de sauts.

Conclusions

Aujourd'hui, nos applications peuvent organiser les données dans la mémoire ou sur le disque de différentes manières. Les cartes et les listes jouent un rôle important dans l'organisation des données dans différents ordres à des fins diverses. Ces structures garantissent des performances, une efficacité des ressources et des capacités suffisantes.

Parfois, cela ne suffit pas à nos besoins et l'application doit être modifiée dans les parties critiques pour être plus optimale. Certains cas peuvent bénéficier de l'utilisation de structures de données plus adaptées, telles que des arbres pour une correspondance inexacte ou une économie de mémoire. D'autres proviennent d'améliorations de l'algorithme, telles que l'utilisation de méthodes asynchrones pour améliorer les performances des threads individuels.

Lorsque toutes les autres options sont épuisées, l’approche restante consiste à adapter la structure des données et à ajuster la méthodologie d’utilisation. Il existe des exemples de modifications de la structure des données pour les rendre plus adaptées à une tâche pratiquement spécifique.

Bien qu'une liste chaînée soit principalement une structure de données en écriture seule et par analyse de séquence, elle peut être optimisée davantage que l'arborescence RB et rester efficace dans un cas d'écriture seule. Cependant, l’amélioration de certaines caractéristiques peut avoir un impact sur d’autres. Par conséquent, le meilleur moyen est de donner la priorité à ce qui est important et d’écarter ce qui ne l’est pas.