Warum die Verwendung von mehr Threads langsamer ist als die Verwendung von weniger Threads?

30

Versucht, Programm X mit 8 Threads auszuführen und es war in n Minuten vorbei .
Versucht, dasselbe Programm mit 50 Threads auszuführen, und es war in n * 10 Minuten vorbei .

Warum passiert das und wie kann ich die optimale Anzahl an Threads ermitteln, die ich verwenden kann?

multithreading PoGibas
quelle

Antworten:

33

Dies ist eine komplizierte Frage, die Sie stellen. Ohne mehr über die Natur Ihrer Fäden zu wissen, ist es schwer zu sagen. Einige Dinge, die bei der Diagnose der Systemleistung zu beachten sind:

Ist der Prozess / Thread

  • CPU-gebunden (benötigt viele CPU-Ressourcen)
  • Speicher gebunden (benötigt viele RAM-Ressourcen)
  • E / A-gebunden (Netzwerk- und / oder Festplattenressourcen)

Alle diese drei Ressourcen sind endlich und jede kann die Leistung eines Systems einschränken. Sie müssen sich ansehen, welche (möglicherweise 2 oder 3 zusammen) Ihre spezielle Situation belastet.

Sie können ntopund iostatund verwenden, um vmstatzu diagnostizieren, was gerade vor sich geht.

slm
quelle
8
Auch die Hardware spielt eine Rolle. Physisch, virtuell, Anzahl der Kerne, Art des Kerns, L1 / L2 / L3-Cache usw.
EightBitTony
46

"Warum passiert das?" ist leicht zu beantworten. Stellen Sie sich vor, Sie haben einen Korridor, in dem Sie vier Personen nebeneinander unterbringen können. Sie möchten den gesamten Müll an einem Ende an das andere Ende verschieben. Die effizienteste Anzahl von Menschen ist 4.

Wenn Sie 1-3 Leute haben, dann verpassen Sie etwas Platz im Korridor. Wenn Sie 5 oder mehr Personen haben, bleibt mindestens eine dieser Personen die ganze Zeit hinter einer anderen Person in der Warteschlange stecken. Wenn immer mehr Menschen den Korridor verstopfen, wird die Aktivität nicht beschleunigt.

Sie möchten also so viele Leute haben, wie Sie hineinpassen können, ohne dass es zu Warteschlangen kommt. Warum Sie Warteschlangen (oder Engpässe) haben, hängt von den Fragen in der Antwort von slm ab.

EightBitTony
quelle
1
Ihr Beispiel ist irreführend. Es wäre besser, etwas zu sagen wie: "Sie haben einen Korridor, in den Sie vier Personen nebeneinander stellen können, und er wird von Ihnen und anderen Personen für verschiedene Aufgaben verwendet. Es gibt einen Schiedsrichter, der entscheidet, wer durch den Korridor gehen darf Dann ist die effizienteste Anzahl von Personen größer als 4 und kleiner als eine Anzahl, bei der Ihre Leute anfangen, sich in eine Warteschlange zu stellen [stark kontextabhängig]. " Gewöhnlich ist es besser, wenn einige Threads mehr als die Anzahl der CPUs aufweisen, als wenn genau 4 Threads verwendet werden. Wenn Sie der einzige sind, der die CPU verwendet, 4ist dies die beste Zahl.
Bakuriu
7
Tolles Beispiel, +1. Bakuriu ist ein Beispiel für das Problem einer begrenzten gemeinsamen Ressource. Es erklärt das Problem und nicht, wie man die optimale Anzahl von Threads findet.
Bananguin
1
Es wäre auch nützlich zu bedenken, dass Threads immer noch ihre eigene Art der Kontextumschaltung haben. Das Erhöhen der Anzahl der Threads erhöht nicht die Leistungskapazität (wie Sie bereits betont haben), sondern beansprucht auch die CPU-Zeit, da der Kernel mehr Arbeit zu erledigen hat. Grundsätzlich sind die Renditen beim Threading rückläufig, und wenn zu viel getan wird, ist die Leistung rückläufig.
Bratchley
9
Jedes Problem kann auf vielen Komplexitätsebenen beschrieben werden. Ich habe eine Annäherung an das Problem angeboten, die meines Erachtens nützlich ist, um die Grundlagen zu erklären. Natürlich kann es verfeinert und detaillierter sein, aber je detaillierter Sie es gestalten, desto weniger nützlich ist es als Einführung in das Thema.
EightBitTony
Ich möchte nur hinzufügen, dass anstatt viel Zeit damit zu verbringen, die optimale Anzahl von Threads zu berechnen, Sie sie einfach so codieren, dass sie leicht geändert werden können. Jede große Zusammenführung wie diese erfordert zahlreiche Testläufe (die meisten mit kleinen Teilmengen Ihrer Daten), um zu perfektionieren. Erhöhen Sie die Anzahl der Threads, bis Sie feststellen, dass die Leistung stark abnimmt oder andere Systemaktivitäten inakzeptabel sind.
DocSalvager
20

