Czy tablice niesąsiadujące są wydajne?

W języku C #, gdy użytkownik tworzy List<byte>i dodaje bajty, istnieje szansa, że ​​zabraknie miejsca i będzie musiał przydzielić więcej miejsca. Przydziela podwójny (lub inny mnożnik) rozmiar poprzedniej tablicy, kopiuje bajty i odrzuca odwołanie do starej tablicy. Wiem, że lista rośnie wykładniczo, ponieważ każda alokacja jest droga, co ogranicza ją do O(log n)alokacji, w których dodanie za 10każdym razem dodatkowych pozycji skutkowałoby O(n)alokacjami.

Jednak w przypadku dużych rozmiarów macierzy może być dużo zmarnowanego miejsca, być może prawie połowa macierzy. Aby zmniejszyć pamięć, napisałem podobną klasę, NonContiguousArrayListktóra używa List<byte>jako magazynu kopii zapasowych, jeśli na liście znajdowało się mniej niż 4 MB, to przydzieliłoby dodatkowe 4 MB tablic bajtowych w miarę NonContiguousArrayListpowiększania się.

W przeciwieństwie do List<byte>tych tablic nie są ciągłe, więc nie ma kopiowania danych, tylko dodatkowy przydział 4M. Kiedy element jest szukany, indeks jest dzielony przez 4M, aby uzyskać indeks tablicy zawierającej przedmiot, a następnie modulo 4M, aby uzyskać indeks w tablicy.

Czy możesz wskazać problemy z tym podejściem? Oto moja lista:

• Nieciągłe tablice nie mają lokalizacji pamięci podręcznej, co powoduje złą wydajność. Jednak przy wielkości bloku 4M wydaje się, że będzie wystarczająca lokalizacja dla dobrego buforowania.
• Dostęp do przedmiotu nie jest tak prosty, istnieje dodatkowy poziom pośrednictwa. Czy zostanie to zoptymalizowane? Czy spowodowałoby to problemy z pamięcią podręczną?
• Ponieważ po osiągnięciu limitu 4M następuje liniowy wzrost, możesz mieć o wiele więcej przydziałów niż zwykle (powiedzmy, maks. 250 przydziałów na 1 GB pamięci). Żadna dodatkowa pamięć nie jest kopiowana po 4M, jednak nie jestem pewien, czy dodatkowe alokacje są droższe niż kopiowanie dużych fragmentów pamięci.

W skalach, o których wspomniałeś, obawy są zupełnie inne niż te, o których mówiłeś.

Lokalizacja pamięci podręcznej

• Istnieją dwa powiązane pojęcia:
  1. Lokalizacja, ponowne wykorzystanie danych na tej samej linii pamięci podręcznej (lokalizacja przestrzenna), którą ostatnio odwiedzono (lokalizacja czasowa)
  2. Automatyczne pobieranie z pamięci podręcznej (streaming).
• Przy wspomnianych skalach (sto MB do gigabajtów, w porcjach 4 MB), dwa czynniki mają więcej wspólnego z wzorcem dostępu do elementu danych niż z układem pamięci.
• Moja (nieświadoma) prognoza jest taka, że ​​statystycznie może nie być dużej różnicy wydajności niż gigantyczny ciągły przydział pamięci. Bez zysku, bez strat.

Wzorzec dostępu do elementu danych

• Ten artykuł ilustruje wizualnie, w jaki sposób wzorce dostępu do pamięci wpłyną na wydajność.
• Krótko mówiąc, pamiętaj, że jeśli twój algorytm jest już wąski z powodu przepustowości pamięci, jedynym sposobem na poprawę wydajności jest bardziej użyteczna praca z danymi, które są już załadowane do pamięci podręcznej.
• Innymi słowy, nawet jeśli YourList[k]i YourList[k+1]mają wysokie prawdopodobieństwo bycia konsekutywne (jeden na czterech milionów przypadkiem nie jest), fakt ten nie pomoże wydajność, jeśli dostęp do listy całkowicie losowo, lub w dużych nieprzewidywalnych krokami m.in.while { index += random.Next(1024); DoStuff(YourList[index]); }

