Czy możliwe jest zaimplementowanie mapy wolnej od blokady w C++

Question

Opracowujemy aplikację opartą na sieci C/S, stwierdziliśmy, że istnieje zbyt wiele blokad dodających do std :: map, że wydajność serwera stała się zła.

Zastanawiam się, czy możliwe jest wdrożenie mapy bez blokady, jeśli tak, w jaki sposób? Czy jest tam jakiś kod open source?

EDYTOWANIE: Aktualnie używamy std :: map do przechowywania informacji o gniazdach, zrobiliśmy enkapsulację w oparciu o opis pliku gniazda w celu włączenia innych niezbędnych informacji, takich jak adres IP, port, typ gniazda, tcp lub udp, itp. .

aby Podsumowując, mamy globalną mapę mówią, że to

map<int fileDescriptor, socketInfor*> SocketsMap, 

następnie każdy wątek, który jest używany do przesyłania danych musi mieć dostęp SocketsMap, a oni musieli dodać muteksu przed przeczytaniem od SocketsMap lub pisząc do SocketsMap , więc poziom współbieżności całej aplikacji znacznie spadłby z powodu s o wiele blokad dodawania do SocketsMap.

Aby uniknąć problemu z poziomem współbieżności, mamy dwa rozwiązania: 1. przechowuj każdy socketInfor * oddzielnie 2. używaj jakiejś mapy wolnej od blokady.

Chciałbym znaleźć jakieś wolne mapie zamka, ponieważ kody zmiany wymagane przez tego rozwiązania są znacznie mniejsze niż w przypadku rozwiązania 1.

Answer 1

Faktycznie istnieje sposób, choć nie wdrożyły to sam jest artykuł o lock free map using hazard pointers od wybitnego eksperta C++ Andrei Alexandrescu.

Answer 2

Możesz zaimplementować mapę, używając optimistic design lub transactional memory.

To podejście jest szczególnie skuteczne, gdy szansa na dwie operacje jednoczesne adresowania mapy i jedna zmienia jej strukturę jest stosunkowo niewielka - i nie chcesz narzutów blokowania za każdym razem.

Jednak od czasu do czasu zdarza się kolizja i trzeba ją jakoś zmusić (zwykle cofając się do ostatniego stabilnego stanu i ponawiając operacje).

Jeśli twój sprzęt obsługuje wystarczająco dobre operacje atomowe - można to łatwo zrobić za pomocą Compare And Swap (CAS) - gdzie sam zmieniasz odniesienie (i kiedy zmieniasz mapę, pracujesz nad kopią mapy, a nie oryginałem, i ustaw ją jako podstawową tylko wtedy, gdy dokonasz zatwierdzenia).

Answer 3

HashMap byłby odpowiedni? Spójrz na Intel Threading Building Blocks, mają ciekawą współbieżną mapę. Nie jestem pewien, czy nie jest zablokowany, ale mam nadzieję, że interesuje Cię dobra wydajność wielowątkowości, a nie szczególnie w przypadku blokady.Ponadto można sprawdzić CityHash lib

EDIT:

Właściwie TBB za hash mapa nie jest zablokować wolne

Answer 4

jestem nikt zaskoczony wspomniał, ale Kliknij Cliff wdrożył czekać wolne hashmap in Java, który wierzę, że może być przeniesiony do C++,

Answer 5

Jeśli używasz C++ 11, można rzucić okiem na AtomicHashMap z facebook/folly

Answer 6

Tak, wdrożyliśmy Lock-Free Unordered Map (docs) w języku C++ przy użyciu koncepcji "listy rozdzielone uporządkowanymi". Jest to automatycznie rozwijany kontener i obsługuje miliony elementów w 64-bitowym CAS bez problemów ABA. Pod względem wydajności jest to beast (patrz strona 5). To było extensively tested z milionami losowych operacji.