Søren in Norwegen

Freitags versuche ich immer ein Flash T-Shirt anzuziehen. Aus Prinzip und weil’s mein Lieblingssuperheld ist.
Dies im Speziellen hat nur aeuszerst periphaer mit dem Thema dieses Artikels zu tun: „Das dauert mir zu lange! Das muss doch schneller gehen!“ … Aber i.A. passt das schon … … … wobei „aueszerst peripher“ sinnlos ist, denn die Peripherie ist ja schon der aeuszere Rand einer Zone.

Ein ganz anderer Anfang: heute plaudere ich mal etwas aus dem Naehkaestchen und versuche mehrere Wochen des freudigen Programmierens und Problemløsens in nur diesen einen Beitrag zu packen, ohne all zu technisch zu werden.

Die neulich beschriebene Idee, das Kevin-Bacon-Problem in Vektoren zu fassen, ist streng genommen nicht nøtig um das Linknetzwerk zu durchschreiten. Es reicht vøllig, dass das alles in den Speicher passt und dann kann man (wie im verlinkten Artikel gesagt) mittels Fallunterscheidungen schon ’ne ganze Menge machen.

Nachdem ich die Titel zu Zahlen transformiert hatte, habe ich einen derartigen Algorithmus mal schnell implementiert um zu sehen, wie lange der denn braucht … und der brauchte so ca. 53 Jahre!

Wait! What!? Wenn ich mich richtig erinnere, dann hatte der Code noch nicht mal alle Analyseteile, welche noch mehr Zeit benøtigt haetten.
Dies war natuerlich zu viel und ich musste eine (mathematische) Løsung finden, welche dann hoffentlich nicht so viel Zeit braucht. Das ist das, was ich beim letzten Mal beschrieb.
Dieser „Vektorcode“, brauchte in Python 3.7.3 ca. vier Minuten um das Linknetzwerk einer Seite zu analysieren. Das war zwar besser, aber fuer alle ca. 6 Millionen Seiten waeren das immer noch 45 Jahre, die mein Rechner durchgehend haette laufen muessen. … Verdammt!

Da daemmerte mir, dass ich wohl nicht umhin komme, dass ganze in C zu schreiben.
Davor versuche ich mich immer zu druecken. Der Grund ist (wie an anderer Stelle bereits (indirekt) erwaehnt), dass ich mich da um grundlegende Sachen wie Speicherverwaltung selber kuemmern muss. Und wenn da was schief geht, dann bekomme ich das mitunter gar nicht mit, weil ich keine Ahnung von C habe.

Hinzu kam, dass die aeuszerste Ordnungsstruktur, das Lexikon (das „Dictionary“ oder die „Lokomotive“ (wie ich es an anderer Stelle nenne), welche die vielen „Waggons“ mit den ganzen Links „zieht“) in der Form gar nicht existiert in C. Zumindest nicht in der einfach zu verstehenden, einfach zu handhabenden und vielseitig anwendbaren Form wie in Python.
Und das ist ein riesiges Problem, denn auf jedem Linklevel, muss ich in besagtem Lexikon tausend-, millionen-, ja fast zweihundertmillionenmal nachschauen welcher Titel welche Links (die „Ausgaenge“ zum naechsten Linklevel) hat. Und das ganze dann noch mal ca. 6 Millionen Titel.
Deswegen muss so ein Lexikon effizient und gut in the gesamte Sprache integriert sein. Ich meine tatsaechlich die Programmiersprache an sich (und Dictionaries sind extrem gut in Python integriert), denn hierbei wird verdammt gute Speicherverwaltung benøtigt!