Interakcja z systemem GC

• Moim zdaniem na tym powinieneś skupić się najbardziej.
• Przynajmniej zrozum, w jaki sposób Twój projekt będzie współdziałał z:
  • Pokoleniowe usuwanie śmieci ,
  • Kupa dużych obiektów
• Nie znam się na tych tematach, więc zostawiam innych, aby mogli się przyłączyć.

Koszty obliczeń przesunięcia adresu

• Typowy kod C # już wykonuje wiele obliczeń przesunięcia adresu, więc dodatkowy narzut z twojego schematu nie byłby gorszy niż typowy kod C # działający na pojedynczej tablicy.
  • Pamiętaj, że kod C # wykonuje również sprawdzanie zakresu tablicy; i ten fakt nie uniemożliwia C # osiągnięcia porównywalnej wydajności przetwarzania macierzy z kodem C ++.
  • Powodem jest to, że wydajność jest głównie ograniczona przez przepustowość pamięci.
  • Sztuką maksymalizacji użyteczności z przepustowości pamięci jest użycie instrukcji SIMD do operacji odczytu / zapisu w pamięci. Nie robi tego ani typowy C #, ani typowy C ++; musisz uciekać się do bibliotek lub dodatków językowych.

Aby zilustrować dlaczego:

• Wykonaj obliczenia adresu
• (W przypadku OP załaduj podstawowy adres porcji (który jest już w pamięci podręcznej), a następnie wykonaj więcej obliczeń adresu)
• Odczyt / zapis na adres elementu

Ostatni krok nadal zajmuje lwią część czasu.

Osobista sugestia

