Sauter la liste contre l'arborescence de recherche binaire

J'ai récemment rencontré la structure de données connue sous le nom de liste de saut . Il semble avoir un comportement très similaire à un arbre de recherche binaire.

Pourquoi voudriez-vous jamais utiliser une liste de saut sur un arbre de recherche binaire?

Les listes de sauts se prêtent mieux à un accès / modification simultané. Herb Sutter a écrit un article sur la structure des données dans des environnements simultanés. Il contient des informations plus approfondies.

L'implémentation la plus fréquemment utilisée d'un arbre de recherche binaire est un arbre rouge-noir . Les problèmes simultanés 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'arbre, ce qui nécessiterait un verrouillage mutex sur de nombreux nœuds d'arbre. 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

J'ai lu le dernier article de Fraser and Harris, Concurrent Programming without locks . Vraiment bien si vous êtes intéressé par des structures de données sans verrouillage. L'article se concentre sur la mémoire transactionnelle et une opération théorique multi-mots-comparer-et-swap MCAS. Les deux sont simulés dans un logiciel car aucun matériel ne les prend en charge pour le moment. Je suis assez impressionné qu'ils aient réussi à construire MCAS dans un logiciel.

Je n'ai pas trouvé la mémoire transactionnelle particulièrement convaincante car elle nécessite un garbage collector. La mémoire transactionnelle logicielle est également en proie à des problèmes de performances. Cependant, je serais très excité si la mémoire transactionnelle matérielle devenait courante. En fin de compte, il s'agit toujours de recherches et ne sera pas utilisé pour le code de production avant une dizaine d'années.

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.

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

Mise à jour
Voici un article sur les arbres sans verrouillage : arbres rouge-noir sans verrouillage utilisant CAS .
Je ne l'ai pas examiné en profondeur, mais en surface, il semble solide.

Premièrement, vous ne pouvez pas comparer équitablement une structure de données randomisée avec celle qui vous offre les pires garanties.

Une liste de sauts équivaut à un arbre de recherche binaire à équilibrage aléatoire (RBST) de la manière qui est expliquée plus en détail dans Dean and Jones "Exploring the Duality Between Skip Lists and Binary Search Trees" .

Dans l'autre sens, vous pouvez également avoir des listes de saut déterministes qui garantissent les performances les plus défavorables, cf. Munro et al.

Contrairement à ce que certains prétendent ci-dessus, vous pouvez avoir des implémentations d'arbres de recherche binaires (BST) qui fonctionnent bien dans la programmation simultanée. Un problème potentiel avec les BST axés sur la concurrence est que vous ne pouvez pas facilement obtenir les mêmes garanties d’équilibrage que vous le feriez à partir d’un arbre rouge-noir (RB). (Mais les listes de saut "standard", c'est-à-dire aléatoires, ne vous offrent pas non plus ces garanties.) Il y a un compromis entre maintenir l'équilibre à tout moment et un bon accès simultané (et facile à programmer), donc des arbres RB détendus sont généralement utilisés lorsqu'une bonne simultanéité est souhaitée. La relaxation consiste à ne pas rééquilibrer l'arbre tout de suite. Pour une enquête quelque peu datée (1998), voir «Les performances des algorithmes d'arbre rouge-noir simultanés» de Hanke [ps.gz] .

L'une des améliorations les plus récentes à ce sujet est le soi-disant arbre chromatique (fondamentalement, vous avez un poids tel que le noir serait 1 et le rouge serait nul, mais vous autorisez également des valeurs intermédiaires). Et comment un arbre chromatique se compare-t-il à la liste de saut? 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 les verrous de Bronson et al. de 63% à 224%, et un RBT qui utilise la mémoire transactionnelle logicielle (STM) de 13 à 134 fois

EDIT to add: Pugh's lock-based skip list, qui a été référencé dans Fraser and Harris (2007) "Concurrent Programming Without Lock" comme se rapprochant de leur propre version sans verrouillage (un point sur lequel la première réponse ici insiste amplement), est également modifié pour un bon fonctionnement simultané, cf. Pugh "Concurrent Maintenance of Skip Lists" , bien que d'une manière plutôt douce. Néanmoins, un article plus récent / 2009 "Un algorithme de liste de saut optimiste simple"par Herlihy et al., qui propose une implémentation supposée plus simple (que celle de Pugh) des listes de sauts simultanées, a critiqué Pugh pour ne pas avoir fourni une preuve d'exactitude suffisamment convaincante pour eux. Laissant de côté ce scrupule (peut-être trop pédant), Herlihy et al. montrent que leur implémentation plus simple basée sur le verrouillage d'une liste de sauts échoue en fait ainsi que l'implémentation sans verrouillage du JDK, mais uniquement pour les conflits élevés (50% d'insertions, 50% de suppressions et 0% de recherches) ... que Fraser 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 saut avec ~ 500 000 éléments). La mise en œuvre plus simple de Herlihy et al. se rapproche également de la solution sans verrouillage du JDK en cas de faible conflit qu'ils ont testé (70% de recherches, 20% d'insertions, 10% de suppressions); ils ont en fait battu la solution sans verrou pour ce scénario lorsqu'ils ont fait leur liste de sauts assez grande, c'est-à-dire en passant de 200K à 2M d'éléments, de sorte que la probabilité de contention sur n'importe quel verrou est devenue négligeable. Cela aurait été bien si Herlihy et al. avaient surmonté leur accrochage sur la preuve de Pugh et testé son implémentation aussi, mais hélas, ils ne l'ont pas fait.

