Ich habe eine große Baumstruktur, auf der mehrere Threads gleichzeitig arbeiten. Idealerweise hätte ich gerne eine individuelle Mutex-Sperre für jede Zelle.
Ich habe mir die Definition von pthread_mutex_t in bits/pthreadtypes.h angeschaut und sie ist ziemlich kurz, daher sollte die Speicherbelegung in meinem Fall kein Problem sein.
Gibt es jedoch eine Leistungseinbuße bei der Verwendung von vielen (sagen wir ein paar tausend) verschiedenen pthread_mutex_t s für nur 8 Threads?
Wenn Sie sehr häufig sperren und entsperren, kann es zu einer Strafe kommen, da das Abrufen und Freigeben von Sperren einige Zeit in Anspruch nimmt und bei Konstrikten mit Sperren sehr viel Zeit in Anspruch nehmen kann.
Wenn Sie viele Sperren in einer Struktur wie dieser verwenden, müssen Sie sehr genau festlegen, was jede Sperre tatsächlich sperrt, und sicherstellen, dass Sie auf AB-BA-Deadlocks achten. Wenn Sie beispielsweise die Struktur des Baums während einer Sperroperation ändern, müssen Sie alle Knoten, die geändert werden sollen, in einer konsistenten Reihenfolge sperren und sicherstellen, dass Threads, die an Nachkommen arbeiten, nicht verwechselt werden.
Wenn Sie eine sehr große Anzahl von Sperren haben, die sich über den gesamten Arbeitsspeicher verteilen, können Probleme mit der Zwischenspeicherung je nach Architektur zu Leistungsproblemen führen, da Sperrenoperationen im Allgemeinen zumindest einen Teil des Zwischenspeichers ungültig machen.
Am besten ist es wahrscheinlich, eine einfache Sperrstruktur zu implementieren, sie dann zu profilieren und dann zu verfeinern, um gegebenenfalls die Leistung zu verbessern. Ich bin mir nicht sicher, was Sie mit dem Baum machen, aber ein guter Anfang wäre vielleicht eine einzige Leser-Schreiber-Sperre für den ganzen Baum, wenn Sie mehr erwarten, als Sie aktualisieren.
"Wir sollten kleine Wirkungsgrade vergessen, sagen wir etwa 97% der Zeit: vorzeitige Optimierung ist die Wurzel allen Übels." - Donald Knuth
Ihre Sperr- / Zugriffsmuster müssen angegeben werden, um dies richtig bewerten zu können. Wenn jeder Thread nur eine oder mehrere Sperren gleichzeitig hält und die Wahrscheinlichkeit, dass zwei oder mehr Threads die gleiche Sperre zur gleichen Zeit wünschen, ist niedrig (entweder ein Zufallszugriffsmuster oder 8 Läufer an verschiedenen Positionen auf einer kreisförmigen Spur mit ungefähr der gleichen Geschwindigkeit oder anderen komplizierteren Dingen laufen), dann wirst du meistens den schlimmsten Fall vermeiden, wo ein Thread schlafen muss, um eine Sperre zu erhalten (oder in einigen Fällen das Betriebssystem involvieren muss, um zu entscheiden, wer gewinnt), weil du es hast paar Fäden und so viele Schlösser.
Wenn jeder Thread zu irgendeinem Zeitpunkt Hunderte oder Tausende von Sperren haben möchte, werden sich die Dinge ändern.
Ich werde Deadlock-Vermeidung nicht berühren, weil ich nichts über den Container weiß, den Sie verwenden, aber Sie müssen sich der Notwendigkeit bewusst sein, sie zu vermeiden.