Statische und dynamische Typisierung

Es wird sehr viel „Informatik-Theologie“ um die Frage der statischen und dynamischen Typisierung betrieben. Da ich mir zu dieser Frage noch keine abschließende Meinung gebildet habe, kann ich hier nur ein paar Überlegungen zu der Thematik darlegen.

Eine Frage ist, wie statisch ist diese statische Typisierung eigentlich? Ein typischer Kandidat ist Java, das immer gerne als Musterbeispiel für statische Typisierung aufgeführt wird. Nun ist Java aber erst einmal sicher dynamisch typisiert. Jedes Java-Objekt hat seinen Typ dabei und dieser wird zur Laufzeit beachtet. Es gibt dann „ClassCastException“ oder so etwas. Man kommt recht weit ohne Casts. Früher brauchte man die für die Collections, aber das ist durch Generics ein Stück weit entschärft worden. Nun sind aber Generics in einigen Kombinationen dermaßen schwierig zu handhaben, man denke nur an die Kombination aus Collections und Arrays. Und wie viele kennen Kovarianz und Kontravarianz Manche Fälle werden dann in der Realität so gelöst, dass man die Generics wegcastet. Das ist Realität in den Java-Quelltexten dieser Welt, auch wenn man es noch so schlecht findet… Was bleibt ist die dynamische Typisierung und „etwas“ statische Typisierung. Es ist viel statische Typisierung, aber keineswegs durchgängig. Andere Programmiersprachen, wie z.B. F#, Scala oder Haskell haben die statische Typisierung konsequenter umgesetzt und dort funktioniert sie auch besser.

Man braucht natürlich einen Mechanismus, um die richtige Funktionalität für die Daten zu verwenden. Das kann durch eine Art von dynamischer Typisierung geschehen, im Prinzip für Polymorphie wichtig. Oder es kann auch programmatisch geschehen, indem quasi die richtige Funktionalität aufgerufen wird und das entsprechend schon zur Compilezeit so festgelegt wird. Das kann durch statische Typisierung unterstützt werden, aber es gibt natürlich auch andere Mechanismen.

Was statische Typisierung verspricht ist aber, dass man weniger Fehler macht. Man kann sagen, dass statische Typen eine Art „Constraints“ sind. Man sieht dadurch bestimmte Fehler, die man vermeiden kann. Die Freunde dynamischer Typisierung schreiben aber genügend Unit-Tests und so findet man die Fehler sowieso. Und die Unit-Tests muss man auch bei statisch typisierten Sprachen schreiben. Also gewinnt man etwas durch die statische Typisierung? Ein bisschen schon, aber es relativiert sich, wenn man seriös Unit-Tests schreibt.

Nun kann eine statische Typisierung den Vorteil haben, dass sie Variablen, Parameter und Rückgabewerte dokumentiert und zwar auf eine Art, die immer aktualisiert werden muss und nicht den Stand von vor ein paar Monaten widerspiegelt, der nie aktualisiert worden ist, weil das vergessen wurde oder die Zeit gefehlt hat.

Dynamische Typisierung kann vorteilhaft sein, wenn man Schnittstellen entwickelt, die mit einem Spektrum von Versionen von Software zusammenarbeiten können, indem man einfach die Typen zur Laufzeit erkennt und richtig behandelt. So kann man ein großes System robuster bauen, weil es zunehmend schwierig ist, ein größeres System komplett auf einmal zu aktualisieren, je größer dieses ist.

Share Button

Nokia schließt Verkauf der Mobiltelefonsparte an Microsoft ab

Mit Wirkung zum 25. April 2014 wird die Übernahme der (ehemaligen) Nokia-Mobiltelefonsparte durch Microsoft abgeschlossen.

Damit kommt eine merkwürdige Entwicklung zum Abschluss, die unabhängig von der juristischen Fragestellung sehr nach Korruption oder zumindest dubiosen Geschäften aussieht, weil der ehemalige Nokia-CEO recht offensichtlich mehr die Interessen seines ehemaligen Arbeitgebers Microsoft als seines dann aktuellen Arbeitgebers Nokia vertreten hat. Unter Elop (und nicht davor) ist Nokia vom Marktführer bei Smartphones zu einem Nischenanbieter geworden. Das mag sich mit den Symbian-Geräten abgezeichnet haben, aber es hätte plausible Ansätze gegeben, zumindest in der Spitzengruppe zu bleiben, wenn Meego oder Android als System eingesetzt worden wäre. Nun hat Samsung die Spitzenposition übernommen, die Nokia einst hatte. Apple war weltweit nie die Nummer eins und wird es wohl auch mit an Sicherheit grenzender Wahrscheinlichkeit nie werden. In einzelnen Märkten, z.B. in der Schweiz, haben sie aber immer noch große Marktanteile.

