Liste überspringen vs. Binärer Suchbaum

Ich bin kürzlich auf die Datenstruktur gestoßen, die als Überspringliste bekannt ist . Es scheint ein sehr ähnliches Verhalten wie ein binärer Suchbaum zu haben.

Warum sollten Sie jemals eine Sprungliste über einem binären Suchbaum verwenden wollen?

Überspringlisten sind für den gleichzeitigen Zugriff / die gleichzeitige Änderung zugänglicher. Herb Sutter schrieb einen Artikel über die Datenstruktur in gleichzeitigen Umgebungen. Es enthält ausführlichere Informationen.

Die am häufigsten verwendete Implementierung eines binären Suchbaums ist ein rot-schwarzer Baum . Die gleichzeitigen Probleme treten auf, wenn der Baum geändert wird, der häufig neu ausgeglichen werden muss. Die Neuausgleichsoperation kann große Teile des Baums betreffen, was eine Mutex-Sperre für viele der Baumknoten erfordern würde. Das Einfügen eines Knotens in eine Überspringliste ist weitaus lokaler, nur Knoten, die direkt mit dem betroffenen Knoten verknüpft sind, müssen gesperrt werden.

Update von Jon Harrops Kommentaren

Ich habe Frasers und Harris 'neueste Zeitung Concurrent Programming ohne Sperren gelesen . Wirklich gutes Zeug, wenn Sie an sperrenfreien Datenstrukturen interessiert sind. Das Papier konzentriert sich auf den Transaktionsspeicher und eine theoretische Operation zum Mehrwort-Vergleichen und Austauschen von MCAS. Beide werden in Software simuliert, da sie noch von keiner Hardware unterstützt werden. Ich bin ziemlich beeindruckt, dass sie MCAS überhaupt in Software erstellen konnten.

Ich fand das Transaktionsspeichermaterial nicht besonders überzeugend, da es einen Garbage Collector erfordert. Auch der Transaktionsspeicher von Software ist mit Leistungsproblemen behaftet. Ich würde mich jedoch sehr freuen, wenn Hardware-Transaktionsspeicher jemals üblich werden. Am Ende ist es noch Forschung und wird für Produktionscode für ein weiteres Jahrzehnt oder so nicht von Nutzen sein.

In Abschnitt 8.2 vergleichen sie die Leistung mehrerer gleichzeitiger Baumimplementierungen. Ich werde ihre Ergebnisse zusammenfassen. Es lohnt sich, das PDF herunterzuladen, da es auf den Seiten 50, 53 und 54 einige sehr informative Grafiken enthält.

• Das Sperren von Sprunglisten ist wahnsinnig schnell. Sie lassen sich unglaublich gut mit der Anzahl der gleichzeitigen Zugriffe skalieren. Dies ist das Besondere an Überspringlisten. Andere sperrenbasierte Datenstrukturen neigen dazu, unter Druck zu krächzen.
• Sperrfreie Überspringlisten sind durchweg schneller als das Sperren von Überspringlisten, jedoch nur knapp.
• Transaktionssprunglisten sind durchweg 2-3 mal langsamer als die sperrenden und nicht sperrenden Versionen.
• Das Sperren von rot-schwarzen Bäumen krächzt bei gleichzeitigem Zugriff. Ihre Leistung verschlechtert sich linear mit jedem neuen gleichzeitigen Benutzer. Von den beiden bekannten rot-schwarzen Baumimplementierungen hat eine im Wesentlichen eine globale Sperre während des Baumausgleichs. Der andere verwendet eine ausgefallene (und komplizierte) Sperreneskalation, führt jedoch die globale Sperrversion nicht wesentlich aus.
• sperrfreie rot-schwarze Bäume existieren nicht (nicht mehr wahr, siehe Update).
• Transaktionsrot-Schwarz-Bäume sind mit Transaktions-Sprunglisten vergleichbar. Das war sehr überraschend und vielversprechend. Transaktionsspeicher, wenn auch langsamer, wenn auch viel einfacher zu schreiben. Es kann so einfach sein wie schnelles Suchen und Ersetzen in der nicht gleichzeitigen Version.

Update
Hier ist ein Artikel über sperrenfreie Bäume: Sperrenfreie rot-schwarze Bäume mit CAS .
Ich habe nicht tief hineingeschaut, aber an der Oberfläche scheint es solide zu sein.

Erstens können Sie eine randomisierte Datenstruktur nicht fair mit einer vergleichen, die Ihnen Worst-Case-Garantien bietet.

