Na ja, einschalten würde helfen.
Dann kann ich natürlich so laut drehen, wie ich nur gerade will.
So, also, eine Hilfestellung zu den Turfsmustern.
Das finde ich eine tolle Chance für Sie.
Und wir machen jetzt weiter mit der Implementierung.
Und zwar waren wir letztes Mal stehen geblieben bei der Paralysierung.
Das letzte war also die Matrizenvektormultiplikation.
Und wir haben da eine Technik angewandt, die nennt man
Gebietsverteilung, Gebietszerlegung.
Das heißt, Sie haben eine Datenstruktur, in diesem Fall eine Matrize.
Und um sie zu paralysieren, sagen wir, mit vier oder acht Prozessoren,
ist es meist so, dass wir Matrizen haben mit wesentlich mehr Zeilen.
Haben wir gesagt, wir teilen die Matrize auf in Abschnitte von Zeilen,
die gerade so lang sind, dass N durch 8 Zeilen drin vorkommen, wobei N
eben die Anzahl der Zeilen ist.
Und wie gesagt, man kann sich diese Matrize als ein Gebiet vorstellen,
das man zerlegt und die einzelnen Teile unabhängig bearbeitet.
Das ist eines der möglichen Muster.
Ein anderes Muster haben wir ja schon gesehen.
Das war das Produzer-Consumer-Muster, Erzeuger-Verbraucher-Muster.
Dann hatten wir schon den Auftraggeber-Auftragnehmer gesehen, wo wir
Aufgaben verteilen und das Fließband.
Das Fließband werden wir als nächstes anschauen, als Beispiel.
Jetzt kommt allerdings erst noch...
Achso, ja, das ist ein Beispiel, wo man sehen kann, wie die
Prozessoren ausgelastet werden.
Wenn Sie also so eine Vektor-Matrizen-Multiplikation starten mit vier
Prozessoren, können Sie sich das anzeigen lassen.
Und dann sieht man tatsächlich, dass hier die Auslastung der einzelnen
Prozessoren nach oben springt, in diesem Fall auf 100%.
Das untere ist weniger wichtig.
Das sieht auf jedem Rechner-Typ ein bisschen anders aus.
Aber auf Apple ist das Beispiel in der Konsole.
Da können Sie sich anzeigen lassen, was die einzelnen Prozessoren
machen und dann beobachten, ob auch wirklich was passiert.
So, als nächstes käme die Matrizen-Matrizen-Multiplikation.
Die ist natürlich überhaupt nicht schwierig für uns.
Warum nicht?
Das ist nichts anderes als die Vektor-Matrizen-Multiplikation
wiederholt.
Für alle Spalten der zweiten Matrize.
Also es ist nicht schwierig, es gibt allerdings unterschiedliche
Algorithmen, um die Arbeiten unterschiedlich aufzuteilen.
Das ist etwas, das Sie lesen dürfen.
Das Selbststudium mit einem Beispiel, wie lange es geht.
Hier kommt noch ein weiteres Beispiel, die numerische Integration.
Das ist aber auch eine Technik, die wir schon kennen.
Da machen wir im Wesentlichen auch eine Gebietszerlegung.
Und was wir jetzt als wichtiges noch machen müssen, das ist alles
durchprogrammiert.
Was noch wichtig ist, sind Maßzahlen für parallele Algorithmen.
Wie gut ist denn meine Parallelisierung?
Sie ist natürlich nicht gut, wenn sie langsamer läuft als die
sequenzielle Variante.
Dann haben wir irgendwo einen Fehler gemacht.
Und da gibt es zwei Maßzahlen, das eine ist die Beschleunigung.
Die Beschleunigung, das muss man sich dummerweise einfach merken, ich
habe auch eine Weile gebraucht, aber das ist der Bruch von der Zeit,
die der Einprozessor-Lösung braucht, deswegen die 1, dividiert durch
die Zeit, die die P-Prozessor-Lösung braucht.
Also sagen wir mal, ich habe etwas, das läuft 10 Sekunden.
Ich nehme 10 Prozessoren her und erreiche es, dass ich dann das
Problemstart in 10 Sekunden in einer Sekunde löse.
Dann ist die Beschleunigung 10 durch 1 oder 10-fach.
10 mal so schnell, oder anders ausgedrückt, ein Zehntel der Zeit, die
die Parallellösung braucht.
Wie soll ich mir das merken?
Sie müssen sich merken, dass Sie eigentlich das Gewunsch haben, immer
die Beschleunigung, eine Zahl ist die größere als 1, also gehört die
größere Zahl in den Zähler und die kleinere in den Nenner.
Die größere Zahl ist natürlich T1, T von 1.
Diese Zahl Beschleunigung ist in der Regel so, dass sie kleiner ist
als die Anzahl der Prozessoren.
Im Idealfall ist es so, dass die Beschleunigung genauso groß ist wie
P. Aber meistens schafft man das nicht, weil es Verlangsamungen gibt,
dadurch dass man parallel arbeitet und sich abstimmen muss,
insbesondere wenn es irgendwo Möglichkeiten für Wettläufe gibt und
damit Monitore benutzt werden müssen.
Die erzeugen einen bestimmten Zusatzaufwand, der relativ hoch sein
kann, für sehr feingranulare Arbeiten.
Dadurch ist die Beschleunigung von P meistens deutlich geringer als P.
Aber sie sollte nicht geringer als 1 sein.
Und jetzt sagt man noch folgendes...
Achso, ja, ich kann das natürlich, diese Beschleunigungszahl, kann ich
jetzt auf ein konkretes Programm anwenden, 10 zu 1 oder so etwas.
Ich kann es auch im O-Kalkül benutzen.
Also sagen wir, Sie hätten eine Sortierfunktion, die im sequentiellen
Fall O von N log N erfordern würde.
Also O von N von log N.
Das würde die Haltensortierung garantieren, QuickSort ja nicht, denn
das QuickSort variiert zwischen N² und N log N.
Aber nehmen wir an, wir hätten hier also im Zähler N log N stehen.
Und dann erfinden Sie einen parallelen Algorithmus, der läuft in
Zeitlog N.
Und Sie nehmen den her und dividieren durch N log N durch Log N.
Und dann kommt natürlich N heraus.
Dann hätten Sie eine einfache Beschleunigung.
Dabei ist dann bei der theoretischen Überlegung, betrachtet man
meistens nicht so sehr, ja gut, in diesem Fall würde man wohl N
Prozessoren einsetzen, Zeitlog N erreicht, falls es die Beschleunigung
N -fach.
Was ein sehr gutes Ergebnis wäre wieder.
Die Zahl, die man noch benutzt, ist die Effizienz.
Die Effizienz versteht man am besten so, dass man sagt, man nimmt die
Beschleunigung und teilt sie durch P. Ich sagte Ihnen gerade vorhin,
dass die Beschleunigung maximal P ist.
Die maximale Beschleunigung ist P. Jetzt normieren wir das durch das
Maximum.
Wir rechnen also SP durch P. Wir bekommen dadurch eine Zahl, die ist 1
oder kleiner.
Sie ist 0 oder 1.
Und das nennt man die Effizienz.
Die Effizienzzahl sagt Ihnen, wie viel Prozent gewissermaßen von den
gesamten vorhandenen Ressourcen, den Prozessorressourcen, die in dem
Rechner eingesetzt werden, werden tatsächlich sinnvoll genutzt.
Wenn ich wieder bei P Prozessoren eine Beschleunigung von P habe,
dividiert durch P, kriege ich natürlich 1.
Das ist perfekt.
Wenn ich aber jetzt zum Beispiel eben nicht eine so perfekte
Beschleunigung bekommen hätte, die also etwas weniger ist als P,
bekomme ich natürlich eine Zahl, die ist unter 1.
Die Effizienz liegt zwischen 0 und 1.
Das ist der übliche Effizienzbegriff, dass man mit dem Maximum
normiert und damit eine Zahl bekommt, die im Bereich von 0 bis 1 ist.
Je näher die Effizienz natürlich an der 1 liegt, desto besser haben
Sie Ihre Ressourcen ausgenutzt.
Das können Sie natürlich auch einsetzen, die 1 durch P und dann noch
das P dazu.
Das wären also die Bewertungsmaßzahlen.
Das kann gut sein, dass wir so etwas fragen.
Was ist Beschleunigung?
Rechnen Sie die Beschleunigung aus?
Das kann dann schon passieren.
Und jetzt kommt noch eine andere Überlegung, die sagt, könnte ich denn
von vornherein bestimmen, wie viel Beschleunigung ich überhaupt
schaffen kann?
Sie sagt ja, idealerweise ist es P, aber es gibt Situationen, wo das
nicht erreichbar ist.
Gibt es da eine Berechnung, die mir die Grenze sagen würde?
Den nehme ich dafür.
Und wir machen das folgendermaßen.
Wir sagen, also eine ganz grobe Abschätzung sagen wir, wir haben ein
paralleles Programm, da gibt es sequenzielle Anteile, die sich nicht
beschleunigen lassen.
Das kann ein Block sein am Anfang zur Initialisierung zum Beispiel
oder ein Block am Schluss zur Ausgabe.
Und das lässt sich nicht weiter parallelisieren, nehmen wir an.
Davor gibt es aber andere Teile in meinem Code, die ich
parallelisieren kann.
Dann ist es klar, dass die sequenzielle Laufzeit, wir sagen Sigma ist
die Zeit für den sequenziellen Teil und Pi ist die Anzahl für die
sequenzielle Ausführung des parallelisierbaren Anteils.
Dann ist die sequenzielle Laufzeit einfach die Summe von Sigma und Pi.
Soweit so gut.
Und die parallele Laufzeit bei Pi Prozessoren ist Sigma plus Pi
dividiert durch die Anzahl der Prozessoren.
Unter der Annahme wieder, dass wir perfekt parallelisieren können.
Besser geht es nicht.
Unter der Annahme wiederum, dass Sigma sich nicht parallelisieren
lässt.
Und dann kann man sich überlegen, welche Beschleunigung kann ich denn
da erreichen.
Aber erst noch ein Bild zur Illustration.
Hier ist ein Programm, das besteht aus 5 Blöcken.
Jeder Block dauert 100 Sekunden.
Dann haben wir eine sequenzielle Ausführungszeit von 500 und wenn wir
parallel ausführen mit nur einem Prozessor, haben wir auch 500.
Hier wäre die Beschleunigung 1.
Das ist uninteressant.
Jetzt nehmen wir den Fall, dass wir die grünen Dinge parallelisieren
können.
Wir verwenden zwei Prozessoren und haben jetzt eine Zahl von 100 plus
50 plus 100 plus 50 plus 100 macht insgesamt 400.
Sequenziell ist immer noch 500.
500 durch 400 ist 1,25.
Hier haben wir schon den Fall, dass wir nicht 2 erreichen, sondern nur
1,25.
Oder noch extremer, wir sagen, angenommen dieser parallelisierbare
Teil lässt sich so stark parallelisieren, dass ich 1.000 Prozessoren
einsetzen kann oder noch mehr und dann ist das hier geteilt durch 1
.000 so klein, dass es nicht mehr messbar ist.
Also quasi gegen 0 geht.
Dann ist die Laufzeit dieses Programms 100 plus nichts plus 100 plus
nichts plus 100 also 300.
Beschleunigung ist jetzt 500 durch 300 oder 1,7 maximal.
Maximal 1,7.
Und da wollen wir hin.
Besser geht es nicht.
Ich habe also die Annahme gemacht, dass ich den parallelisierbaren
Teil perfekt parallelisieren kann, sodass ein Anteil verschwindet.
Und jetzt haben wir so eine Limits-Idee.
Und die kann man natürlich jetzt ausrechnen.
Und zwar ist die Formel dafür Sie wollen die Beschleunigung
ausrechnen.
Die ist T1 durch T von P. T1 ist natürlich Sigma plus P. TP ist Sigma
plus Pi dividiert durch P.
Jetzt schätzen wir einfach ab.
Wir lassen hier im Nenner diesen positiven Anteil weg.
Damit wird dieser Bruch höchstens größer.
Also da sagen wir, das Ding geht gegen 0.
Das ist aber im Nenner.
Das heißt, wenn wir hier noch Sigma plus P durch Sigma schreiben, dann
ist das der Limit.
So, das wandeln wir jetzt nochmal um, indem wir durch Sigma plus P
dividieren.
Und dann taucht diese Formel auf.
Was ist jetzt das Sigma dividiert durch Sigma plus P?
Sigma plus P ist die Gesamtlaufzeit sequentiell.
Und Sigma ist die Laufzeit des sequentiellen Anteils.
Sagen wir Sigma wie S.
Das heißt also, dieser Bruch hier ist der Anteil des sequentiellen
Teils.
Der sequentielle Anteil an der Laufzeit.
Und damit haben wir die maximale Beschleunigung gesagt.
Das ist 1 durch F.
Das ist das sogenannte Armtasche-Gesetz.
Dieses F ist gerade das Sigma durch Sigma plus P. Das ist der
sequentielle, nicht realisierbare Anteil.
Na wunderbar, sagen sie.
Und jetzt muss ich Ihnen ein Bild zeigen.
Das habe ich noch nicht in die Präsentation eingebaut.
Darum müssen wir kurz warten, bis ich da umschaue.
Hier ist ein Diagramm davon.
Das habe ich erst kürzlich entdeckt.
Das ist eine Illustration des Armtaschen-Gesetzes.
Wir schauen uns erst die blaue Kurve an.
Die blaue Kurve sagt, der parallele Anteil ist 50%.
Das heißt, der sequentielle Anteil ist auch 50%.
Was ist die maximale Beschleunigung, die ich bekomme?
Das wissen wir jetzt.
1 durch 0,5 ist 2.
Wir kommen nicht mehr über eine Anzahl von 2 in der Beschleunigung
heraus.
Egal wie viele Prozessoren wir benutzen.
Hier sind 65.000 ausgerechnet.
Das ist klar, wir haben extrem niedrige Effizienz.
Die Beschleunigung ist 2, dividiert durch 65.000.
Das ist lächerlich.
Nehmen wir eine andere Zahl.
Der parallele Abschnitt wäre 90% bzw.
der sequentielle Anteil wäre 10%.
1 durch 10% 1 durch 10% ist 10.
Das heißt, der maximale Speedup oder Beschleunigung ist 10.
Wenn wir nur einen 10%igen, nicht parallelisierbaren sequentiellen
Anteil haben, können wir nie eine Beschleunigung erreichen, die größer
als 10 ist.
Wenn wir es mit 95% parallelisieren, 5% ist nicht mehr
parallelisierbar, dann sind nur 5% nicht parallelisierbar.
Und das sehen Sie hier in dem Diagramm.
Das Beste, was wir bekommen, ist 20-fach.
Es hat also keinen Sinn, wesentlich mehr als um 64 Prozessoren zu
benutzen.
Wenn ich 64 Prozessoren benutze, habe ich nicht mal eine
Beschleunigung von 16.
Auch eine schlechte Effizienz, aber vielleicht gerade noch tragbar.
Also das wären 16 durch 64.
Das wäre ein Viertel.
0,25 ist die Effizienz.
Aber wichtig dabei am amtualschen Gesetz ist, es geht einfach nicht
schneller.
Wir können uns da so viele Prozessoren reinwerfen und so viele GPUs
kaufen, wie wir mögen.
Wenn wir einen sequentiellen Anteil haben, dann bildet der die Grenze.
Denn der sequentielle Anteil wird immer da sein.
Genau diese Zeit, die ins Verhältnis gesetzt wird, gibt uns diese
Beschleunigung.
Als nächstes...
Moment, ich muss meine Präsentation zurückschalten.
Da waren wir gerade stehen geblieben.
Das war das amtualsche Gesetz.
Gibt es dazu Fragen?
Beschleunigung als theoretisches Merkmal, Effizienz als theoretische
Zahl und das amtualsche Gesetz.
Das sagt uns etwas aus über die Präsierungsmöglichkeiten, die wir
haben.
Wie gut sie sind, wie effizient sie Ressourcen nutzen und was das
Maximum ist.
Wenn Sie keine Fragen haben, dann gehe ich zum nächsten.
Das nächste ist eine Fallstudie.
Das ist ein bisschen wie QUIC, aber doch ganz anders.
Was wir hier machen wollen, ist folgendes.
Wir wollen einen sogenannten invertierten Index bilden.
Sie nehmen also Ihren Rechner her und wollen einen invertierten Index
all Ihrer Dateien bilden.
Invertierter Index heißt, Sie können ein Wort angeben und dann fragen,
welche Dateien enthalten dieses Wort.
Also zum Beispiel, Sie wollen die Dateien finden, in denen das Wort
Tichy und Multicore vorkommt.
Ein invertierter Index, der ist ein bisschen gekürzt, der zeigt nicht
die ganzen Pfadesack.
Das Wort Multicore kommt in der Datei Multicore-Programmierung vor,
SC12, Kapitel 4.2.2, Parallel-Algorithmen, da kommt es vor.
Und mein Name kommt in diesen Dingen drin vor.
Und siehe da, da gibt es eine Datei, Multicore-Programmierung und
Multicore -Programmierung, die in diesen beiden vorkommt.
Ich bilde den Durchschnitt hier und stelle fest, diese beiden Wörter
befinden sich in dieser einen Datei.
Das macht also der invertierte Index.
Und was der invertierte Index ist, ist einfach folgendes, das sagt,
für jedes Wort, das irgendwo auf meinem ganzen Platte irgendwo
vorkommt, liste ich auf die Dateien, in denen dieses Wort mindestens
einmal vorkommt.
Kann natürlich auch mehrfach vorkommen.
Wie können wir das berechnen?
Wir wollen jetzt zunächst ein sequentielles Programm schreiben, das in
ihrem Dateiverzeichnis absteigt und durchsucht und so einen Index
aufbaut, sodass sie nachher mit diesem Index schnell suchen können.
Also die sogenannte Desktop-Suche geht zum Beispiel so.
Sie braucht so einen invertierten Index oder zum Worteingeben irgendwo
ein Suchfenster und finden sie Dateien, die das Ding enthalten.
Okay.
Wie geht das jetzt?
Wir machen das folgendermaßen.
Wir müssen erstmal die Dateinamen finden.
Das heißt, wir müssen bei einem bestimmten Startpunkt der Wurzel eines
Dateibaums oder der Wurzel eines anderen Sub-Baums absteigen, den Baum
rekursiv durchwandern bis zu der vorhandenen maximalen Tiefe und für
jedes dieser Dinge den Dateinamen ausspucken, einstens des Pfades,
damit wir dann diese Datei öffnen.
Wir können jetzt zum Beispiel die Dateinamen alle auf einmal erzeugen,
wieder wo abspeichern und dann dem Analyseprogramm geben oder wir
können sie nach und nach erzeugen und gleich die Analyse machen.
Wir werden sehen, was wir davon nehmen.
Das Nächste ist, wenn wir Dateinamen haben, dann können wir die Datei
öffnen und die Terme extrahieren.
Also die Wörter.
Dann müssen wir den Index aktualisieren, das heißt für jeden Term
nehmen wir jetzt das Paar aus diesem Term und den Dateinamen und fügen
es in den Index ein.
Der Index ist jetzt wieder eine Datenstruktur, die ich hoffentlich
auch schnell durchsuchen kann, aber die ist indiziert nach Namen.
Also eine Abbildung, ein Map von Wort auf Datein.
Für jedes Wort führt dieser Index eine Liste von Dateinamen.
Das kann ich jetzt eben abspeichern machen, den Index aktualisieren
und der letzte Schritt wäre dann auch noch diese Indexdatei
rauszuschreiben, wenn ich das machen will, um sie später wiederholt zu
benutzen.
Und da fragt man sich jetzt natürlich, welche dieser Schritte soll ich
jetzt eigentlich paralysieren und welches Muster für die Verarbeitung
sollte ich bei der Paralysierung benutzen und schließlich lohnt es
sich überhaupt.
Hier ist ein spezielles Problem vorhanden, nämlich ich habe ein
Plattenlaufwerk, das schon mal mit dem Prozessor verglichen langsam
ist und das wird jetzt richtig ordentlich in die Pflicht genommen,
denn ich habe möglicherweise ein Parallelsprogramm, das durch den
Dateinamen sich durchwühlt parallel schon ein anderer Prozess liest
die Dateien auch und da können wir jetzt tausende von Prozessoren
draufwerken, habe aber nur ein Plattenlaufwerk.
Das heißt also, die eine Ausgabe lässt sich nicht mehr paralysieren,
denn dieses Gerät ist sequenziell.
Das ist möglicherweise der Flaschenhals.
Nur wenn die Platte im Vergleich zu den anderen Arbeitsschritten, die
wir machen müssen, noch Zeit übrig hat, leer läuft, hat diese
Parallelisierung überhaupt einen Sinn.
Und das müssen wir uns anschauen, was dieses Verarbeitungsmuster
betrifft.
So bietet sich hier sofort ein Fließband an.
Also hier Producer-Consumer, hier Producer-Consumer und nochmal
Producer -Consumer.
Drei Stück davon von solchen Paaren mit Puffern dazwischen und da
nehmen wir einen Parallelprozess oder einen Faden, der erzeugt
Dateinamen, steckt sie in den Puffer, sodass der Term-Extraktor, wenn
er dann soweit ist, die Dateien nach und nach öffnet und dann den
Index, natürlich die Terme ausliest, in den Index schreibt und den
können wir vielleicht auch paralysieren, und dann das Index-Datei
schreiben.
Da haben wir einen sequentiellen Fall, den können wir nicht
beschleunigen.
Ich muss das Datei sequentiell schreiben.
Die Platte bearbeitet nur einen Auftrag, einen Schreibauftrag auf
einmal.
Interessant, das wird uns natürlich möglicherweise alles verlangsamen.
Wir werden dann sehen, dass wir das mal weglassen und dass wir genauer
sehen, was hier drin passieren kann.
So, was war jetzt der erste Schritt, der durchzuführen ist?
Der erste Schritt ist durchzuführen und sagen, von was reden wir jetzt
eigentlich?
Wie schnell ist denn das, oder wie langsam ist denn das sequentielle
Fall?
Was wir dann gemacht haben, ist, wir haben mit Testfallmengen 50.000
Dateien erzeugt.
Das waren also fast ein Gigabyte reine Textdateien, das ist gar nicht
mal so viel.
Und wir haben erstmal nur reine Textdateien benutzt, also kein PDF,
kein Docx, kein Excel, kein dies und das, keine XML-Dateien, also
einfach nur Textdateien, weil wir wollten ja erstmal mal hier nicht
viel Zeit verbringen, ein PDF-Format auch noch auseinandernehmen zu
können und daraus die Wörter zu extrahieren.
Dann einen sequentiellen Indizierer gebaut und auf der Zielplattform
vermessen, das war jetzt eine Vierkernplattform, aber natürlich hat
man im sequentiellen Fall nur einen Kern benutzt.
So, das geht also so.
Die Dateinamen-Erzeugung für diese 50.000 Dateien dauert 5 Sekunden.
Das reine Lesen der Dateien, Zeichen für Zeichen, einfach nur die
Dateien aufmachen, durchlesen, nichts damit machen und wieder
schließen.
Das dauert insgesamt 77 Sekunden.
Wenn wir jetzt noch zusätzlich die Terme extrahieren, also bestimmen,
wo die Wortgrenzen sind.
In diesem Fall, im ersten Fall, haben wir nur die Datei Zeichen für
Zeichen gelesen.
Wenn wir jetzt auch noch die Wortextraktion mitschalten, das heißt
also die Sonderzeichen und Zwischenräume und so weiter finden, sodass
wir die Worte portionieren können, dann dauert es 11 Sekunden länger,
also 88 Sekunden.
Und die Index-Aktualisierung, noch nicht das Schreiben, das lassen wir
gleich mal weg, der Einfachkeit halber, Index-Aktualisierung im
Hauptspeicher dauert 22 Sekunden.
Na ja, jetzt können wir sagen, da wird sich wohl das nicht so sehr
rentieren, hier dran zu schrauben, denn das ist der kleinste Anteil.
Wir qualisieren natürlich den größten Anteil und der ist dann 88
Sekunden.
Wenn wir den auf ein Viertel herunter reduzieren, das wäre also 22
Sekunden, so schnell geht das und der ist dann genauso schnell wie die
Index -Aktualisierung.
Da brauchen wir die Index-Aktualisierung auch nicht mehr schneller
machen und das hier auch nicht, zunächst mal.
Außerdem können Sie von den Zahlen ablesen, dass die Platte noch nicht
völlig ausgelastet ist.
Woran erkennen Sie das?
Wie müssten die Zahlen aussehen, wenn die Platte schon der
Flaschenhals wäre?
Irgendeine Idee?
Die Antwort steht schon auf der Folie.
Sie müssen nur die Zahlen richtig interpretieren, da kommt keiner
drauf.
Wenn die Platte schon ausgereizt wäre in ihrer Leistung, dann würde
das zusätzliche Extrahieren der Therme keinen zusätzlichen Zeit
erfordern.
Wir lesen einen Block ein und analysieren den, das ist aber schneller
als das Einlesen, dann würde eben das zusätzliche Analysieren keine
Verlangsamung mehr erfordern, denn wir warten immer auf die Platte,
dass die uns Daten liefert.
Die liefert uns die Daten viel zu lange, wir rutschen da einfach durch
und rechnen alles, was zu rechnen ist, was ja nicht viel ist.
Hier besteht noch eine Chance, aber sie ist nicht furchtbar groß.
Wir können aus dieser Platte wahrscheinlich nicht mehr besonders viel
herausholen.
Das kann man jetzt auch noch ausrechnen, wenn man will, im besten
Fall, aber wir probieren es jetzt erstmal.
Der erste Parallelisierungsversuch.
Wir haben einen Faden, der macht die Dateinamenerzeugung, wir nehmen
gleich drei Thermextraktoren her, das parametrisieren wir so, dass wir
die Thermextraktoren von 1 bis was weiß ich, beliebige Zahl variieren
können, automatisch beim Erzeugen.
Die sind alle mit einem eigenen Faden versehen, laufen also auch
parallel zu dem hier.
Dann gibt es den Indexaufbau, den haben wir ja gesagt, brauchen wir
nicht parallelisieren, weil der ist schon von vornherein eh mehr
genug.
Und dann setzen wir da Puffer dazwischen.
Das ist jetzt die bekannte Fließband-Pipeline-Architektur.
Hier haben wir Puffer.
Und das ist jetzt wieder wichtig, wenn ein Fließband zu langsam ist,
dann sucht man die langsamste Stufe, denn die bestimmt die
Geschwindigkeit der Verarbeitung und wir replizieren die einzelnen
Stufen.
Hier muss sich gar kein besonderes Parallelisierungsprogramm erzeugen.
Ich muss nur das Programm, das die Thermextraktion macht,
dreimal, viermal, fünfmal initialisieren und laufen lassen.
Die Thermextraktoren holen sich auf dem Puffer die nächsten
Dateinamen.
Wir wissen, wie das geht.
Da müssen sie mit einem Wait nachfragen, ob der Puffer voll ist oder
leer ist.
Dann den Namen extrahieren.
Zuvor natürlich den Monitor betreten, den Dateinamen extrahieren und
ein NotifyAll schicken, falls der Puffer voll ist, dass der Dateinamen
wieder anlaufen kann.
Insgesamt haben wir also fünf Fäden laufen und jetzt kommt die
Überraschung.
Man lässt es laufen und es ist zehnmal langsamer.
Langsamer und nicht bloß ein bisschen, sondern mit dem gleichen Faktor
zehn.
Eine Größenordnung langsamer als die sequenzielle Version.
Dann ist man erstmal geknickt als Parallelisierer und jetzt dürfen Sie
raten, warum das so langsam ist.
Vielleicht liegt es an der Technik der Festplatte.
Der Vorschlag des Kollegen war, vielleicht liegt es an der Platte,
weil die Platte jetzt, in meinen Worten, unregelmäßig zugegriffen
wird.
Im sequenziellen Fall würde man zum Beispiel eine Datei komplett
durchlesen, dann käme die nächste dran.
Im Parallelfall lese ich ein Stück aus der Datei, dann kommt der
andere Faden und lese ein Stück aus der anderen Datei, positioniert
also den Kopf permanent herum.
Das kann zu einer Verlangsamung beitragen.
Es kann sein, dass der Arbeitsspeicher nicht ausreicht.
Da waren wir schlau genug, das gleich zu machen.
Sie sehen, die Datenmenge ist gar nicht mehr so groß.
Aber es ist ein wichtiger Punkt.
Sobald der Hauptspeicher nicht mehr reicht, muss ich auf die Platte
auslagern und einlagern und hin und her senden.
Das kann natürlich auch zu einer extremen Verlangsamung führen, war
aber hier nicht das Problem.
Das Problem ist der Monitor.
Der Monitor für diese beiden Puffer.
Da hängen alle.
Er erzeugt einen Dateinamen, will in den Puffer eingehen.
Was muss er machen?
Er muss in den Monitor eintreten, das ist eine extrem lange und
langsame Operation.
Er muss sehen, ob der Puffer noch Platz hat.
Wenn ja, ablegen, dann notify all schicken und dann den
synchronisierten Block verlassen.
Die Time Extractoren machen das gleiche.
Das heißt also, die synchronisieren sich schon hier an diesem Puffer.
Einer nach dem anderen.
Wenn sie besonders schnell sind.
Das Problem ist einfach, dass die Datenübergabe in diesem Falle über
diesen Monitor zu viel Zeit kostet.
Verglichen mit der Arbeit, die zu leisten ist pro Monitoreintritt.
Hier dann übrigens genauso.
Wie kriege ich das los?
Jeden Faden die eigenen Dateien liefern.
Wir haben hier keinen separaten Faden mehr.
Wir haben einfach einen Vorlauf.
Gewissermaßen einen sequenziellen Schritt.
Der geht die Dateien durch.
Ist ja nur 5 Sekunden verglichen mit dem Rest.
Und er spuckt die Dateienamen jetzt ohne Synchronisation weil diese
Time Extractoren noch gar nicht laufen.
Ohne Synchronisation hier in diese Puffer rein.
Im Umfallverfahren.
Erster Name hier, zweiter Name hier, dritter Name hier.
Und so weiter und so weiter.
Er füllt also zirkulär diese Puffer ein.
Mit all den Namen auf.
Damit haben wir, was Sie gesagt haben, jetzt hat jeder seinen eigenen
Vorrat an Namen und kann jetzt unabhängig davon arbeiten.
Jetzt starten wir die Time Extractoren.
4, 5, 6 muss man alles durchprobieren.
Und die schreiben jetzt wieder in diesen Puffer.
Das ist schon schneller.
Denn hier habe ich keine Synchronisation mehr.
Das spart mir sehr viel Zeit.
Aber es ist immer noch langsamer als die sequenzielle Version.
Und ich habe es Ihnen ja schon verraten.
Es liegt auch hier noch ein Problem vor.
Das Problem hier ist übrigens extrem feingranular.
Diese Termablage hier, hier in den Puffer, ist so, dass sie für jedes
Wort, das ein Term Extractor in seinem Text findet, hier in die
Synchronisation gehen müssen mit einem NotifyAll und einem Wait.
Eventuell mit einem Wait, nicht unbedingt.
Aber wie feingranular ist denn das?
Feingranular ist so, dass Sie sagen können, wenn Sie ein Wort von 10
Buchstaben auslesen wollen aus einer Datei, das sind pro Zeichen
vielleicht 5 Instruktionen.
Sie müssen prüfen, ob eine Wortgrenze erreicht ist.
Wenn nicht, das Zeichen herausnehmen und wohin kopieren in ein
StringArray oder so etwas.
Da brauchen Sie nicht mehr als 5 pro Zeichen.
Insgesamt 50 Instruktionen brauchen Sie jetzt.
Und schon nach 50 Instruktionen müssen Sie wieder in den Monitor
reingehen, der Sie 500 Instruktionen mindestens kostet.
Zeitmäßig.
Auch schlecht.
Sie sehen schon, da kann man...
Das ist ja blöd, ich habe gerade erst die Batterie gewechselt.
Dann probieren Sie.
Dann kommt noch Folgendes vor.
Eine weitere Quelle der Infizienz sind Duplikate.
Nehmen wir an, wir lesen jetzt eine Datei und wir finden darin mehrere
Vorkommen des Wortes Multicore.
So wie wir das inzwischen gemacht haben, ist, dass ich jeweils das
Paar Multicore mit dem zugehörigen Dateinamen dem Indexaufbau
übergeben muss.
Der sagt natürlich, ich schaue mal, wo die Dateinamen sind.
Wenn ich den schon habe, dann schaue ich mir die Liste der Wörter, die
mit dem Dateinamen verknüpft sind.
Dann muss ich nachsehen, ob es da ein Duplikat gibt.
Das heißt also, ich kann zwar mit dem Dateinamen hier arbeiten und ein
Hashmap benutzen, was schnell ist, aber wenn ich dann den
entsprechenden Eintrag habe, dann muss ich trotzdem noch sequenziell
eine möglicherweise lange Liste von Wörtern durchgehen, um zu sagen,
das Wort ist aber schon als Duplikat vorhanden, ich muss es nicht
eintragen.
Also muss ich noch etwas machen, nämlich ich muss vermeiden, dass ich
dem Indexaufbau Duplikate gebe.
Denn dann muss er gar nicht noch Duplikaten prüfen.
Aber wie mache ich das?
Ich brauche jetzt auch wieder einen Termextraktor, der nicht jeden
Term mit dem zugehörigen Dateinamen für sich einsetzt, sondern der
erzeugt die Termliste für die gegebene Datei.
Und diese Dateinamen wird dem Indexerzeuger übergeben.
Auf einmal.
Also wenn ich da in so einem Dokument 10.000 Wörter habe, wollen wir
mal nicht zu hoch greifen, also vielleicht 1.000, dann muss ich ihm 1
.000 Wörter auf einmal übergeben.
Und ich lasse schon vom Termextraktor die Duplikate eliminieren.
Das mache ich dann natürlich auch wieder lokal mit einem HashMap.
Das sieht also jetzt so aus.
Ich nehme also mehrere Termextraktoren.
Das hier ist der sequenzielle Anteil, mit dem kann ich nichts machen.
Termextraktoren arbeiten parallel, legen aber jetzt in dem Puffer
nicht einzelne Paare ab, sondern den ganzen Wortlisten ab mit dem
zugehörigen Dateinamen.
Und den Indexaufbau mache ich jetzt auch noch parallel, denn jetzt
kommen wir an die Grenze.
Der ist auch noch ein bisschen zu langsam, also nehme ich 4
Indexaufbauer hier.
Die bauen ihren eigenen Index auf.
Ich könnte, wenn ich wollte, sogar eine 1 zu 1 Organisation wählen.
Das haben wir jetzt noch nicht mehr durchprobiert.
Also auch diesen Puffer komplett loswerden und 3 Termextraktoren und 3
Indexaufbauer zu haben.
Das ist nur dann natürlich nützlich, wenn man damit noch ein bisschen
Zeit sparen kann.
Aber jetzt lassen wir das mal so, wie es ist.
Dieser Puffer ist jetzt schon unproblematisch geworden, weil wir den
ganzen Wortlisten übergeben anstelle einzelner Wörter.
Und dann, wenn ich 4 verschiedene Indexaufbauer habe, dann muss ich
natürlich sie irgendwie vereinigen.
Das heißt, einen Index davon erzeugen.
Das geht über einen Reduktionsaufbau.
Dann nehme ich diesen Index her und baue ihn und schiebe den Index,
den zweiten, in den ersten rein.
Dann habe ich schon für beide.
Und dann behandle ich die beiden genauso gleichzeitig.
Also diese zwei vereinen, diese zwei vereinen.
Geht parallel.
Und dann die Paare noch mal ein letztes Mal vereinigen.
Das wäre so ein Reduktionsbau mit nur zwei Stufen.
Auch das lassen wir jetzt weg.
Ich muss das jetzt noch ein bisschen einfacher halten.
Termliste pro Datei optional.
Den Vereiniger lassen wir auch weg.
Denn, wenn ich schon nicht aus in die auf die Dateien rausschreibe den
Index, reicht es ja auch mit vier Indizes abzufragen.
Wenn sie nach dem Wort Multicore suchen, dann frage ich eben alle vier
ab.
Es kann natürlich sein, dass Multicore in mehreren dieser Indexe
vorkommt und das muss das Ergebnis dann wieder vereinigen.
Aber das kann ich dann ja auch parallel machen.
Ich habe ja vier Prozessoren.
Wenn ich anfrage, schicke ich halt vier Anfragen auf gleichzeitig.
Muss gar nicht vereinfachen.
Okay, gut.
Aber jetzt ist die Frage, wie viele Termextraktoren und wie viele
Indexaufbaufäden brauche ich denn eigentlich?
Es ist auch nicht einfach zu lösen, diese Aufgabe.
Diese Aufgabe ist so, dass es abhängig ist von der Plattform, von der
Anzahl Prozessoren, die man hat, von der Größe des Hauptspeichers, von
der Schnelligkeit der lokalen Platte, ob es vielleicht zwei
Plattenlaufwerke gibt und so weiter.
Das können Sie alles nicht ein für allemal festlegen.
Hier ist so ein Beispiel, was wir herausgefunden haben.
Wenn wir ein Rechen mit vier Kernen benutzen, einen
Dateinamenerzeuger, drei Termextraktoren und zwei Indexaktualisierer
und keine Verschmelzung, dann erreichen wir eine Beschleunigung von 4
,7, also fast 5.
Das ist schon nicht schlecht.
Und das sind die entsprechenden Zahlen, die wir brauchen.
Beim 8-Kerner, andere Maschine, brauchen wir 6 Termextraktoren, 2
Indexaktualisierer und bekommen nur eine Beschleunigung von 2.
Und hier bei den dritten 32-Kerner, 9 Termextraktoren, 4
Indexaktualisierer und kriegen trotzdem nur eine Beschleunigung von 3
,5.
Also hier sieht man ganz deutlich, dass irgendwann mal die Platte halt
doch zum Flaschenhals wird.
Egal wie viele Prozessoren ich auf das Ding werfe, schneller geht es
halt nicht.
So, das war also ein etwas längeres Beispiel.
Was haben wir jetzt davon gelernt?
Nummer 1, ein neues Parallelisierungsverfahren, nämlich die Pipeline.
Dann haben wir gelernt, dass wir Stufen in so einem Fließband, in
einem Pipeline replizieren können, damit sie gleichzeitig laufen
können, wenn sie eine langsame Stufe haben.
Das langsamste Glied der Kette bestimmt die Laufzeit.
Also beschleunigen wir die einzelnen Stufen.
Drittens, dass wir einen Vergleich mit der sequentiellen Version
brauchen.
Nummer 3, damit wir überhaupt vergleichen können.
Nummer 4 war, Synchronisierung kann teuer sein, also kann ich die
nicht auf einer sehr feingranularen Aktionsebene durchführen, sondern
muss dafür sorgen, dass ich größere Brocken auf einmal bearbeiten
kann.
Das hat man dann gesehen bei der einen Fall, wo wir gesagt haben, wir
liefern jetzt Wortlisten anstelle einzelner Wörter.
Also einen größeren Brocken.
Und im anderen Fall, im allerersten Fall haben wir gesagt, können wir
den Puffer überhaupt loswerden, indem wir die Arbeit geschickt im
Vorab schon verteilen.
Das ist das, was wir gelernt haben.
Und das Letzte ist, dass die Anzahl der Prozessoren, die man einsetzt,
nicht automatisch richtig ist, sondern dass man nach der richtigen
Arbeitspunkt suchen muss.
Da gibt es ein Verfahren, das hatte ich hier irgendwo vorher schon
erwähnt.
Da gibt es ein Verfahren, das heißt Auto-Tuning oder automatisches
Tunen, um diese Punkte zu finden.
Da gibt es also eine Technik, die wir auch mit erfunden haben, der man
diese Parameter gibt, die Anzahl von einzelnen Fäden, die einstellbar
sind und dann den Auto-Tuner einfach alles durchprobieren lässt, wie
gesagt, die und die Kombination ist auf dem Rechner die Beste.
Aber das müssen wir jetzt nicht weiter bearbeiten.
Gibt es zu diesem Beispiel noch Fragen?
Gibt es zu diesem Thema noch mehr zu lernen?
Ja, gibt es.
Also wir haben gesehen, Gebietszerlegung, Auftraggeber, Auftragnehmer,
Masterworker, Erzeuger, Verbraucher mit Puffer und Fließband mit
Puffern zwischen Stufen und Eigenfäden pro Stufe.
Das hatten wir schon in den Turfsmustern gesehen.
Es gibt noch andere Verfahren, z.B.
Parallelsteile und Herrsche.
Sie kennen ja Teile und Herrsche Verfahren, da sagt man, ich habe eine
große Aufgabe, die spalte ich in zwei und bearbeite die zwei
hintereinander.
Die Hälften kann ich noch in Viertel teilen und die Viertel nochmal
halbieren.
Im sequenziellen Fall geht man einfach so nach und nach diese Dinge
hintereinander durch.
Warum nicht gleichzeitig?
Dann kann man also aufteilen.
Die zwei Hälften können gleichzeitig bearbeitet werden, indem ich sie
wieder aufteile in vier und die Vierte dann mit vier Fäden
gleichzeitig durcharbeite.
Beim Rückkehren muss ich dann dafür sorgen, dass die vier Ergebnisse
wieder zusammengeführt werden.
Das ist dann meistens wieder ein sequenzieller Prozess, aber das geht
so.
Der gute alte Merge Sort würde so funktionieren.
Merge Sort sagt ja, aufteilen, die beiden Hälften sortieren, rekursiv
und dann was zurückkommt, ist beides schon aufsteigend sortiert, beide
Folgen.
Die muss ich jetzt noch verschmelzen, sodass ich die Gesamtfolge
mache.
Und das mache ich nicht nur auf der obersten Ebene, sondern auf
mehreren Ebenen.
Hängt natürlich an, wie viele Fäden ich habe.
Wenn ich eine Position erreiche, wo ich mehr Abschnitte habe, die für
sich sortiert werden müssen, als ich Fäden oder Prozessoren zur
Verfügung habe, hat es keinen Sinn, das nochmal parallel aufzuteilen.
Dann schalte ich um in einen sequenziellen Algorithmus.
Wir nehmen wieder Merge Sort, sie teilen auf in 2, dann teilen sie
nochmal auf in 4.
Bei 4 haben sie jetzt die Anzahl Fäden erreicht.
Die 4 Viertel werden alle von jeweils einem Faden sequenziell
sortiert.
Und dann werden sie wieder zusammengeführt, verschmolzen.
Und dieses Verschmelzen, da brauche ich jetzt entweder einen
sequenziellen Algorithmus, der durch zwei Folgen nach und nach durch
geht und immer den kleinsten herausholt und in die Zielfolge einsetzt.
Oder aber es gibt auch parallel Verschmelzungsverfahren, die bespreche
ich jetzt aber nicht.
Die sind recht kompliziert.
Dass wir also parallel teilen und herstellen.
Dann gibt es noch ein bekanntes Ding, das heißt Map Reduce.
Das ist aber nicht weiter kompliziert.
Map heißt, ich habe viele Datenelemente und auf all diesen
Datenelementen führe ich eine bestimmte Operationsfolge auf und das
mache ich gleichzeitig.
Im Internet.
Oder in meinem Firma oder in der Cloud oder sonst irgendwo, wo es
viele viele Rechner gibt.
Die führen also auf jedem Ding irgendwas aus, was immer es ist.
Zum Beispiel eine Suchoperation, gibt es da drin was, nachdem ich
suche.
Und das Reduce heißt dann, wenn ich jetzt 10.000 Fäden arbeiten lese,
muss ich natürlich das Gesamtergebnis zusammenführen.
Das ist der Reduce Schritt oder der Reduktionsschritt, der die
Ergebnisse dann zusammenfasst.
Wenn ich zum Beispiel an 10.000 Stellen etwas suche und ich habe an
mehreren hundert Stellen ein Ergebnis, dann liefern die alle ein
Ergebnis -Tupel zurück.
Diese Ergebnis-Tupel werden dann von weiteren Fäden zusammengefasst.
War für eine Weile das aller neueste und tollste.
Aber es ist auch nur ein Muster von vielen für Parallelisierung.
Wo können Sie jetzt mehr dazu lernen?
Natürlich bei mir, sonst hätte ich da nicht so lange drüber
gesprochen.
Es gibt gleich drei verschiedene Vorlesungen.
Das eine heißt Multikernrechner und Rechnerbündel, das andere heißt
Softwareentwicklung von modernen Parallelplattformen, Praxis der
Multikernprogrammierung, alles im Master.
Und können Sie allerdings auch schon im Bachelor zum Teil besuchen.
Je nachdem, wer das erlaubt, geht das gehen.
Multikernrechner und Rechnerbündel, der passt sich also mit den
Multikernern, wie wir sie hier gesehen haben, aber auch mit Cluster,
also mit Rechnern, die mit Kabel zusammengeschaltet sind und daher ein
Programmiermuster braucht, mit dem man Botschaften verschickt,
anstelle gemeinsamen Speichen zu haben.
Verbindungsnetze, Programmiermodelle dazu, Basistechniken für
Parallelalgorithmen, das kommt hier vor.
Das andere ist Softwareentwicklung von modernen Parallelplattformen,
Parallelentwurfsmuster werden da behandelt, aktuell
Parallelprogrammiersprachen und Bibliotheken, Übersetzerbautechnik für
Parallelität.
Kann ich zum Beispiel dem Übersetzer die Parallelisierung überlassen?
Könnte der das machen?
Die Antwort ist in manchen Fällen ja.
Und dann auch noch, was passiert eigentlich auf GPUs, wie werden die
programmiert?
Nur eine Vorlesung und dann gibt es noch die Praxis der
Multikernprogrammierung.
Da ist es jetzt so, dass hier die praktische Übung im Vordergrund
steht.
Es ist eine Mischung zwischen Vorlesungsanteil und Praktikumsanteil.
Auch hier lernen Sie Entwurfsmuster, Bibliotheken, Fehlersuche,
praktische Übungen und Fallstudien und die Benotung ist über die
Teilnahme an den praktischen Übungen nicht über eine Prüfung.
Aber es ist so, dass wir ein reines Praktikum damit nicht machen
können, weil man ja doch erst etwas lernen muss, bevor man eine
praktische Übung machen kann.
Da ist es immer so zweigeteilt.
Und dann gibt es noch eine ganz andere Vorlesung, die heißt empirische
Softwaretechnik.
Da untersucht man Methoden der Softwaretechnik auf ihre Effektivität.
Und das ist ein Gebiet der Softwaretechnik, das in den letzten 20
Jahren stark gewachsen ist, sodass alle heutigen neuen Methoden oder
Werkzeuge, die sich Leute ausdenken, sagen, ich baue da noch etwas in
Eclipse ein und ich habe da noch eine Fehlerfindungstechnik oder eine
Testtechnik, dass man wissen will, ob das wirklich eine Verbesserung
bringt.
Und das macht man mit Versuchen.
Und zwar entweder mit Versuchen mit menschlichen Teilnehmern Da
braucht man also Subjekte, die Programmieraufgaben lösen mit
unterschiedlichen Techniken und die vergleicht man dann in der
Geschwindigkeit oder in der Fehleranfälligkeit.
Oder man benutzt große Datenbanken von vorhandenen Projekten.
Zum Beispiel Quelloffene Softwareprojekte gibt es ja zu tausenden.
Und das ist eigentlich großer Datenschatz, den man untersuchen kann,
um festzustellen, zum Beispiel welche Eigenschaft von Software zu
häufigen Fehlern führt.
Aber das steht auf dem anderen Blatt.
Jedenfalls lernt man da auch sehr viel über statistische Auswertung
aber auch Techniken, wie sie in den Benutzerschnittstellen Bewertung
benutzt werden.
Auch da macht man ja Versuche, dass man sagt, warum sieht Word so
komisch aus, wie es aussieht?
Warum sind die Menüs so und so organisiert?
Nun, da haben die Leute von Microsoft in Reihenweise Versuche
durchgeführt, um festzustellen, was Benutzer am leichtesten für sie
verständlich finden.
Okay, das war jetzt die Übersicht.
Gibt es dazu noch Fragen?
Das hat mit KI zu tun, nämlich mit Fachverarbeitung der
Softwaretechnik.
Das ist auch noch ein interessantes Thema.
Aber das werde ich jetzt nicht behandeln.
Jetzt kommt noch ein ganz kurzes Kapitel.
Programmierrichtlinien sind nur acht Folien.
Das haben wir gleich abgehackt.
Programmierrichtlinien ist etwas, was Sie die ganze Zeit benutzen.
Zum Beispiel, wie man Klassen benennt und wie man Methoden benennt.
Und der Grund ist, dass man einen konsistenten Stil braucht.
Konsistentes Stil erleichtert die Lesbarkeit für Sie selbst, aber auch
für die Einarbeitung von anderen Personen, die irgendwann mal ihre
Software übernehmen und weiterentwickeln wollen oder einen Fehler
suchen oder sonst etwas damit anstellen.
Wenn da jeder seine eigene Einrückung, Warnungsgebung, Kommentierung
machen würde, dann habe ich damit ein Problem.
Wenn ich das einheitlich habe, dann ist es bei Personalwechsel und
Wiedereinarbeitung viel einfacher.
Auch Zeitersparnis beim Fehler finden.
Und für einen Profi, sage ich immer, im Gegensatz zu den vielen
Programmierern da draußen, die keinerlei Ausbildung in Informatik
haben, sondern sich selbst angearbeitet haben, sind Sie in der Wolle
gefärbte Informatiker.
Für Sie muss ein guter Stil auch Ehrensache sein.
Wir rotzen nicht irgendwas hin.
Das ist unser Hauptzweck.
Das machen wir gut.
Wir machen das nicht.
Auf die schnelle Tour, die dann Fehler enthält und schwer zu ändern
ist.
Also ein guter Stil ist in jedem Fall für einen Informatiker
Ehrensache.
Es muss konsistent eingehalten werden.
Und selbstverständlich macht man auch da manchmal unter Lauf einem
Nachlässigkeiten.
Deswegen gibt es später dann etwas, was wir noch besprechen werden,
nämlich Inspektionen und Durchsichten von Software.
Das heißt so, Sie haben was geschrieben, getestet oder auch
Formtesten, legen das Ihren Kollegen vor und die kritisieren das.
Suchen darin Fehler.
Und da ist einer der Fehler, nach dem gesucht wird, auch der
Programmierstil, den man hat, den man anwenden soll.
Also firmenweit oder zumindest abteilungsweit einen bestimmten
Programmierstil einhalten soll, damit jeder in der Abteilung mit
Software leichter zurechtkommt.
Aber man soll diese Stile nicht übertreiben, wenn es eben immer Fälle
gibt, wo sie nicht mehr so richtig anwendbar sind.
Dann kann man auch etwas anderes machen.
Jetzt vier Beispiele über den unterschiedlichen Stilrichtungen.
Die stammen jetzt aus C, sind natürlich auch in Java anwendbar.
Da gibt es also den K&R Stil.
K&R steht für Königin und Ritchie, das sind die Definierer von C.
Das sieht so aus, wie Sie es kennen, nämlich falls Sie eine If
-Bedingung haben, dann schreiben Sie geschweifte Klammer hier, dann
den Rumpf etwas eingerückt und dann die geschweifte Klammer außen.
Ja und?
Na ja, schauen Sie mal, es geht auch noch anders.
Sie können diese geschweifte Klammer mit dem Rumpf ausrichten und die
ebenfalls.
Das ist der sogenannte Whitesmith-Style.
Ein anderes Stil der Formatierung.
Dann gibt es den Allman-Stil nach dem Eric Allman, auch BSD, Berkeley
-Proctor -Distribution.
Das sieht so aus, dass die geschweifte Klammer nach außen rücken.
Also das ist sowas wie der Whitesmith-Stil mit den Klammern hier nach
außen.
Sieht so aus.
Und schließlich noch der GNU-Stil.
Der ist eine Mischung von beiden, erfordert aber, dass man zweimal
einrückt.
Also erstmal für die Klammern einrücken und dann nochmal den Rumpf
einrücken.
Braucht also mehr Platz nach rechts raus.
Oder gibt es eben jetzt eine Reihe von Stile, auch für die
unterschiedlichen Programmiersprachen, bespreche ich jetzt nicht, denn
was das Einrücken betrifft, kann das Eclipse ja schon.
Eclipse macht das sowieso für Sie schon gut, aber auch die anderen und
wenn man will, kann man das noch anpassen.
Es kommen noch ein paar Folien über diese Anpassung, aber die sparen
wir uns.
Das müssen Sie natürlich nicht lernen, sondern ich will nur zeigen,
dass Sie sowas machen können.
Sie können einen neuen Stil importieren oder einen neuen Stil
definieren und das Einrücken per Klick und Point und so weiter
einstellen.
Müssen wir jetzt aber nicht durchbesprechen.
Dazu gehören zum Programmierstil und das habe ich jetzt nicht mehr,
weil Sie das ja schon mit Falsch und Blut aufgenommen haben, wie man
Klassen benennt, also einen Nomen oder Nominalfrase im Singular, die
Methoden als eine Verbalfrase, die den Klassennamen nicht wiederholt,
zum Beispiel und so weiter.
Das wäre Programmierrichtlinien ganz kurz, damit Sie wissen, warum man
das macht.
Man macht das nicht, weil wir das so sagen, weil wir möchten, dass Sie
schön kommentieren, sondern weil Kommentare und Formatierung die
Softwarebearbeitung vereinfachen.
Das war ganz schnell, aber es gibt noch eines und das ist das
selbstkontrollierte Programmieren.
Das ist jetzt ein bisschen länger, aber nicht sehr viel.
Selbstkontrolliertes Programmieren.
Was ist darunter zu verstehen?
Bis jetzt haben Sie wahrscheinlich einfach vor sich hin programmiert
und gehofft, dass Sie noch rechtzeitig fertig werden und es dann
abgeben können.
Sie haben wohl noch nicht versucht, Ihre eigenen Fehler zu vermeiden,
in Zukunft zu vermeiden.
Und die Idee des selbstkontrollierten Programmierens ist genau das.
Sie sagen, Sie beobachten sich selbst, beobachten Ihre eigenen Fehler,
überlegen sich, wie Sie diese Fehler in Zukunft vermeiden wollen und
kontrollieren sich damit selbst und werden damit effizienter.
Zeigen, wie man das machen kann.
Sie brauchen gewissermaßen einen Katalog von Programmierregeln, die
Ihre eigene Fehleranfälligkeit reduziert.
Es sieht ungefähr so aus.
Sie haben eine Spezifikation, Sie programmieren, Sie bekommen ein
Programm raus, bekommen korrekte Ergebnisse, wunderbar.
In dem Fall, wo Sie einen Versagen oder einen Aussetzer haben, machen
Sie eine Fehleranalyse.
Sie machen die Fehleranalyse nicht nur so in der Form, dass Sie das
Programm selbst korrigieren, sondern Sie fragen sich, wie könnte ich
in Zukunft diesen Art von Fehler vermeiden.
Nehmen wir ein Beispiel.
Es passiert Ihnen öfters, dass Sie geschweifte Klammern nicht richtig
setzen.
Dass der Bereich für ein If oder ein While zu groß oder zu klein wird.
Oder Sie machen Fehler bei numerischen Berechnungen und
Rundungsfehler.
Ach, das habe ich doch schon immer so gemacht.
Oder es passiert Ihnen, dass Kommentare nicht abgeschlossen werden, zu
lange werden und damit der ganze Programmtext zum Kommentar wird, was
man natürlich sofort sieht.
Wie vermeide ich das?
Das ist meistens mit ganz einfachen Schritten zu vermeiden.
Man muss eben seine Aufmerksamkeit dorthin lenken.
Dann gibt es die Fehler wie um eins daneben.
Sie gehen durch ein Feld und vergessen das erste, das letzte oder das
erste oder gerade eins zu viel.
Sie haben einen Indexüberlauf, Indizierungsüberlauf, kriegen eine
Fehlermeldung.
Dann sagen Sie, das habe ich schon dreimal gehabt.
Das möchte ich jetzt mal vermeiden, dass mir das wieder passiert.
Was muss ich da tun?
Manchmal ist es nur so, dass Sie sagen, ich muss bei Schleifen besser
aufpassen.
Ich muss bei Schleifen besser aufpassen, sodass ich wirklich die
Grenzen der Felder richtig berücksichtige.
Indexfehler oder aber Sie haben einen Nullzeiger, die sollen Sie
dereferenzieren, kriegen einen Speicherfehler.
Dann sagen Sie, was muss ich machen, um diese Probleme zu beseitigen?
Da wäre zum Beispiel eins dabei, dass man sagt, immer initialisieren.
Wenn das geht, immer zu einer Initialisierung sorgen.
Was ja auch der Compiler haben will.
Dann gibt es das Problem mit den falschen Hypothesen.
Ich hoffe, Sie haben noch keine entwickelt, aber ich hatte schon
welche entwickelt.
Multiplikationen dauern wesentlich länger als Addition, gerade im
Gleitkommabereich.
Das ist heute vorbei.
Potenzieren ist aufwendiger, das ist geringfügig aufwendiger, aber
nicht mehr dramatisch.
Aber in der Vergangenheit hat man gesagt, das ist ein
Performancefehler.
Wenn ich potenziere, dann muss ich speziell berücksichtigen, wie ich
das Potenzieren schneller hinkriege.
Und dann sagt man, Caches sind sowieso unwichtig, das ist eine
Automatik, die macht alles richtig für Sie.
Wenn Sie etwas zugreifen, wird das ein Cache geben, bla bla bla.
Geht also schnell, muss man nicht berücksichtigen.
Ganz falsch.
Man muss Caches durchaus berücksichtigen.
Und ein Beispiel haben wir vorhin übersprungen, das war die
Matrizenmultiplikation.
Da kommt ein Beispiel vor, wo der naive Algorithmus, der das Cache
nicht berücksichtigt, deutlich langsamer ist im Faktor zwei oder so,
glaube ich, als einer, der über Caches Bescheid weiß.
Das zentrale Problem dabei ist, wenn man Caches benutzt und eine
Cachezeile in das Cache geladen wird, sagen wir mal, eine Zeile eines
Feldes, dann wird der Rest, ein Stück der Zeile eines Feldes, auch
mitgeladen.
Damit kann ich zahlenweise durch eine Matrize sehr schnell durchgehen,
weil mit dem Laden des ersten Elements gleich 10, 20 weitere geladen
werden.
Damit verliere ich keine Zeit.
Wenn Sie jetzt aber einen Algorithmus haben, der spaltenweise
durchgeht, durch eine Matrize spaltenweise, wie die
Matrizenmultiplikation vorkommt, dann vermeiden Sie gerade diesen
Vorteil des Caches, nämlich Sie nehmen die Spalte, holen sich also die
Spaltenzeile raus und dann gehen Sie schon zum nächsten Spalte, das
heißt, Sie müssen wieder ein Stück Zeile holen und wieder ein Stück
Zeile und wieder ein Stück Zeile und damit wird das Programm langsam.
Also Cache-Optimierungen können durchaus wichtig sein.
Und manchmal hat man so blöde Algorithmen, bei denen sich das
auftritt.
Dann gibt es Tücken der Maschinenarithmetik, die zu beachten sind.
Zum Beispiel, wenn Sie Gleitkommazahlen vergleichen, nie, nie, nie,
niemals mit Gleichheit, mit Missgleichheitszeichen, also gleich
gleich.
Der Grund ist, dass Gleitkommazahlen selbst wenn Sie meinen, sie sind
gleich, immer irgendwo ein bisschen abweichen.
Wenn Sie rechnen, wird es kaum mal vorkommen, dass Sie ein Ergebnis
bekommen, das wirklich null ist, wo alle Bits null sind.
Das hängt damit zusammen mit den Rundungsfehlern, die bei den
Rechnungen passieren.
Das heißt also, das ist der richtige Vergleich.
Sie ziehen A und B voneinander ab.
Sie wollen also A und B auf Gleichheit prüfen.
Das heißt, Sie nehmen den Absolutbetrag der Differenz und sehen nach,
ob das unter einer bestimmten Schranke ist von 10 hoch minus 9 oder 10
hoch minus 12.
Je nachdem, was Ihre Genauigkeitsanforderungen sind.
Weil es in den letzten Bits halt immer wieder einige gibt, die anders
sind.
Gerade bei 64 Bit Floating Point Zahl, da können Sie auf verschiedenen
Rechenwegen nie die gleiche Zahl bekommen.
Oder beim Aufsummieren von Summanden.
Manche Summanden sind vielleicht sehr, sehr klein.
Also addieren Sie die und das Ergebnis geht bei der Rundung verloren.
Weil Sie einfach weit draußen sind.
Während Sie sich aber in einer unterschiedlichen Reihenfolge gerechnet
hätten, dann hätten vielleicht manche der größeren Summanden nicht
mehr so zum Tragen weil sie durch einen anderen wieder weg subtrahiert
werden.
Hier kommt auch so ein Beispiel.
Fassen Sie sich mal diese beiden Gleitkommazahlen an.
1,23456789 und der ist 1,356780.
Also die unterscheiden sich nur in einer Ziffer.
Wenn diese beiden voneinander subtrahiert werden dann bekommt diese
Zahl heraus.
Nämlich 9 mal 10 hoch minus 8.
Das ist die Gleitkommazahl die durch Normalisierung entsteht.
Eigentlich sogar 0,9 mal 10 hoch minus 9.
Binaire Format.
Egal was ich damit sagen will, diese Zahl sieht aus als hätte sie 1
,23456789 signifikante Stellen.
Die korrekt wären.
Wir sind hier in diesem Fall in 0.
So sieht es nämlich aus.
Das ist aber nicht der Fall.
Denn wir wissen nicht was die richtigen Zahlen hier waren.
Die richtigen Ziffern.
Die sind durch Rundung verloren gegangen.
Durch ein Format das hier irgendwann mal abschneiden muss die Anzahl
der Bits die ich zur Darstellung brauche.
Und ich bekomme jetzt so eine Zahl raus.
Da stehen natürlich nicht nur dringend Nullen da.
Sondern irgendwelche anderen Ziffern da die durch weitere Rechnungen
entstanden sind.
Und sie meinen die sind alle exakt.
Sind aber nicht.
In diesem Fall ist genau eine Stelle richtig.
Der Rest ist alles Rauschen.
Die Nullen sind Rauschen.
Also da kann man auch auf die Nase fallen bei Gleitkommarechnungen
wenn man numerisch rechnet.
Diese Typen muss man kennen um die Fehler zu finden.
So.
Irreführende Namen.
Fallheitsnamens der falsche Semantik vortäuscht.
Oder Fallheitsnamen x1, x2, x3, x4.
Und daraus können sich fehlerhafte Annahmen ergeben.
Und damit interpretiert man das Programm verkehrt.
Oder unvorständige Bedingungen.
Man hat nicht alle Fälle berücksichtigt.
Komplexe, logische Bedingungen sind halt auch schwer aufzustellen.
Die Komplexität von Zusammenhängen wird nicht richtig erfasst.
Zum Beispiel Sie verwechseln globale Größen mit Hilfsgrößen die nur
einen Beitrag zu den globalen Größen reichen.
Oder Sie haben falsche oder initialisiert oder gar nicht
initialisiert.
Sie betrachten nur das was wichtig ist genau und das was so Nebenfälle
sind oder sicherheitsunkritisch ist.
Das wird irgendwie gelöst, aber nicht so genau wie der Normalfall, der
häufig auftretende Fall.
Damit bekommen Sie ein Programm, das abgestufte Qualität hat.
Manches ist gut.
Aber die Sonderfälle sind nicht gut durchdacht und führen dann
plötzlich zu Überraschungen.
Zu Fehlern, zu Sicherheitsproblemen.
Und dieser Dinge muss man sich bewusst sein, dass man das gerne macht.
Das ist ganz normal, dass Sie auf das Wichtige besonders Augenmerk
legen.
Aber es muss Ihnen klar sein, dass das Unwichtige auch berücksichtigt
werden muss und zwar mit der gleichen Sorgfalt.
Trügerische Redundanz tritt in vielen Fällen auf.
Machtloses Kopieren.
Es werden Strukturen geschaffen, die den menschlichen Denkapparat
überfordern.
Wir kopieren von da nach da und da nochmal und ein drittes Mal und ein
viertes Mal.
Und plötzlich ändert sich irgendwas, sodass alle diese Kopien gefunden
werden müssen und nachkorrigiert werden müssen.
Da wäre es viel besser gewesen, wenn Sie statt Copy&Paste eine neue
Methode erfunden hätten und mit Parametrisieren, dann müssen Sie nur
an einer Stelle ändern.
Was ich zu Programmieren gelernt habe, und das war nicht in C oder
sowas, sondern in Assembler, da war ich noch Schüler, da durfte ich
schon auf diesen großen alten Maschinen programmieren.
Was mich da am meisten beeindruckt hat, dass die Leute, die wirklich
gut programmieren konnten, unglaublich viele Unterprogramme erzeugt
haben und das jetzt in Assembler, das heißt also zwei Instruktionen in
Assembler sind ziemlich wenig, aber so ungefähr, wenn man eine
Handvoll Instruktionen hatte, die man an mehreren Stellen brauchte,
dann wurde schon eine Methode definiert.
Also in diesem Fall nicht Methode genannt, sondern Funktion.
Also achten Sie darauf, wenn Sie zwei Zeilen oder mehr wiederholt
gebraucht werden, machen Sie eine Methode draus.
Nicht lang zögern.
Anstelle, dass Sie es viermal kopieren, kopieren Sie es einmal, nehmen
den Methodenamen davor, Parameter dazu und schon haben Sie ein Problem
weniger.
Oder viele Probleme weniger.
So, das Lernen aus Fehlern ist jetzt wichtig, um Denkfallen zu
vermeiden.
Wie gesagt, wenn man sich darauf konzentriert, die eigenen Fehler zu
vermeiden, dann wird man besser und man wird schneller.
Dazu sollte man ein sogenanntes Fehlerbuch anlegen.
Und zwar, ich zeige Ihnen gleich, wie das aussieht.
Ein Fehlerbuch führen, das kann digital sein, das kann eine Excel
-Tabelle sein oder so etwas.
Ich zeige Ihnen gleich, was da interessant ist daran.
Das ist Zweck dazu, wenn ich einen Fehler hatte, der lange gedauert
hat, wenn ich ein Semikolon vergessen habe, das muss ich nicht in mein
Fehlerbuch reintun.
Aber wenn das lange gedauert hat zu lösen, das Problem lange
unentdeckt geblieben ist oder hohe Kosten verursacht hat.
Was mache ich dann?
Dann wollen Sie wissen, ob Sie solche Fehler wiederholt machen.
Ich mache das immer wieder.
Immer wieder mache ich bei einem Schleifen ein Problem.
Immer wieder bei einer numerischen Rechnung mache ich ein
Vergleichsproblem.
Da hat man also eine Programmierregel oder eine Gegenmaßnahme.
Es gibt ein ganzes Buch darüber.
Wenn Sie das interessiert, wie man seinen persönlichen Softwareprozess
optimiert.
Clean Coder, Clean Coder.
Da gibt es mehrere Bücher.
Aber wir schauen uns jetzt nur ein solches Fehlerlogbuch an.
Das könnte also so aussehen mit einem laufenden Nummer.
Entdeckung des Fehlers.
Ich falte jetzt gleich weiter, damit Sie es sehen.
Sie legen da ab.
Natürlich, wenn es passiert ist.
Das kann automatisch passieren mit dem geeigneten Ding.
Sie sagen, in welcher Phase in der Implementierung.
Das ist ein Implementierungsfehler, ein Toolsfehler, ein Fehler in der
Anforderung, ein Fehler im Betrieb usw.
Das können Sie ignorieren.
Das wäre also die Phase.
Sie schreiben den Fehlertyp.
Fehlertyp ist Dokumentation, Syntax, Bild, Zuweisung, Schnittstellen,
Prüfung, Daten usw.
Sie können Ihre eigenen Kategorien hinzufügen.
Fehlertyp, wo er herkam.
Wenn Sie in der Implementierung sind, könnte es aus der
Implementierung stammen, ist klar.
Könnte aber auch ein Fehler im Entwurf sein.
Und schließlich sagen Sie, ist es ein Folgefehler von etwas anderem,
das ich verkehrt gemacht habe.
Und eine Beschreibung dazu.
Diese Dinge sammle ich erstmal.
Wenn ich einen neuen eintrage, sage ich mir, habe ich diesen Typ von
Fehler schon mal gemacht und was könnte ich denn tun, um ihn in
Zukunft zu vermeiden.
Meistens sagen wir, ich muss bei Schleifen z.B.
einfach besser aufpassen.
Ich muss bei Initialisierung besser aufpassen.
Ich muss bei Vergleichen besser aufpassen.
So ungefähr sieht das dann aus.
Das wäre das Fehlerlogbuch gewesen.
Es gibt noch ein anderes, das Zeitlogbuch.
Da geht man her, das ist jetzt wirklich sehr detailliert, für
Zeiterfassung.
Wozu brauche ich das?
Sie brauchen jetzt natürlich noch keine Zeiterfassung.
Sie müssen nur sehen, dass Sie den Termin schaffen.
Und die Zeiterfassung ist wichtig.
Nummer 1 für die Abrechnung.
Nummer 2 ist für die Schätzung.
Sie erinnern sich, ich hatte am Anfang mal gesagt, wenn man ein
Projekt startet, dann würde man gerne wissen, wie viel es kosten wird.
Wie viel es kosten wird, hängt damit zusammen, wie lange ich brauchen
werde, um eine Software zu schreiben.
Und dafür haben Sie keinerlei Erfahrung.
Wie sammle ich die Erfahrung?
Indem ich ein Zeitlogbuch führe.
Um also bei der Schätzung genauer zu werden, so ein Zeitlogbuch sieht
ungefähr so aus.
Da ist der Anfang und der Ende, Unterbrechungen, von welcher Zeit,
verbrauchte Zeit, da schreibt man hier die Phasen dran und den Art von
Typ, den man gemacht hat.
Hier steht ein bisschen wenig, weil noch nichts über die Software
selbst dasteht.
Aber das müsste man noch hinzufügen.
Aber so müssen Sie es eigentlich gar nicht mehr machen.
Sie können das natürlich mit Tabellenkalkulation machen.
Da gibt es natürlich mehrere.
Aber Sie können es auch automatisch machen.
Da gibt es eben diese Timer, die Sie laufen lassen.
Sie sagen, ich drücke jetzt drauf, ich arbeite jetzt an dem, dem und
dem.
Wenn ein Telefonaufruf kommt, drücken Sie wieder drauf, dann wird die
Zeit unterbrochen.
Wir sprechen, machen weiter, drücken wieder drauf, damit kriegen Sie
diese Zeiterfassung hin.
Dann müssen Sie nur noch eintragen, an was Sie gearbeitet haben.
Und da erreichen Sie mit der Zeit eben auch eine bessere Möglichkeit
zu schätzen, wie lange Sie brauchen, indem Sie sich mal die Zeiten
vornehmen.
Wie lange brauche ich denn, um eine Methode zu schreiben, im Schnitt?
Was kostet es mich denn, eine Klasse mit fünf Methoden zu testen?
Wie lange brauche ich dazu, die Testfälle auszudenken?
Das kann ich dann aus diesen Daten ablesen.
Damit können Sie besser planen.
Wir geben Ihnen auch entweder ein Fehlerlogbuch oder ein Zeitlogbuch,
oder beides stellen wir Ihnen zur Verfügung, wenn Sie das benutzen
wollen.
Wie ich Ihnen sagte, ist vielleicht in Ihrem Studium noch nicht so
interessant, aber wenn Sie schon programmieren, könnten Sie zumindest
das Zeitlogbuch mitführen.
Damit Sie später mal besser sagen können, wie schnell Sie sind.
Unterbrechungen muss man natürlich abziehen davon.
So, jetzt haben wir noch eine Viertelstunde.
Gibt es noch Fragen?
So, jetzt ein bisschen entspannen, während ich umschalte.
So, jetzt kommt das nächste Kapitel.
Kapitel Testen und Prüfen.
Jetzt wird es wieder handgreiflich.
Also, wir sind jetzt mit unserem Wasserfallmodell hier, was nicht ganz
richtig ist, denn die Implementierung selbst hat ja auch einen
Testanteil.
In der Implementierung testen Sie ja die einzelnen Komponenten, das
heißt die einzelnen Klassen und Methoden.
Hier ist also schon ein Testanteil dabei.
Wo können Sie drüber lesen?
Was sollen Sie drüber lesen?
Das ist Kapitel 11 in Brücke.
Und nicht scheuen, einfach lesen.
Nicht lang rum tun.
Es ist leider so, dass Software-Artifakte immer Fehler enthalten.
Wir können sie offenbar sehr schwer perfekt machen.
Und das Problem ist, je später die Fehler auftreten, desto teurer sind
sie zu behandeln, zu korrigieren, denn dann befindet sich die Software
bereits im Betrieb.
Dann benutzen sie Leute schon.
Jetzt müssen sie dort aktualisieren, neue CDs schicken oder
übers Internet aktualisieren, was nicht sehr viel Zeit erfordert.
Aber es kann auch sein, dass dann Datenbestände konvertiert werden
müssen und dann wird es schon komplizierter.
Also, wenn Sie einen Anforderungsfehler haben, der übersetzt wurde in
funktionierenden Code und dann auch noch getestet wurde, und dann erst
stellen Sie fest, dass die Anforderung falsch war, da ist ein
ziemlicher Aufwand reingegangen, um etwas, was falsch war, von
vornherein falsch war, eben durch den ganzen Entwicklungszyklus
durchzuziehen.
Und das sollte man vermeiden.
Je später die Fehler gefunden werden...
Ziel ist es also, Fehler möglichst früh zu finden.
Allerdings ist jetzt etwas Wichtiges, was ich sagen muss, das ist in
diesem kleinen Zitat zusammengefasst von einem der Informatikpioniere,
Edgar Dijkstra, und er sagt, Testing shows the presence of bugs, but
not their absence.
Das heißt also, wir können nie sicher sein, den letzten Fehler
gefunden zu haben.
Egal, wie viel wir testen, es können sich immer noch Probleme
verbergen.
Wenn ein Fehler auftritt, dann wissen wir, dass es diesen Fehler gab,
aber wir wissen, wenn wir ihn korrigiert haben, nicht
notwendigerweise, dass sonst keiner da ist.
Das haben Sie sicher auch schon gemerkt.
Und warum können wir nicht alles testen?
Weil die Anzahl der Kombinationen der Eingabewerte gigantisch ist.
Auch nicht herstellbar.
Ein ganz einfaches Beispiel.
Angenommen, Sie wollten den Gleitkomma-Multiplizierer testen.
Das heißt, Sie brauchen 2 hoch 64 verschiedene Eingaben für den ersten
Operanten, 2 hoch 64 Eingaben für den zweiten Operanten, das sind 2
hoch 128.
2 hoch 128.
Verschiedene PID-Muster, um das vollständig zu testen.
Sie müssen dann auch noch wissen, was das richtige Ergebnis ist.
Für alle diese 2 hoch 128 PID-Muster.
Das alleine ist schon unmöglich in unserem Lebensdauer überhaupt zu
erledigen, denn 2 hoch 128, das dürfte etwa 10 hoch 80 sein.
Also so viele
Atome, wie es im Universum gibt.
Das ist nicht machbar.
Und das ist nur für 2 Zahlen.
Jetzt stellen Sie sich vor, Sie müssten einen Internet-Browser testen.
Unmöglich, alle möglichen Webseiten sich erstmal herzustellen.
Es sind so gigantisch viele, das ist völlig aussichtslos, dass Sie
alles durchtesten.
Wenn Sie absolute Korrektheit wollen, dann müssen Sie
Programmverifikationen benutzen.
Aber das werden wir leider in der Praxis nicht sehen, weil man da nur
in seltenen Fällen so kleine Programme hat, dass sie tatsächlich
formal bewiesen werden können, richtig zu sein.
Zweitens brauchen Sie dazu eine formale Spezifikation.
Dann können Sie eben sagen, das Programm erfüllt die Spezifikation
oder nicht.
Aber die Spezifikation selbst kann auch noch Fehler enthalten.
Also auch das gibt mir keine hundertprozentige Sicherheit.
Also gut.
Und jetzt stellt sich die Frage, wie viel soll ich testen?
Ihr Chef sagt zu Ihnen, haben Sie genügend getestet?
Dann sagen Sie, testing shows the presence of bugs, not their absence.
Dann sagt er, wie lange wollen Sie denn noch testen?
Dann muss ich noch eine Woche testen.
Nach einer Woche haben Sie immer noch Fehler gefunden und dürfen Sie
jetzt bitte schön aufhören.
Was ist ein vernünftiges Kriterium?
Wohlwissend, dass es noch weitere Fehler gibt.
Wenn ich dieses Kriterium erfüllt habe, dann habe ich wenigstens alles
mal probiert.
Jeden Codepfad irgendwann mal ausgeführt.
Vielleicht nicht wiederholt, nicht in allen Kombinationen, aber
wenigstens einmal.
Und das sind die sogenannten Testvollständigkeitskriterien oder
Testabdeckungskriterien.
Das Testvollständigkeitskriterium wird oft einfach nicht wahrgenommen
von Studenten, wenn ich so eine Frage stelle, wozu brauche ich denn
ein Testvollständigkeitskriterium?
Ein Testvollständigkeitskriterium sagt einfach, das ist ein Kriterium,
das sagt, jetzt darfst du zu testen aufhören, wenn du dieses Kriterium
erfüllt hast.
Und diese Kriterien werden wir uns demnächst genau vornehmen.
So, dann gibt es noch bestimmte Unterschiede bei den Verfahren.
Wir sprechen von testenden, verifizierenden und analysierenden
Verfahren.
Die testenden Verfahren, die suchen Fehler zu erkennen.
Wohlwissen, wir können sie nicht alle finden, immer in allen Fällen,
aber wir wollen Fehler damit erkennen, aber nicht notwendigerweise
oder wir können überhaupt nicht garantieren oder beweisen, dass keine
Fehler mehr da sind.
Wir wollen sie auch finden.
Das machen die testenden Verfahren.
Die verifizierenden Verfahren, die beweisen die Korrektheit auf
formalen Wege, mit einem formalen mathematischen Beweis.
Ist ein Thema für andere Vorlesungen, aber wird auch bei uns
sorgfältig und erforscht.
Und die analysierenden Verfahren sagen, geben wir Aussagen über ein
Programm.
Eigenschaften von Systemkomponenten und da sind natürlich dann
Eigenschaften von Interesse, die zu Fehlern führen können.
Die garantieren nicht, hier liegt ein Fehler vor, sondern sagt
lediglich, ich habe deine Software analysiert, da kommt folgendes
Problem vor, nämlich du benutzt Methoden, die sehr lang sind.
Methoden, die zwei Seiten lang sind.
Das ist ein Hinweis für nicht nur einen schlechten Programmierstil,
sondern auch eine Gefahrenquelle.
Oder man hat eine Methode, die sehr viele andere Methoden aufruft.
Das ist eine Gefahrenquelle, denn diese anderen Methoden könnten
falsch sein.
Schau dir mal diese Methode nochmal genauer an.
Plus die aufgerufenen, um sie genauer zu testen.
Vielleicht kommen da zusätzliche Fehler vor.
Das sind also die analysierenden Verfahren.
Die geben uns Tipps, aber keine Tipps auf Fehleranfälligkeit, aber
keine konkreten Fehler.
Die konkreten Fehler kommen aus den testenden Verfahren.
So, und jetzt habe ich von Fehlern gesprochen.
Fehler ist das Wort Fehler selbst.
Es ist ein sehr überladener Begriff.
Er bedeutet nämlich drei verschiedene Dinge, mindestens drei
verschiedene Dinge.
Zum einen bedeutet es ein Versagen oder ein Ausfall.
Sie führen also ihr Programm durch, aus, der Rechner führt es aus und
es tritt ein Fehler auf, sagt man.
Es tritt ein Fehler auf.
Das ist also ein Ereignis, um das von den anderen Fehlerarten zu
verunterscheiden, benutzen wir dazu das Wort Versagen oder Aussetzer
oder Ausfall.
Sager, Aussetzer, Ausfall.
Das ist ein Ereignis.
Ich lasse ein Programm laufen, es tritt ein Aussetzer auf.
Das Programm stürzt ab oder liefert falsches Ergebnis.
Das ist der Versager.
Ein Defekt ist die Stelle im Programm, die diesen Aussetzer oder
Versager verursacht.
Das ist also ein falsch formuliertes Programm, das zu einem Versagen
führen kann, aber nicht muss.
Deswegen ist es ja so, dass wir durch das Testen nicht alle Fehler
finden.
Der Defekt ist immer da, aber nur unter bestimmten glücklichen oder
unglücklichen Zuständen bekommen wir Eingaben, die gerade diesen
fehlerhaften Code ausführen und dann der Fehler sich auch noch zeigt
als Versager oder Ausfall.
Also wir unterscheiden Versager und Defekt und schließlich der Irrtum.
Auch das bezeichnet man oft als Fehler.
Der Irrtum ist derjenige, wo Sie sagen, da habe ich einen Fehler
gemacht.
Da habe ich einen Fehler gemacht, sagt man ja im Umgang sprachlich.
Gemeint ist damit, dass Sie ein Irrtum aufgesetzt sind oder einen
Herstellungsfehler begangen haben, der einen Defekt verursacht, eine
falsche Programmzeile und diese falsche Programmzeile führt
schließlich zu einem Versagen.
Drei verschiedene Typen von Fehlern.
Das ist ein Diagramm übrigens aus dem Brügge-Buch, der sagt, der
stellt diese Zusammenhänge als UML-Diagramm dar.
Sie sehen unten das Versager, Sie sehen den Defekt und den Irrtum.
Der Defekt verursacht den Versager, der Irrtum den Defekt.
Das haben wir ausführlich besprochen.
Ein Testfall findet einen Versager.
Ein Defekt wird korrigiert, durch eine Korrektur hier repariert.
Ein Testfall ist, das kennen Sie auch aus JUnit, Ausführen eines
vorhandenen Programms unter bekannten Umständen, nämlich mit bekannten
Eingaben und erwarteten Ergebnissen.
Das ist ein Testfall.
Er kann in Testfolgen oder Test-Suiten zusammengefasst werden.
Das ist auch UML.
Und schließlich, ein Testfall kann auch noch Testhelfer und
Testdreiber enthalten.
Testdreiber stoßen die Rechnung an.
Ein Testhelfer hilft mit dem Test zu überprüfen.
Testhelfer müssen wir uns gleich noch genauer anschauen.
Hier kommen die Testhelfer.
Stummel oder Stub oder sowas.
Dann haben wir Ertrappen und Nachahmungen.
Der Stummel ist eine unvorständige Implementierung.
In der Regel komplett leer.
Der Stummel sagt einfach, da wird diese Methode aufgerufen.
Ich habe sie noch nicht implementiert, also schreibe ich sie einfach
mal hin mit ihrem Namen und ihren Parametern.
Wenn sie aufgerufen wird, kann ich das Programm laufen lassen.
Es kommt kein Ergebnis dabei raus, aber es hilft mir wenigstens, dass
das übergeordnete Programm lauffähig ist und hoffentlich hängt es
jetzt nicht zu arg an dem Stummel-Ergebnis ab, damit ich schon mal
testen kann.
Natürlich Sachen, die dann in den Stummel erfordern, um einen Testfall
zu generieren, kann ich in diesem Fall nicht machen.
Nicht laufen lassen.
Eine Ertrappe
simuliert eine noch nicht vorhandene Komponente.
Sie tut so.
Sie könnte zum Beispiel immer das gleiche Ergebnis zurückliefern.
Oder sie hat einfach eine Tabelle und die Tabelle sagt, wenn diese
Eingabe, dann diese Antwort.
Aber sie rechnet nicht, weil sie noch nicht fertig ist.
Weil noch jemand dran arbeitet oder noch niemand dazugekommen ist.
Aber sie brauchen schon eine Ertrappe, die schon mal Ergebnisse
liefert, selbst wenn sie immer 42 zurückliefert, ist auch okay.
Unter Umständen kann das okay sein.
Eine Nachahmung ist ein bisschen mehr.
Die liefert schon etwas zurück.
Also es ist auch eine Ersatzimplementierung, aber sie liefert schon
etwas zurück, das brauchbar ist und das ich sogar einstellen kann.
Also zum Beispiel, angenommen, sie brauchen etwas, das auf einem
anderen Rechner läuft.
Eine Komponente, die auf einem anderen Rechner läuft.
Aber den anderen Rechner gibt es nicht oder die Komponente gibt es
noch nicht.
Also bauen Sie eine Nachahmung, die lokal läuft und lokal entweder
implementiert ist oder und das ist ein ganz großer Trick bei den
Nachahmungen.
In Nachahmungen können Sie für die Testfälle sagen, welche Ergebnisse
sie liefern sollen.
Was sagen Sie?
Sowas wie im Vorlauf des Testfalles, beim Aufbau des Testfalles, sagen
Sie ich sage jetzt der Nachahmung, dass sie mir die Werte x, y und z
zurückliefern soll, wenn sie gerufen wird.
Oder ich kann auch der Nachahmung noch sagen, dass sie die
aufgerufenen Werte überprüfen soll.
Ob die Werte, die reinkommen als Parameter, bestimmte Bedingungen
erfüllen.
Also die Nachahmung hat schon ein bisschen mehr Logik drin.
Benutze ich natürlich auch nicht mehr, sobald die echte Komponente
dafür vorhanden ist.
Dann kann ich das wahrscheinlich besser ausführen.
Genaueres dazu werden wir noch hören.
Und jetzt mache ich noch die letzte Folie, nämlich die Fehlerklassen.
Die Fehlerklassen unterscheidet man einfach da, wo sie herkommen.
Kommen Sie aus den Anforderungen, unverständlich, inkonsistent,
undurchführbar, einfach verkehrt, inkorrekt.
Kommen Sie aus dem Entwurf, dann liegen Sie defekt in der
Spezifikation.
Unverständliche oder fehlerhafte Umsetzung in Entwurfsmuster oder
Klassen, Inkonsistenzen zwischen Anforderung, Spezifikation und
Entwurf.
Gut, der Fehler wurde Entwurfsfehler begangen und schließlich der
Implementierungsfehler.
Das ist klar, den kennen Sie aus der Programmierung selbst.
Und da machen wir nächstes Mal weiter.
Dankeschön.