webentwicklung-frage-antwort-db.com.de

Liste überspringen vs. Binärer Suchbaum

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

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

207
Claudiu

Überspringlisten sind für den gleichzeitigen Zugriff/die gleichzeitige Änderung leichter zugänglich. Herb Sutter schrieb einen Artikel über Datenstruktur in gleichzeitigen Umgebungen. Es hat mehr detaillierte Informationen.

Die am häufigsten verwendete Implementierung eines binären Suchbaums ist 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. Es müssen nur Knoten gesperrt werden, die direkt mit dem betroffenen Knoten verknüpft sind.


Update von Jon Harrops Kommentaren

Ich habe die neueste Arbeit von Fraser und Harris gelesen Gleichzeitige Programmierung ohne Sperren . Wirklich gutes Zeug, wenn Sie an sperrenfreien Datenstrukturen interessiert sind. Der Artikel konzentriert sich auf Transactional Memory und eine theoretische Operation zum Vergleichen und Vertauschen von MCAS mit mehreren Wörtern. Beide werden in der Software simuliert, da sie noch nicht von der Hardware unterstützt werden. Ich bin ziemlich beeindruckt, dass sie MCAS überhaupt in Software bauen konnten.

Ich fand das Transaktionsspeicher-Zeug nicht besonders überzeugend, da es einen Müllsammler erfordert. Auch Software-Transaktionsspeicher leidet unter Leistungsproblemen. Ich würde mich jedoch sehr freuen, wenn Hardware-Transaktionsspeicher jemals üblich wird. Am Ende ist es immer 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 einige sehr informative Grafiken auf den Seiten 50, 53 und 54 enthält.

  • Das Sperren von Überspringlisten ist wahnsinnig schnell. Sie lassen sich mit der Anzahl der gleichzeitigen Zugriffe unglaublich gut skalieren. Dies ist es, was Skip-Listen zu etwas Besonderem macht. Andere sperrenbasierte Datenstrukturen neigen dazu, unter Druck zu quaken.
  • Sperrfreie Sprunglisten sind durchweg schneller als das Sperren von Sprunglisten, jedoch nur knapp.
  • Transaktionsüberspringlisten sind durchweg 2-3-mal langsamer als die sperrenden und nicht sperrenden Versionen.
  • Sperren von rot-schwarzen Bäumen unter gleichzeitigem Zugriff quaken. Ihre Leistung verschlechtert sich linear mit jedem neuen gleichzeitigen Benutzer. Von den beiden bekannten Rot-Schwarz-Baum-Sperrimplementierungen hat eine im Wesentlichen eine globale Sperre während des Neuausgleichs des Baums. 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).
  • rot-schwarze Transaktionsbäume sind mit Transaktionsüberspringlisten vergleichbar. Das war sehr überraschend und sehr vielversprechend. Transaktionsspeicher, wenn auch langsamer, wenn auch viel einfacher zu schreiben. Es kann so einfach wie schnelles Suchen und Ersetzen auf der nicht-gleichzeitigen Version sein.

Aktualisieren
Hier ist ein Artikel über Bäume ohne Sperre: Bäume ohne Sperre, rot-schwarz mit CAS .
Ich habe nicht tief hineingeschaut, aber oberflächlich betrachtet scheint es solide zu sein.

239
deft_code

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

Eine Sprungliste entspricht einem zufällig ausgewogenen binären Suchbaum (RBST), wie in Dean und Jones ' "Erforschung der Dualität zwischen Sprunglisten und binären Suchbäumen" .

