Pomiń listę a drzewo wyszukiwania binarnego


Odpowiedzi:


257

Listy pomijania są bardziej podatne na równoczesny dostęp / modyfikację. Herb Sutter napisał artykuł o strukturze danych we współbieżnych środowiskach. Ma więcej szczegółowych informacji.

Najczęściej stosowaną implementacją drzewa wyszukiwania binarnego jest drzewo czerwono-czarne . Równoległe problemy pojawiają się, gdy drzewo jest modyfikowane, często musi zostać ponownie zrównoważone. Operacja ponownego równoważenia może wpływać na duże części drzewa, co wymagałoby blokady mutex w wielu węzłach drzewa. Wstawienie węzła do listy pominięć jest znacznie bardziej zlokalizowane, tylko węzły bezpośrednio połączone z danym węzłem muszą zostać zablokowane.


Aktualizacja komentarzy Jona Harropsa

Przeczytałem najnowszy artykuł Fraser i Harrisa Równoczesne programowanie bez blokad . Naprawdę dobre rzeczy, jeśli interesują Cię struktury danych bez blokowania. Artykuł koncentruje się na pamięci transakcyjnej i teoretycznej operacji MCAS z porównywaniem i zamianą wielu słów. Oba są symulowane w oprogramowaniu, ponieważ nie obsługuje ich jeszcze żaden sprzęt. Jestem pod wrażeniem, że w ogóle byli w stanie zbudować MCAS w oprogramowaniu.

Nie uważałem transakcji pamięci za szczególnie atrakcyjne, ponieważ wymagają one modułu wyrzucania elementów bezużytecznych. Również oprogramowanie związane z pamięcią transakcyjną ma problemy z wydajnością. Byłbym jednak bardzo podekscytowany, gdyby sprzętowa pamięć transakcyjna stała się powszechna. W końcu są to badania i nie będą one przydatne dla kodu produkcyjnego przez kolejną dekadę.

W sekcji 8.2 porównują one wydajność kilku współbieżnych implementacji drzewa. Podsumuję ich ustalenia. Warto pobrać plik pdf, ponieważ zawiera on bardzo pouczające wykresy na stronach 50, 53 i 54.

  • Blokowanie list pomijania jest niesamowicie szybkie. Skalują się niewiarygodnie dobrze przy liczbie równoczesnych dostępów. To sprawia, że ​​listy pominięć są wyjątkowe, inne struktury danych oparte na blokadach mają tendencję do skakania pod presją.
  • Listy pomijania bez blokady są konsekwentnie szybsze niż listy pomijania, ale tylko nieznacznie.
  • transakcyjne listy pominięć są konsekwentnie 2-3 razy wolniejsze niż wersje blokująca i nieblokująca.
  • blokując czerwono-czarne drzewa rechoczące pod jednoczesnym dostępem. Ich wydajność zmniejsza się liniowo z każdym nowym równoczesnym użytkownikiem. Spośród dwóch znanych blokujących czerwono-czarnych implementacji drzewa, jedna zasadniczo ma globalną blokadę podczas ponownego równoważenia drzewa. Drugi używa wymyślnej (i skomplikowanej) eskalacji blokady, ale nadal nie wykonuje znacząco globalnej wersji blokady.
  • czerwono-czarne drzewa bez blokady nie istnieją (nie jest już prawdą, patrz Aktualizacja).
  • transakcyjnie czerwono-czarne drzewa są porównywalne z transakcyjnymi listami przewozowymi. To było bardzo zaskakujące i bardzo obiecujące. Pamięć transakcyjna, choć wolniejsza, ale o wiele łatwiejsza do napisania. Może być tak proste, jak szybkie wyszukiwanie i zamiana w wersji niebieżnej.

Aktualizacja
Oto artykuł o drzewach bez blokady : Drzewa bez blokady czerwono-czarne za pomocą CAS .
Nie zagłębiłem się w to głęboko, ale na powierzchni wydaje się solidna.


3
Nie wspominając już o tym, że na nie-zdegenerowanej liście narciarskiej około 50% węzłów powinno mieć tylko jedno łącze, które sprawia, że ​​wstawianie i usuwanie jest wyjątkowo wydajne.
Adisak

2
Ponowne równoważenie nie wymaga blokady mutex. Zobacz cl.cam.ac.uk/research/srg/netos/lock-free
Jon Harrop

