Hi, habrozhiteli! Die Sprache C ++ wird gewählt, wenn Sie wirklich blitzschnelle Anwendungen erstellen müssen. Und eine wettbewerbsfähige Verarbeitung von hoher Qualität wird sie noch schneller machen. Mit den neuen Funktionen von C ++ 17 können Sie die volle Leistungsfähigkeit der Multithread-Programmierung nutzen, um auf einfache Weise die Probleme der Grafikverarbeitung, des maschinellen Lernens usw. zu lösen. Anthony Williams, Experte für wettbewerbsorientierte Verarbeitung, betrachtet Beispiele und beschreibt praktische Aufgaben und gibt Geheimnisse preis, die für alle von Nutzen sind einschließlich der erfahrensten Entwickler.
Im Buch • Ein vollständiger Überblick über die Funktionen von C ++ 17. • Start und Ablaufsteuerung. • Synchronisation von Wettbewerbsvorgängen. • Entwicklung von Wettbewerbscode. • Debuggen von Multithread-Anwendungen. Das Buch eignet sich für Entwickler mit mittlerer Entwicklungsstufe, die C und C ++ verwenden. Programmiererfahrung ist nicht erforderlich.
Wettbewerbsfähige Code-Entwicklung
8.1. Möglichkeiten zum Verteilen der Arbeit zwischen Threads
Stellen Sie sich vor, Sie müssen ein Haus bauen. Dazu müssen Sie eine Baugrube graben, das Fundament selbst füllen, Mauern errichten, Rohre und elektrische Leitungen verlegen usw. Theoretisch kann mit ausreichenden Kenntnissen alles unabhängig durchgeführt werden, aber höchstwahrscheinlich wird es viel Zeit in Anspruch nehmen und Sie müssen von einem Job auf einen anderen wechseln ein anderer. Man kann aber Assistenten einstellen. Dann müssen Sie auswählen, wie viele Assistenten eingestellt werden sollen, und entscheiden, wozu sie in der Lage sein sollen. Sie können zum Beispiel zwei Arbeiter einstellen und mit ihnen arbeiten. Dann muss man noch von einem Werk zum anderen wechseln, aber jetzt wird es schneller gehen, da es mehr Künstler geben wird.
Sie können eine andere Option wählen - ein Team von Spezialisten wie Maurer, Schreiner, Elektriker und Klempner einstellen. Jeder wird in seiner eigenen Spezialität arbeiten, daher wird er untätig sitzen, bis der Klempner eine Arbeitsfront hat. Und doch wird es schneller gehen als zuvor, da es mehr Arbeiter gibt, und während der Elektriker die Verkabelung in der Küche durchführt, kann der Klempner zur Toilette gehen. Wenn jedoch für einen bestimmten Spezialisten keine Arbeit geleistet wird, entstehen mehr Ausfallzeiten. Es kann jedoch festgestellt werden, dass die Arbeit trotz der berücksichtigten Ausfallzeiten schneller von einem Spezialisten als von einem Arbeitsteam ausgeführt wird. Spezialisten müssen die Werkzeuge nicht ständig wechseln, und mit Sicherheit erledigt jeder seine Aufgabe schneller als der Arbeiter. Ob dies tatsächlich so sein wird, hängt von den konkreten Umständen ab: Alles wird in der Praxis gelernt.
Auch wenn Sie Spezialisten einbeziehen, müssen Sie immer noch eine andere Anzahl von Arbeitern verschiedener Fachrichtungen auswählen. Vielleicht ist es sinnvoll, zum Beispiel mehr Maurer als Elektriker einzustellen. Darüber hinaus können sich die Zusammensetzung Ihres Teams und die allgemeine Effektivität seiner Arbeit ändern, wenn Sie mehrere Häuser gleichzeitig bauen müssen. Auch wenn ein Klempner in einem Haus nur wenig Arbeit hat, kann der Bau mehrerer Häuser gleichzeitig den ganzen Tag dauern. Wenn Sie keine Spezialisten für Ausfallzeiten bezahlen müssen, können Sie außerdem ein größeres Team einstellen, auch wenn sich die Anzahl der gleichzeitig arbeitenden Personen nicht ändert.
Aber hör auf über den Bau zu reden. Was hat das alles mit Threads zu tun? Sie können ähnliche Überlegungen anstellen. Sie müssen entscheiden, wie viele Threads verwendet werden und welche Aufgaben sie ausführen sollen. Benötigen wir Universalfäden, die die Arbeit erledigen, die zu einem bestimmten Zeitpunkt benötigt wird, oder Spezialfäden, die gut auf nur eine Sache abgestimmt sind? Oder lohnt es sich, beides zu kombinieren? Diese Entscheidungen müssen unabhängig von den Gründen für die Parallelisierung des Programms getroffen werden, und die Leistung und Klarheit des Codes hängen wesentlich davon ab, wie erfolgreich sie sind. Daher ist es wichtig, sich vorzustellen, welche Optionen zur Verfügung stehen, um bei der Entwicklung der Anwendungsstruktur eine kompetente Entscheidung zu treffen. In diesem Abschnitt werden verschiedene Methoden zum Verteilen von Aufgaben behandelt, beginnend mit der Verteilung von Daten zwischen Threads, bis andere Arbeiten ausgeführt wurden.
8.1.1. Verteilung von Daten zwischen Threads vor der Verarbeitung
Am einfachsten zu parallelisieren sind einfache Algorithmen wie std :: for_each, die Operationen für jedes Element eines Datensatzes ausführen. Um diesen Algorithmus zu parallelisieren, können Sie jedes Element einem der Verarbeitungsthreads zuordnen. In Zukunft wird bei der Betrachtung von Leistungsproblemen deutlich, dass die beste Verteilungsoption zur Erzielung einer optimalen Leistung von den Merkmalen der Datenstruktur abhängt.
Der einfachste Fall beim Verteilen von Daten ist, wenn die ersten N Elemente einem Stream, die nächsten N Elemente einem anderen Stream usw. zugewiesen werden (Abb. 8.1). Es können jedoch auch andere Schemata verwendet werden. Unabhängig von der Methode der Datenverteilung verarbeitet jeder Thread nur die ihm zugewiesenen Elemente, ohne mit anderen Threads zu interagieren, bis die Verarbeitung abgeschlossen ist.
Die Struktur sollte allen bekannt sein, die mit der Programmierung in den Umgebungen Message Passing Interface (MPI,
www.mpi-forum.org ) oder OpenMP (http://www.openmp.org/) gearbeitet haben: Die Aufgabe ist in viele Aufgaben unterteilt, die parallel ausgeführt werden. Workflows führen sie unabhängig voneinander aus, und die Ergebnisse werden in der letzten Informationsphase gesammelt. Dieser Ansatz wurde im Beispiel mit der Akkumulationsfunktion aus Abschnitt 2.4 verwendet: Sowohl parallele Tasks als auch die Reduktionsstufe sind Akkumulationen. Für einen einfachen for_each-Algorithmus fehlt der letzte Schritt, da nichts zu reduzieren ist.
Die Tatsache, dass eine Mischung als das Wesentliche der Endstufe definiert ist, spielt eine sehr wichtige Rolle: Eine elementare Implementierung ähnlich der in Listing 2.9 gezeigten führt diese Mischung als letzte sequenzielle Stufe aus. Diese Phase wird jedoch häufig auch parallelisiert: Die Akkumulation ist eine Reduktionsoperation, sodass der Code in Listing 2.9 geändert werden kann, um einen rekursiven Aufruf desselben Codes zu erhalten, wenn beispielsweise die Anzahl der Threads die Mindestanzahl der vom Thread verarbeiteten Elemente überschreitet. Sie können Workflows auch zwingen, Rollup-Schritte auszuführen, sobald jeder von ihnen seine Aufgabe abgeschlossen hat, anstatt jedes Mal neue Threads zu starten.
Bei aller Wirksamkeit ist diese Technik nicht vielseitig. Manchmal können Daten nicht genau im Voraus aufgeteilt werden, da die Zusammensetzung jedes Teils erst während der Verarbeitung bekannt wird. Dies zeigt sich insbesondere bei der Verwendung von rekursiven Algorithmen wie Quicksort, weshalb ein anderer Ansatz erforderlich ist.
8.1.2. Rekursive Datenverteilung
Der Quicksort-Algorithmus besteht aus zwei Hauptschritten: Aufteilen der Daten in zwei Teile - alles, was zu einem der Elemente (Referenz) führt, und alles danach in der endgültigen Sortierreihenfolge und rekursives Sortieren dieser beiden Hälften. Es ist unmöglich, sie durch vorläufige Aufteilung der Daten zu parallelisieren, da nur während der Verarbeitung der Elemente bestimmt werden kann, in welche „Hälfte“ sie fallen. Wenn Sie diesen Algorithmus parallelisieren möchten, müssen Sie das Wesentliche der Rekursion verwenden. Auf jeder Rekursionsstufe werden immer mehr Aufrufe der Funktion quick_sort ausgeführt, da Sie sowohl diejenigen sortieren müssen, die größer als die Referenz sind, als auch diejenigen, die kleiner als diese sind. Diese rekursiven Aufrufe sind voneinander unabhängig, da sie sich auf separate Elementmengen beziehen. Aus diesem Grund sind sie die ersten Kandidaten für die Wettbewerbsfähigkeit. Diese rekursive Verteilung ist in Fig. 2 dargestellt. 8.2.
Diese Implementierung wurde bereits in Kapitel 4 erfüllt. Anstatt zwei rekursive Aufrufe für die größere und kleinere Hälfte durchzuführen, haben wir die Funktion std :: async () verwendet, die bei jedem Schritt asynchrone Tasks für die kleinere Hälfte ausführt. Aufgrund der Verwendung von std :: async () musste die C ++ - Threadbibliothek entscheiden, wann die Task in einem neuen Thread gestartet werden soll und wann - im synchronen Modus.
Es gibt einen wichtigen Umstand: Wenn Sie einen großen Datensatz sortieren, führt das Starten eines neuen Threads für jede Rekursion zu einem schnellen Anstieg der Anzahl der Threads. Bei der Untersuchung von Leistungsproblemen wird angezeigt, dass zu viele Threads die Anwendung verlangsamen können. Darüber hinaus ist eine große Anzahl von Datenflüssen möglicherweise nicht ausreichend. Die Idee, die gesamte Aufgabe in einem solchen rekursiven Modus aufzuteilen, scheint sehr erfolgreich zu sein. Sie müssen lediglich die Anzahl der Threads sorgfältig überwachen. In einfachen Fällen übernimmt die Funktion std :: async () diese Aufgabe, es gibt jedoch auch andere Optionen.
Eine davon besteht darin, die Funktion std :: thread :: hardware_concurrency () zu verwenden, um die Anzahl der Threads auszuwählen, wie dies in der parallelen Version der Funktion accumulate () aus Listing 2.9 der Fall war. Anstatt für jeden rekursiven Aufruf einen neuen Thread zu starten, können Sie das zu sortierende Fragment beispielsweise wie in den Kapiteln 6 und 7 beschrieben auf einen thread-sicheren Stapel legen. Wenn der Thread nichts zu tun hat oder die Verarbeitung aller seiner Fragmente abgeschlossen ist oder auf das Sortieren des Fragments wartet, kann er es nimm ein fragment aus dem stapel und sortiere es.
Listing 8.1 zeigt eine einfache Implementierung dieser Technologie. Wie in den meisten anderen Beispielen wird nur die Absicht demonstriert, und es handelt sich nicht um einen Code, der für die praktische Verwendung bereit ist. Wenn Sie den C ++ 17-Compiler verwenden und Ihre Bibliothek ihn unterstützt, sollten Sie die von der Standardbibliothek bereitgestellten parallelen Algorithmen gemäß den Beschreibungen in Kapitel 10 verwenden.
Listing 8.1. Ein paralleler Quicksort-Algorithmus, der einen Stapel von Fragmenten verwendet, die auf die Sortierung warten
Hier ordnet die Funktion parallel_quick_sort
(19) den Großteil der funktionalen Verantwortlichkeiten der Klasse sorter
(1) zu , wodurch der Stapel unsortierter Fragmente
(2) und mehrerer Threads
(3) auf einfache Weise gruppiert werden kann. Die Hauptarbeit wird in der do_sort-Komponentenfunktion
(9) ausgeführt , die mit der üblichen Datenpartitionierung
(10) belegt ist . Dieses Mal wird kein neuer Thread für jedes Fragment gestartet, sondern dieses Fragment auf dem Stapel (11) abgelegt und nur dann ein neuer Thread gestartet, wenn eine freie Prozessorressource vorhanden ist (12). Da ein Fragment mit niedrigeren Werten als dem des Referenz-Streams von einem anderen Stream verarbeitet werden kann, sollten wir auf dessen Bereitschaft warten
(13) . Damit keine Zeit verschwendet wird (für den Fall, dass wir einen einzelnen Thread haben oder alle anderen Threads bereits belegt sind), wird versucht, Fragmente aus dem Stapel für diese Wartezeit zu verarbeiten
(14) . Die try_sort_chunk-Funktion ruft ein Fragment aus dem Stapel
(7) ab , sortiert es
(8) und speichert die Ergebnisse in dem Versprechungsversprechen, damit sie den Stream empfangen können, der dieses Fragment auf den Stapel legt
(15) .
Jetzt befinden sich gerade gestartete Threads in einer Schleife und versuchen, Fragmente aus dem Stapel
(17) zu sortieren, wenn das Flag end_of_data
(16) nicht gesetzt ist. Zwischen Überprüfungen geben sie die Rechenressource an andere Threads weiter, damit sie zusätzliche Arbeit auf den Stapel schieben können. Die Arbeit des Codes beim Ordnen dieser Threads hängt vom Destruktor Ihrer Sorter
(4) -Klasse ab. Wenn alle Daten sortiert sind, gibt die Funktion do_sort die Kontrolle zurück (auch wenn die Aktivität der Arbeitsthreads beibehalten wird), der Hauptthread kehrt von parallel_quick_sort
(20) zurück und zerstört das Sortiererobjekt. Durch Setzen des Flags end_of_data
(5) wird gewartet, bis die Threads ihre Arbeit beendet haben
(6). Durch Setzen des Flags wird die Schleife in der Threads-Funktion gestoppt (16).
Mit diesem Ansatz verschwindet das Problem der unbegrenzten Anzahl von Threads, die in der Funktion spawn_task enthalten sind, mit der der neue Thread gestartet wurde, und die Abhängigkeit von der C ++ - Threadbibliothek, die die Anzahl der Threads für Sie auswählt, wie dies bei der Verwendung von std :: async () der Fall ist. Stattdessen wird die Anzahl der Threads durch den von der Funktion std :: thread :: hardware_concurrency () zurückgegebenen Wert begrenzt, um ein zu häufiges Wechseln der Tasks zu verhindern. Es ergibt sich jedoch ein anderes Problem: Die Verwaltung dieser Streams und der Datenaustausch zwischen ihnen erschweren den Code erheblich. Obwohl Threads einzelne Datenelemente verarbeiten, greifen alle auf den Stapel zu, fügen neue Fragmente hinzu und nehmen Fragmente für die Verarbeitung auf. Solch ein intensiver Wettbewerb kann die Leistung verringern, selbst wenn ein sperrfreier (daher nicht blockierender) Stapel verwendet wird, und die Gründe dafür werden bald in Betracht gezogen.
Dieser Ansatz ist eine spezielle Version des Thread-Pools - ein Satz von Threads, von denen jeder Arbeit aus der Liste der zurückgestellten Jobs erhält, sie ausführt und dann die Liste nach einem neuen durchsucht. In Kapitel 9 werden einige potenzielle Probleme des Thread-Pools (einschließlich der Konkurrenz beim Zugriff auf die Liste der Werke) und Möglichkeiten zu ihrer Lösung erörtert. Nachdem Sie die erstellte Anwendung so skaliert haben, dass sie auf mehreren Prozessoren ausgeführt wird, werden Sie später auf dieses Kapitel eingehen (siehe Unterabschnitt 8.2.1).
Bei der Verteilung von Daten sowohl vor der Verarbeitung als auch im rekursiven Modus wird davon ausgegangen, dass sie im Voraus festgelegt wurden und eine Suche nach ihrer Verteilung durchgeführt wird. Dies ist jedoch nicht immer der Fall: Wenn die Daten im dynamischen Modus erstellt werden oder aus einer externen Quelle stammen, funktioniert dieser Ansatz nicht. In diesem Fall ist es möglicherweise sinnvoller, die Arbeit nach Art der Aufgabe und nicht nach den Daten selbst zu verteilen.
8.1.3. Verteilung der Arbeit nach Aufgabentyp
Die Aufteilung der Arbeit zwischen den Threads durch Zuweisung der einzelnen Daten (vorab oder während der Datenverarbeitung rekursiv) basiert auf der Annahme, dass die Threads an jedem Teil die gleiche Arbeit leisten werden. Eine alternative Arbeitsteilung ist die Spezialisierung der Abläufe, bei der jeder eine eigene Aufgabe ausführt, da Klempner und Elektriker beim Hausbau unterschiedliche Aufgaben ausführen. Streams können mit unterschiedlichen oder denselben Daten arbeiten, im letzteren Fall jedoch für unterschiedliche Zwecke.
Diese eigentümliche Arbeitsteilung ergibt sich aus der Aufgabentrennung mit Hilfe des Wettbewerbs: Jeder Thread hat eine eigene Aufgabe, die er unabhängig von anderen Abläufen erledigt. Manchmal können andere Threads Daten an den Stream liefern oder Ereignisse erzeugen, auf die er reagieren sollte. Im Allgemeinen konzentriert sich jeder Stream jedoch auf die hohe Leistung einer einzelnen Aufgabe. Dies ist eine gute Grundkonstruktion, bei der jeder Code für eine Sache verantwortlich sein sollte.
Verteilung der Arbeit nach Art der Aufgabe, um die Verantwortung zu teilen
Eine Single-Threaded-Anwendung muss mit Konflikten im Zusammenhang mit dem Prinzip der Einzelverantwortung fertig werden, wenn mehrere Aufgaben für eine bestimmte Zeit ununterbrochen ausgeführt werden müssen, oder die Anwendung muss die rechtzeitige Verarbeitung eingehender Ereignisse bewältigen (z. B. wenn ein Benutzer eine Taste drückt oder Daten über das Netzwerk eingehen). in Gegenwart anderer unvollendeter Aufgaben. In einer Single-Threaded-Computerumgebung müssen Sie unabhängig Code erstellen, der einen Teil von Task A und einen Teil von Task B ausführt, überprüft, ob die Taste gedrückt wurde und keine Netzwerkpakete vorhanden sind, und dann zyklisch zum nächsten Teil von Task A zurückkehren. Dies erschwert die Ausführung des Codes Aufgaben A aufgrund der Notwendigkeit, seinen Zustand beizubehalten und die Steuerung regelmäßig an die Hauptschleife zurückzugeben. Wenn Sie dem Zyklus zu viele Aufgaben hinzufügen, kann die Arbeit erheblich verlangsamt werden und der Benutzer wird wahrscheinlich eine langsame Reaktion auf Tastenanschläge bemerken. Ich bin sicher, dass jeder die extremen Manifestationen einer ähnlichen Situation in bestimmten Anwendungen beobachtet hat: Sie haben eine Aufgabe für die Anwendung festgelegt, und die Benutzeroberfläche reagiert erst, wenn sie abgeschlossen ist.
Hier kommen Ströme auf die Bühne. Wenn Sie jede Task in einem separaten Thread ausführen, kann dies das Betriebssystem anstelle von Ihnen ausführen. Im Code für Aufgabe A können Sie sich darauf konzentrieren, die Aufgabe zu erledigen, ohne sich Gedanken über die Beibehaltung des Status und die Rückkehr zur Hauptschleife zu machen oder darüber, wie viel Zeit vergehen wird, bevor dies geschieht. Das heißt, das Betriebssystem speichert den Status automatisch und wechselt zur richtigen Zeit zu Task B oder C, und wenn das System, auf dem das Programm ausgeführt wird, über mehrere Kerne oder Prozessoren verfügt, können die Tasks A und B gleichzeitig ausgeführt werden. Der Code für die Verarbeitung von Tastenanschlägen oder Quittungen Netzwerkpakete können jetzt zeitnah ausgeführt werden, und jeder wird davon profitieren: Der Benutzer erhält eine angemessene Programmantwort, und Sie als Entwickler erhalten vereinfachten Code, da jeder Stream weitergeleitet werden kann Operationen auszuführen, die in direktem Zusammenhang mit seinen Aufgaben stehen, ohne sie mit dem Kontrollfluss und der Benutzerinteraktion zu vermischen.
Ein ideales Bild entsteht. Aber kann alles so werden? Wie immer hängt alles von den jeweiligen Umständen ab. , . , . , , - . , - , . , . - , . , , - , , , . , , , .
. -, , . , , , . . . , , , , . , , — , , .
. , , .
, . : , , .
— . , , . , , , .
, 8.1.1, , . , .
, : , . , 20 , 3 . , . , , , , 12 , 24 — . . 20 . . . , , , , 12 . , 12 , . , : , , , , , . 3 12 .
, 9 , . . , , . 25 , — . , , : , 100 , , 1 , 100 , 1 100 . , , . , , , .
, , , , .
8.2. ,
, , . , , . , 16 , .
, — , , ( ), . , : ?
8.2.1. ?
( ) , . , , , . , . , . , , ( ) . , , , .
16- 16 : 16 . , 16 . , , ( ). , 16 , , , 1. (oversubscription).
, , C++11 (Standard Thread Library) std::thread::hardware_concurrency(). .
std::thread::hardware_concurrency() : - , , . , , std::thread::hardware_concurrency(), . std::async() , . .
, , , . — , , . , , , , C++. , std::async(), , , . , . , , std::thread::hardware_concurrency(), . , , , .
, . , , , , .
, — .
»Weitere Informationen zum Buch finden Sie auf
der Website des Herausgebers»
Inhalt»
Auszug25% —
C++Nach Bezahlung der Papierversion des Buches wird ein elektronisches Buch per E-Mail verschickt.