Und die innovativsten ehemaligen Nokia-Mitarbeiter haben eine neue Firma Jolla gegründet, die an Nokias innovativere Zeiten anzuknüpfen versucht, und vielversprechende Produkte anbietet. Wenn Jolla sich langfristig als Nischenanbieter etablieren kann, ist das sicher ein Erfolg und eine Bereicherung für den Markt.

Microsoft will die neue Abteilung unter dem Namen „Microsoft Mobile Oy“ betreiben. Sie haben die Rechte erworben, den Namen „Nokia“ und die Social-Media-Auftritte von Nokia für eine gewisse Zeit zu verwenden. Das ist nicht ungewöhnlich bei Übernahmen. Z.B. stellt die Firma Volvo seit 1999 keine Autos mehr her, aber sie haben die entsprechenden Aktivitäten verkauft und der aktuelle Besitzer kann auch nach 15 Jahren noch die Marke verwenden. Bei Nokia/Microsoft wird das aber nur für wenige Jahre möglich sein, außer die Verträge werden für entsprechende Zahlungen verlängert.

Share Button

Elixir II

Da ich das Glück hatte, an einer halbtägigen Elixir-Schulung teilzunehmen, möchte ich das Thema wieder aufgreifen.

Elixir ist eine relativ neue Programmiersprache, die sich von der Syntax an Ruby anlehnt. Die Programme laufen auf der Erlang-VM (BEAM). Diese VM ist anscheinend restriktiver als die Java-VM und so ist Elixir von den Konzepten her auch sehr nahe an Erlang.

Grundsätzlich ist Elixir wie Erlang eine funktionale Sprache, nicht wie Ruby objektorientiert. Es gibt aber die Möglichkeit, Strukturen aus Listen und Tupeln aufzubauen und weiterzugeben. Alle diese Strukturen sind immutable. Das heißt, dass Änderungen daran stets das Original unverändert lassen und eine Kopie mit den Änderungen generieren. Im Falle von verketteten Listen funktioniert das gut, wenn man nur am Anfang ein Element hinzufügt, weil dann kein eigentliches Kopieren erforderlich ist. Fügt man am Ende etwas hinzu, muss die Liste kopiert werden, was eine aufwändigere Operation ist. Es gibt keine Schleifen, wie in den meisten herkömmlichen Programmiersprachen, sondern man verwendet stattdessen Rekursion. Endrekursion sollte bevorzugt werden, weil das intern in Schleifen umgewandelt wird. Über die Parameterliste dieser Funktion kann man einen „Zustand“ weiterreichen.

Es ist sehr einfach und auch üblich, „Prozesse“ zu generieren. Dies sind nicht OS-Prozesse, sondern Konstrukte innerhalb von Erlang, man kann etwa an Aktoren denken, wie es bei Scala und Akka genannt wird. Wenn genug Hardware-Ressourcen vorhanden sind, kann man ohne weiteres mehrere Millionen solcher „Prozesse“ gleichzeitig haben. Jeder Prozess hat seinen eigenen Speicher und kann jedem anderen Prozess mit

send(...)

Nachrichten (messages) senden. Diese werden in eine sogenannte Mailbox (eine Warteschlange / engl. Queue) des Prozesses eingefügt und von diesem mit

receive(...)

empfangen. Das typische Muster ist, dass ein Prozess mittels Rekursion in einer Endlosschleife ist und jeweils mit receive Messages empfängt und verarbeitet.

Über diese Prozesse kann man doch so etwas wie einen Zustand modellieren. Man hat einfach einen Prozess mit so einer Endlosschleife und schickt ihm „set“- und „get“-Nachrichten. Die „set“-Nachrichten ändern den Zustand, der in der Endlosschleife über die Parameter weitergereicht wird, die get-Nachrichten lösen aus, dass eine Nachricht an den Absender geschickt wird, die dieser wiederum mit receive abfangen muss.

Funktionen mit gleichem Namen werden nach der Anzahl der Parameter, nicht aber nach dem Typ der Parameter, unterschieden. Die Sprache ist dynamisch typisiert. Man kann statt ein großes „if“ innerhalb einer Funktion zu haben, diese auch für verschiedene Fälle definieren und es wird für den tatsächlichen Aufrufparameter die richtige Teildefinition gefunden.

Share Button

Numerische Typen

