Leistung von pthread_mutex_lock / unlock

Anstatt sich um die Grashalme zu kümmern, treten Sie zurück und beobachten Sie den ganzen Wald.

Jeder Algorithmus, der von zwei Threads abhängt, die sich potentiell gegenseitig auf die Zehen treten, ist von Natur aus ineffizient. Versuchen Sie, einen Weg zu finden, um den Bedarf an Interaktion drastisch zu reduzieren.

Wenn zum Beispiel ein Thread Daten erzeugt und der andere Daten verwendet, kann man sich leicht einen ineffizienten Algorithmus ausdenken, bei dem der Produzent die Daten im Shared Memory veröffentlicht und dann darauf wartet, dass der andere ihn konsumiert. In der Zwischenzeit wartet der Verbraucher darauf, dass der Produzent fertig wird, usw., usw. Dies wird alles viel vereinfacht, indem der Produzent in eine Datei oder ein Rohr schreibt und der Verbraucher daraus liest.

pthread_mutex_lock und pthread_mutex_unlock variieren in den Kosten abhängig von der Konkurrenz:

1. Verwendung eines einzelnen Threads - Entweder existiert nur ein Thread oder nur ein Thread verwendet den Mutex und die Ressource, die er schützt: Sperren ist praktisch frei , vielleicht höchstens 80-100 Zyklen.
2. Mehrere Threads, die die Ressource verwenden, aber Sperren werden für sehr kurze Intervalle gehalten, und Konflikte sind selten: Sperren haben einige Kosten und sind schwer zu messen. Die Kosten bestehen hauptsächlich darin, die Cache-Zeilen anderer Cores / Cpus ungültig zu machen.
3. Signifikante Sperrkonkurrenz: Fast jede Sperre und Entsperrung erfordert Unterstützung vom Kernel, und die Kosten betragen leicht mehrere tausend (möglicherweise sogar zehntausend) Zyklen pro Sperre / Entsperrung.

Dennoch sollten Mutexe in den meisten Situationen und bei den meisten Implementierungen das kostengünstigste Sperrelement sein. Gelegentlich können Spinlocks besser funktionieren. Ich würde niemals erwarten, dass Semaphore besser funktionieren.

Soweit ich sehen kann, ist Ihre Sperrstrategie nicht optimal, da die meisten Sperren nicht zum Ändern der Daten verwendet werden, sondern nur, um den Weg durch den Baum zu finden und zu finden.

pthread_rwlock_t könnte dabei helfen. Sie würden den Pfad in der Baumstruktur nur lesen, bis Sie auf einen Knoten treffen, auf dem Sie Änderungen vornehmen möchten. Dort würden Sie dann eine Schreibsperre nehmen. Dadurch könnten andere Threads die gleiche Aufgabe ausführen, wenn sie in einem anderen Zweig den Baum hinuntergehen, ohne sich gegenseitig zu stören.

Eine vernünftige Implementierung von pthread_rwlock_t würde dies mit einem Zähler für die Leser tun, den es mit atomaren Operationen ändert, solange es keinen Konflikt mit Writern gibt. Dies sollte sehr schnell sein. Sobald es Streit gibt, wäre es so teuer wie ein Mutex, denke ich.

Sperren und Entsperren sind im Fall von pthread_mutex_lock / unlock sehr teuer. Mit mehr Details zum Algorithmus könnte ich einige Vorschläge machen, aber soweit ich das beurteilen kann, kann ich Ihnen nichts sicher sagen. Semaphore sind eine Alternative (wiederum abhängig vom Algorithmus) und auch Barrieren sind eine weitere nützliche Methode für die Parallelität. Um den Overhead zu unterstützen, können Sie beispielsweise die Größe oder Granularität Ihrer Sperren erhöhen. Sperren innerhalb von Schleifen, die mehrere Male durchlaufen, sind eine schlechte Idee und Sie möchten sie möglicherweise außerhalb der Schleife verschieben. Dies ist nur ein Beispiel, aber es gibt wahrscheinlich mehr, die ich mir vorstellen kann. Es geht darum festzustellen, ob die Kosten für die Sperre höher sind als für den kritischen Abschnitt Ihres Codes. Wenn Sie Ihren Algorithmus oder einen Beispielcode zur Verfügung stellen, würde ich gerne einen Blick darauf werfen.

Ihre Schlösser sind wahrscheinlich zu feinkörnig. Natürlich kann die optimale Granularität je nach Arbeitslast variieren.

Sie können eine einzelne Sperre für den gesamten Baum verwenden und kann besser funktionieren. Aber wenn Sie viel lesen und relativ wenige Einfügungen / Löschungen durchführen, endet der ganze Baum oft ohne guten Grund. Vielleicht möchten Sie eine Leser-Schreiber-Sperre verwenden, die mehrere Leser gleichzeitig erlauben würde.

Ihre Frage hat mich an diese andere erinnert, wenn es einen Vergleich gibt feinkörniges Sperren und grobkörniges Sperren für eine verkettete Liste. Während in der grobkörnigen Version jeder Thread der Reihe nach (nicht parallel) lief, und die Gesamtlaufzeit war etwas mehr als die Summe der Laufzeit jedes Threads, und in der feinkörnigen Version war die Gesamtlaufzeit viel geringer als die Summe der Laufzeit jedes Threads, der zusätzliche Overhead der feinkörnigen Verriegelung, der diese Vorteile vollständig ausgleicht, macht die feinkörnige Version langsamer als die grobkörnige Version.