Ignorer la liste par rapport à l’arbre de recherche binary

Je suis récemment tombé sur la structure de données appelée liste de passage . Il semble avoir un comportement très similaire à un arbre de recherche binary.

Pourquoi voudriez-vous jamais utiliser une liste de passage sur un arbre de recherche binary?

Les listes de sauts sont plus facilement accessibles / modifiées simultanément. Herb Sutter a écrit un article sur la structure des données dans des environnements concurrents. Il dispose d’informations plus détaillées.

L’implémentation la plus utilisée d’un arbre de recherche binary est un arbre rouge-noir . Les problèmes concomitants surviennent lorsque l’arbre est modifié, il doit souvent être rééquilibré. L’opération de rééquilibrage peut affecter de grandes parties de l’arborescence, ce qui nécessite un verrou mutex sur la plupart des nœuds d’arborescence. L’insertion d’un nœud dans une liste de saut est beaucoup plus localisée, seuls les nœuds directement liés au nœud affecté doivent être verrouillés.


Mise à jour des commentaires de Jon Harrops

Je lis le dernier article de Fraser et Harris Programmation concurrente sans serrures . Des choses vraiment intéressantes si vous êtes intéressé par des structures de données sans locking. Le document se concentre sur la mémoire transactionnelle et une opération théorique MCAS multi-mots-comparatifs-swap. Les deux sont simulés dans le logiciel car aucun matériel ne les supporte encore. Je suis assez impressionné qu’ils aient pu construire MCAS dans un logiciel.

Je n’ai pas trouvé la mémoire transactionnelle particulièrement intéressante car elle nécessite un ramasse-miettes. La mémoire transactionnelle du logiciel est également en proie à des problèmes de performances. Cependant, je serais très enthousiaste si la mémoire transactionnelle du matériel devenait commune. En fin de compte, c’est toujours la recherche et ne sera pas utile pour le code de production pour une autre décennie.

Dans la section 8.2, ils comparent les performances de plusieurs implémentations d’arborescence simultanées. Je vais résumer leurs conclusions. Cela vaut la peine de télécharger le pdf car il contient des graphiques très instructifs aux pages 50, 53 et 54.

  • Les listes de passage verrouillées sont incroyablement rapides. Ils évoluent incroyablement bien avec le nombre d’access simultanés. C’est ce qui rend les listes de saut spéciales, d’autres structures de données basées sur des verrous ont tendance à croquer sous la pression.
  • Les listes de sauts sans verrou sont systématiquement plus rapides que les listes de sauts de locking, mais à peine.
  • Les listes de saut transactionnel sont systématiquement 2 à 3 fois plus lentes que les versions verrouillables et non verrouillables.
  • verrouiller les arbres rouge-noir croasse sous un access simultané. Leurs performances se dégradent linéairement avec chaque nouvel utilisateur simultané. Parmi les deux implémentations connues d’arbre rouge-noir de locking, l’une comporte essentiellement un verrou global lors du rééquilibrage de l’arborescence. L’autre utilise l’escalade sophistiquée (et compliquée) des verrous, mais n’exécute toujours pas de manière significative la version globale du verrou.
  • les arbres rouge-noir sans verrou n’existent pas (plus vrai, voir la mise à jour).
  • les arbres rouge-noir transactionnels sont comparables aux listes de passage transactionnelles. C’était très surprenant et très prometteur. Mémoire transactionnelle, mais plus lente si elle est beaucoup plus facile à écrire. Cela peut être aussi simple qu’une recherche rapide et remplacer sur la version non concurrente.

Mettre à jour
Voici un article sur les arbres sans serrure : des arbres rouge-noir sans verrou utilisant CAS .
Je ne l’ai pas regardé profondément, mais en surface il semble solide.

Premièrement, vous ne pouvez pas comparer avec précision une structure de données randomisée à une structure qui vous offre les garanties les plus défavorables.

