Ist es möglich zu implementieren lock frei-map in C++
Entwickeln wir eine Netzwerk-Anwendung basierte C/S -, wir finden, es gibt zu viele Schlösser hinzufügen zu std::map, dass die Leistung der server wurde schlecht.
Frage ich mich, ob es möglich ist, implementieren Sie eine lock-frei-Karte, wenn ja, wie? Gibt es eine open-source-code?
BEARBEITEN:
Tatsächlich verwenden wir die std::map zu speichern sockets Informationen, die wir haben-Kapselung auf der Grundlage der socket-Datei Beschreibung, um einige andere notwendige Informationen wie ip-Adresse, port -, socket-Typ, die tcp-oder udp usw.
Zur Zusammenfassung, wir haben eine Globale Karte sagen, es ist
map<int fileDescriptor, socketInfor*> SocketsMap, dann jeden Faden, die verwendet wird, um Daten zu senden, muss der Zugang SocketsMap, und Sie müssen hinzufügen mutex vor dem Lesen von SocketsMap oder schreiben Sie SocketsMap, so ist die Parallelität der Ebene der gesamten Anwendung wäre wesentlich reduziert, weil so viele Schlösser addding zu SocketsMap.
Zu vermeiden, die concurrency-level-problem, wir haben zwei Lösungen: 1. speichern Sie jeden socketInfor* 2 separat. verwenden Sie irgendeine Art von lock-free-Karte.
Ich möchte zu finden eine Art von lock-free-Karte, weil die codes, die änderungen durch diese Lösung sind deutlich geringer als bei Lösung 1.
- In aller fairness, dieser sagt ausdrücklich und C++, das speziell sagt C... Sie sind sehr verschiedene Sprachen, vor allem, wenn man bedenkt, atomaren Variablen.
- ein sehr guter Punkt, sir. Ich werde reißen Sie den link.
- Wenn Sie einen assoziativen container, aber erfordern nicht bestellen, könnte es einfacher sein, zu verwenden einen hash wie
std::unordered_map. Es könnte schneller sein, auch mit Ihrem aktuellen grob-Verriegelung (vor allem, wenn Sie verschieben können, keine teuren hash-Berechnung außerhalb der gesperrten Bereich), aber ich vermute, dass eine gelegentliche teure re-hash ist auch einfacher zu handhaben als eine gelegentliche re-balance, für die optimistische lockfree-version. - Wie ist das Verhältnis von Lesern zu Autoren?
- Ich bearbeitet die post, sehen Sie bitte den Teil BEARBEITEN.
- Haben Sie sah von reader-writer-locks? Code tut-lookup verwenden Sie eine reader-lock. Code tut, einfügen oder löschen müssen, verwenden Sie einen Schreiber zu sperren. Mehrere Leser können auf die Daten gleichzeitig zugreifen. RW-locks sind gut, wenn Sie haben viel mehr Leser als Schreiber.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Gibt es eigentlich eine Möglichkeit, obwohl ich noch nicht implementiert, es mir ein Papier auf eine lock-free-Karte mit hazard-Pointern von eminenter C++ - Experte Andrei Alexandrescu.
std::map< int, socketInfor* > info[10]; mutex mutexes[10]; ... mutexes[ fileDesc % 10 ].lock(); info[ fileDesc % 10 ][ fileDesc ]; .... In jedem Fall rollt eine bug-frei-lock freie Karte auf Ihrem eigenen in Anspruch nehmen dürfte viel von Zeit zu überprüfen, & debug.Ja, ich habe implementiert eine Lock-Freie Ungeordnete Anzeigen (docs) in C++ unter Verwendung der "Split-Geordnete Listen" - Konzept. Es ist ein auto-expandierendes container und unterstützt Millionen von Elementen auf einem 64-bit-CAS ABA ohne Probleme. Performance-Weise, ist es ein beast (siehe Seite 5). Es ist schon ausgiebig getestet mit Millionen von zufällige ops.
HashMap passen würde? Haben Sie einen Blick auf Intel Threading Building Blocks, Sie haben eine interessante gleichzeitige anzeigen. Ich bin nicht sicher, es ist lock-free, aber ich hoffe, Sie sind daran interessiert, gute multithreading-performance, vor allem nicht in lock-Mahlgrad. Auch können Sie die CityHash lib
EDIT:
Eigentlich TBB die hash-Tabelle ist nicht gesperrt-frei
Wenn Sie C++11, können Sie einen Blick auf AtomicHashMap von facebook/folly
Implementieren Sie können die Karte mit optimistisch-design oder transactional memory.
Dieser Ansatz ist besonders wirksam, wenn Sie die chance auf zwei Vorgänge gleichzeitig adressieren Sie die Karte und verändert die Struktur er relativ klein ist - und Sie nicht möchten, dass der Aufwand für das sperren jedes mal.
Jedoch von Zeit zu Zeit - Kollision auftreten wird, und Sie muss es irgendwie (meist durch ein Rollback auf den letzten stabilen Zustand und Wiederholung der Operationen).
Wenn Ihr hardware-Unterstützung gut genug Atomare Operationen - dies kann leicht getan werden mit Vergleichen Und Swap (CAS) - wo ändern Sie den Verweis allein (und wenn man die Karte wechseln, Sie arbeiten auf einer Kopie der Karte, und nicht das original, und legen Sie es als die primäre nur, wenn Sie commit).
Ich bin überrascht, niemand erwähnt hat, aber Auf Cliff umgesetzt hat, eine wait-free hashmap in Java, die ich glaube, könnte die Portierung nach C++,