Millibytes

Wir lernen alle paar Monate oder mindestens alle paar Jahre neue Begriffe wie Kilobyte, Megabyte, Gigabyte, Terabyte, Petabyte und Exabyte kennen. Man muss immer aufpassen, weil damit die Potenzen von 1024 oder die von 1000 gemeint sein können. 1024 ist praktischer in der Informatik, aber 1000 ist praktischer für Anbieter von Festplatten, weil sie dann ein eindrucksvolleres Schild auf die Ware kleben können, ohne sehr unehrlich zu sein. Und bei Terabytes macht der Unterschied schon etwa 10% aus und es wird mehr wenn wir Exabytes oder Hepabytes oder Okabytes oder was auch immer man da erfinden wird, verwenden. Im Moment betrifft das Problem nur große Firmen wie Google und Google achtet bei der Einstellung von neuen Mitarbeitern sehr auf ein gewisses Mindestniveau, so dass sie nicht gefährdet sind, sich beim Festplattenhersteller wegen dieser 10-20% über den Tisch ziehen zu lassen.

Aber wie sieht es aus mit Millibytes? Das klingt komisch. Kleiner als ein Byte geht nicht, außer man überlegt etwas länger und kommt darauf, dass es noch Bits gibt, also Achtelbytes. Jedes Bit ist eine Antwort auf eine Frage, die nur mit Ja oder Nein beantwortet werden kann. Ein kleiner Nebenaspekt kommt mit Binärdaten ins Spiel. Diese sind üblicherweise als eine Sequenz von Bytes dargestellt. In Wirklichkeit sollte es eine Sequenz von Bits sein, das heißt, wir sollten genaugenommen beim letzten Byte wissen, welche Bits noch dazugehören und welche nur Füllbits sind, die wir ignorieren müssen. Das lässt sich durch entsprechende Binärformate in den Griff bekommen, wenn man angibt, wieviele Bits die Daten lang sind und dann die Bytes folgen.

Aber gibt es halbe Bits? Oder Millibits? So absurd ist die Idee nicht. Wenn wir eine Netzwerkverbindung haben, die absolut zuverlässig funktioniert, dann ist ein Bit das ankommt definitiv dasselbe wie das, was reingeschickt wurde. Es enthält also den Gegenwert von einem Bit Information darüber, was eingegeben wurde. Wenn der Kanal nun gar nicht funktioniert und zufällige Bits rauskommen, ist deren Informationsgehalt 0. Man erfährt gar nichts darüber, was gesendet wurde. Typische Verbindungen liegen irgendwo dazwischen. Das Bit was rauskommt, hat also etwas mit dem was reingesteckt wurde, zu tun, ist aber nicht 100% zuverlässig. Mit fehlerkorrigierenden Codes kann man die Zuverlässigkeit auf Kosten der Kapazität steigern. Analysiert man die ganze Situation, stellt man fest, dass ein physikalisch empfangenes Bit weniger als ein Bit Information bringt. Man braucht im Durchschnitt etwas mehr als ein übertragenes Bit, um ein Bit wirkliche Information von der Quelle wirklich mit einer gewünschten Zuverlässigkeit zu ermitteln. Die Zuverlässigkeit wird nie 100% erreichen, aber theoretisch 99.9999% mit so vielen Neunen wie man will. Am Ende des Tages bringt uns ein Bit, das physikalisch übertragen wird, also durchschnittlich nur 0.7, 0.95 oder 0.00012 Bits tatsächliche Information, weil es im Kontext der Fehlerkorrektur mit anderen Bits kombiniert werden muss. Und das sind dann 700, 950 oder 0.12 Millibits bzw. 87.5, 118.75 oder 0.015 Millibytes. Die Diskussion wegen 1024 und 1000 ist auch hier relevant, aber ich überlasse sie gerne den Lesern…

Share Button

Flashsort in Ruby

Es gibt auf github eine einfache Implementierung von Flashsort in Ruby, nachdem hier auf github schon eine Implementierung in C zu finden ist. Die C-Implementierung ist typischerweise schneller als die libc-Funktion qsort, aber letztlich hängt das von den Daten ab und davon, wie gut die metric-Funktion ist, die man zusätzlich zur Vergleichsfunktion bei Flashsort liefern muss. Man kann sich diese metric-Funktion als eine Art monotone Hashfunktion vorstellen, also gilt

    \[\bigwedge_{a,b: a\le b} m(a) \le m(b) \]

Diese zusätzlich benötigte Funktion oder Methode ist nicht wirklich vorhanden, außer bei numerischen Werten, was den Einsatz von Flashsort etwas erschwert. Entscheidend für eine gute Performance ist eine gute metric-Funktion, allerdings sind bei typischen Text-Dateien schon ziemlich triviale Implementierungen ganz brauchbar.

In diesem Blogbeitrag sind weitere Sortieralgorithmen für Ruby gezeigt.

Share Button

Advanced Akka