3
@Jon, tak i nie. Nie są znane żadne wolne od blokady implementacje czerwono-czarnego drzewa. Fraser i Harris pokazują, w jaki sposób zaimplementowano czerwono-czarne drzewo oparte na pamięci transakcyjnej i jego wydajność. Pamięć transakcyjna jest nadal bardzo ważna na arenie badawczej, więc w kodzie produkcyjnym czerwono-czarne drzewo nadal będzie musiało zablokować duże części drzewa.
deft_code

4
@deft_code: Intel ogłosił niedawno implementację Transactional Memory przez TSX na Haswell. Może to okazać się interesujące w przypadku wspomnianych struktur danych bez blokowania.
Mike Bailey

2
Myślę, że odpowiedź Fizz jest bardziej aktualna (od 2015 r.) Niż ta odpowiedź (2012 r.) I dlatego do tej pory prawdopodobnie powinna być preferowaną odpowiedzią.
fnl

81

Po pierwsze, nie można rzetelnie porównać losowej struktury danych z taką, która daje najgorsze gwarancje.

Lista pominięć jest równoważna losowo zbalansowanemu drzewu wyszukiwania binarnego (RBST) w sposób wyjaśniony bardziej szczegółowo w Dean and Jones „Exploring the Duality Between Skip Lists and Binary Search Trees” .

Odwrotnie, możesz również mieć deterministyczne listy pominięć, które gwarantują najgorsze wyniki, por. Munro i in.

W przeciwieństwie do tego, co twierdzą niektórzy powyżej, możesz mieć implementacje drzew wyszukiwania binarnego (BST), które działają dobrze w programowaniu współbieżnym. Potencjalny problem z BST zorientowanymi na współbieżność polega na tym, że nie można łatwo uzyskać tego samego, co ma gwarancje równoważenia, jak w przypadku drzewa czerwono-czarnego (RB). (Ale „standardowe”, tj. Losowe, listy pomijania również nie dają tych gwarancji.) Istnieje kompromis między utrzymywaniem równowagi przez cały czas a dobrym (i łatwym do zaprogramowania) równoczesnym dostępem, więc zwykle używane są zrelaksowane drzewa RB kiedy pożądana jest dobra współbieżność. Relaks polega na niezwłocznym przywróceniu równowagi w drzewie. Dla nieco przestarzałej (1998) ankiety zobacz Hanke's „The Performance of Concurrent Red-Black Tree Algorytmy” [ps.gz] .

Jednym z najnowszych ulepszeń jest tak zwane drzewo chromatyczne (w zasadzie masz trochę takiej wagi, że czarny będzie miał 1, a czerwony będzie zero, ale dopuszczasz również wartości pomiędzy). A jak wygląda drzewo chromatyczne na liście pominięć? Zobaczmy, co Brown i in. „Ogólna technika drzew nieblokujących” (2014) musi powiedzieć:

z 128 wątkami nasz algorytm przewyższa nieblokującą listę Skiplista Javy o 13% do 156%, drzewo AVL oparte na blokadzie Bronson i in. o 63% do 224%, a RBT, który wykorzystuje programową pamięć transakcyjną (STM) 13 do 134 razy

EDYCJA, aby dodać: lista pominięć oparta na blokadzie Pugh, która została porównana w testach „Concurrent Programming Without Lock” Frasera i Harrisa (2007), jako zbliżających się do ich własnej wersji bez blokady (punkt, na który zdecydowanie nalegał w górnej odpowiedzi tutaj), jest również dostosowywany pod kątem dobrego współbieżnego działania, por. „Równoczesne utrzymanie list pomijanych” Pugh , choć w dość łagodny sposób. Niemniej jednak jeden z nowszych artykułów z 2009 r. „Prosty optymistyczny algorytm listy pomijania”przez Herlihy i wsp., który proponuje rzekomo prostszą (niż Pugh) opartą na blokadzie implementację współbieżnych list pominięć, skrytykował Pugh za brak dostatecznego dla nich dowodu poprawności. Odkładając na bok ten (może zbyt pedantyczny) skrupułów, Herlihy i in. pokazują, że ich prostsza implementacja listy pominięć oparta na blokowaniu faktycznie nie skaluje się, podobnie jak implementacja JDK bez blokady, ale tylko dla dużej rywalizacji (50% wstawień, 50% usunięć i 0% wyszukiwań) ... które Fraser a Harris wcale nie testował; Fraser i Harris przetestowali tylko 75% wyszukiwań, 12,5% wstawek i 12,5% usunięć (na liście pominięć z ~ 500 000 elementów). Prostsze wdrożenie Herlihy i in. zbliża się również do rozwiązania blokującego z JDK w przypadku niskiej rywalizacji, którą przetestowali (70% wyszukiwań, 20% wstawień, 10% usunięć); faktycznie pokonali rozwiązanie bez blokady dla tego scenariusza, kiedy zrobili wystarczająco dużą listę pominięć, tj. przechodząc z 200K do 2M elementów, tak że prawdopodobieństwo rywalizacji o dowolną blokadę stało się znikome. Byłoby miło, gdyby Herlihy i in. przeszli przez zawieszenie się na dowodzie Pugh i przetestowali jego implementację, ale niestety nie zrobili tego.