Eine übliche Empfehlung ist n + 1 Threads, wobei n die Anzahl der verfügbaren CPU-Kerne ist. Auf diese Weise können n Threads die CPU bedienen, während 1 Thread auf Festplatten-E / A wartet. Wenn weniger Threads vorhanden sind, wird die CPU-Ressource nicht vollständig ausgelastet (irgendwann muss immer auf E / A gewartet werden). Wenn mehr Threads vorhanden sind, kommt es zu Konflikten um die CPU-Ressource.

Threads kommen nicht frei, sondern mit Overhead-ähnlichen Kontextwechseln und - wenn Daten zwischen Threads ausgetauscht werden müssen, was normalerweise der Fall ist - verschiedenen Sperrmechanismen. Dies ist nur dann die Kosten wert, wenn Sie tatsächlich über mehr dedizierte CPU-Kerne verfügen, auf denen Code ausgeführt werden kann. Auf einer Single-Core-CPU ist ein einzelner Prozess (keine separaten Threads) in der Regel schneller als ein Threading. Threads beschleunigen Ihre CPU nicht auf magische Weise, sondern bedeuten nur zusätzlichen Arbeitsaufwand.

Frostschutz
quelle
Dies sollte die allgemeine Antwort sein, wenn die Menge der verfügbaren Informationen gegeben ist. Wir brauchen keine vollständige These und Philosophie wie andere Antworten
Allahjane
9

Wie andere bereits betont haben ( slm answer , EightBitTony answer ), ist dies eine komplizierte Frage , zumal Sie nicht beschreiben, was Sie tun und wie sie es tun.

Aber definitiv mehr Threads zu werfen kann die Dinge noch schlimmer machen.

Auf dem Gebiet des parallelen Rechnens gibt es Amdahls Gesetz , das anwendbar sein kann (oder nicht, aber Sie beschreiben nicht die Details Ihres Problems, also ...) und allgemeine Einsichten über diese Klasse von Problemen geben kann.

Der Punkt der Amdahl Gesetz ist , dass in jedem Programm (in jedem Algorithmus) gibt es immer einen Prozentsatz, der nicht sein können parallel ausgeführt (der sequentiellen Abschnitt ) , und es ist ein weiterer Prozentsatz, werden parallel ausgeführt (der parallele Abschnitt ) [Offensichtlich diese beiden Anteile addieren sich zu 100%].

Diese Teile können als Prozentsatz der Ausführungszeit ausgedrückt werden. Beispielsweise können 25% der Zeit für streng sequentielle Vorgänge aufgewendet werden, und die verbleibenden 75% der Zeit werden für Vorgänge aufgewendet, die parallel ausgeführt werden können.

Bild aus Wikipedia (Bild aus Wikipedia )

Das Amdahlsche Gesetz sagt voraus, dass Sie für jeden gegebenen parallelen Teil (z. B. 75%) eines Programms die Ausführung nur so weit beschleunigen können (z. B. höchstens viermal), selbst wenn Sie immer mehr Prozessoren für die Arbeit verwenden.

