Judy Array: Dostosowana Drzewa Trie świadomie pamięciowe |…

Podstawa 256-Way Radix Trie

Judy array jest podstawowym *digital trie* lub radix tree, który konstruuje się na bajtach klucza zamiast porównując całe klucze. Dla 32-bitowego klucza całkowitego, drzewo ma do czterech poziomów, jeden dla każdego bajtu, a w każdym poziomie węzeł może gałęzić się w do maksymalnie 256 kierunkach, ponieważ bajt zawiera 256 różnych wartości. Przechodzenie od korzenia do liścia zajmuje zatem ograniczoną liczbę kroków, co najwyżej cztery dla klucza 32-bitowego lub ośmie dla klucza 64-bitowego, całkowicie niezależnie od liczby przechowywanych w drzewie kluczy. To jest kluczowa strukturalna różnica względem porównawczych drzew, takich jak drzewa czerwonokolorowe lub B-trees, gdzie długość ścieżki rośnie z logarytmem liczby przechowywanych kluczy. W drzewie Judy długość ścieżki jest ustalonej przez szerokość klucza, a nie przez liczbę przechowywanych kluczy, co oznacza, że koszt wyszukiwania nie zdegeneruje się wraz z rosnącym rozmiarem drzewa. Naiwny sposób na implementację 256-kierunkowego gałęziażenia na każdym poziomie to prosty tablicowy format zawierający 256 wskaźników na każdy węzeł. Jest szybki, ponieważ dla każdego poziomu wymaga tylko jednego indeksowanego dostępu do pamięci, ale jest również bardzo zdechlonizujący: węzeł mający tylko dwie lub trzy potomne nadal rezerwuje miejsca dla 256, spowodując spalone kilobyty pamięci na małą liczbę rzeczywistych wpisów. Ponieważ Judy array jest explicitnie zaprojektowany do obsługi *sparse* przestrzeni kluczy, takich jak zestaw kilkuset 64-bitowych identyfikatorów rozrzedzonych po dużym zakresie, taki naiwny format byłby przeciwne celom. Struktura przeznaczona do zapisywania pamięci nie może przydzielać równomiernie dla najgęstszej możliwej sytuacji na każdym węźle. Ta sprzeczność, chcąc prędkości *O(1)* na poziomie za pomocą bezpośredniego indeksowania, ale przestrzeni pamięci struktury, która płaci tylko za potomne węzły, jest dokładnie to, co motywuje kluczowe podejście do projektu Judy. Zamiast wybrać jednolity format węzła i akceptować jego trade-off na całym drzewie, struktura pozwala, aby format każdego węzła zmieniał się niezależnie, wybierany tak, aby pasował do rzeczywistej liczby potomnych poniżej. Węzeł blisko korzenia, który może mieć setki potomnych, może sobie pozwolić na gęste reprezentacje denseskie. Węzeł głęboko w rzadkim drzewie, który może mieć tylko jednego lub dwóch potomnych, używa małego formatu kosztującego praktycznie nic. Ta adaptowalność na poziomie węzła, zastosowana rekurencyjnie całe drzewo, jest mechanizmem badanym w kolejnym sekcji.

Reprezentacje adaptacyjne węzłów: Lista, Bitmapa i Pełny tablicowy