EDYCJA 2: Znalazłem (opublikowaną w 2015 r.) Matkę wszystkich testów porównawczych: „Więcej niż kiedykolwiek chciałeś wiedzieć o synchronizacji Gramoli. Synchrobench, Pomiar wpływu synchronizacji na współbieżne algorytmy” : Oto fragment zdjęcia odpowiadający temu pytaniu.

wprowadź opis zdjęcia tutaj

„Algo.4” jest prekursorem (starsza wersja z 2011 r.) Wspomnianego wyżej Browna i in. (Nie wiem, o ile lepsza lub gorsza jest wersja 2014). „Algo.26” to wspomniany wyżej Herlihy; jak widać, jest on niszczony przez aktualizacje i znacznie gorzej na zastosowanych tutaj procesorach Intel niż na procesorach Sun z oryginalnego papieru. „Algo.28” to ConcurrentSkipListMap z JDK; nie działa tak dobrze, jak można by się spodziewać w porównaniu z innymi implementacjami list pomijania opartymi na CAS. Zwycięzcami o wysokiej rywalizacji są „Algo.2” algorytm blokujący (!!) opisany przez Crain i in. w „A drzewku wyszukiwania binarnego przyjaznym dla rywalizacji i „Algo.30” jest „rotującą listą narciarską” z „Logarytmicznych struktur danych dla multicores” . „. Informujemy, że Gramoli jest współautorem wszystkich trzech artykułów z algorytmem zwycięzcy. „Algo.27” to implementacja C ++ listy pominięć Frasera.

Wniosek Gramoli jest o wiele łatwiejszy do zepsucia opartej na CAS implementacji drzewa współbieżnego niż do zepsucia podobnej listy pominięć. Na podstawie danych liczbowych trudno się nie zgodzić. Wyjaśnia to:

Trudność w zaprojektowaniu drzewa bez blokady wynika z trudności z atomową modyfikacją wielu odniesień. Listy pomijania składają się z wież połączonych ze sobą za pomocą wskaźników następczych, w których każdy węzeł wskazuje węzeł bezpośrednio pod nim. Często uważa się je za podobne do drzew, ponieważ każdy węzeł ma następcę w wieży następcy, a pod nią, jednak głównym rozróżnieniem jest to, że wskaźnik skierowany w dół jest zasadniczo niezmienny, a zatem upraszcza atomową modyfikację węzła. To rozróżnienie jest prawdopodobnie przyczyną, dla której listy pomijania przewyższają drzewa pod silną rywalizacją, jak pokazano na rycinie [powyżej].

Przezwyciężenie tej trudności było głównym problemem w najnowszej pracy Browna i wsp. Mają cały osobny (2013) artykuł „Pragmatyczne prymitywy dla nieblokujących struktur danych” na temat budowania wielu rekordów „prymitywów” związku LL / SC, które nazywają LLX / SCX, które same zostały zaimplementowane przy użyciu (na poziomie maszyny) CAS. Brown i in. użył tego bloku konstrukcyjnego LLX / SCX w swojej implementacji drzewa współbieżnego 2014 (ale nie w 2011).