EDIT2: Je trouve un (2015 publié) motherlode de tous les points de référence: de Gramoli « plus que vous avez toujours voulu savoir sur la synchronisation Synchrobench, Mesurer l'impact de la synchronisation sur Concurrent algorithmes. » : Voici une image Extrait pertinente à cette question.

"Algo.4" est un précurseur (ancien, version 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 fait 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 très disputés sont "Algo.2", un algorithme basé sur les verrous (!!) décrit par Crain et al. dans "A Contention-Friendly Binary Search Tree" et "Algo.30" est le "skiplist rotatif" de "Logarithmic data structures for multicores" . ". Sachez que Gramoli est co-auteur de ces trois articles sur l'algorithme gagnant. "Algo.27" est l'implémentation C ++ de la liste de saut de Fraser.

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

La difficulté de concevoir un arbre sans verrouillage provient de la difficulté de modifier plusieurs références de manière atomique. Les listes de sauts sont constituées de tours reliées les unes aux autres par des pointeurs successeurs et dans lesquelles chaque nœud pointe vers le nœud immédiatement en dessous. Ils sont souvent considérés comme similaires aux arbres car chaque nœud a un successeur dans la tour successeur et en 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 à une forte contention, comme observé dans la figure [ci-dessus].

Surmonter cette difficulté était une préoccupation clé dans les travaux récents de Brown et al. Ils ont un document séparé (2013) "Pragmatic Primitives for Non-blocking Data Structures" sur la construction de "primitives" composées de LL / SC à plusieurs enregistrements, qu'ils appellent LLX / SCX, elles-mêmes implémentées à l'aide de CAS (au niveau de la machine). Brown et al. utilisé ce bloc de construction LLX / SCX dans leur implémentation d'arborescence simultanée en 2014 (mais pas en 2011).

Je pense qu'il vaut peut-être aussi la peine de résumer ici les idées fondamentales de la liste de sauts «pas de point chaud» / favorable aux conflits (CF). Il ajoute une idée essentielle à partir des arbres RB détendus (et des structures de données friablement similaires): les tours ne sont plus construites immédiatement après l'insertion, mais retardées jusqu'à ce qu'il y ait moins de conflits. Inversement, la suppression d'une haute tour peut créer de nombreux contentieux; cela a été observé dès la publication simultanée de Pugh en 1990, c'est pourquoi Pugh a introduit l'inversion du pointeur sur la suppression (une friandise que la page de Wikipedia sur les listes de sauts ne mentionne toujours pas à ce jour, hélas). La liste de sauts des FC va encore plus loin et retarde la suppression des niveaux supérieurs d'une haute tour. Les deux types d'opérations différées dans les listes de sauts CF sont effectuées 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 . Les derniers Brown et al. l'implémentation (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 32+ disponible? J / K Mon point est que vous pouvez les gérer vous-même.

Aussi, en plus des réponses données (facilité de mise en œuvre associée à des performances comparables à un arbre équilibré). Je trouve que la mise en œuvre de la traversée dans l'ordre (en avant et en arrière) est beaucoup plus simple car une skip-list a effectivement une liste liée dans son implémentation.

Dans la pratique, j'ai trouvé que les performances de l'arbre B sur mes projets se sont avérées meilleures que les listes de sauts. 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 trouvé comment implémenter une liste de sauts simultanés sans verrouillage qui n'utilise que 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 il n'est pas trop difficile non plus d'écrire une variante d'arbre B simultanée - je l'ai vu faire par quelqu'un d'autre - si vous fractionnez et fusionnez les nœuds de manière préventive "au cas où" lorsque vous descendez dans l'arbre, vous n'aurez pas à vous inquiétez pas des blocages et n'avez besoin que de maintenir un verrou sur 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.

D'après l' article de Wikipédia que vous avez cité:

Les opérations Θ (n), qui nous obligent à visiter chaque nœud dans l'ordre croissant (comme l'impression de la liste entière) offrent la possibilité d'effectuer une dérandomisation en arrière-plan de la structure de niveau de la liste de saut de manière optimale, amener la liste de sauts au temps de recherche O (log n). [...] Une liste de sauts, sur laquelle nous n'avons pas récemment effectué [de telles] opérations Θ (n), ne fournit pas les mêmes garanties de performances absolues dans le pire des cas que les structures de données d'arbre équilibrées plus traditionnelles , car il est toujours possible (mais avec une très faible probabilité) que les lancers de pièces utilisés pour construire la liste de sauts produisent une structure mal équilibrée

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

Les listes de saut sont implémentées à l'aide de listes.

Il existe des solutions sans verrouillage pour les listes liées individuellement ou doublement - mais il n'existe pas de solutions sans verrouillage utilisant directement CAS uniquement pour toute structure de données O (logn).

Vous pouvez cependant utiliser des listes basées sur CAS pour créer des listes de saut.

(Notez que MCAS, qui est créé à l'aide de CAS, permet des structures de données arbitraires et une arborescence rouge-noir de preuve de concept a été créée à l'aide de MCAS).

Aussi étranges soient-elles, elles s'avèrent très utiles :-)

Les sauts de listes ont l'avantage de supprimer les verrous. Mais, le temps d'exécution dépend de la façon 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 saut a pris plus de temps qu'un arbre d'affichage et l'arbre a pris 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 supprimé de manière simultanée.

Skip List et des listes ordonnées similaires sont utilisées lorsque la localité de référence est nécessaire. Par exemple: trouver des vols à côté et avant une date dans une application.

Un arbre splay de recherche binaire en mémoire est génial et plus fréquemment utilisé.

Skip List Vs Splay Tree Vs Hash Table Runtime on dictionary find op