Une liste de saut est équivalente à une arborescence de recherche binary (RBST) équilibrée de manière aléatoire, comme cela est expliqué plus en détail dans Dean and Jones “Exploration de la dualité entre les listes de sauts et les arbres de recherche binary” .

À l’inverse, vous pouvez également avoir des listes de saut déterministes qui garantissent les performances les plus défavorables, cf. Munro et al.

Contre ce que certains prétendent ci-dessus, vous pouvez avoir des implémentations d’arbres de recherche binary (BST) qui fonctionnent bien dans la programmation concurrente. Un problème potentiel avec les BST axés sur la concurrence est que vous ne pouvez pas facilement obtenir les mêmes garanties sur l’équilibrage que vous le feriez d’un arbre rouge-noir (RB). (Mais les listes de saut “standard”, c’est-à-dire aléatoires, ne vous donnent pas non plus ces garanties). Il faut trouver un équilibre entre le maintien de la balance et un access concourant (et facile à programmer). quand une bonne concurrence est souhaitée. La relaxation consiste à ne pas rééquilibrer l’arbre tout de suite. Pour une étude quelque peu datée (1998), voir «La performance des algorithmes concomitants de l’arbre rouge-noir» de Hanke [ps.gz] .

L’une des améliorations les plus récentes concerne le soi-disant arbre chromatique (en gros, vous avez un poids tel que le noir serait 1 et le rouge serait zéro, mais vous permettez également des valeurs entre). Et comment un arbre chromatique peut-il se comparer à une liste de sauts? Voyons ce que Brown et al. “Une technique générale pour les arbres non bloquants” (2014) doit dire:

avec 128 threads, notre algorithme surpasse de 13% à 156% le skiplist non bloquant de Java, l’arbre AVL basé sur le verrou de Bronson et al. de 63% à 224%, et un RBT utilisant la mémoire transactionnelle logicielle (STM) de 13 à 134 fois

EDIT pour append: la liste de sauts à base de cadenas de Pugh, qui a été comparée dans Fraser et Harris (2007) “Programmation concurrente sans verrou” comme étant proche de leur propre version sans verrou (un point amplement souligné dans la première réponse), est également modifié pour une bonne opération simultanée, cf. “Maintien simultané des listes de sauts” de Pugh, bien que d’une manière plutôt douce. Néanmoins, un article récent / 2009 intitulé «Un algorithme de liste de sélection optimiste simple» par Herlihy et al., Qui propose une implémentation de listes de sauts concurrentes supposée plus simple que Pugh, a critiqué Pugh pour ne pas avoir suffisamment prouvé sa justesse pour eux. Laissant de côté ce qualm (peut-être trop pédant), Herlihy et al. montrer que leur implémentation simplifiée basée sur des verrous d’une liste de sauts échoue en réalité, ainsi que son implémentation sans verrou du JDK, mais uniquement pour des conflits élevés (50% d’insertions, 50% de suppressions et 0% de recherches) … et Harris n’a pas testé du tout; Fraser et Harris n’ont testé que 75% des recherches, 12,5% des insertions et 12,5% des suppressions (sur la liste de sauts avec ~ 500K éléments). La mise en œuvre plus simple de Herlihy et al. se rapproche également de la solution sans locking du JDK en cas de faible contention testée (recherches à 70%, insertions à 20%, suppressions à 10%); ils ont en fait battu la solution sans verrou pour ce scénario quand ils ont rendu leur liste de saut assez importante, c’est-à-dire passant de 200K à 2M éléments, de sorte que la probabilité de conflit sur n’importe quel verrou devienne négligeable. Cela aurait été bien si Herlihy et al. Ils avaient surmonté leur suspicion par rapport à la preuve de Pugh et avaient également testé son implémentation, mais hélas ils ne l’avaient pas fait.

EDIT2: J’ai trouvé un code mère (publié en 2015) de tous les tests: Gramoli “Plus que ce que vous avez toujours voulu savoir sur la synchronisation. Synchrobench, Mesure de l’impact de la synchronisation sur les algorithmes concomitants” :