Umgekehrt können Sie auch deterministische Überspringlisten haben, die Worst-Case-Performance 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 BSTs mit Schwerpunkt auf Parallelität besteht darin, dass Sie nicht auf einfache Weise dieselben Garantien für das Ausgleichen erhalten wie bei einem Rot-Schwarz-Baum (RB). ("Standard" -Sprunglisten, dh zufällige Listen, geben 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, also Entspannte RB-Bäume werden normalerweise verwendet, wenn eine gute Parallelität gewünscht wird. Die Entspannung besteht darin, den Baum nicht gleich wieder ins Gleichgewicht zu bringen. Für eine etwas veraltete (1998) Umfrage siehe Hankes '' Die Leistung von simultanen Rot-Schwarz-Baum-Algorithmen '' [ps.gz] .

Eine der jüngsten Verbesserungen bei diesen ist der sogenannte Chromatic Tree (im Grunde haben Sie ein gewisses Gewicht, so dass Schwarz 1 und Rot Null wäre Sie können aber auch Werte dazwischen zulassen. Und wie verhält sich ein chromatischer Baum gegenüber der Überspringliste? Mal sehen, was Brown et al. "Eine allgemeine Technik für nicht blockierende Bäume" (2014) muss sagen:

mit 128 Threads übertrifft unser Algorithmus den nicht blockierenden Skilisten von Java um 13% bis 156%, den auf Sperren basierenden AVL-Baum von Bronson et al. von 63% auf 224% und eine RBT, die 13- bis 134-mal Software Transactional Memory (STM) verwendet

BEARBEITEN, um hinzuzufügen: Pughs sperrenbasierte Überspringliste, die in Fraser und Harris (2007) "Concurrent Programming Without Lock" als nahezu sperrenfrei eingestuft wurde ( ein Punkt, auf den in der oberen Antwort hier reichlich bestanden wird), wird auch für eine gute gleichzeitige Operation optimiert, vgl. Pughs "Concurrent Maintenance of Skip Lists" , wenn auch in eher milder Weise. Trotzdem eine neuere Veröffentlichung "A Simple Optimistic skip-list Algorithm" von Herlihy et al., Die eine vermeintlich einfachere (als Pughs) sperrenbasierte Implementierung von gleichzeitigen Sprunglisten vorschlägt kritisierte Pugh, dass er keinen für sie überzeugenden Beweis für die Richtigkeit erbracht habe. Abgesehen von dieser (möglicherweise zu pedantischen) Bedenken haben Herlihy et al. zeigen, dass ihre einfachere sperrenbasierte Implementierung einer Überspringliste tatsächlich nicht skalierbar ist, ebenso wie die sperrenfreie Implementierung des JDK, jedoch nur für hohe Konkurrenz (50% Einfügungen, 50% Löschungen und 0% Nachschlagevorgänge) ... die Fraser und Harris hat überhaupt nicht getestet; Fraser und Harris haben nur 75% Lookups, 12,5% Inserts und 12,5% Deletes getestet (auf der Skip-Liste mit ~ 500K Elementen). Die einfachere Implementierung von Herlihy et al. kommt auch der lock-free-Lösung des JDK nahe, wenn nur wenige Tests durchgeführt wurden (70% Lookups, 20% Inserts, 10% Deletes); Sie haben die Lösung ohne Sperre für dieses Szenario tatsächlich übertroffen, als sie ihre Sprungliste groß genug gemacht haben, d. h. von 200.000 auf 2 Millionen Elemente, sodass die Wahrscheinlichkeit von Konflikten mit einer Sperre vernachlässigbar wurde. Es wäre schön gewesen, wenn Herlihy et al. Sie waren über Pughs Beweis hinweggekommen und hatten auch seine Implementierung getestet, aber das taten sie leider nicht.

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

enter image description here

"Algo.4" ist ein Vorläufer (ältere Version, 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 Herlihy oben erwähnt; Wie Sie sehen, wird es bei Updates in den Papierkorb geworfen und auf den hier verwendeten Intel-CPUs viel schlimmer als auf den Sun-CPUs aus dem Originaldokument. "Algo.28" ist ConcurrentSkipListMap vom JDK. Es funktioniert nicht so gut, wie man es sich erhofft hätte, verglichen mit anderen CAS-basierten Implementierungen von Überspringlisten. Die Gewinner unter den umkämpften Gewinnern sind "Algo.2", ein auf Sperren basierender Algorithmus (!!), der von Crain et al. in "A Contention-Friendly Binary Search Tree" und "Algo.30" ist der "rotierende Skiplist" aus "Logarithmische Datenstrukturen für Multicores" . "Algo.29" ist die "Keine nicht blockierende Hotspot-Überspringliste" . Bitte beachten Sie, dass Gramoli Mitautor aller drei Artikel zum Gewinner-Algorithmus ist. "Algo.27" ist die C++ - Implementierung von Frasers Überspringliste.

Gramolis Fazit ist, dass es viel einfacher ist, eine CAS-basierte Concurrent-Tree-Implementierung zu vermasseln, als eine ähnliche Skip-Liste zu vermasseln. Und auf der Grundlage der Zahlen ist es schwer zu widersprechen. Seine Erklärung für diese Tatsache lautet:

Die Schwierigkeit beim Entwerfen eines Baums, der keine Sperren enthält, ergibt sich aus der Schwierigkeit, mehrere Referenzen atomar zu ändern. Überspringlisten bestehen aus Türmen, die durch 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 und darunter hat. Ein Hauptunterschied besteht jedoch darin, dass der Abwärtszeiger im Allgemeinen unveränderlich ist, wodurch die atomare Modifikation eines Knotens vereinfacht wird. Diese Unterscheidung ist wahrscheinlich der Grund, warum Skip-Listen Bäume, die stark umkämpft sind, übertreffen (siehe Abbildung [oben]).

Die Überwindung dieser Schwierigkeit war ein zentrales Anliegen der jüngsten Arbeit von Brown et al. Sie haben eine eigene (2013) Veröffentlichung "Pragmatische Primitive für nicht blockierende Datenstrukturen" zum Aufbau von zusammengesetzten LL/SC-Primitiven mit mehreren Datensätzen, die sie LLX/SCX nennen , selbst implementiert mit (Maschinenebene) CAS. Brown et al. haben diesen LLX/SCX-Baustein in ihrer 2014 (aber nicht in ihrer 2011) gleichzeitigen Baumimplementierung verwendet.

Ich denke, es lohnt sich vielleicht auch, hier die Grundgedanken der "no hot spot"/contention friendly (CF) -Übersprungliste zusammenzufassen. Es fügt eine wesentliche Idee aus den entspannten RB-Bäumen (und ähnlichen konkretistischen Datenstrukturen) hinzu: Die Türme werden nicht mehr sofort nach dem Einfügen aufgebaut, sondern verzögert, bis weniger Konflikte auftreten. Umgekehrt kann die Streichung eines hohen Turms viele Konflikte hervorrufen. Dies wurde bereits in Pughs gleichzeitigem Überspringlistenpapier von 1990 beobachtet, weshalb Pugh eine Zeigerumkehr beim Löschen einführte (ein Leckerbissen, das Wikipedia auf Ü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 seine Autoren als "Adapting Thread" bezeichnen.

Der Synchrobench-Code (einschließlich aller getesteten Algorithmen) ist verfügbar unter: https://github.com/gramoli/synchrobench . Das neueste Patent von 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 Maschine verfügbar? J/K Mein Punkt ist, dass Sie diese selbst ausführen können.

75
Fizz

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

12
Evan Teran

In der Praxis habe ich festgestellt, dass die Leistung von B-Tree in meinen Projekten besser war als die von Skip-Listen. Überspringende Listen scheinen einfacher zu verstehen, aber die Implementierung eines B-Baums ist nicht das schwer.

Der einzige Vorteil, den ich kenne, ist, dass einige clevere Leute herausgefunden haben, wie man eine sperrenfreie gleichzeitige Überspringliste implementiert, die nur atomare Operationen verwendet. Zum Beispiel 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 parallele B-Baum-Variante zu schreiben - ich habe es von jemand anderem gesehen -, wenn Sie Knoten "nur für den Fall" beim Abstieg aufteilen und zusammenführen, müssen Sie dies nicht tun Sorgen Sie sich um Deadlocks und müssen Sie immer nur ein Schloss auf zwei Ebenen des Baums gleichzeitig halten. Der Synchronisationsaufwand wird etwas höher sein, aber der B-Baum ist wahrscheinlich schneller.

9
Jonathan

Aus dem Wikipedia Artikel, den Sie zitiert haben:

Θ (n) Operationen, die uns zwingen, jeden Knoten in aufsteigender Reihenfolge zu besuchen (z. B. das Drucken der gesamten Liste), bieten die Möglichkeit, die Ebenenstruktur der Überspringliste im Hintergrund auf optimale Weise zu derandomisieren. Bringen Sie die Überspringliste zur Suchzeit O (log n). [...] Eine Überspringliste, für die wir in letzter Zeit keine derartigen Θ (n) -Operationen durchgeführt haben , bietet nicht die gleichen absoluten Garantien für die Leistung im ungünstigsten Fall wie traditionell ausgewogene Baumdatenstrukturen , da es immer (wenn auch mit sehr geringer Wahrscheinlichkeit) möglich ist, dass die zur Erstellung der Überspringliste verwendeten Münzwürfe eine schlecht ausgeglichene Struktur ergeben

BEARBEITEN: Es ist also ein Kompromiss: Überspringende Listen verbrauchen weniger Speicher, und es besteht die Gefahr, dass sie zu einem unausgeglichenen Baum ausarten.

8
Mitch Wheat

Überspringlisten werden mithilfe von Listen implementiert.

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

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

(Beachten Sie, dass MCAS, das mit CAS erstellt wurde, 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 :-)

2
Blank Xavier