Performance verlust bei Thread Locks vermeiden?



  • Hi,

    welche möglichkeiten gibt es den um zu vermeiden, das man bei einem 8/16 CPU Kerne system (und in Zukunft evtl. viel höher) bei der nutzung von Threads zuviel Rechenzeit für Locking verbraucht, ausser das man versucht weniger Locks zu nutzen?

    Bisher "kenne" ich z.B. Verteilte Programmierung, also anstelle von Threads eben Prozesse via Shared Memory oder MPCHI2 oder ähnliches, was aber eine komplett andere Programmier Weise beudetet (was kein Problem ist, da das eventuelle Programm noch nicht geschrieben ist, sondern erst in Planung).



  • Beste Lösung ist es wohl, möglichst wenig Berührungspunkte zwischen den Threads einzubauen, wo du die Zugriffe synchronisieren mußt.

    PS: Weil das nicht wirklich ein C++ Problem ist, bekommst du mal einen kräftigen Stoß 😉



  • Dieser Thread wurde von Moderator/in CStoll aus dem Forum C++ (auch C++0x) in das Forum Rund um die Programmierung verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.



  • Das ist eine komische Frage.
    Die einzige Antwort ist naheliegend, aber sicher nicht das was du wissen willst: dass man die Locks schneller macht.

    Die praktikable Lösung ist aber eher die, die du explizit ausgenommen hast, nämlich weniger oft Locks zu verwenden.



  • CStoll schrieb:

    Beste Lösung ist es wohl, möglichst wenig Berührungspunkte zwischen den Threads einzubauen, wo du die Zugriffe synchronisieren mußt.

    PS: Weil das nicht wirklich ein C++ Problem ist, bekommst du mal einen kräftigen Stoß 😉

    Sorry, mir war bewusst das es keine C++ spezifische Frage war. Habe lediglich nicht genau geguckt welche Foren es hier noch gibt 🙄 nochmals: Sorry 😞



  • hustbaer schrieb:

    Das ist eine komische Frage.
    Die einzige Antwort ist naheliegend, aber sicher nicht das was du wissen willst: dass man die Locks schneller macht.

    Die praktikable Lösung ist aber eher die, die du explizit ausgenommen hast, nämlich weniger oft Locks zu verwenden.

    Hmm, naja weniger Locks ist nunmal kaum/garnicht möglich, da oft Werte verändert werden wo unklar ist wieviele Threads sie brauchen zum Lesen/Schreiben und Wann, Wie oft usw.

    Was ich gerne auch vermeiden würde ist ein Flaschenhals Seitens des Programms. Am liebsten Sollte lediglich das Betriebssystem der Flaschenhals sein bzw. die Hardware. Allerdings ist mir klar das man mit Locks eben nunmal Rechenzeit verlieren wird.

    Man hat mir Boost::Interprocess empfohlen (soweit ich mich korrekt erinnere). Boost::Interprocess brachte mich (ebenfals soweit ich mich korrekt erinnere) indirekt zu Message Queues, welche ich nun ziemlich interressant finde. Löst allerdings natürlich nicht das Locks "Problem".

    Weiter kommen noch Probleme z.b. eine Datenbankverbindung mit Asnychronen Aufrufen und Asynchroner Netzwerk Kommunikation innerhalb der Threads Thread-Safe zu verteilen bzw. zur verfügung zu stellen und die Last gleichmäßig auf die Threads zu verteilen.



  • Viel hast du noch nicht programmiert. Mach doch nicht so ein Chaos an Threads, nur weil es jetzt Multicores gibt.



  • Baue dir in jedem Thread einen mehr oder wenig großen Zwischenspeicher im threadlokalen Bereich auf und "pushe" ihn in deinen globalen Bereich, falls er überläuft oder der Thread endet. Nur beim "Pushen" brauchst du dann deinen Lock.



  • struct schrieb:

    hustbaer schrieb:

    Das ist eine komische Frage.
    Die einzige Antwort ist naheliegend, aber sicher nicht das was du wissen willst: dass man die Locks schneller macht.

    Die praktikable Lösung ist aber eher die, die du explizit ausgenommen hast, nämlich weniger oft Locks zu verwenden.

    Hmm, naja weniger Locks ist nunmal kaum/garnicht möglich

    Wenn du meinst...
    Dann ist das Thema ja erledigt.



  • It depends... Evtl. sind lock-free Datenstrukturen was fuer dich, kommt aber aufs Problem an. Und sollte das was fuer dich sein: nicht selbst zu implementieren versuchen, sondern libraries verwenden. Lock-Free ist ne sehr komplizierte Sache, da kann man sehr sehr viel falsch machen ;). Wenn du das besser beschreibst, faellt uns vllt. noch 'n Weg ein, Locks zu sparen. aber so generell laesst sich da nicht viel sagen.



  • Es ist im Prinzip möglich alle parallelen Algorithmen lockfrei zu implementieren. Siehe Peterson-Lock, das auf n Threads erweitert werden kann. Nur sind diese Ansätze sehr kompliziert und auch ineffizient (vor allem was den zusätzlichen Speicher angeht).

    Schau dir mal das Compare and Swap (CAS) Prinzip an. Das ist eine Möglichkeit für feingranulares locking.
    In Java heisst die Funktion wirklich compareAndSwap(...) und in C# Interlocked.CompareExchange(...). Hier wird bestimmt auch jemand wissen wie man das in C++ anwenden kann 😉
    Ich musste z.B. gerade vor einer Woche eine lockfreie multithreaded queue implementieren und habe dabei CompareExchange vewendet.

    Aber wie ein anderer schon gesagt hat:
    Nutze möglichst libraries. Parallele Programmierung ist aus meiner Sicht sehr kompliziert und sehr fehleranfällig. Normale Programmierbücher behandeln meistens leider kein multithreaded programming.



  • Blue-Tiger schrieb:

    It depends... Evtl. sind lock-free Datenstrukturen was fuer dich, kommt aber aufs Problem an. Und sollte das was fuer dich sein: nicht selbst zu implementieren versuchen, sondern libraries verwenden. Lock-Free ist ne sehr komplizierte Sache, da kann man sehr sehr viel falsch machen ;). Wenn du das besser beschreibst, faellt uns vllt. noch 'n Weg ein, Locks zu sparen. aber so generell laesst sich da nicht viel sagen.

    Ah! Lock-Free Datenstrukturen hören sich interessant/nützlich an um Global Daten (Variablen, Structs usw.) Lock-Free den (Worker-)Threads zur verfügung zu stellen und mit Ring-Buffer könnte man dann noch ne Art Lock-Free Message Queue realisieren oder z.b. Linux Kernel Message Queues (oder je nach OS halt) um z.b. "Befehle" unter Threads auszutauschen?

    PS: Danke an Alle die bisher geanwortet haben 🙂



  • icarus2 schrieb:

    Es ist im Prinzip möglich alle parallelen Algorithmen lockfrei zu implementieren. Siehe Peterson-Lock, das auf n Threads erweitert werden kann. Nur sind diese Ansätze sehr kompliziert und auch ineffizient (vor allem was den zusätzlichen Speicher angeht).

    Schau dir mal das Compare and Swap (CAS) Prinzip an. Das ist eine Möglichkeit für feingranulares locking.
    In Java heisst die Funktion wirklich compareAndSwap(...) und in C# Interlocked.CompareExchange(...). Hier wird bestimmt auch jemand wissen wie man das in C++ anwenden kann 😉
    Ich musste z.B. gerade vor einer Woche eine lockfreie multithreaded queue implementieren und habe dabei CompareExchange vewendet.

    Aber wie ein anderer schon gesagt hat:
    Nutze möglichst libraries. Parallele Programmierung ist aus meiner Sicht sehr kompliziert und sehr fehleranfällig. Normale Programmierbücher behandeln meistens leider kein multithreaded programming.

    Danke 🙂 CAS habe ich soweit ich mich korrekt erinnere via Google oder/und Wikipedia entdeckt, allerdings nur überflogen (mehr oder weniger)...

    Sind Hazard-Pointers oder Ring-Buffer ebenfals ineffizienter als CAS?



  • struct schrieb:

    Sind Hazard-Pointers oder Ring-Buffer ebenfals ineffizienter als CAS?

    Kommt drauf an. Ist Blau denn effizienter als Sonntag?



  • du musst erst das problem haben (oder zumindestens genug expertise) und dann kannst du eine loesung suchen.
    jetzt schon loesungen zu erarbeiten fuer hypothetische probleme kann genau das gegenteil erreichen von dem was du moechtest -> schlechter skalierbar mit der anzahl der threads.

    es haengt zudem auch sehr von der hardware ab was 'gut' oder 'schlecht' ist, ein opteron vs cell vs core2 vs nehalem verhalten sich ziemlich anders, wenn du so low level locks begutachtest.
    es haengt auch davon ab wie genau deine daten sein sollen, manchmal macht es nichts wenn man nicht die aktuellsten daten hat, dann kann man sogar komplett ohne atomics arbeiten, trotz multithreading, aber das ist eben von deinem konkreten fall abhaengig.

    bekomm es erstmal grundsaetzlich zum laufen was du moechtest, halt es flexibel und dann solltest du profilen und das problem finden und anschliessend loesen, damit bist du am besten beraten.



  • Es ist oftmals auch sehr schwierig (bis teilweise unmöglich) abzuschätzen welche Implementierung nun die effizienteste ist. Da gibts oft nur eins: Beides implementieren und dann die Laufzeit vergleichen.



  • hustbaer schrieb:

    struct schrieb:

    Sind Hazard-Pointers oder Ring-Buffer ebenfals ineffizienter als CAS?

    Kommt drauf an. Ist Blau denn effizienter als Sonntag?

    Hehe... hab erst später kapiert/gelernt das (bzw. soweit ich es verstanden habe) Ring-Buffer und Co. anscheinend trotzdem CAS (CMPXCHG) benutzen um ihr "lock-free" zu "erreichen", oder?



  • @rapso: Danke für die Hinweise 🙂 Aber kannst du vielleicht näher auf die Beiden Aussagen eingehen:

    rapso schrieb:

    es haengt zudem auch sehr von der hardware ab was 'gut' oder 'schlecht' ist, ein opteron vs cell vs core2 vs nehalem verhalten sich ziemlich anders, wenn du so low level locks begutachtest.
    es haengt auch davon ab wie genau deine daten sein sollen, manchmal macht es nichts wenn man nicht die aktuellsten daten hat, dann kann man sogar komplett ohne atomics arbeiten, trotz multithreading, aber das ist eben von deinem konkreten fall abhaengig.

    @icarus2: Danke fürn Tip 🙂 Sowas in der Art wollte ich, soweit ich mich erinnere, selber schon tuen um zu sehen was nun konkret performanter wäre.



  • struct schrieb:

    hustbaer schrieb:

    struct schrieb:

    Sind Hazard-Pointers oder Ring-Buffer ebenfals ineffizienter als CAS?

    Kommt drauf an. Ist Blau denn effizienter als Sonntag?

    Hehe... hab erst später kapiert/gelernt das (bzw. soweit ich es verstanden habe) Ring-Buffer und Co. anscheinend trotzdem CAS (CMPXCHG) benutzen um ihr "lock-free" zu "erreichen", oder?

    Ja. Lock-Free heißt da nur, daß nicht die übliche "Nur einer kann was was machen, alles anderen müssen WARTEN"-Strategie verfolgt wird. Also keine Mutex/Semaphore/CritSect. Insbesondere nicht der Unfall, daß der Eine, der die CritSect gerade offen hat, blöderweise gerade mal Code einlagern muß, die Platte anruckeln läßt und 1750ms wartet, und alle anderen aus lauter Solidarität mitwarten.
    Trotzdem muß sowas wie CAS benutzt werden und CAS muß auf Prozessorebene schon ein bißchen lockenund braucht ungeheure 20 Takte.


Log in to reply