• Możesz podać CopyRangefunkcję, która zachowywałaby się jak Array.Copyfunkcja, ale działałaby między dwoma twoimi wystąpieniami NonContiguousByteArraylub między jednym wystąpieniem a drugim normalnym byte[]. funkcje te mogą korzystać z kodu SIMD (C ++ lub C #) w celu maksymalnego wykorzystania przepustowości pamięci, a następnie kod C # może działać w kopiowanym zakresie bez nakładania wielu dereferencji lub obliczania adresu.

Obawy dotyczące użyteczności i interoperacyjności

• Najwyraźniej nie można tego używać NonContiguousByteArrayz żadnymi bibliotekami C #, C ++ ani bibliotekami obcymi, które oczekują ciągłych tablic bajtów lub tablic bajtów, które można przypiąć.
• Jeśli jednak napiszesz własną bibliotekę akceleracji C ++ (z P / Invoke lub C ++ / CLI), możesz przekazać listę bazowych adresów kilku bloków 4 MB do kodu podstawowego.
  • Na przykład, jeśli chcesz dać dostęp do elementów zaczynających się od (3 * 1024 * 1024)i kończących się na (5 * 1024 * 1024 - 1), oznacza to, że dostęp będzie obejmował chunk[0]i chunk[1]. Następnie możesz zbudować tablicę (rozmiar 2) tablic bajtowych (rozmiar 4M), przypiąć te adresy fragmentów i przekazać je do kodu źródłowego.
• Innym problemem jest to, że użyteczność nie będzie w stanie wdrożyć IList<byte>interfejs wydajnie: Inserti Removebędzie po prostu zbyt długo, aby proces, ponieważ będą one wymagać O(N)czasu.
  • W rzeczywistości wygląda na to, że nie możesz zaimplementować niczego innego IEnumerable<byte>, tzn. Można go skanować sekwencyjnie i to wszystko.

Warto zauważyć, że C ++ ma już równoważną strukturę według standardu std::deque. Obecnie jest zalecany jako domyślny wybór dla potrzeb sekwencji losowego dostępu.

Rzeczywistość jest taka, że ​​ciągła pamięć jest prawie całkowicie niepotrzebna, gdy dane przekroczą pewien rozmiar - linia pamięci podręcznej ma tylko 64 bajty, a rozmiar strony to tylko 4-8 KB (obecnie typowe wartości). Gdy zaczniesz mówić o kilku MB, to naprawdę problem. To samo dotyczy kosztu alokacji. Cena przetwarzania wszystkich tych danych - nawet po prostu ich odczytu - i tak przewyższa cenę przydziałów.

Jedynym innym powodem do zmartwień jest interfejs API C. Ale i tak nie można uzyskać wskaźnika do bufora listy, więc nie ma tu żadnych obaw.

Gdy fragmenty pamięci są przydzielane w różnych punktach czasowych, tak jak w pod-macierzach w strukturze danych, można je umieścić w pamięci z dala od siebie. To, czy jest to problem, czy nie, zależy od procesora i jest bardzo trudne do przewidzenia. Musisz to przetestować.

To świetny pomysł, z którego korzystałem w przeszłości. Oczywiście powinieneś używać potęgi dwóch dla rozmiarów pod-macierzy i przesunięcia bitów dla podziału (może się zdarzyć w ramach optymalizacji). Odkryłem, że ten typ struktury jest nieco wolniejszy, ponieważ kompilatory mogą łatwiej zoptymalizować pośrednią macierz. Musisz przetestować, ponieważ te typy optymalizacji cały czas się zmieniają.

Główną zaletą jest to, że możesz biegać bliżej górnej granicy pamięci w systemie, o ile konsekwentnie używasz tego typu struktur. Dopóki powiększasz swoje struktury danych i nie produkujesz śmieci, unikasz dodatkowych kolekcji śmieci, które występowałyby dla zwykłej listy. W przypadku ogromnej listy może to mieć ogromną różnicę: różnica między kontynuowaniem działania a brakiem pamięci.

Dodatkowe przydziały stanowią problem tylko wtedy, gdy fragmenty pod-macierzy są małe, ponieważ w każdej alokacji macie narzut pamięci.

Stworzyłem podobne struktury dla słowników (tabele skrótów). Słownik dostarczony przez .NET ma taki sam problem jak List. Słowniki są trudniejsze, ponieważ należy także unikać ponownego ładowania.

Przy wielkości bloku 4M nawet jeden blok nie gwarantuje ciągłości pamięci fizycznej; jest większy niż typowy rozmiar strony maszyny wirtualnej. Miejsce nie ma znaczenia w tej skali.

Będziesz musiał się martwić o fragmentację sterty: jeśli alokacje zdarzają się w taki sposób, że twoje bloki są w dużej mierze nieciągłe w stercie, to po ich odzyskaniu przez GC otrzymasz stertę, która może być zbyt podzielona, ​​aby zmieścić się w późniejszy przydział. Jest to zwykle gorsza sytuacja, ponieważ awarie będą występować w niepowiązanych miejscach i prawdopodobnie wymuszą ponowne uruchomienie aplikacji.

Obracam niektóre z najbardziej centralnych części mojej bazy kodu (silnik ECS) wokół opisanej przez ciebie struktury danych, chociaż wykorzystuje mniejsze ciągłe bloki (bardziej jak 4 kilobajty zamiast 4 megabajtów).

Używa podwójnej wolnej listy w celu uzyskania ciągłego wstawiania i usuwania z jedną wolną listą dla wolnych bloków, które są gotowe do wstawienia (bloki, które nie są pełne) i pod-wolną listą wewnątrz bloku dla indeksów w tym bloku gotowy do odzyskania po włożeniu.

Omówię zalety i wady tej struktury. Zacznijmy od kilku wad, ponieważ jest ich kilka:

Cons

1. Wstawienie do tej struktury kilkuset milionów elementów zajmuje około 4 razy więcej niż std::vector(struktura czysto ciągła). I jestem całkiem przyzwoity w mikrooptymalizacjach, ale jest tylko koncepcyjnie więcej pracy do wykonania, ponieważ zwykły przypadek musi najpierw sprawdzić wolny blok na górze listy wolnych bloków, a następnie uzyskać dostęp do bloku i otworzyć wolny indeks z bloku wolna lista, napisz element w wolnej pozycji, a następnie sprawdź, czy blok jest pełny, i usuń blok z listy wolnych bloków, jeśli tak jest. Nadal jest to operacja o stałym czasie, ale ze znacznie większą stałą niż cofanie się std::vector.
2. Zajmuje to około dwa razy więcej czasu podczas uzyskiwania dostępu do elementów przy użyciu wzorca losowego dostępu, biorąc pod uwagę dodatkową arytmetykę indeksowania i dodatkową warstwę pośredniczącą.
3. Dostęp sekwencyjny nie jest skutecznie odwzorowywany na projekt iteratora, ponieważ iterator musi wykonywać dodatkowe rozgałęzienia za każdym razem, gdy jest zwiększany.
4. Ma trochę narzutu pamięci, zwykle około 1 bit na element. 1 bit na element może nie brzmieć dużo, ale jeśli używasz go do przechowywania miliona 16-bitowych liczb całkowitych, oznacza to 6,25% więcej wykorzystania pamięci niż idealnie kompaktowa tablica. Jednak w praktyce zużywa to mniej pamięci, niż w std::vectorprzypadku kompaktowania w vectorcelu wyeliminowania rezerwy nadmiaru. Poza tym generalnie nie używam go do przechowywania takich drobnych elementów.

Plusy

1. Dostęp sekwencyjny za pomocą for_eachfunkcji, która przyjmuje zakresy przetwarzania elementów zwrotnych elementów w bloku, prawie rywalizuje z szybkością dostępu sekwencyjnego std::vector(tylko jak 10% różnicy), więc nie jest to wcale mniej wydajne w najbardziej krytycznych dla mnie przypadkach użycia ( większość czasu spędzonego w silniku ECS ma dostęp sekwencyjny).
2. Umożliwia ciągłe usuwanie ze środka, a struktura zwalnia bloki, gdy stają się całkowicie puste. W rezultacie jest to całkiem przyzwoite, aby upewnić się, że struktura danych nigdy nie zużywa znacznie więcej pamięci niż to konieczne.
3. Nie unieważnia wskaźników dla elementów, które nie są bezpośrednio usuwane z kontenera, ponieważ pozostawia po sobie dziury, stosując metodę z bezpłatną listą, aby odzyskać te dziury po kolejnym wstawieniu.
4. Nie musisz się tak bardzo przejmować brakiem pamięci, nawet jeśli ta struktura zawiera imponującą liczbę elementów, ponieważ żąda tylko niewielkich ciągłych bloków, które nie stanowią problemu dla systemu operacyjnego, aby znaleźć ogromną liczbę ciągłych nieużywanych strony.
5. Dobrze nadaje się do współbieżności i bezpieczeństwa wątków bez blokowania całej struktury, ponieważ operacje są zazwyczaj lokalizowane w poszczególnych blokach.

Teraz jednym z największych plusów było dla mnie, że stworzenie niezmiennej wersji tej struktury danych stało się banalne:

Od tego czasu otworzyło to wiele drzwi do pisania większej liczby funkcji pozbawionych skutków ubocznych, co znacznie ułatwiło osiągnięcie bezpieczeństwa wyjątkowego, bezpieczeństwa wątków itp. Niezmienność była czymś, co odkryłem, co mogłem łatwo osiągnąć dzięki ta struktura danych z perspektywy czasu i przez przypadek, ale prawdopodobnie jedna z najpiękniejszych korzyści, jakie przyniosła, ponieważ znacznie ułatwiła utrzymanie bazy danych.

Nieciągłe tablice nie mają lokalizacji pamięci podręcznej, co powoduje złą wydajność. Jednak przy wielkości bloku 4M wydaje się, że będzie wystarczająca lokalizacja dla dobrego buforowania.

Lokalizacja odniesienia nie jest czymś, czym można się martwić w blokach tego rozmiaru, nie mówiąc już o blokach 4 kilobajtów. Linia pamięci podręcznej ma zwykle tylko 64 bajty. Jeśli chcesz zmniejszyć liczbę braków w pamięci podręcznej, po prostu skoncentruj się na odpowiednim wyrównaniu tych bloków i preferuj bardziej sekwencyjne wzorce dostępu, jeśli to możliwe.

Bardzo szybkim sposobem przekształcenia wzorca pamięci o dostępie swobodnym w sekwencyjny jest użycie zestawu bitów. Powiedzmy, że masz mnóstwo wskaźników i są one w losowej kolejności. Możesz po prostu przebijać je i oznaczać bity w zestawie bitów. Następnie możesz iterować po swoim zestawie bitów i sprawdzać, które bajty są niezerowe, sprawdzając, powiedzmy, 64-bitowe na raz. Po napotkaniu zestawu 64-bitów, w których ustawiono co najmniej jeden bit, można użyć instrukcji FFS, aby szybko ustalić, które bity są ustawione. Bity mówią ci, do których indeksów powinieneś uzyskać dostęp, chyba że teraz posortujesz indeksy w kolejności sekwencyjnej.

Ma to pewne koszty ogólne, ale w niektórych przypadkach może być opłacalną wymianą, szczególnie jeśli zamierzasz wielokrotnie zapętlać te indeksy.

Dostęp do przedmiotu nie jest tak prosty, istnieje dodatkowy poziom pośrednictwa. Czy zostanie to zoptymalizowane? Czy spowodowałoby to problemy z pamięcią podręczną?

Nie, nie można go zoptymalizować. Przynajmniej ten dostęp zawsze będzie kosztował więcej. Często jednak nie zwiększa to tak bardzo braków w pamięci podręcznej, ponieważ masz tendencję do uzyskiwania wysokiej lokalizacji czasowej z tablicą wskaźników do bloków, szczególnie jeśli twoje wspólne ścieżki wykonywania spraw używają wzorców sekwencyjnego dostępu.

Ponieważ po osiągnięciu limitu 4M następuje liniowy wzrost, możesz mieć o wiele więcej przydziałów niż zwykle (powiedzmy, maks. 250 przydziałów na 1 GB pamięci). Żadna dodatkowa pamięć nie jest kopiowana po 4M, jednak nie jestem pewien, czy dodatkowe alokacje są droższe niż kopiowanie dużych fragmentów pamięci.

W praktyce kopiowanie jest często szybsze, ponieważ jest to rzadki przypadek, występujący tylko jako log(N)/log(2)suma czasów, a jednocześnie upraszczający brudny zwykły przypadek, w którym można po prostu napisać element do tablicy wiele razy, zanim się zapełni i trzeba ją ponownie przydzielić. Tak więc zazwyczaj nie będziesz uzyskiwać szybszych wstawień przy tego typu strukturze, ponieważ zwykła praca z przypadkami jest droższa, nawet jeśli nie musi ona zajmować się tym drogim rzadkim przypadkiem realokacji dużych tablic.

Podstawową zaletą tej struktury dla mnie, pomimo wszystkich wad, jest zmniejszenie zużycia pamięci, nie martwienie się o OOM, możliwość przechowywania indeksów i wskaźników, które nie są unieważniane, współbieżności i niezmienności. Fajnie jest mieć strukturę danych, w której można wstawiać i usuwać rzeczy w stałym czasie, podczas gdy one same się oczyszczają i nie unieważniają wskaźników i wskaźników w strukturze.