Serce tablicy Judy stanowią mała rodzina reprezentacji węzłów, każda dostosowana do innej zakresu populacji, z implementacją automatycznie konwertującą węzeł z jednej reprezentacji na inną podczas dodawania lub usuwania potomków. Mimo że dokładne próg i format różnią się między wariantami Judy1, JudyL i JudySL, strategia podstawowa jest zgodna i może być rozumiana jako trzy szerokie poziomy. *Listowe węzły liniowe* są używane, gdy węzeł ma tylko mało potomków, zwykle mniej niż około dziesięć. W takim przypadku węzeł przechowuje krótki uporządkowany tabliczkowy zestaw rzeczywistych wartości bajtów obecnych, zgodny z tablicą wskaźników na potomki, a znalezienie potomka oznacza krótkie skanowanie liniowe lub binarne, zamiast bezpośredniego indeksu. Jest to świadomie proste: ze względu na tak małą liczbę elementów, kompaktowa lista wygrywa nad rzadką bitmapę i 256-elementową tablicę w każdym aspekcie, pamięciowo oraz z powodu faktu, że cała lista mieści się w jednym lub dwóch liniach buforu, co przysporza szybkości. *Bitmapowe węzły* przejmują kontrolę, gdy liczba potomków wzrasta ponad zakres komfortowy listy, ale nadal jest niewielka. Zamiast przechowywać rzeczywiste wartości bajtów, bitmapa węzła używa wektora 256-bitowego, 32 bajtów, z jednym ustawionym bitym dla każdego bajtu, który ma potomka, oraz skompaktowaną tabliczkową listę wskaźników tylko dla istniejących potomków. Znalezienie potomka oznacza testowanie jednego bity i następnie liczenie ustawionych bitów przed nim, czyli *liczba populacji*, aby znaleźć indeks wskaźnika w skompaktowanej tablicy. Ta reprezentacja jest znacznie gęstsza niż lista, gdy jest już kilkudziesiąt potomków, ale nadal unika zarezerwowania miejsca dla brakujących potomków. *Pełne tablicowe węzły* są przeznaczone dla węzłów, gdzie większość lub cała 256 możliwych wartości bajtów prowadzi do potomka. Tutaj Judy wraca do prostej tablicy direct-indexed z 256 wskaźnikami, ponieważ przy tak gęstym rozkładzie koszt operacji liczenia populacji bitmapy już nie płaci się za siebie, a pojedyncze operacje indeksowe są najbardziej efektywne i pamięciożerne. Podczas dodawania i usuwania potomków przesuwa się populację węzła przez te prógi, Judy transparentnie przemienia węzeł między reprezentacjami, tak że cała struktura używa zawsze najbardziej lokalnie odpowiedniej formy, nigdy nie płaci gęsto za rzadkość ani sparsowanie za gęstość.

Dlaczego świadomość linii pamięci jest nieodłączna od projektowania

Wybór odpowiedniej reprezentacji dla populacji węzła jest tylko połoviną historii inżynieryjnej Judy; druga połowa polega na tym, że każda reprezentacja jest świadomie rozmiarów i ułożenia z myślą o zachowaniu linii pamięci CPU, co zwykle oznacza typowe 64-bajtowe linie pamięci znalezionych na większości procesorów, dla których Judy została zaprojektowana. Przejście przez drzewo trie nominalnie *O(1)* na poziomie w asymptotycznej przestrzeni może nadal być wolne w praktyce, jeśli dostęp do każdego poziomu węzła spowoduje brak wejścia do pamięci RAM, ponieważ brak wejścia do pamięci RAM może kosztować około stu razy więcej cykli niż dostęp do L1 lub L2 cache. Projektanci Judy traktowali minimalizację braków wejść do pamięci jako główny cel równie ważny jak minimalizacja obwodu pamięciowego, i kształtowali formaty listy, bitmapy i tablicy węzłów tak, aby pojedynczy węzeł lub mała stała liczba z nich zwykle pasowała do jednej lub dwóch linii pamięci. To ma konkretne konsekwencje dla implementacji. Reprezentacja bitmapy 256-bitowego wektora jest dokładnie cztery 64-bajtowe słowa, wystarczająco małe, aby można było je przetestować i zliczyć przy użyciu tylko kilku instrukcji maszynowych bez przerwania na wiele linii pamięci. Małe węzły listy są utrzymywane w taki sposób, że bajty klucza i ich wskaźniki bracia często mieszczą się w jednej linii, więc liniowy przeszukanie kilku wpisów kosztuje jedno odczyt pamięci zamiast wielu. Judy używa również technik takich jak przechowywanie szerokich fragmentów klucza bezpośrednio, gdy to możliwe, a nie pełnych wskaźników, oraz pakowanie metadanych w nieużywane bity wskazówek przekształconych do zgodności z aligmentem, aby zmieścić więcej użytecznej informacji na każdym odczytanej linii pamięci. Zyskiem jest to, że nawet jeśli tablica Judy może wykonywać kilka dostępow do węzłów, aby rozwiązać jeden klucz, każdy dostęp jest zaprojektowany tak, aby był tanio, często zcacheowanym, sekwencyjnym lub przewidywalnym odniesieniem pamięci, a nie niewyobrażalnym śledzeniem wskaźników do chłodnej pamięci. To stanowi jasną kontrast z niemączonymi strukturami podwójnie skierowanymi, takimi jak drzewa binarne niezbalansowane, gdzie każdy poziom zwykle oznacza niewyobrażalny skok do nowej alokacji w pamięci. To kombinacja, ograniczonej strukturalnie głębokości drzewa trie plus wewnętrznego zrozumienia linii pamięci, pozwala na konkurencję ze stacjonarnymi tabelami hash, które wykonują tylko jeden lub dwa dostępy do pamięci w średnim przypadku, ale rozmieszcza te dostępy nieprzewidywalnie po pamięci, szczególnie gdy czynnik obciążenia tablicy hash wzrosie lub musi ona ponownie rozmiarować.