Myślę, że być może warto również streścić tutaj podstawowe idee listy pominięć „bez gorących punktów” / przyjaznych dla rywalizacji (CF). Dodaje zasadniczy pomysł z rozluźnionych drzew RB (i podobnych struktur danych ze smażącą współbieżnością): wieże nie są już budowane natychmiast po wstawieniu, ale opóźniają się, dopóki nie będzie mniej rywalizacji. I odwrotnie, usunięcie wysokiej wieży może wywołać wiele kontrowersji; zaobserwowano to już w równoległym dokumencie Pugh z 1990 r., dlatego Pugh wprowadził odwrócenie wskaźnika po usunięciu (ciekawostka, której strona Wikipedii na listach pomijanych nadal niestety nie wspomina). Lista pominięć CF idzie o krok dalej i opóźnia usuwanie górnych poziomów wysokiej wieży. Oba rodzaje opóźnionych operacji na listach pomijania CF są wykonywane przez (oparty na CAS) oddzielny wątek podobny do śmieciarza, który jego autorzy nazywają „wątkiem dostosowującym”.

Kod Synchrobench (w tym wszystkie przetestowane algorytmy) jest dostępny na stronie : https://github.com/gramoli/synchrobench . Najnowszy Brown i in. implementacja (nieuwzględniona powyżej) jest dostępna na stronie http://www.cs.toronto.edu/~tabrown/chromatic/ConcurrentChromaticTreeMap.java Czy ktoś ma dostęp do 32-rdzeniowej maszyny? J / K Chodzi mi o to, że możecie sami je uruchomić.


12

Oprócz udzielonych odpowiedzi (łatwość implementacji w połączeniu z porównywalną wydajnością do zrównoważonego drzewa). Uważam, że implementacja przechodzenia w kolejności (do przodu i do tyłu) jest znacznie prostsza, ponieważ lista pominięć skutecznie zawiera listę połączoną wewnątrz swojej implementacji.


1
czy przechodzenie w kolejności dla drzewa bin nie jest tak proste jak: „def func (węzeł): func (lewy (węzeł)); op (węzeł); func (prawy (węzeł))”?
Claudiu

6
Jasne, że to prawda, jeśli chcesz przejść wszystko w jednym wywołaniu funkcji. ale staje się o wiele bardziej irytujące, jeśli chcesz mieć iterator w stylu jak w std :: map.
Evan Teran

@Evan: Nie w funkcjonalnym języku, w którym można po prostu pisać w CPS.
Jon Harrop,

@Evan: def iterate(node): for child in iterate(left(node)): yield child; yield node; for child in iterate(right(node)): yield child;? =). kontrola nielokalna jest awesom .. @Jon: pisanie w CPS jest uciążliwe, ale może masz na myśli kontynuacje? Generatory są w zasadzie specjalnym przypadkiem kontynuacji Pythona.
Claudiu

1
@Evan: tak, działa tak długo, jak parametr węzła jest wycinany z drzewa podczas modyfikacji. Przechodzenie w C ++ ma takie samo ograniczenie.
deft_code

10

W praktyce odkryłem, że wydajność B-drzewa w moich projektach okazała się lepsza niż listy pominięć. Listy pomijane wydają się łatwiejsze do zrozumienia, ale wdrożenie B-drzewa nie jest takie trudne.

Jedną z zalet, o których wiem, jest to, że niektórzy sprytni ludzie wymyślili, jak zaimplementować równoczesną listę pominięć bez blokady, która wykorzystuje tylko operacje atomowe. Na przykład Java 6 zawiera klasę ConcurrentSkipListMap, a jeśli jesteś szalony, możesz odczytać do niej kod źródłowy.

Ale nie jest też zbyt trudne napisanie współbieżnego wariantu B-drzewa - widziałem to zrobione przez kogoś innego - jeśli zapobiegawczo rozdzielisz i scalisz węzły „na wszelki wypadek”, idąc w dół drzewa, nie będziesz musiał martwcie się impasem i zawsze musicie trzymać zamek na dwóch poziomach drzewa jednocześnie. Narzut związany z synchronizacją będzie nieco wyższy, ale B-drzewo jest prawdopodobnie szybszy.


4
Myślę, że nie powinieneś nazywać Binary Tree B-Tree, istnieje zupełnie inna DS o tej nazwie
Shihab Shahriar Khan

8

Z cytowanego artykułu z Wikipedii :