Es geht hier nicht um dynamische oder statische Typsisierung, sondern eher darum, was von den Programmiersprachen an Funktionalität für numerische Typen angeboten wird. Irgendeine Form der Typisierung (dynamisch oder statisch) ist natürlich erforderlich, damit das funktionieren kann. Im Extremfall reicht vielleicht sogar der Ansatz, dass durch die Funktionsnamen unterschieden wird, als welche Typen die Eingabeparameter zu interpretieren sind, was z.B. bei Assemblersprachen praktisch durchgängig so üblich ist.

Was ich bei numerischen Typen sehr wichtig finde, ist dass man die Formeln, die die Berechnung beschreiben, so hinschreiben kann, wie sie sind, also z.B.

    \[ a = b \cdot c + d \cdot e \]

oder

a = b * c + d * e

oder gerne auch

a := b (*) c (+) d (*) e

statt

a = (b * c) + (d * e),

denn „Punktrechnung vor Strichrechnung“ lernt man in der Grundschule und das sollte zumindest bei Leuten, die sich mit Quelltexten von Software beschäftigen, im Erwachsenenalter sitzen. Damit will ich nicht sagen, dass man jeweils alle Präzendenzhierarchiestufen aller verwendeten Programmiersprachen kennen sollte, aber diese her schon. Smalltalk zwingt einen zu diesen Klammern.

Noch schlimmer ist Java, wo man für die meisten numerischen Typen etwa so etwas schreiben muss:

a = b.multiply(c).add(d.multiply(e));

Da erkennt kaum jemand die Formel wieder und Fehler sind vorprogrammiert…
Für Software, die in größerem Stil Dinge tut, die mit den primitiven numerischen Typen nicht machbar sind, ist Java nicht geeignet. Andere JVM-Programmiersprachen haben Operatorüberladung und erlauben es, mit geringerem Fehlerrisiko solche Dinge zu entwickeln. Eventuell kann auch ein Präprozessor eingesetzt werden, der eine Java-ähnliche Sprache mit einer Form von Operatorüberladung in Java übersetzt.

Was vielleicht auch geht, ist statt Infix auf Postfix- oder Präfixnotation zu wechseln. Ob man da die Formeln noch erkennt, ist ein bißchen eine Gewohnheits-, Geschmacks- und vielleicht auch Fähigkeitsfrage, wobei es sicher gute SW-Entwickler gibt, die einfach nicht den Blick dafür haben, Infix-Notation oder Postfix-Notation zu erkennen. Das sieht dann mit Präfixnotation in Lisp etwa so aus:

(setq a (+ (* b c) (* d e)))

oder mit Postfix-Notation, die man von alten HP-Taschenrechnern oder von Forth oder von der Druckersprache Postscript kennen könnte etwa so:

&a
b
c
*
d
e
*
+
=

oder etwa so:

b ENTER C * ENTER d ENTER e * + STO a

Angeblich soll das verständlicher sein als die Infixnotation, sagen manche HP-Taschenrechner-Fans aus den 80er Jahren.

In diesem Blogbeitrag über Zahlen steht ein bißchen dazu, auf was sich numerische Typen beziehen können. Eine 1:1-Zuordnung ist in der Regel nicht möglich, weil selbst „unbegrenzte“ Ganzzahlen wie bei Ruby oder Lisp in Wirklichkeit durch den Speicher des Rechners begrenzt sind. Aber man kann doch eine realistische Approximation erkennen.

  Ruby Perl Python Java Scala Clojure Elixir C C++
{\Bbb N}, {\Bbb N_0} ? ? ? (unsigned long eingeschränkt da, Überlauf) (unsigned long eingeschränkt da, Überlauf)
{\Bbb Z} nativ (Integer, BigNum) BigInt ? (BigInteger eingeschränkt wegen fehlendem Operator-Überladen) BigInteger nativ nativ (externe Libraries, z.B. GMP, eingeschränkt brauchbar wegen fehlendem Operator-Überladen) externe Libraries, z.B. GMP
{\Bbb Q} Rational Math::BigRat Fraction (externe Libraries, eingeschränkt brauchbar wegen fehlendem Operator-Überladen) externe Libraries, eventuell Aufnahme in Standardlibrary geplant. nativ ? (externe Libraries, z.B. GMP, eingeschränkt brauchbar wegen fehlendem Operator-Überladen) externe Libraries, z.B. GMP
{\Bbb R} Float, LongDecimal, BigDecimal ja ? Double, BigDecimal Double, BigDecimal ? ? double double
{\Bbb C} Complex ? ? externe Libraries ohne Operatorüberladung mühsam und fehleranfällig. ? ? ? complex ?

p-adische Zahlung und endliche Körper sind wohl schon zu sehr in der Mathematik angesiedelt und selten nativ in Programmiersprachen zu finden, außer in Programmiersprachen, die gezielt eine mathematiklastige Clientel ansprechen. Dabei sind gerade endliche Körper noch recht wichtig für Kryptographie und Codierungstheorie und werden dort natürlich auch benutzt.