Eine Sprungliste entspricht einem zufällig ausgeglichenen binären Suchbaum (RBST), wie in Dean und Jones ' "Exploring the Duality Between Skip Lists" und "Binary Search Trees" ausführlicher erläutert .

Umgekehrt können Sie auch deterministische Sprunglisten haben, die die Leistung im ungünstigsten Fall garantieren, vgl. Munro et al.

Entgegen der obigen Behauptung können Sie Implementierungen von binären Suchbäumen (BST) haben, die bei der gleichzeitigen Programmierung gut funktionieren. Ein potenzielles Problem bei den auf Parallelität ausgerichteten BSTs besteht darin, dass Sie nicht so einfach die gleichen Garantien für den Ausgleich erhalten können wie bei einem rot-schwarzen Baum (RB). (Aber "Standard", dh zufällig übersprungene Überspringlisten, bieten Ihnen diese Garantien auch nicht.) Es gibt einen Kompromiss zwischen der Aufrechterhaltung des Gleichgewichts zu jeder Zeit und einem guten (und einfach zu programmierenden) gleichzeitigen Zugriff, sodass normalerweise entspannte RB-Bäume verwendet werden wenn eine gute Parallelität gewünscht wird. Die Entspannung besteht darin, den Baum nicht sofort wieder ins Gleichgewicht zu bringen. Für eine etwas veraltete (1998) Umfrage siehe Hankes "The Performance of Concurrent Red-Black Tree Algorithms" [ps.gz] .

Eine der jüngsten Verbesserungen ist der sogenannte chromatische Baum (im Grunde haben Sie ein gewisses Gewicht, so dass Schwarz 1 und Rot Null wäre, aber Sie lassen auch Werte dazwischen zu). Und wie verhält sich ein chromatischer Baum gegen die Sprungliste? Mal sehen, was Brown et al. "Eine allgemeine Technik für nicht blockierende Bäume" (2014) muss sagen:

Mit 128 Threads übertrifft unser Algorithmus Javas nicht blockierende Skiplist um 13% bis 156%, den sperrbasierten AVL-Baum von Bronson et al. um 63% bis 224% und eine RBT, die den Software-Transaktionsspeicher (STM) 13- bis 134-mal verwendet

BEARBEITEN, um hinzuzufügen: Pughs sperrbasierte Überspringliste, die in Fraser und Harris (2007) "Concurrent Programming Without Lock" als Annäherung an ihre eigene sperrenfreie Version bewertet wurde (ein Punkt, auf den in der oberen Antwort hier reichlich bestanden wird), wird auch für einen guten gleichzeitigen Betrieb optimiert, vgl. Pughs "Concurrent Maintenance of Skip Lists" , wenn auch eher mild. Trotzdem eine neuere / 2009 erschienene Veröffentlichung "A Simple Optimistic Skip-List Algorithm"von Herlihy et al., die eine angeblich einfachere (als Pughs) sperrenbasierte Implementierung von gleichzeitigen Überspringlisten vorschlägt, kritisierten Pugh dafür, dass er keinen für sie überzeugenden Korrektheitsnachweis erbracht habe. Abgesehen von dieser (vielleicht zu pedantischen) Bedenken haben Herlihy et al. zeigen, dass ihre einfachere sperrbasierte Implementierung einer Überspringliste nicht so gut skaliert werden kann wie die sperrenfreie Implementierung des JDK, jedoch nur für hohe Konflikte (50% Einfügungen, 50% Löschungen und 0% Suchvorgänge) ... die Fraser und Harris testete überhaupt nicht; Fraser und Harris testeten nur 75% Lookups, 12,5% Inserts und 12,5% Deletes (auf der Überspringliste mit ~ 500K Elementen). Die einfachere Implementierung von Herlihy et al. kommt auch der sperrfreien Lösung des JDK bei geringen Konflikten nahe, die sie getestet haben (70% Lookups, 20% Inserts, 10% Deletes); Sie haben die sperrfreie Lösung für dieses Szenario tatsächlich übertroffen, als sie ihre Überspringliste groß genug gemacht haben, dh von 200.000 auf 2 Millionen Elemente gewechselt sind, so dass die Wahrscheinlichkeit von Konflikten mit einer Sperre vernachlässigbar wurde. Es wäre schön gewesen, wenn Herlihy et al. hatte über Pughs Beweis hinweggelegt und auch seine Implementierung getestet, aber leider taten sie das nicht.

EDIT2: Ich habe einen (2015 veröffentlichten) Motherlode aller Benchmarks gefunden: Gramolis "Mehr als Sie jemals über Synchronisation wissen wollten. Synchrobench, Messung des Einflusses der Synchronisation auf gleichzeitige Algorithmen" : Hier ist ein Auszug, der für diese Frage relevant ist.