Zum Glueck hatte ich schonmal was von Hashtabellen gehørt. Hashtabellen sind sowas wie ein Lexikon — ein „Ausgangswert“ (hier die Titel) wird irgendwas zugeordnet. Dabei kann es aber zu sogenannten Kollisionen kommen. Das waren dann bei ein und demselben Ausgangswert mehrere Zuordnungen. Beim Lexikon nehme man das Wort „Wurzel“. Das kønnte die Wurzel einer Pflanze sein oder die Wurzel einer Zahl.
Hashtabellen løsen dieses Problem (muessen sie ja, denn ansonsten wuerden sie nicht benutzt werden) aber Kollisionsvermeidung fuehrt dazu, dass der Zugriff in Hashtabellen unter Umstaenden sehr langsam sein kann. Das ist ein riesiges Problem denn, wie bereits erwaehnt, muss ich urst oft in dieser Hashtabelle nachschlagen.
Vor allen Dingen ist die zeitraubende Kollisionsvermeidung ein unnøtiger Prozess in meinem Fall, weil ich nach der „Verzahlung“ eindeutige „Ausgangswerte“ habe und es niemals zu Kollisionen kommen kann.

Dazu kam, dass es auch solche Hashtabellen nicht „fertig aus der Tuete“ in C gibt und ich das selber programmieren musste.
Aber die 45 Jahre Laufzeit waren mir zu viel. Und deswegen machte ich mich auf, mir das Ganze mal anzuschauen. Zunaechst etwas zøgerlich, ja gar etwas aengstlich, aber dann immer enthusiastischer. Ich fand ein paar extrem gute Erklaerungen im Netz und die dortigen Løsungen schaffte ich fuer mein Problem zu modifizieren. Das war spannend!

Dann implementierte ich den beim letzten Mal vorgestellten Vektoralgorithmus und das ging ganz toll. Anstatt ca. 4 Minuten pro Titel brauchte ich nur noch 3.2 Sekunden (! … !!! … !!!einseinself) pro Titel … wait! WHAT?! … Anstatt 45 Jahre wuerde ich fuer alle ca. 6 Millionen Titel dann nur noch ca. 7 Monate brauchen!

JIPPIE!!!!! Damit wurde das Projekt ganz konkret durchfuehrbar.

Nun war besagte Zeit aber immer noch ohne die eigentliche Analyse.
Doch dann erinnerte ich mich, dass Computer heutzutage ja Mehrkernprozessoren haben, von denen meistens nur einer ausgelastet ist und der Rest Pause macht. Und die Macht dieser restlichen Kerne wollte ich auch nutzen. Das Ganze kønnte man auf deutsch „simultaner Mehrfadenbetrieb“ nennen, aber ich denke nicht, dass das irgendwer sagt. Deswegen benutze ich den englischen Begriff multithreading.
Wusste ich wie das zu programmieren ist? Die Antwort ist ein klares „Nein“. Aber das war super interessant und zunaechst etwas zøgerlich, ja gar etwas aengstlich, aber dann immer enthusiastischer machte ich mich daran die technische Seite des multithreading besser zu verstehen und zu implementieren.

Das hørt sich jetzt komplizierter an als es ist. Beim multithreading ist es eigentlich nur so, dass der Computer auf Kern #1 das Linknetzwerk von Titel 516 (als Beispiel) durchsucht, auf Kern #2 das von Titel 517, auf Kern #3 das von Titel 518 usw.
Dabei muss man im Wesentlichen darauf achten, dass bestimmte Ressourcen von allen „Threads“ benutzt werden. Beim Lesen ist das nicht so tragisch, da kann der Thread auf Kern #2 warten bis der Thread auf Kern #1 fertig ist. Beim Schreiben ist das aber von ganz erheblicher Bedeutung. Klar, wird da auch gewartet, aber der thread auf Kern #2 kønnte Information ueberschreiben, die der Thread auf Kern #1 (oder Kern #3 usw.) noch braucht.
Das wird oft dadurch geløst, dass man schaut welche Ressource gerade von welchem Thread „in Benutzung“ ist und die darf dann von keinem anderen Thread „angefasst“ werden. Das ist aber URST krass zeitraubend, weil dann ja wieder alle Prozessoren Pause machen bis die Ressource frei ist. Deswegen musste ich die Teile des Vektoralgorithmus welche von allen Threads benutzt werden auf andere weise „threadsicher“ machen. Die Løsung war, dass jeder Thread seine eigenen Vektoren bekommt und dann war es technisch nur noch eine kleine Herausforderung, dass die Zuteilung der Vektoren zu den richtigen Threads automatisch geschieht (weil das ja ca. 6 Millionen mal gemacht werden muss).