Am schmerzhaftesten ist wohl immer noch, dass so wenige Programmiersprachen einen guten ganzzahligen numerischen Typ in die Sprache integriert haben, der es erlaubt, mit beliebig langen Zahlen (im Rahmen von Hauptspeicher) umzugehen.

Programmiersprachen, die so etwas wie Rational als numerischen Typ kennen, lassen ein gängiges Problem erkennen. Erfahrungsgemäß werden bei längeren Rechnungen Nenner und Zähler sehr sehr groß und die Berechnung entsprechend langsam. Dass man gut kürzen kann, ist eher die Ausnahme. Daran sollte man denken und entsprechende Performance- und Lasttests machen, um zu sehen, ob man in Laufzeit- und Speicherprobleme gerät.

Share Button

Shift- and Rotation Functions

Deutsch

In a comment to Carry Bit: How does it work the question about shift and rotation functions has been asked. Which exist and how they work exactly depends off course on the CPU architecture, but I will try to give a high level overview anyway.

The following aspects have to be considered:

  • 8, 16, 32, 64,… Bit: How many Bits are affected by the operation?
  • Shift vs. Rotate: Shift moves bits to the left or right, filling in 0 or 1 in the positions that get freed by this. The bits that get shifted out usually go to the carry bit, so the last one of these wins, if the shift is done by more than one bit. Rotation means what some English knowledge suggests: The bits shifted out are moved in on the other side.
  • ROL and ROR vs RCL and RCR: Rotation through Carry (RCL or RCR) means that the carry bit participates as bit 9., 17., 33. or 65. ROL and ROR leave the carry bit alone, at least do not use it as input.
  • Logical vs. Arithmetic Shift: This deals with the „sign“. For arithmetic Shift the number is considered to be signed in two’s complement. Therefore right shift does not necessarily introduce a 0 as new most significant bit, but depending on the sign introduces a 0 or a 1.

Current CPUs have barrel shifts or something like that built into the hardware, so shift and rotate operations by more than one bit position are much faster than sequences of single shifts. This technology has been around on better CPUs for decades and is not at all new.

How the commands are called exactly and possibly some details about there operations depend on the CPU architecture.

Examples (8 bit) for shifting and rotating by one bit position:

Vorher (Carrybit in Klammern)ROL
(rotate left)
RCL
(rotate left through carry)
ROR
(rotate right)
RCR
(rotate right through carry)
ASL / SHL
(arithmetic/logical shift left)
SHR
(logical shift right)
ASR
(arithmetic shift right)
00000000 (0)00000000 (0)00000000 (0)00000000 (0)00000000 (0)00000000 (0)00000000 (0)00000000 (0)
00000000 (1)00000000 (1)00000001 (0)00000000 (1)10000000 (0)00000000 (0)00000000 (0)00000000 (0)
00000001 (0)00000010 (0)00000010 (0)10000000 (0)00000000 (1)00000010 (0)00000000 (1)00000000 (1)
00000001 (1)00000010 (1)00000011 (0)10000000 (1)10000000 (1)00000010 (0)00000000 (1)00000000 (1)
10000000 (0)00000001 (0)00000000 (1)01000000 (0)01000000 (0)00000000 (1)01000000 (0)11000000 (0)
10000000 (1)00000001 (1)00000001 (1)00000001 (1)11000000 (0)00000000 (1)01000000 (0)11000000 (0)
11111111 (0)11111111 (0)11111110 (1)11111111 (0)01111111 (1)11111110 (1)01111111 (1)11111111 (1)
11111111 (1)11111111 (1)11111111 (1)11111111 (1)11111111 (1)11111110 (1)01111111 (1)11111111 (1)

These shift and rotate operations are needed to express multiplications by powers of two and division by powers of two. In C, C++, C#, Perl, Java and some other porgramming languages these operations are included and written as „<<" (for ASL or SHL), ">>“ (for SHR) and „>>>“ for ASR.

Links

Share Button

Shift- und Rotationsfunktionen

English