Als Faustregel gilt: Je mehr von Ihnen programmieren, die Sie nicht parallel ausführen können, desto weniger können Sie mit mehr Ausführungseinheiten (Prozessoren) erzielen.

Da Sie Threads (und keine physischen Prozessoren) verwenden, kann die Situation noch schlimmer sein. Denken Sie daran, dass Threads (abhängig von der Implementierung und der verfügbaren Hardware, z. B. CPUs / Kerne) mit demselben physischen Prozessor / Kern verarbeitet werden können (eine Form von Multitasking, wie in einer anderen Antwort angegeben).

Diese theoretische Vorhersage (über die CPU-Zeiten) berücksichtigt andere praktische Engpässe nicht als

  1. Begrenzte E / A-Geschwindigkeit (Festplatten- und Netzwerkgeschwindigkeit)
  2. Speichergrößenbeschränkungen
  3. Andere

das kann leicht der begrenzende Faktor in praktischen Anwendungen sein.

DavAlPi
quelle
Diese Antwort muss ausgewählt werden.
Eonil
6

Der Schuldige sollte hier das "CONTEXT SWITCHING" sein. Hierbei wird der Status des aktuellen Threads gespeichert, um die Ausführung eines anderen Threads zu starten. Wenn mehrere Threads die gleiche Priorität erhalten, müssen sie vertauscht werden, bis die Ausführung abgeschlossen ist.

In Ihrem Fall findet bei 50 Threads eine große Menge an Kontextwechsel statt, im Vergleich dazu, dass nur 10 Threads ausgeführt werden.

Dieser Zeitaufwand, der durch das Wechseln des Kontexts entsteht, führt dazu, dass Ihr Programm langsam läuft

extrem
quelle
Da wir nicht wissen, was die Threads sind, scheint dies eine Vermutung zu sein. Ja, die Kontextumschaltung erhöht den Aufwand, aber wenn die Threads eine Art Datenanalyse durchführen, kann dies an Cache-Problemen liegen (dh, Sie können den Cache nicht verwenden, da Sie ihn jedes Mal leeren müssen, wenn Sie die Threads wechseln).
EightBitTony
Thread-Kontextwechsel an und für sich haben wahrscheinlich keinen Einfluss in der Größenordnung auf die Leistung , es sei denn, wir haben es mit einer großen Anzahl von Kontextwechseln zu tun . 50 Threads sind hoch, aber nicht extrem (auf meiner Box werden ps ax | wc -lderzeit 225 Prozesse gemeldet, und sie ist keineswegs stark ausgelastet). Ich bin geneigt, mit der Vermutung von @ EightBitTony zu gehen; Die Ungültigmachung des Caches ist wahrscheinlich ein größeres Problem, da die CPU jedes Mal, wenn Sie den Cache leeren, auf Code und Daten aus dem RAM warten muss .
ein CVn
3

So korrigieren Sie die Metapher von EightBitTony:

"Warum passiert das?" ist leicht zu beantworten. Stellen Sie sich vor, Sie haben zwei Swimmingpools, einen vollen und einen leeren. Sie möchten das gesamte Wasser von einem zum anderen bewegen und haben 4 Eimer . Die effizienteste Anzahl von Menschen ist 4.

Wenn Sie 1-3 Leute haben, dann verpassen Sie die Verwendung einiger Eimer . Wenn Sie 5 oder mehr Personen haben, wartet mindestens eine dieser Personen auf einen Eimer . Das Hinzufügen von mehr und mehr Personen beschleunigt die Aktivität nicht.

Sie möchten also so viele Leute haben, wie gleichzeitig arbeiten können (verwenden Sie einen Eimer) .

Eine Person hier ist ein Thread, und ein Bucket repräsentiert die Ausführungsressource, die der Engpass ist. Das Hinzufügen weiterer Threads hilft nicht, wenn sie nichts tun können. Darüber hinaus sollten wir betonen, dass das Weitergeben eines Eimers von einer Person zu einer anderen in der Regel langsamer ist, als wenn eine einzelne Person den Eimer nur über dieselbe Distanz trägt. Das heißt, dass zwei Threads, die sich auf einem Kern abwechseln, in der Regel weniger Arbeit verrichten als ein einzelner Thread, der doppelt so lang läuft.