Porządkowane kolejności, zapytania zakresowe i przeszukiwanie uporządkowane

Tablica haszująca osiąga średnio stałą czasową operację wyszukiwania, zniszczyjąc na celo relację między wartością klucza a lokalizacją przechowywania. Dobra funkcja haszująca rozrzuca podobne klucze do niespokojnych buforów. To rozrzucanie jest dokładnie tym, dlaczego tablice haszujące nie mogą efektywnie odpowiadać na pytania takie jak *znajdź najmniejszy klucz większy od X* lub *iterować wszystkie klucze między A a B w porządku*, ponieważ by to wymagało ponownego posortowania całego zestawu. Tablica Judy nie płaci podobnej ceny, ponieważ jest ona trie organizowana bezpośrednio według bajtów wartości klucza, dokładnie takiej struktury, jaką wymagałby uporządkowany reprezentacji kluczy. Dzięki temu, że dzieci każdego wewnętrznego węzła, czy przechowywane jako lista, bitmapa lub pełny tablicz, zawsze są logicznie posortowane według wartości bajtu, przeszukiwanie uporządkowane w trie Judy odwiedza klucze w stricte rosnącej kolejności bez dodatkowego kroku sortowania ani potrzeby metadanych uporządkowanych. To sprawia, że operacje takie jak *pierwszy*, *ostatni*, *następny* i *poprzedni* są naturalne i efektywne, przemieszczając się po trie w bok i w dół, folgując porządkowi bajtowemu już zapisanemu w strukturze węzła. Zapytania zakresowe, odzyskiwanie wszystkich kluczy między dwoma granicami, stają się ograniczone przeszukiwaniem trie, które odwiedza tylko węzły i liście rzeczywiście zawarte w żądanej dziedzinie, zamiast pełnego skanowania struktury. Ta zdolność do przeszukiwania uporządkowanego nie jest małą dodatkową funkcją doliczoną do Judy po fakcie; wynika ona bezpośrednio z używania trie radix jako podstawowej struktury, a nie tablicy haszującej. Praktyczne konsekwencje są istotne dla wielu rzeczywistych obciążen: struktury indeksowe bazy danych, tabele routingu IP potrzebujące do dopasowania najdłuższego prefiksu, i implementacje bitmapy lub zbioru rozrzucanej, które muszą wspierać uporządkowane przeiterowanie lub zapytania stylu najbliższego sąsiada takie jak *następny bit ustawiony po pozycji N* wszystkie od nich korzystają. Tablica haszująca może być dopasowana do podtrzymania takich zapytań za pomocą dodatkowej struktury uporządkowanej, ale to oznacza utrzymanie dwóch struktur i płatność dwóch zestawów kosztów pamięciowych i aktualizacyjnych. Judy oferuje dostęp uporządkowany jako wewnętrzna, prawie bezkosztowa właściwość swojej adaptatywnej projektu trie, jedno z najwyraźniejszych miejsc, gdzie jest ono punktem projektu, który ani tablice haszujące, ani proste drzewa równoważne nie osiągnęły samodzielnie.

Przeciwstawienie się w odniesieniu do tablic hasowych i drzew B