Im Kommentar zu Carry Bit: How does it work ist nach den Shift- und Rotationsfunktionen gefragt worden. Welche es genau gibt, hängt natürlich von der Prozessorarchitektur ab, aber grundsätzlich muss man die folgenden Aspekte beachten:

  • 8, 16, 32, 64,… Bit: Wieviele Bits sind von der Operation betroffen?
  • Shift vs. Rotate: Beim Shift werden an einer Seite Bits als 0 oder 1 ergänzt und auf der anderen Seite wandern sie in das Carry-Bit, beim Rotieren werden Bits im Kreis rotiert, die herausfallenden Bits vom einen Ende werden am anderen Ende wieder eingefügt.
  • ROL und ROR vs RCL und RCR: Beim Rotieren durch Carry wird das Carry-Bit als 9., 17., 33. oder 65. Bit miteinbezogen.
  • Logical vs. Arithmetic Shift: Bezieht sich auf die Vorzeichenbehandlung. Für arithmetic Shift wird die Zahl als vorzeichenbehaftet im Zweierkomplement gelesen wird. Deshalb wird beim Right-Shift nicht zwingend eine 0 als höchstwertiges Bit eingefügt, sondern je nach Vorzeichen eine 0 oder eine 1.

Heutige CPUs haben Barrelshifter oder etwas vergleichbares eingebaut und können deshalb auch Shift- und Rotate-Operationen um mehr als eine Bit-Position schnell ausführen.

Wie die Befehle genau heißen, und welche es gibt, hängt vom Prozessor ab:

Beispiele (8 Bit), Verschiebung oder Rotation nur um eine Bitposition:

Vorher (Carrybit in Klammern)ROL
(rotate left)
RCL
(rotate left through carry)
ROR
(rotate right)
RCR
(rotate right through carry)
ASL / SHL
(arithmetic/logical shift left)
SHR
(logical shift right)
ASR
(arithmetic shift right)
00000000 (0)00000000 (0)00000000 (0)00000000 (0)00000000 (0)00000000 (0)00000000 (0)00000000 (0)
00000000 (1)00000000 (1)00000001 (0)00000000 (1)10000000 (0)00000000 (0)00000000 (0)00000000 (0)
00000001 (0)00000010 (0)00000010 (0)10000000 (0)00000000 (1)00000010 (0)00000000 (1)00000000 (1)
00000001 (1)00000010 (1)00000011 (0)10000000 (1)10000000 (1)00000010 (0)00000000 (1)00000000 (1)
10000000 (0)00000001 (0)00000000 (1)01000000 (0)01000000 (0)00000000 (1)01000000 (0)11000000 (0)
10000000 (1)00000001 (1)00000001 (1)00000001 (1)11000000 (0)00000000 (1)01000000 (0)11000000 (0)
11111111 (0)11111111 (0)11111110 (1)11111111 (0)01111111 (1)11111110 (1)01111111 (1)11111111 (1)
11111111 (1)11111111 (1)11111111 (1)11111111 (1)11111111 (1)11111110 (1)01111111 (1)11111111 (1)

Diese Shift- und Rotate-Operationen braucht man vor allem, um Multiplikation mit Zweierpotenzen und Division durch Zwierpotennzen auszudrücken. In C, C++, Perl, Java und einigen anderen Programmiersprachen gibt es diese Operationen „<<" (für ASL oder SHL), ">>“ (für SHR) und „>>>“ für ASR.

Share Button

Sortieren mit Multithreading

Eine Barriere muss man sich so vorstellen, dass verschiedene Threads jeweils ihre eigene Aufgabe durchführen und dann auf die Barriere „warten“, was bedeutet, dass sie darauf warten, dass alle anderen beteiligten Threads auch auf die Barriere warten, also die davor angesetzte Aufgabe abgeschlossen haben.

Als Anwendung für die sogenannte „Barriere“ habe ich einmal ein kleines C-Programm geschrieben, das eingelesene Zeichenketten sortiert. Über einen Parameter kann man wählen, ob Heapsort oder Flashsort oder Quicksort verwendet wird. Dafür habe ich zwei Funktionen (mit Header-Datei) hsort und hsort_r geschrieben, die das gleiche Interface wie qsort und qsort_r haben, so dass man sie austauschbar nutzen kann. Entsprechend auch drei Funtkionen fsort, fsort_r und fsort_f (mit Headern), die sich an das Interface von qsort anlehnen, aber noch einen zusätzlichen Funktionisparameter haben, der eine Art monotone Hash-Funktion nach double darstellt. Die gegebenen Zeichenketten werden zu möglichst gleichen Teilen auf eine frei wählbare Anzahl Threads verteilt. Jeder Thread sortiert seinen Teil mittels hsort_r oder fsprtr oder qsort_r. Anschließend wird mit einer Barriere sichergestellt, dass alle Threads ihren Teil sortiert haben und dann werden baumartig die Ergebnisse von jeweils zwei Threads zusammengefügt, jeweils gefolgt von einer weiteren Verwendung Barriere. An Schluss bleibt ein Thread mit seinem Ergebnis übrig und das ist das Sortierergebnis.

