Pomiń listę a drzewo wyszukiwania binarnego

Ostatnio natknąłem się na strukturę danych znaną jako lista pominięć . Wygląda na bardzo podobne zachowanie do drzewa wyszukiwania binarnego.

Dlaczego miałbyś kiedykolwiek chcieć używać listy pominięć w drzewie wyszukiwania binarnego?

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.

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.

„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ć.

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.

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.

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.

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 :-)

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