Judy arrays są często porównywane z trzema alternatywami: tablicami hasowymi, drzewami binarnymi równoważnymi (takimi jak czerwonokrótkie lub AVL) oraz drzewami B. Te porównania wyjaśniają dokładnie, w jakim zakresie znajduje się projekt. W stosunku do dobrze dostosowanych tablic hasowych Judy osiąga porównywalne lub często lepszą przepustowość wyszukiwania dla dużych zbiorów danych, głównie dlatego, że layouty węzłów zorientowane na pamięć cache zachowują mały i często już obecny w pamięci *working set* podczas wyszukiwań. Tablice hasowe cierpią na nieprzewidywalne braki w pamięci cache ze względu na łańcuchy kolizji lub probe open-addressing, a muszą czasem płacić drogą rehashing pełnego zestawu tablic podczas ich rozrostu. Pamiętanie Judy używa również mniej pamięci na klucz niż tablice hasowe, ponieważ tablice hasowe muszą zawsze utrzymywać swój współczynnik obciążenia poniżej pewnej granicy, często poniżej siedemdziesięciu lub osiemdziesiątego procenta, aby zachować szybkość, co spowoduje odpadanie reszty pojemności, podczas gdy Judy dostosowuje swoje reprezentacje do rzeczywistej populacji, a nie zarezerwuje nadmiarowej pojemności. W stosunku do klasycznych drzew binarnych równoważnych, takich jak czerwonokrótkie lub AVL, Judy wygrywa jednoznacznie zarówno w szybkości, jak i pamięci dla dużych liczb kluczy. Porównanie bazowe opiera się na tym, że porównania oparte na porównaniach w drzewie binarnym o złożoności *O(log n)* wiążą się z wieloma nieprzewidywalnymi śledztwami wskaźników, jedno dla każdego porównania, oraz nadmiernym obciążeniem na poziomach węzłów z danymi do utrzymania równowagi. W przeciwieństwie do tego, Judy ma ograniczone porównanie oparte na szerokości klucza i jej węzły są skompaktowane i przyjazne dla pamięci cache. W stosunku do drzew B, porównanie jest bliższe, ponieważ drzewa B zostały zaprojektowane z myślą o efektywności blokowej lub cache-lineowej, szczególnie dla przechowywania na dysku. Jednakże Judy nadal wygrywa w przypadku prac pamięciowych, ponieważ jej reprezentacje węzłów są bardziej dostosowane do rzeczywistej gęstości niż stała rozgałęzienie drzewa B i unika całkowitego porównania kluczy, używając zamiast tego bezpośredniego indeksowania bajtów. Przeciwstawienia są jednak realne. Złożoność implementacji Judy jest znacząca, z wieloma typami węzłów, prógmi konwersji i starannym pakietem bitów, co sprawia, że jest znacznie trudniejsze do prawidłowej implementacji i utrzymania niż tablice hasowe lub drzewa B. Dlatego produkcjonalne implementacje Judy pozostają stosunkowo rzadko uzywane w porównaniu do powszechnych bibliotek tablic hasowych. Judy również wykazuje najlepsze wyniki dla kluczy całkowitych lub o ustalonej strukturze, gdzie dekompozycja bajtowa trie jest naturalna, a wymaga więcej staranności do efektywnego zastosowania do dowolnych kluczy o zmiennej długości.

Często zadawane pytania

Czy tablica Judy jest taka sama jak trie?

Tablica Judy to specjalizowana, intensywnie optymalizowana wersja trie, konkretnie 256-wymiarowy tryb radix over bajty klucza, ale przekracza ona zrozumiałą implementację triedry. Tryb regularny typowo używa jednego ustalonego reprezentacji węzła wszędzie, zwykle tablicy stałą rozmiaru z wskaźnikami na dzieci, co jest proste, ale zużywa dużo pamięci gdy triedra jest rzadka. Charakterystyczne cechy Judy polega na tym, że każdy indywidualny węzeł może wybrać między wieloma reprezentacjami - skompaktowaną listę, bitmapą lub pełną tablicę - oparte na rzeczywistym liczbę dzieci tego węzła, a dalszy odniesiony do efektywności pamięci i układu cache CPU. W związku z tym każda tablica Judy jest triedrą, ale nie każda triedra jest tablicą Judy; Judy dodaje warstwę adaptacyjnej reprezentacji i świadomego cache na podstawie idei triedry radix.

Dlaczego tablice Judy mogą utrzymywać klucze uporządkowane, a tablice hash nie?