Bei einer Beispieleingabe mit 8603049 Wörtern war fsort mit einem Thread etwas schneller als qsort und qsort war etwa viermal so schnell wie hsort, aber mit einer größeren Anazhl Threads ließen sich alle drei beschleunigen.
Interessant war auf einem Rechner mit 4 Core-CPU und Hyperthreading, also 8 logischen CPUs, die unter /proc/cpuinfo angezeigt wurden, dass das Sortieren mit mehr Threads bei hsort mehr profitierte als bei qsort und um Faktor 5 schneller wurde, während fsort nur um Faktor 2 schneller wurde.

Das erklärt sich wohl vor allem durch das assymptotisch gute Verhalten von fsort (O(n)), was beim Sortieren großer Datenmengen in einem Thread besonders stark zum Tragen kommt. hsort ist im „worst case“ auch noch O(n \log n)

Threads Messwert Quicksort Heapsort Flashsort
1 real 4.090s 16.909s 3.757s
1 user 4.028s 16.815s 3.686s
1 sys 0.053s 0.053s 0.062s
           
2 real 2.753s 8.915s 2.672s
2 user 4.177s 16.457s 3.925s
2 sys 0.074s 0.054s 0.066s
           
3 real 2.333s 6.584s 2.392s
3 user 4.261s 16.676s 4.159s
3 sys 0.070s 0.064s 0.067s
           
4 real 2.027s 5.288s 2.093s
4 user 4.331s 16.202s 4.137s
4 sys 0.067s 0.072s 0.077s
           
5 real 2.151s 5.013s 2.254s
5 user 4.681s 17.423s 4.567s
5 sys 0.060s 0.056s 0.076s
           
6 real 2.039s 4.519s 2.104s
6 user 5.264s 18.511s 4.892s
6 sys 0.072s 0.062s 0.078s
           
7 real 1.928s 4.127s 2.092s
7 user 5.333s 18.878s 5.265s
7 sys 0.080s 0.056s 0.094s
           
8 real 1.862s 3.879s 1.931s
8 user 5.638s 19.338s 5.380s
8 sys 0.080s 0.061s 0.069s
           
9 real 2.032s 4.079s 2.174s
9 user 5.484s 19.594s 5.460s
9 sys 0.072s 0.066s 0.081s
           
10 real 2.017s 4.040s 2.130s
10 user 5.426s 19.091s 5.356s
10 sys 0.084s 0.080s 0.090s
           
11 real 1.954s 4.055s 2.081s
11 user 5.427s 19.240s 5.460s
11 sys 0.077s 0.081s 0.095s
           
12 real 1.928s 3.842s 2.053s
12 user 5.409s 18.860s 5.462s
12 sys 0.078s 0.075s 0.092s
           
13 real 1.923s 3.884s 2.040s
13 user 5.384s 19.123s 5.511s
13 sys 0.077s 0.072s 0.080s
           
14 real 1.870s 3.793s 2.037s
14 user 5.482s 18.566s 5.610s
14 sys 0.064s 0.070s 0.089s
           
15 real 1.895s 3.679s 1.979s
15 user 5.578s 18.549s 5.554s
15 sys 0.090s 0.067s 0.084s
           
16 real 1.861s 3.790s 1.979s
16 user 5.576s 19.033s 5.640s
16 sys 0.088s 0.085s 0.101s
           
17 real 2.025s 3.885s 2.181s
17 user 5.647s 18.699s 5.799s
17 sys 0.090s 0.076s 0.102s
           
18 real 2.019s 3.879s 2.156s
18 user 5.688s 18.532s 5.723s
18 sys 0.069s 0.107s 0.095s
           
19 real 2.022s 3.918s 2.140s
19 user 5.774s 18.783s 5.681s
19 sys 0.093s 0.085s 0.091s
           
20 real 1.975s 3.774s 2.129s
20 user 5.588s 18.095s 5.732s
20 sys 0.093s 0.087s 0.105s
           
100 real 1.978s 3.263s 2.099s
100 user 5.686s 15.371s 6.034s
100 sys 0.150s 0.115s 0.141s
           
400 real 2.013s 2.996s 2.092s
400 user 5.719s 13.150s 6.184s
400 sys 0.242s 0.185s 0.259s
           
1000 real 1.992s 2.876s 2.106s
1000 user 5.802s 12.608s 6.469s
1000 sys 0.325s 0.250s 0.392s

Man sieht also, was auch zu erwarten ist, dass Parallelisierung beim Sortieren hilfreich sein kann. In diesem Fall eignet sich der Algorithmus gut für die Parallelisierung, weil im ersten Schritt jeder Thread seinen getrennten Bereich sortiert und in den weiteren Schritten jeweils ein Thread die eigenen Daten mit denen eines anderen Threads zusammenfügt, während dieser andere Thread nur auf die Barriere wartet. Es gibt sicher noch bessere Verfahren, das zu parallelisieren, aber man sieht, dass es sich lohnt, wenn man wirklich genug CPUs zur Verfügung hat.

