Viele Wege führen zum Sort

Abstract

Moderne Prozessoren protzen mit immer mehr Kernen ("Wegen" auf gut Neudeutsch), aber traditionelle Unix-Tools wie grep und sort wissen wenig damit anzufangen, was lästig ist, wenn man mal schnell ein File mit 40 Millionen Zeilen sortieren will.

In diesem Workshop sollen einige Wege erforscht werden, ein einfaches paralleles sort zu schreiben. Ich werde eine Variante in Perl (weil ich das gut kenne und weil es mit Threads so überhaupt nichts am Hut hat) und Go (weil ich das noch nicht kenne, es aber behauptet besonders gut für Multiprozessorsysteme geeignet zu sein) vorstellen. Die Teilnehmer sind herzlich eingeladen, eigene Varianten in den Programmiersprachen ihrer Wahl zu entwickeln.

Programme

psort-1merge.pl

Grundidee: Sortieren ist O(n·log(n)), splitten und mergen aber nur O(n), daher ist es sinnvoll, die Records auf mehrere Prozesse aufzusplitten, parallel zu sortieren und anschließend wieder zusammenzumergen.

Hauptprozess ist mit Kindprozessen über Pipes verbunden, teilt Input an die Kindprozesse auf, diese sortieren ihren Teil und schreiben wieder an den Elter zurück - der merget zusammen und gibt aus.

Wie man an der Graphik sieht, wird hier der falsche Teil optimiert: Der Großteil der Zeit wird gar nicht beim Sortieren verbraten, sondern beim Lesen (inklusive berechnen des Sortierschlüssels) und Schreiben des Resultats. Der erste Schritt wird parallelisiert (das Berechnen des Sortierschlüssels passiert im Sortierprozess), aber das Mergen nicht - mit steigender Anzahl Prozesse dominiert dieser Teil.

Zum Teil liegt das Problem sicher bei Perl: Sortieren ist eine eingebaute Funktion, die ziemlich schnell ist. Das Mergen hingegen muss in Perl ausprogrammiert werden, wodurch der Overhead des Bytecode-Interpreters relevant wird. Eine Reimplementation des gleichen Algorithmus in C wäre sicher deutlich schneller.

psort.go

Hauptprozess liest ganzen Input ein und startet "goroutines" (threads), die jeweils einen zusammenhängenden Teil sortieren. Anschließend wird gemergt und ausgegeben.

psort-mmerge.pl

Variation von psort-1merge.pl. Wie bereits festgestellt ist das zusammenmergen von n Thread in einem Prozess recht aufwendig. Daher wird hier auch das parallelisiert: Der Parent erzeugt genau 2 Kindprozesse, auf die er seinen Input aufteilt und deren Output wieder zusammengemergt wird. Die Kindprozesse machen entweder rekursiv das gleiche oder sie sortieren ihren Input.

Die Zeit, die mit dem Mergen verbracht wird, ist nun von der Anzahl der Prozesse unabhängig (weil der letzte immer die gleiche Anzahl Records aus genau zwei Streams zusammenmergen muss). Das Splitten wird zunächst deutlich schneller und danach zumindest nicht mehr langsamer. Somit wird mit zunehmer Parallelisierung (und damit kürzeren Sortierzeiten) das Programm immer schneller, wenn auch 15 Prozesse nur unwesentlich schneller sind als 7.