In der vergangenen Wochenende hat sich die Möglichkeit ergeben, an der Type-Safe-Schulung über „Advanced Akka“ teilzunehmen. Akka ist ein Framework zur Parallelisierung und Verteilung von Verabeitungsoperationen einer größeren Applikation, das auf Scala basiert. Akka ist selbst in Scala geschrieben, aber es wurde darauf geachtet, dass es auch mit Java benutzbar ist. Unabhängig von der konkreten Implementierung ist es aber auch konzeptionell interessant, weil Akka Ideen umsetzt, wie man massiv parallele Applikationen entwickeln kann. Erlang, LFE und Elixir verwenden zum Beispiel ähnliche Konzepte, vielleicht noch etwas radikaler, während Scala ja einen „sanften“ Übergang zur funktionalen Welt ermöglichen soll, ähnlich wie C++ für den Einstieg in die Objektorientierung von ein paar Jahren.

Im Fall, dass man Akka verteilt betreibt, sind natürlich wieder die Serialisierungsmechanismen interessant. Man sollte das berücksichtigen und zumindest nicht zu feingranulare Zugriffe über das Netzwerk verteilt durchführen, wenn die Parallelisierung eine hohe Performance bieten soll.

Share Button

Systemprogrammierung für Posix und Win32

Systemprogrammierung macht man in beiden Fällen mit C, da sollte es einige Ähnlichkeiten zwischen den Systemen geben und wenn man genau schaut, sieht man die auch. Aber auf den ersten Blick sehen die entsprechenden C-Programme sehr verschieden aus. Das überrascht nun wieder, da doch eigentlich mit der Programmiersprache C auch die libc standardisiert ist und das sogar einigermaßen eingehalten wird. Leider ist die libc gerade im betriebssystemnahen Bereich mehr oder weniger auf die Schnittmenge vieler Systeme zugeschnitten und stellt einiges an Funktionalität der darunter liegenden Betriebsysteme nicht zur Verfügung. So kann man vieles generisch programmieren, aber es gibt doch immer wieder Bereiche, in denen es vorteilhaft oder sogar fast zwingend notwendig ist, eine betriebssystemspezifische Implementierung zu wählen.

Rein optisch sieht man den Unterschied sofort. Die typischen Win32/Win64-Programme verwenden schon Funtionsnamen mit Camel-Case und großen Anfangsbuchstaben und bevorzugt sehr lange Namen für Funktionen, Variablen, Konstanten und Macros und sehr lange Parameterlisten. So werden die MS-Windowsprogramm lang, aber man kann wenigstens oft sehen, was in etwa gemeint ist. Letztlich muss man aber die Konzepte verstanden haben und Zugriff auf eine Funktions- und API-Referenz haben, ob das nun Man-Pages oder die Webseite einer großen Firma ist, ist sekundär. Eigentlich ist dieser Unterschied auch nicht so wichtig, weil man sich an andere Schreibweisen für die konzeptionell gleiche Sache schnell gewöhnen kann. Ärgerlich ist nur, dass man wirklich alles zweimal schreiben muss. In der Praxis wird man vielleicht die I/O- und IPC-Funktionalität, die die Software benötigt, an der man arbeitet, in einer oder mehreren Bibliotheken behandeln, wohlgemerkt spezifisch das, was man braucht und nicht eine generische Verallgemeinerung beider APIs, die nie fertig und nie richtig gut wird. Die restliche Programmlogik kann man vielleicht generisch gestalten.

Es gibt auch Möglichkeiten, unter MS-Windows mehr oder wenigeer viele der unter Posix (Linux, Unix, MacOSX, etc.) bekannten Funktionen unter MS-Windows zu benutzen. Mit cygwin bekommt man die meisten, das ist sozusagen so eine generische Schicht, aber auch die nativen Win32/Win64-Bibliothken enthalten oft über das geforderte Minimum hinaus Funktionen, die so typischerweise unter Posix üblich sind, z.B. open(), close(), read() und write().

Möglichkeiten zur Generierung von Nebenläufigkeit mit Prozessen und Threads sind in beiden Systemen vorhanden, aber auch hier mit subtilen semantischen Unterschieden, die es einem schwer machen können. Interprozesskommunikation haben beide Systeme und man kann natürlich auch recht vie l mit TCP/IP-lösen, was dann generisch ist.
Die bekannte Thematik mit „/“ vs. „\“ als Datei-Pfad-Trennzeichen kann man dagegen leicht lösen, indem man konsequent „/“ verwendet. Das verstehen die Win32- und Win64-API-Funktionen gut.

Die leidige Problematik mit den Zeilenwecheln mit ctrl-M ctrl-J vs nur Ctrl-J ist auch nicht so schlimm, wie man meint. Man kann eine Datei unter MS-Windows binär anlegen und dann wird das Ctrl-M nicht eingefügt. Und über weite Strecken werden beide Konventionen auf beiden Systemen problemlos verstanden und können entsprechend eingesetzt werden. Sinnvoll ist nur, dass man das definiert und sich auf einen Weg einigt.

Share Button

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