Share Button

Threads oder Prozesse

Zur Parallelisierung einer Software kann man auf Threads und Prozesse zugreifen. Es lohnt sich, diese beiden Ansätze etwas genauer anzuschauen, um die geeignete Wahl treffen zu können.

Warum Parallelisierung?

  • Mehr CPUs nutzen
  • Moore’s law: Anzahl der Transistoren in IC verdoppelt sich ca. alle 2 Jahre.
  • Bis vor ca. 10 Jahren verdoppelte sich die CPU-Leistung auch regelmäßig.
  • Seit ca. 10 Jahren nur noch mehr Cores
  • Nur nutzbar durch Parallelisierung
  • Parallelisierung kann aber auch Dinge vereinfachen.
  • Beispiel Pipes:
cat `find /usr/bin/* -type d -prune -o -type f -print` \
| perl -p -e 's/sch/\\v s/g;s/\r/\n/g;' | strings \
| sort > /tmp/out.log &
  • Startet pro Pipe-Komponente einen Prozess, viel flexibler und meist perfomanter als wenn man Zwischenergebnisse in Dateien zwischenspeichern muss.
  • Integration verschiedener Software-Komponenten.
  • Typische Beispiele:
    • Datenbank
    • Messaging-System
    • SAP
    • Heterogene Software (mehrere Programmiersprachen…)

Probleme bei Parallelisierung

Unabhängig von der verwendeten Technologie muss man sich mit u.a. diesen Problemen auseinandersetzen:

  • Deadlocks (Verklemmung)
  • Fehler bei gleichzeitigem Ressourcenzugriff
  • Overhead der Parallelisierung
  • Erschwerte Fehlersuche

Deadlocks

Beispiel für Deadlock:

  • Zwei parallel laufende Programmteile A und B greifen exklusiv auf zwei Ressourcen X und Y zu.
  • A reserviert sich erst X und dann Y, B reserviert sich erst Y und dann X.
  • Bei ungünstigem Verlauf wartet A endlos auf Y und B endlos auf X.

Fehler bei gleichzeitigem Ressourcenzugriff

  • Beispiel Datenstruktur wird von Programmteil A und Programmteil B gleichzeitig verwendet.
  • Wenn beide Zugriffe nur lesend sind, ist das ok.
  • Wenn einer schreibt, kann es Inkonsistenzen geben, wegen Pointern sogar Programmabstürze, merkwürdige Fehler u.s.w.
  • Schwierig zu finden
  • Tritt oft erst auf dem Produktivsystem auf, beim Testen scheint alles gut zu sein.

Overhead

Wenn man Software parallelisiert muss man zusätzlich Dinge tun, die man sonst nicht braucht:

  • Locking
  • Kommunikation
  • Synchronisation
  • Memory
  • Mehr Entwicklungsaufwand

Das kann sich aber lohnen.
Besser frühzeitig daran denken!!!

Wie zähmt man die Parallelisierung?

  • In Applikationsentwicklung mit geeigneten Werkzeugen, Frameworks,…
  • In der Praxis viele Probleme und oft wenig Gewinn
  • Aber es gibt Wege die funktionieren..
  • Traum: Compiler parallelisiert automatisch
  • Aber für Systemprogrammierung explizite Kontrolle wichtig!

Threads oder Prozesse

Threads oder Prozesse???

Man kann für die Parallelisierung drei Wege gehen (oder Kombinationen daraus):

  • Prozesse
  • Threads auf OS-level
  • Eigener Mechanismus (User Threads)

Prozesse

  • Prozesse haben ihren eigenen Speicherbereich
  • Können auf verschiedenen Rechnern laufen
  • Explizite Kommunikation
  • Mit shared memory kann man auch gemeinsamen Speicher nutzen
  • Mehr Overhead als Threads

Threads

  • Threads laufen auf derselben Maschine
  • Teilen sich dasselbe Memory
  • Trennung muss man explizit erzwingen

Funktionsweise Prozess (POSIX)

  • Ein neuer Prozess wird mit fork() erzeugt
  • Dupliziert den ganzen Speicher
  • Effizient wegen copy-on-write
  • Achtung: overcommit
  • Danach (meistens) exec

Unter MS-Windows wird das Erzeugen eines neuen Prozesses und das Starten eines neuen Programms gleichzeitig in einem Schritt ausgeführt.

IPC