Θ (n) operacje, które zmuszają nas do odwiedzania każdego węzła w porządku rosnącym (takie jak wydrukowanie całej listy) dają możliwość przeprowadzenia za kulisami derandomizacji struktury poziomu listy pominięć w optymalny sposób, sprowadzając listę pominięć do czasu wyszukiwania O (log n). [...] Lista pominięć, na której ostatnio nie przeprowadziliśmy [takich] operacji Θ (n), nie zapewnia takich samych bezwzględnych gwarancji wydajności w najgorszym przypadku jak bardziej tradycyjnych zrównoważonych struktur danych drzewa , ponieważ zawsze jest to możliwe (choć z bardzo małym prawdopodobieństwem), że rzuty monetą użyte do zbudowania listy pominięć wytworzą źle zrównoważoną strukturę

EDYCJA: więc jest to kompromis: listy pomijane zużywają mniej pamięci na ryzyko, że mogą przekształcić się w niezrównoważone drzewo.


byłby to powód, aby nie używać listy pominięć.
Claudiu,

7
cytując MSDN, „Szanse [na 100 elementów poziomu 1] wynoszą dokładnie 1 na 1 266 650 600, 228,229,401,496,703,205,376”.
peterchen

8
Dlaczego powiedziałbyś, że zużywają mniej pamięci?
Jonathan

1
@peterchen: Rozumiem, dziękuję. Czy to nie występuje w deterministycznych listach pominięć? @Mitch: „Listy pomijania zużywają mniej pamięci”. W jaki sposób listy pominięć zużywają mniej pamięci niż zrównoważone drzewa binarne? Wygląda na to, że mają 4 wskaźniki w każdym węźle i zduplikowanych węzłach, podczas gdy drzewa mają tylko 2 wskaźniki i nie mają duplikatów.
Jon Harrop,

1
@Jon Harrop: Węzły na poziomie pierwszym potrzebują tylko jednego wskaźnika na węzeł. Wszystkie węzły na wyższych poziomach potrzebują tylko dwóch wskaźników na węzeł (jeden do następnego węzła i jeden do poziomu poniżej niego), choć oczywiście węzeł poziomu 3 oznacza, że ​​używasz łącznie 5 wskaźników dla tej jednej wartości. Oczywiście nadal będzie to zajmowało dużo pamięci (więcej niż wyszukiwanie binarne, jeśli chcesz niepotrzebnej listy pominięć i dużego zestawu danych) ... ale myślę, że coś mi brakuje ...
Brian

2

Listy pomijania są realizowane za pomocą list.

Istnieją rozwiązania bez blokady dla pojedynczo i podwójnie połączonych list - ale nie ma rozwiązań bez blokady, które bezpośrednio wykorzystują tylko CAS dla dowolnej struktury danych O (logn).

Możesz jednak użyć list opartych na CAS, aby utworzyć listy pominięć.

(Należy zauważyć, że MCAS, który jest tworzony przy użyciu CAS, pozwala na dowolne struktury danych i drzewko czerwono-czarne proof of concept zostało utworzone przy użyciu MCAS).

Choć dziwne, okazują się bardzo przydatne :-)


5
„nie ma rozwiązań bez blokady, które bezpośrednio wykorzystują tylko CAS dla dowolnej struktury danych O (logn)”. Nie prawda. Przykłady liczników patrz cl.cam.ac.uk/research/srg/netos/lock-free
Jon Harrop

-1

Listy pomijania mają tę zaletę, że usuwają blokady. Ale czas działania zależy od tego, w jaki sposób zostanie ustalony poziom nowego węzła. Zwykle odbywa się to za pomocą Random (). W słowniku zawierającym 56 000 słów lista pominięć zajęła więcej czasu niż drzewo splay, a drzewo zajęło więcej czasu niż tabela haszująca. Pierwsze dwa nie mogły się równać z czasem działania tabeli mieszającej. Również tablicę tablicy skrótów można jednocześnie rozdzielić blokadą.

Lista pomijania i podobne uporządkowane listy są używane, gdy potrzebna jest lokalizacja odniesienia. Na przykład: znajdowanie lotów we wniosku przed i przed datą.

Drzewo binarnych drzewek wyszukiwania wyszukiwania jest świetne i częściej używane.

Pomiń listę Vs Splay Tree vs. Hash Tabela Środowisko uruchomieniowe w słowniku znajdź op


Rzuciłem okiem i twoje wyniki pokazują, że SkipList jest szybszy niż SplayTree.
Chinasaur

Wprowadzanie losowości jako części listy pomyłek jest mylące. Kluczowe znaczenie ma sposób pomijania elementów. Dochodzi do losowania struktur probabilistycznych.
user568109,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.