Ob die begrenzende Ausführungsressource (Bucket) für Ihre Zwecke eine CPU oder ein Core oder eine Hyper-Thread-Anweisungs-Pipeline ist, hängt davon ab, welcher Teil der Architektur Ihr begrenzender Faktor ist. Beachten Sie auch, dass wir davon ausgehen, dass die Threads völlig unabhängig sind. Dies ist nur der Fall, wenn sie keine Daten gemeinsam nutzen (und Cache-Kollisionen vermeiden).

Wie einige Leute vorgeschlagen haben, ist die begrenzende Ressource für E / A möglicherweise die Anzahl der sinnvollen E / A-Vorgänge in der Warteschlange: Dies kann von einer ganzen Reihe von Hardware- und Kernelfaktoren abhängen, kann aber auch viel größer sein als die Anzahl Kerne. Hier ist der Kontextwechsel, der im Vergleich zu ausführungsgebundenem Code so kostspielig ist, im Vergleich zu E / A-gebundenem Code ziemlich billig. Leider denke ich, dass die Metapher völlig außer Kontrolle geraten wird, wenn ich versuche, dies mit Eimern zu rechtfertigen.

Beachten Sie, dass das optimale Verhalten mit E / A-gebundenem Code in der Regel immer noch höchstens einen Thread pro Pipeline / Core / CPU hat. Sie müssen jedoch asynchronen oder synchronen / nicht blockierenden E / A-Code schreiben, und die relativ geringe Leistungsverbesserung rechtfertigt nicht immer die zusätzliche Komplexität.

PS. Mein Problem mit der ursprünglichen Korridor-Metapher ist, dass dringend empfohlen wird, 4 Warteschlangen zu haben, wobei 2 Warteschlangen Müll transportieren und 2 zurückkehren, um mehr zu sammeln. Dann können Sie jede Warteschlange machen fast so lang wie der Flur und das Hinzufügen von Menschen haben beschleunigen den Algorithmus (Sie drehte sich im Grunde den ganzen Flur in ein Förderband).

Tatsächlich ist dieses Szenario der Standardbeschreibung der Beziehung zwischen Latenz und Fenstergröße im TCP-Netzwerk sehr ähnlich, weshalb es mir aufgefallen ist.

Nutzlos
quelle
Es ist keine Metapher, sondern eine Annäherung, die den Menschen das System so erklären soll, dass sie es leicht visualisieren können. Als solches wird es immer von Leuten "verschmutzt", die die nächste Detailebene kennen, aber nicht wissen, dass ihre Detailebene für Anfänger eigentlich nicht notwendig ist. Niemand lernt Teilchenphysik, indem er mit der Promotion beginnt. Alles, was Sie vorher gemacht haben, ist eine Annäherung, die Sie schrittweise hineinführt und dabei verfeinert. Es ist nicht 'falsch', es ist nur nicht das ganze Bild.
EightBitTony
Niemand ist verwirrt darüber, welche Redewendung Sie verwendet haben, und es ist keine schlechte Analogie. Jede Analogie hat eine Grenze, über die sie von der Sache abweicht, die sie beschreiben soll, und die aufhört, nützlich zu sein. Ich erwähnte dies nur, weil das Original mich so stark an ein anderes Szenario erinnerte und weil ich diese Version für die (hoffentlich) verbesserte Vorhersagbarkeit nicht komplexer finde.
Useless
0

Es ist ziemlich unkompliziert und einfach zu verstehen. Wenn Sie mehr Threads haben, als Ihre CPU unterstützt, werden Sie tatsächlich serialisiert und nicht parallelisiert. Je mehr Threads Sie haben, desto langsamer wird Ihr System. Ihre Ergebnisse sind tatsächlich ein Beweis für dieses Phänomen.

Bruno Taboada
quelle