"Algo.4" ist ein Vorläufer (ältere Version von 2011) von Brown et al., Der oben erwähnt wurde. (Ich weiß nicht, wie viel besser oder schlechter die Version 2014 ist). "Algo.26" ist Herlihys oben erwähntes; Wie Sie sehen können, wird es bei Updates verworfen und bei den hier verwendeten Intel-CPUs viel schlimmer als bei den Sun-CPUs aus dem Originalpapier. "Algo.28" ist ConcurrentSkipListMap aus dem JDK; Im Vergleich zu anderen CAS-basierten Skip-List-Implementierungen funktioniert es nicht so gut, wie man es sich erhofft hätte. Die Gewinner sind "Algo.2", ein sperrbasierter Algorithmus (!!), der von Crain et al. in "A Contention-Friendly Binary Search Tree" und "Algo.30" ist die "rotierende Skiplist" aus "Logarithmische Datenstrukturen für Multicores" . "". Beachten Sie, dass Gramoli Co-Autor aller drei dieser Gewinner-Algorithmus-Artikel ist. "Algo.27" ist die C ++ - Implementierung von Frasers Sprungliste.

Gramolis Schlussfolgerung ist, dass es viel einfacher ist, eine CAS-basierte gleichzeitige Baumimplementierung zu vermasseln, als eine ähnliche Sprungliste zu vermasseln. Und basierend auf den Zahlen ist es schwer zu widersprechen. Seine Erklärung für diese Tatsache lautet:

Die Schwierigkeit beim Entwerfen eines Baums, der frei von Sperren ist, ergibt sich aus der Schwierigkeit, mehrere Referenzen atomar zu ändern. Überspringlisten bestehen aus Türmen, die über Nachfolgezeiger miteinander verbunden sind und in denen jeder Knoten auf den Knoten unmittelbar darunter zeigt. Sie werden oft als ähnlich wie Bäume angesehen, da jeder Knoten einen Nachfolger im Nachfolgeturm hat und darunter ein wesentlicher Unterschied darin besteht, dass der Abwärtszeiger im Allgemeinen unveränderlich ist, wodurch die atomare Modifikation eines Knotens vereinfacht wird. Diese Unterscheidung ist wahrscheinlich der Grund, warum Überspringlisten Bäume unter starken Konflikten übertreffen, wie in Abbildung [oben] dargestellt.

Das Überschreiben dieser Schwierigkeit war ein zentrales Anliegen in der jüngsten Arbeit von Brown et al. Sie haben ein ganzes separates (2013) Papier "Pragmatische Primitive für nicht blockierende Datenstrukturen" zum Aufbau von LL / SC-Verbund-Primitiven mit mehreren Datensätzen , die sie LLX / SCX nennen und die selbst mit CAS (auf Maschinenebene) implementiert wurden. Brown et al. verwendeten diesen LLX / SCX-Baustein in ihrer gleichzeitigen Baumimplementierung 2014 (jedoch nicht 2011).

Ich denke, es lohnt sich vielleicht auch, hier die Grundgedanken der Überspringliste "No Hot Spot" / Contention-Friendly (CF) zusammenzufassen. Es fügt eine wesentliche Idee aus den entspannten RB-Bäumen (und ähnlichen frittierten Datenstrukturen) hinzu: Die Türme werden nicht mehr sofort nach dem Einfügen aufgebaut, sondern verzögert, bis weniger Streit besteht. Umgekehrt kann das Löschen eines hohen Turms viele Streitigkeiten hervorrufen. Dies wurde bereits in Pughs Papier über die gleichzeitige Überspringliste von 1990 beobachtet, weshalb Pugh beim Löschen die Umkehrung des Zeigers einführte (ein Leckerbissen, das die Wikipedia-Seite über Überspringlisten leider bis heute nicht erwähnt). Die CF-Überspringliste geht noch einen Schritt weiter und verzögert das Löschen der oberen Ebenen eines hohen Turms. Beide Arten von verzögerten Operationen in CF-Überspringlisten werden von einem (CAS-basierten) separaten Garbage-Collector-ähnlichen Thread ausgeführt, den die Autoren als "Anpassungs-Thread" bezeichnen.

Der Synchrobench-Code (einschließlich aller getesteten Algorithmen) ist verfügbar unter: https://github.com/gramoli/synchrobench . Das neueste Brown et al. Die Implementierung (oben nicht enthalten) ist unter http://www.cs.toronto.edu/~tabrown/chromatic/ConcurrentChromaticTreeMap.java verfügbar. Hat jemand einen 32+ Core-Computer zur Verfügung? J / K Mein Punkt ist, dass Sie diese selbst ausführen können.