entrer la description de l'image ici

“Algo.4” est un précurseur (version antérieure, 2011) de Brown et al. Mentionné ci-dessus. (Je ne sais pas combien la version 2014 est meilleure ou pire). “Algo.26” est Herlihy mentionné ci-dessus; comme vous pouvez le voir, il est mis à la poubelle sur les mises à jour, et bien pire sur les processeurs Intel utilisés ici que sur les processeurs Sun du papier d’origine. “Algo.28” est ConcurrentSkipListMap du JDK; il ne se comporte pas aussi bien que l’on aurait pu l’espérer par rapport à d’autres implémentations de listes de sauts basées sur CAS. Les gagnants sous haute contention sont “Algo.2”, un algorithme basé sur des verrous (!!) décrit par Crain et al. dans “Un arbre de recherche binary sans conflit ” et “Algo.30” se trouve le “skiplist tournant” de “Structures de données logarithmiques pour les multicœurs” . “Algo.29” est la “liste des sauts non bloquants des zones sensibles ” . Sachez que Gramoli est co-auteur de ces trois articles sur les algorithmes gagnants. “Algo.27” est l’implémentation C ++ de la liste de sauts de Fraser.

La conclusion de Gramoli est que c’est beaucoup plus facile de bousiller une implémentation d’arborescence concurrente basée sur CAS que de bousiller une liste de saut similaire. Et sur la base des chiffres, il est difficile d’être en désaccord. Son explication pour ce fait est:

La difficulté de concevoir un arbre sans verrou provient de la difficulté de modifier atomiquement plusieurs références. Les listes de sauts sont constituées de tours reliées entre elles par des pointeurs successeurs et dans lesquelles chaque nœud pointe vers le nœud situé immédiatement au-dessous. Ils sont souvent considérés comme similaires aux arbres car chaque nœud a un successeur dans la tour suivante et au-dessous, cependant, une distinction majeure est que le pointeur vers le bas est généralement immuable, ce qui simplifie la modification atomique d’un nœud. Cette distinction est probablement la raison pour laquelle les listes de sauts surpassent les arbres soumis à de nombreux conflits, comme le montre la figure ci-dessus.

Révoquer cette difficulté était une préoccupation majeure dans les travaux récents de Brown et al. Ils ont un document complet (2013) intitulé «Primitives pragmatiques pour les structures de données non bloquantes» sur la création de «primitives» composées LL / SC multi-enregistrements, qu’ils appellent LLX / SCX, elles-mêmes implémentées à l’aide de CAS. Brown et al. utilisé ce bloc de construction LLX / SCX dans leur implémentation d’arborescence concurrente 2014 (mais pas en 2011).

Je pense que cela vaut peut-être la peine de résumer ici les idées fondamentales de la liste de sauts «sans point chaud» / sans conflit (CF) . Il ajoute une idée essentielle des arbres RB assouplis (et des structures de données similaires): les tours ne sont plus construites immédiatement après leur insertion, mais elles sont retardées jusqu’à ce qu’il y ait moins de conflits. Inversement, la suppression d’une grande tour peut créer de nombreuses controverses. Cela a été observé dès le papier de liste de concurrences de Pugh en 1990, raison pour laquelle Pugh a introduit une inversion de pointeur lors de la suppression (une information que la page Wikipedia ne mentionne toujours pas à ce jour, hélas). La liste de saut des FC va encore plus loin et retarde la suppression des niveaux supérieurs d’une grande tour. Les deux types d’opérations retardées dans les listes de sauts CF sont exécutés par un thread de type garbage-collector séparé (basé sur CAS), que ses auteurs appellent le “thread d’adaptation”.