Interprozesskommunikation:

  • Signale
  • Pipe (named oder anonym)
  • Semaphore (Locks)
  • Shared Memory
  • Socket
  • Message Queue
  • File
  • Memory-mapped File
  • High-Level-Mechanismen (DB, Messaging, Corba, Rest, Soap, RPC,…)

Threads (Posix)

  • Mit pthread_create(…) erzeugen
  • Mit pthread_join(…) “einsammeln”
  • Funktion void *f(void *) übergeben
  • In C++ 11 in die Sprache integriert

Was soll man bevorzugen

Es hängt von der Ausgangslage ab.

Entwickelt man mit Ruby oder Perl, sind vielleicht mehrere Prozesse besser, weil Threads in diesen Sprachen nicht so gut unterstützt werden. Entwickelt man mit Scala oder Java, sind Threads vielleicht besser, weil das dort das gängige und gut unterstützte Parallelisierungsverfahren ist und weil JVM-Prozesse jeweils recht schwergewichtig sind, was den Speicherverbrauch betrifft.

Entwickelt man in C oder C++ und hat mehr oder weniger alle Möglichkeiten des Betriebssystems zur Verfügung, dann sind beide Wege gut gangbar. Man kann mit Shared Memory und anderen IPC-Mechanismen mehrere Prozesse zusammenspannen, aber auch mehrere Threads. Man muss sich in jedem Fall darum kümmern, dass gemeinsam genutzte Ressourcen konsistent bleiben und insbesondere nicht in inkonsistentem Zustand gelesen werden.

Man sollte beide Möglichkeiten kennen und im Einzelfall entscheiden, welcher Weg sich am besten eignet.

Share Button

Java 8

Java 8 ist erschienen.
Das bedeutendste neue Feature sind die Lambda-Expressions, die es unter anderem erleichtern, funktional zu programmieren.

Share Button

Mathematical Formulas in WordPress

Deutsch

This blog uses the Plugin WP QuickLaTeX which gets its \LaTeX-rendering done by QuickLaTeX.

If only a page starts with [{\sf latexpage}], formulas can be embedded with \backslash(\ldots\backslash) or \backslash[\ldots\backslash]. They have to be written in LaTeX-notation.

So this blog can use formulas like for example:

    \[ \bigwedge_{z\in\Bbb C}\, \sin z = \sum_{k=0}^\infty \frac{(-1)^k z^{2k+1}}{(2k+1)!}=z-\frac{z^3}{6}+\frac{z^5}{120}-\frac{z^7}{5040}+\ldots \]

    \[ \bigwedge_{z\in\Bbb C}\, \cos z = \sum_{k=0}^\infty {\frac{(-1)^k z^{2k}}{(2k)!}}=1-\frac{z^2}{2}+\frac{z^4}{24}-\frac{z^6}{720}+\ldots \\ \]

    \[ {\bigwedge_\stackrel{z\in\Bbb C}{\cos z \ne 0}} \tan z = \frac{\sin z}{\cos z} \\ \]

    \[ {\bigwedge_\stackrel{z\in\Bbb C}{\sin z \ne 0}} \cot z = \frac{\cos z}{\sin z} \\ \]

    \[ {\bigwedge_\stackrel{z\in\Bbb C}{\cos z \ne 0}} \sec z = \frac{1}{\cos z} \\ \]

    \[ {\bigwedge_\stackrel{z\in\Bbb C}{\sin z \ne 0}} \csc z = \frac{1}{\sin z} \\ \end{align} \]

    \[ \sec(z) = 4\pi \, \sum_{k=0}^{\infty} \frac{(-1)^k(2k+1)} {(2k+1)^2 \pi^2 - 4 z^2 } \]

    \[ \csc(z) = \frac{1}{z} - 2z \, \sum_{k=1}^{\infty}\frac{(-1)^k} {k^2\pi^2-z^2} = \sum_{k=-\infty}^\infty \frac{(-1)^k \, z}{z^2-k^2\pi^2} \]

So I am making use of this, whenever it seems to make sense, so it can be avoided to write mathematical formulas in some unintelligable ASCII-text.

Why don’t we have that in the development environments of modern programming languages? If a formula is given, it could be written in a much nicer way, at least in the comments. I understand that Donald E. Knuth has introduced the concept of literate programming many decades ago. The source file is a .web, .cweb or .fweb file from which the illiterate source and the TeX-documentation can be produced using weave and tangle or cweave and ctangle or fweave and ftangle. This allows for excellent readable printouts and compilable programs from the common (literate) source file. A little bit of this idea has gone into the idea of javadoc and rubydoc and perldoc, but a conveniant and powerful mechanism for mathematical formulas would still be appreciated.

Share Button