Bardzo wydajna mapa skrótów C / C ++ (tabela, słownik) [zamknięte]

Muszę zmapować klucze pierwotne (int, może long) do wartości struktur w strukturze danych o wysokiej wydajności mapy skrótów.

Mój program będzie zawierał kilkaset takich map, a każda mapa będzie miała zazwyczaj najwyżej kilka tysięcy wpisów. Jednak mapy będą stale „odświeżać” lub „burzyć”; wyobraź sobie, że przetwarzasz miliony addi deletewiadomości na sekundę.

Które biblioteki w C lub C ++ mają strukturę danych, która pasuje do tego przypadku użycia? Albo jak poleciłbyś zbudowanie własnego? Dzięki!

Polecam wypróbować Google SparseHash (lub wersję C11 Google SparseHash-c11 ) i sprawdzić, czy odpowiada Twoim potrzebom. Mają implementację wydajną pod względem pamięci, a także zoptymalizowaną pod kątem szybkości. Test porównawczy wykonałem dawno temu, była to najlepsza implementacja do haszowania dostępna pod względem szybkości (jednak z wadami).

Które biblioteki w C lub C ++ mają strukturę danych, która pasuje do tego przypadku użycia? Albo jak poleciłbyś zbudowanie własnego? Dzięki!

Sprawdź macierze Judy na licencji LGPL . Nigdy się nie wykorzystywałem, ale kilka razy był mi reklamowany.

Możesz także spróbować przetestować kontenery STL (std :: hash_map itp.). W zależności od platformy / implementacji i dostrojenia kodu źródłowego (przydział wstępny tak dużo, jak to tylko możliwe, dynamiczne zarządzanie pamięcią jest kosztowne) mogą być wystarczająco wydajne.

Ponadto, jeśli wydajność ostatecznego rozwiązania przewyższa koszt rozwiązania, możesz spróbować zamówić system z wystarczającą ilością pamięci RAM, aby umieścić wszystko w zwykłych tablicach. Wydajność dostępu według indeksu jest bezkonkurencyjna.

Operacje dodawania / usuwania są znacznie (100x) częstsze niż operacje pobierania.

To podpowiada, że ​​możesz najpierw skoncentrować się na ulepszaniu algorytmów. Jeśli dane są tylko zapisywane, a nie czytane, to po co je w ogóle zapisywać?

Po prostu użyj boost::unordered_map(lub tr1itp.) Domyślnie. Następnie sprofiluj swój kod i zobacz, czy ten kod jest wąskim gardłem. Dopiero wtedy radziłbym dokładnie przeanalizować swoje wymagania, aby znaleźć szybszy zamiennik.

Jeśli masz program wielowątkowy, możesz znaleźć przydatne tabele skrótów w bibliotece bloków konstrukcyjnych wątków Intel . Na przykład tbb :: concurrent_unordered_map ma taki sam interfejs API jak std :: unordered_map, ale jego główne funkcje są bezpieczne dla wątków.

Spójrz także na szaleńczą bibliotekę Facebooka , ma ona wysokowydajną tabelę współbieżnych skrótów i listę pomijania .

khash jest bardzo wydajny. Istnieje szczegółowy benchmark autora: https://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/, a także pokazuje, że khash pokonuje wiele innych bibliotek skrótów.

ze źródeł Androida (stąd licencja Apache 2)

https://github.com/CyanogenMod/android_system_core/tree/ics/libcutils

spójrz na hashmap.c, wybierz include / cutils / hashmap.h, jeśli nie potrzebujesz bezpieczeństwa wątków, możesz usunąć kod mutex, przykładowa implementacja znajduje się w libcutils / str_parms.c

Najpierw sprawdź, czy istniejące rozwiązania, takie jak libmemcache, odpowiadają Twoim potrzebom.

Jeśli nie ...

Mapy z haszowaniem wydają się być ostateczną odpowiedzią na Twoje wymagania. Zapewnia wyszukiwanie o (1) na podstawie kluczy. Większość bibliotek STL udostępnia obecnie pewnego rodzaju skróty. Skorzystaj więc z tego, który zapewnia Twoja platforma.

Po wykonaniu tej części musisz przetestować rozwiązanie, aby sprawdzić, czy domyślny algorytm haszowania jest wystarczająco dobry pod względem wydajności dla Twoich potrzeb.

Jeśli tak nie jest, powinieneś zapoznać się z dobrymi algorytmami szybkiego haszowania znalezionymi w sieci

1. dobra stara liczba pierwsza pomnóż algo
2. http://www.azillionmonkeys.com/qed/hash.html
3. http://burtleburtle.net/bob/
4. http://code.google.com/p/google-sparsehash/

Jeśli to nie wystarczy, możesz samodzielnie rzucić moduł haszujący, który rozwiązuje problem, który widziałeś z przetestowanymi kontenerami STL i jednym z algorytmów haszujących powyżej. Pamiętaj, aby gdzieś opublikować wyniki.

Aha i to ciekawe, że masz wiele map ... być może możesz uprościć, mając swój klucz jako 64-bitową liczbę z wysokimi bitami używanymi do rozróżnienia, do której mapy należy, i dodania wszystkich par klucz-wartość do jednego gigantycznego skrótu. Widziałem hashe, które mają około stu tysięcy symboli, które działają doskonale na podstawowym algorytmie haszowania liczb pierwszych.

Możesz sprawdzić, jak to rozwiązanie działa w porównaniu z setkami map ... myślę, że to mogłoby być lepsze z punktu widzenia profilowania pamięci ... proszę, opublikuj gdzieś wyniki, jeśli wykonasz to ćwiczenie

Uważam, że czymś więcej niż algorytmem haszowania może być ciągłe dodawanie / usuwanie pamięci (czy można tego uniknąć?) I profil użycia pamięci podręcznej procesora, które mogą być bardziej kluczowe dla wydajności aplikacji

powodzenia

Wypróbuj tabele skrótów z różnych szablonów kontenerów . Ma closed_hash_mapmniej więcej taką samą prędkość jak Google dense_hash_map, ale jest łatwiejszy w użyciu (brak ograniczeń dotyczących zawartych wartości) i ma również inne zalety.

Proponuję uthash . Po prostu #include "uthash.h"dołącz, a następnie dodaj UT_hash_handledo struktury i wybierz jedno lub więcej pól w swojej strukturze, które będą działać jako klucz. Słowo o wydajności tutaj .

http://incise.org/hash-table-benchmarks.html gcc ma bardzo dobrą implementację. Pamiętaj jednak, że musi uwzględniać bardzo złą standardową decyzję:

Jeśli nastąpi ponowne zhaszowanie, wszystkie iteratory są unieważniane, ale odniesienia i wskaźniki do poszczególnych elementów pozostają ważne. Jeśli nie nastąpi rehash, żadnych zmian.

http://www.cplusplus.com/reference/unordered_map/unordered_map/rehash/

Oznacza to zasadniczo, że norma mówi, że wdrożenie MUSI BYĆ oparte na połączonych listach. Zapobiega otwartemu adresowaniu, które ma lepszą wydajność.

Myślę, że Google rzadko używa otwartego adresowania, chociaż w tych testach porównawczych tylko wersja gęsta przewyższa konkurencję. Jednak rzadka wersja przewyższa całą konkurencję pod względem użycia pamięci. (również nie ma żadnego plateau, czysta linia prosta z liczbą elementów)