Zusätzlich zu den gegebenen Antworten (einfache Implementierung kombiniert mit vergleichbarer Leistung wie ein ausgeglichener Baum). Ich finde, dass das Implementieren von In-Order-Traversal (vorwärts und rückwärts) viel einfacher ist, da eine Sprungliste effektiv eine verknüpfte Liste in ihrer Implementierung enthält.

In der Praxis habe ich festgestellt, dass die B-Tree-Leistung in meinen Projekten besser ist als das Überspringen von Listen. Überspringlisten scheinen leichter zu verstehen, aber die Implementierung eines B-Baums ist nicht so schwierig.

Der einzige Vorteil, den ich kenne, ist, dass einige clevere Leute herausgefunden haben, wie man eine sperrfreie gleichzeitige Überspringliste implementiert, die nur atomare Operationen verwendet. Beispielsweise enthält Java 6 die ConcurrentSkipListMap-Klasse, und Sie können den Quellcode lesen, wenn Sie verrückt sind.

Aber es ist auch nicht allzu schwer, eine gleichzeitige B-Baum-Variante zu schreiben - ich habe es von jemand anderem gesehen -, wenn Sie Knoten "nur für den Fall" präventiv teilen und zusammenführen, während Sie den Baum hinuntergehen, müssen Sie das nicht Sorgen Sie sich um Deadlocks und müssen Sie immer nur zwei Ebenen des Baumes gleichzeitig sperren. Der Synchronisationsaufwand wird etwas höher sein, aber der B-Baum ist wahrscheinlich schneller.

Aus dem von Ihnen zitierten Wikipedia- Artikel:

Θ (n) Operationen, die uns zwingen, jeden Knoten in aufsteigender Reihenfolge zu besuchen (z. B. das Drucken der gesamten Liste), bieten die Möglichkeit, eine Derandomisierung der Ebenenstruktur der Sprungliste hinter den Kulissen auf optimale Weise durchzuführen. Bringen der Überspringliste auf O (log n) Suchzeit. [...] Eine Überspringliste, für die wir kürzlich keine derartigen such (n) -Operationen durchgeführt haben, bietet nicht die gleichen absoluten Leistungsgarantien für den schlechtesten Fall wie herkömmliche ausgeglichene Baumdatenstrukturen , da dies immer möglich ist (allerdings mit sehr geringer Wahrscheinlichkeit), dass die zum Erstellen der Überspringliste verwendeten Münzwürfe eine schlecht ausbalancierte Struktur erzeugen

BEARBEITEN: Es ist also ein Kompromiss: Überspringlisten verbrauchen weniger Speicher, wenn das Risiko besteht, dass sie zu einem unausgeglichenen Baum ausarten.

Überspringlisten werden mithilfe von Listen implementiert.

Es gibt sperrfreie Lösungen für einfach und doppelt verknüpfte Listen. Es gibt jedoch keine sperrenfreien Lösungen, die direkt nur CAS für eine O (logn) -Datenstruktur verwenden.

Sie können jedoch CAS-basierte Listen verwenden, um Überspringlisten zu erstellen.

(Beachten Sie, dass MCAS, das mit CAS erstellt wird, beliebige Datenstrukturen zulässt und mit MCAS ein Proof-of-Concept-Rot-Schwarz-Baum erstellt wurde.)

So seltsam sie auch sind, sie erweisen sich als sehr nützlich :-)

Überspringlisten haben den Vorteil des Entfernens von Sperren. Die Laufzeit hängt jedoch davon ab, wie die Ebene eines neuen Knotens festgelegt wird. Normalerweise erfolgt dies mit Random (). Bei einem Wörterbuch mit 56000 Wörtern dauerte das Überspringen der Liste länger als ein Spreizbaum, und der Baum benötigte mehr Zeit als eine Hash-Tabelle. Die ersten beiden konnten nicht mit der Laufzeit der Hash-Tabelle übereinstimmen. Außerdem kann das Array der Hash-Tabelle gleichzeitig gesperrt werden.

Überspringliste und ähnlich geordnete Listen werden verwendet, wenn der Referenzort benötigt wird. Zum Beispiel: Flüge als nächstes und vor einem Datum in einer Anwendung finden.

Ein Speicher-Spreizbaum für die binäre Suche ist großartig und wird häufiger verwendet.

Liste überspringen Vs Splay Tree Vs Hash Table Runtime im Wörterbuch find op