Praktyczne limity wielkości tabeli mieszającej i słownika w języku c #

Jakie są praktyczne ograniczenia liczby elementów, które może zawierać słownik lub tablica mieszająca C # 4, oraz całkowita liczba bajtów, jaką te struktury mogą zawierać. Będę pracować z dużą liczbą obiektów i chcę wiedzieć, kiedy te struktury zaczną napotykać problemy.

Dla kontekstu użyję 64-bitowego systemu z mnóstwem pamięci. Ponadto będę musiał znaleźć obiekty przy użyciu formy lub „klucza”. Biorąc pod uwagę wymagania dotyczące wydajności, obiekty te będą musiały pozostać w pamięci, a wiele z nich będzie trwało długo.

Sugeruję inne podejścia / wzorce, chociaż muszę unikać korzystania z bibliotek stron trzecich lub bibliotek typu open source. Ze względów specyfikacji muszę być w stanie zbudować to przy użyciu natywnego C # ( lub C ++ \ CLI ).

Należy zwrócić uwagę na to, że słownik nie będzie przechowywał samego obiektu (który może mieć duży ślad pamięci), a jedynie odniesienie do obiektu, więc jeśli obiekty są złożone, nie ma to wpływu na rozmiar słownika.

Zebrałem kilka tysięcy elementów razem w Słowniku w pamięci, a problemem nie jest rozmiar Słownika, ale rozmiar samych obiektów w pamięci. W tych przypadkach sam Słownik stanowił niewielką część pamięci.

W przypadku dużych słowników należy pamiętać o ręcznej konfiguracji pojemności słownika i zarządzaniu nią. W normalnych okolicznościach .Net zarządza tą grzywną (w bieżącej implementacji, jeśli zabraknie miejsca, zmienia rozmiar na liczbę pierwszą, która jest co najmniej dwa razy większa niż aktualny rozmiar słownika). Jeśli jednak wiesz, że zamierzasz stworzyć duży Słownik lub rozszerzyć Słownik zamiast zgadywania i zmiany rozmiaru słownika .Net (co jest stosunkowo kosztowne), prawdopodobnie lepiej jest zrobić to sam (na pewno z początkowym rozmiar i prawdopodobnie zmiana rozmiaru później). Można to zrobić, zarządzając pojemnością Słownika, jeśli masz rozsądne heurystyczne pojęcie o tym, jaka powinna być pojemność Słownika. Microsoft zaleca to w dniuMSDN w swoich uwagach na temat obiektu Dictionary . Wydaje się jednak, że toczy się debata na temat rzeczywistej wartości tego podejścia, chociaż nie jestem pewien, jak rygorystyczny jest ten test i czy istnieją inne optymalizacje, które platforma .Net stosuje, gdy słownik zmienia się niezwykle szybko.

Jest to przydatne pytanie dotyczące przepełnienia stosu dotyczące wielkości obiektu i pamięci.

Praktyczne ograniczenia mogą zależeć od maszyny, na której działa twoje oprogramowanie, a także od liczby obiektów, które faktycznie planujesz zawierać w tych strukturach danych. Jak wspomniano Oded, int.MaxValue jest dużą liczbą, ale czy 2 miliardy pozycji to praktyczny limit? Przechowywanie wielu elementów w pamięci prawdopodobnie nie jest zbyt praktyczne.

Ponieważ dokumentacja nie określa, gdzie fizycznie przechowywane są dane, i nie określa limitu, sugeruję przeprowadzenie eksperymentu z maksymalnym oczekiwanym rozmiarem, jaki prawdopodobnie będziesz mieć, i zanotowanie pamięci systemowej przed i po przydziale pamięci.

Niedawno zaktualizowałem projekt github hash-table-shootout (tutaj: https://github.com/jimbelton/hash-table-shootout ). Standardowa nieuporządkowana mapa gcc ma narzut około 1,8 GB do przechowywania 40 mln obiektów. Wydaje mi się to dość okropne, ale nawet najlepsza pamięć pod względem wydajności, Google sparse_hash_map, zajmuje 600 MB, a za korzystanie z niej płacisz karę wydajności. Jeśli potrzebujesz szybkości, z uwzględnionych algorytmów, Glib GHashTable jest najszybszy i ma dobrą wydajność pamięci (około 1,3 GB narzutu). Wyniki testu porównawczego są publikowane tutaj: https://jimbelton.wordpress.com/2015/07/01/hash-table-shootout-on-github/