Tablica hash przechowuje każdy klucz w lokalizacji wyznaczonej przez przepuszczenie go przez funkcję haszującą, a dobre funkcje haszujące są specjalnie zaprojektowane do rozrzedzenia wartości kluczy powiązanych lub bliskich do niezwiązanych, prawie losowych lokalizacji w tablicy. To rozrzedzenie daje tablicom hash szybkie średnio-casowe wyszukiwanie, ale również usuwa jakąkolwiek relację między wartością klucza a jego pozycją, więc nie ma sposobu na poszukiwanie w tablicy w uporządkowanej kolejności bez najpierw wydzielania i uporządkowywania wszystkich kluczów. Tablica Judy jest z kolei organizowana jako triedra indeksowana bezpośrednio przez bajty każdego klucza, więc dzieci w każdym węźle są naturalnie uporządkowane według rosnących bajtów. Przechodzenie po triedrze w tej naturalnej kolejności powoduje wyszukiwanie kluczy w pełni uporządkowanym sekwencji bez dodatkowego kroku sortowania, a ta sama cecha sprawia, że zapytania rangi i wyszukiwania najbliższego klucza są efektywne.

Dla jakich problemów rzeczywistych są tablice Judy szczególnie dobre?

Tablice Judy są szczególnie dobrze dopasowane do obciążen konserwujących duże, rzadkie kluczowe przestrzenie integer lub kluczy o ustalonej szerokości, gdzie ważna jest efektywność pamięci i uporządkowane dostęp. Przykłady obejmują reprezentowanie ekstremalnie rzadkich bitmap lub zbiorów, takich jak śledzenie, które z bilionów możliwych identyfikatorów są obecnie w użyciu; implementacja tablic asocjacyjnych kluczowych 32-bitowych lub 64-bitowych, takich jak odwrotne indeksy lub tablice symboli; i struktury routingu sieciowej lub klasfikacji pakietów, które korzystają z uporządkowanego, prefix-oświadczającego wyszukiwania. Są mniej często właściwe wyborem dla małych map w pamięci, gdzie prostota implementacji tablicy hash przeważy nad zaletami pamięci i cache Judy, ponieważ te zalety skupiają się głównie na większych skalach.

Jak tablica Judy decyduje kiedy zamienia reprezentację węzła?

Każda reprezentacja węzła jest przystosowana do określonego zakresu populacji, a implementacja śledzi liczbę dzieci danego węzła podczas dodawania lub usuwania kluczy. Gdy liczba dzieci węzła przekracza próg, na przykład rosnąca ponad punkt, o którym listy liniowe nadal pozostają efektywne do skanowania, implementacja alokuje ten węzeł do kolejnej gęstszej reprezentacji, takiej jak bitmapa, kopiując istniejące dzieci do nowego układu. Odwrotnie się dzieje na usunięcie: jeśli wystarczająco dużo dzieci jest usuniętych, że gęstsza reprezentacja staje się śmieciowa, węzeł konwertuje się z powrotem do szerszej formy. Te konwersje mają miejsce lokalnie, jedno węzeło po drugim, tak że cała struktura ciągle dostosowuje swój układ pamięci do bieżącej rozkładu danych bez potrzeby globalnej reorganizacji.

Czy stała głębokość triedry oznacza, że wydajność tablic Judy nigdy nie ulega zniszczeniu ze względu na dodatkowe dane?

Liczba poziomów triedry jest ograniczona przez szerokość bajtową klucza - cztery poziomy dla 32-bitowego klucza lub osiem dla 64-bitowego klucza, więc liczba przeszukiwań węzłów na wyszukiwanie nie rośnie przy dodawaniu kolejnych kluczy, jak w drzewach porównawczych, gdzie długość ścieżki rośnie logarytmicznie z populacją. Jednak to nie oznacza, że wydajność jest całkowicie płaskim: podczas dodawania więcej kluczy pojedyncze węzły po wspólnych prefiksach tendencje do stania się gęstsze, co oznacza, że tańsze listy węzłowe przekształcają się w bitmapy i w końcu w pełne tablice, a każda z tych reprezentacji ma trochę inny koszt na poziomie dostępu i zachowanie pamięci. Dlatego choć głębokość pozostaje stałą, konkretna reprezentacja, a więc dokładna cache i koszt instrukcji, napotkana na każdym poziomie może się zmieniać wraz z zmianą gęstości zbioru danych.

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Judy Array: The Cache-Conscious Adaptive Trie i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.

▶ Otwórz symulację Judy Array: The Cache-Conscious Adaptive Trie