Le code Synchrobench (y compris tous les algorithmes testés) est disponible sur: https://github.com/gramoli/synchrobench . Le dernier Brown et al. la mise en œuvre (non incluse dans ce qui précède) est disponible sur http://www.cs.toronto.edu/~tabrown/chromatic/ConcurrentChromaticTreeMap.java Quelqu’un a-t-il une machine de plus de 32 cœurs? J / K Mon point est que vous pouvez les exécuter vous-mêmes.

En plus des réponses données (facilité de mise en œuvre combinée à des performances comparables à un arbre équilibré). Je trouve que l’implémentation de la traversée dans l’ordre (avant et arrière) est beaucoup plus simple car une liste de sauts a effectivement une liste chaînée dans son implémentation.

En pratique, j’ai constaté que les performances de B-tree sur mes projets étaient meilleures que les listes de passage. Les listes de sauts semblent plus faciles à comprendre, mais l’implémentation d’un arbre B n’est pas si difficile.

Le seul avantage que je connaisse est que certaines personnes intelligentes ont découvert comment implémenter une liste de sauts simultanés sans locking qui utilise uniquement des opérations atomiques. Par exemple, Java 6 contient la classe ConcurrentSkipListMap et vous pouvez y lire le code source si vous êtes fou.

Mais ce n’est pas trop difficile d’écrire une variante de B-Tree simultanée – je l’ai déjà vu par quelqu’un d’autre – si vous divisez et fusionnez de manière préventive des nœuds «juste au cas où» en descendant de l’arbre, S’inquiéter des impasses et ne jamais avoir à tenir une serrure à deux niveaux de l’arbre à la fois. La surcharge de synchronisation sera un peu plus élevée mais l’arbre B est probablement plus rapide.

De l’ article de Wikipedia que vous avez cité:

Operations (n) opérations, qui nous obligent à visiter chaque nœud dans l’ordre croissant (comme imprimer la liste entière), permettent d’effectuer une dérandomisation en coulisses de la structure de niveaux de la liste de saut de manière optimale, apportant la liste de passage au temps de recherche O (log n). […] Une liste de sauts, sur laquelle nous n’avons pas effectué récemment [de telles opérations] Θ (n), ne fournit pas les mêmes garanties absolues de performance que les structures de données arborescentes équilibrées plus traditionnelles , car il est toujours possible (mais avec une très faible probabilité) que les flips utilisés pour construire la liste de sauts produiront une structure mal équilibrée

EDIT: c’est un compromis: Skip Lists utilise moins de mémoire au risque de dégénérer en un arbre déséquilibré.

Les listes de sauts sont implémentées à l’aide de listes.

Il existe des solutions sans locking pour les listes à liaisons simples et doubles – mais il n’existe pas de solutions sans locking qui utilisent directement uniquement CAS pour toute structure de données O (logn).

Vous pouvez toutefois utiliser des listes basées sur CAS pour créer des listes de sauts.

(Notez que MCAS, qui est créé à l’aide de CAS, permet des structures de données arbitraires et qu’un arbre rouge-noir de preuve de concept a été créé à l’aide de MCAS).

Donc, bizarre qu’ils soient, ils s’avèrent très utiles 🙂

Les listes de sauts présentent l’avantage de supprimer les verrous. Mais, le temps d’exécution dépend de la manière dont le niveau d’un nouveau nœud est décidé. Habituellement, cela se fait en utilisant Random (). Sur un dictionnaire de 56 000 mots, la liste de sauts prend plus de temps qu’un arbre splay et l’arbre prend plus de temps qu’une table de hachage. Les deux premiers ne pouvaient pas correspondre à l’exécution de la table de hachage. En outre, le tableau de la table de hachage peut également être verrouillé de manière simultanée.

La liste de passage et les listes ordonnées similaires sont utilisées lorsque la localité de référence est requirejse. Par exemple: trouver des vols à côté et avant une date dans une application.

Un arbre de recherche de recherche binary en mémoire est excellent et plus fréquemment utilisé.

Sauter la liste Vs Splay Tree Vs Hash Table Runtime sur le dictionnaire trouver op