Lange Rede kurzer Sinn, nach der Hashtabelle implementierte ich dann das multithreading.
Nun ist es aber so, dass multithreading extra „Betriebskosten“ (diesmal nicht in Form von Speicher aber in Form von Prozessorzyklen und damit „Rechenzeit“) verursacht. Threadsicherheit ist der Teil der Kosten ueber den ich Kontrolle hatte. Das allermeiste geschieht intern und ich habe absolut keine Ahnung, was das alles ist.
Jedenfalls fuehrt das dazu, dass man die Zeit mit zwei Kernen nicht einfach nur halbieren kann. Aber bei 2 Kernen brauchte ich nur noch 2.8 Sekunden pro Titel. Und mit drei Kernen gar nur 2.2 Sekunden pro Titel. Die Benutzung von 4 Kernen bringt keine weitere Verbesserung, machte meinen Rechner aber urst traege. Das lag natuerlich daran, dass ich nur 4 Kerne habe und auf einem muss ja auch das Betriebssystem laufen.
Drei Theads, und ca. 5 Monate Rechenzeit, sollen es also sein.

Danach „stolperte“ ich ueber eine Kuriositaet, die ich mir nicht erklaeren kann. Dafuer muss ich aber etwas ausholen.

Die Werte der einzelnen Elemente in den Vektoren sind ja nur Null und Eins, nix anderes. Aber soweit habe ich den Algorithmus derart implementiert, dass ich diese als eben das — richtige Zahlen — ansehe, die auch den Wert 23517 annehmen kønnten. Damit folgen die mehrere Bytes Speicherbedarf „richtiger“ Zahlen. Weil es aber nur Nullen und Einsen sind, kønnte der Datentyp (und damit die „Betriebskosten“) dieser Werte auch anders sein.

Also spielte ich mal mit ein paar anderen Datentypen herum und es stellte sich dann heraus, dass ich mit der Verwendung des Datentyps char die Rechenzeit auf nur 1.5 Sekunden pro Titel reduzieren konnte. Das entspricht ein bisschen weniger als ca. 3 1/2 Monate fuer die komplette Wikipedia.
Der Nachteil von char ist, dass da dann halt nur kleine Zahlen rein passen, die nicht mehr als dieses eine Byte brauchen. Zum Glueck sind Null und Eins so klein, dass es kleiner nicht geht.

Superduper … doch dann ging mir auf, dass ich die Analyse der Linklevel ja noch gar nicht implementiert hatte. Das ging aber schnell reinzuhacken und die benøtigte Zeit erhøhte sich (bei der Verwendung von char und drei Threads) um nur 0.15 Sekunden pro Titel. Selbst bei fast 6 Millionen Titeln verlaengerte sich damit die erwartete Gesamtrechenzeit auf nur etwas mehr als ca. 3 1/2 Monate.

Lange Rede kurzer Sinn: nach einigen Wochen hatte ich es nicht nur geschafft die technische Løsung des Kevin-Bacon-Problems ganz konkret in Code zu fassen, sondern ich konnte durch gezielte „Tricks und Kniffe“ die Gesamtrechenzeit von urspruenglich ca. 50 Jahren auf nur 3 1/2 Monate reduzieren.

Da fuehlte ich mich ungefaehr so:

URST! KRASS! … WIE TOLL DOCH ICH BIN! … wa! … Es gibt nichts was ich nicht kann … ICH … BIN … GOTT!

Und deswegen wollte ich das hier mal (trotz der Laenge) wenigstens in der kuerzest møglichen Form mit so wenigen (konkret) technischen Ausfuehrungen wie møglich, hingeschrieben haben.

Dreieinhalbe Monate also. Sagen wir vier, vielleicht fuenf, denn es kønnte ja mittendrin was schief gehen und dann muss ich Teile nochmal machen.

… … … aber Moment … im Buero stehen doch zwei Rechner rum, die sonst nix zu tun haben … … …

… … … hmmmmmmmm … … …

… … … hmmmm hmmmm hmmmm … … …

… … … ca. 7 Wochen spaeter … … …

Die Ergebnisse sind hier!

Aber dazu mehr ab dem naechsten Mal.