Probabilistisches Programmieren⌗

Beim ICCB versuchen wir, unter anderem, seit Jahren Programme wieder schneller zu machen. Programme die nur eine Liste anzeigen und dafür 3GB RAM und 20% der CPU verbrauchen sind uns ein Dorn im Auge. Viele unserer Posts haben bereits geholfen, Entwickler dazu zu bringen wieder qualitativ hochwertigen Code zu produzieren. Dabei konnten wir bereits zeigen, wie z.B. Unions helfen können den Speicherabdruck einer Anwendung zu reduzieren, oder wie der Stack helfen kann, Software auch auf modernen System noch laufbar zu machen.

Heute schlagen wir ein neues Konzept des Programmierens vor. Das Tolle an diesem Konzept ist, dass es sowohl als Erweiterung für Compiler integriert werden kann, als auch von Entwicklern direkt selbst umgesetzt werden kann: Probabilistisches Programmieren.

Was ist probabilistisches Programmieren?⌗

Nach der Analyse von tausenden, ja fast millionen von Programmen ist uns eine Sache ganz besonders aufgefallen: Sehr häufig werden Vergleiche getätigt, die absolut unwahrscheinlich sind und im Normalfall nie auftreten werden. Um das ganze Anschaulich zu machen, führen wir hier durch ein kleines Codebeispiel:

bool equalsInt(int32_t a, int32_t b) {
    return a == b;
}

Diese eine kleine Zeile Code kommt sehr harmlos vor: Jeder von uns hat sowas schonmal geschrieben! Und es ist ja auch noch absolut optimiert, ein equals sollte ja jeder Compiler schnell hinbekommen, oder?

Vielleicht ist dem intelligenten Zuschauer aber sofort eine Sache aufgefallen - hier werden absolut wahnwitzig ungleiche Vergleiche angestellt!

Ein int32_t kann über 4 Milliarden Werte darstellen! Um es genauer zu sagen sind es sogar 4.294.967.295. Und nur in genau einem einzigen Fall davon wird diese Funktion jemals true zurückgeben. Und dafür einen Vergleich von 32 Bits? Das ist doch wahnwitzig. Da ist es 30 mal wahrscheinlicher, den Jackpot im 6+Superzahl Lotto zu gewinnen! Warum verschwenden wir auf 1/4.294.967.295 = 0,00000002 % Wahrscheinlichkeit wertvolle Rechenzyklen? Vor allem, wenn in tausenden Programmen der Welt durch kosmische Strahlung entstehende Bitflips ignoriert werden, welche nach groben Schätzungen bei 20MB verwendetem RAM pro Minute etwa im 0,00018 % Bereich liegt?

Deswegen schlagen wir vom iccb vor, endlich auch als SoftwareentwicklerInnen auf die Mathematik, insbesondere die Wahrscheinlichkeitsrechnung zu hören und diesen Code (im besten Falle vollautomatisiert) umzuwandeln zu:

bool equalsInt(int32_t a, int32_t b) {
    return false; // correct in 4_294_967_294 out of 4_294_967_295 cases, 99.99999997671694% accuracy
}

Der Trick dabei: Es zwingt Entwickler auch automatisch, ein bisschen mitzudenken! Wenn man zum Beispiel nur 2 uint8_t vergleicht, ist es viel effizienter, den Vergleich tatsächlich durchzuführen. Deswegen sollte der Compiler Vergleiche mit kleinen Typen nicht automatisiert ersetzen. Allerdings muss die Grenze geschickt gesetzt werden. In ein int16_t passen schon 65535 Werte, da sind Vergleiche bereits nur noch mit 0,00152590218967 % Wahrscheinlichkeit korrekt. Wir empfehlen also, alle Vergleiche ab int16_t zu ersetzen.

An welchen weiteren Stellen kann diese Optimierung eingesetzt werden?⌗

Wir wissen, dass das hier nur ein Beispiel war. Also möchten wir noch ein paar weitere Stellen vorschlagen, an denen man probabilistisch optimieren kann.

Verkettete / verundete IFs⌗

Schauen wir uns kurz dieses kleine Beispiel an:

if (a == 3 && b == 5 && c == 7) {
    doSomething();
}

Da sich verkettete Wahrscheinlichkeiten multiplizieren wird dieses if nur in sehr wenigen Fällen eintreten. Die Wahrscheinlichkeit dafür setzt sich, falls a,b und c uint8_t sind wie folgt zusammen: 1/256 * 1/256 * 1/256 = 0,0000000596046447754. Diese Wahrscheinlichkeit ist absolut minimal, so kann der Compiler diesen kompletten Branch getrost ignorieren und wegoptimieren. Er ist, wie es im Fachjargon genannt wird, quasi-deadcode.

String Vergleiche⌗

Jede(r) EntwicklerIn, der oder die weiß wie Strings unter der Haube aufgebaut sind, weiß, dass es sich nur um ein Array aus uint8_t handelt. Daher fällt bei Stringvergleichen die selbe Mathematik an wie gerade bei den verketteten ifs:

if (strcmp("HELLO", b)) {}

Kann man diese Zeile nun wegoptimieren? Vielleicht! Vielleicht aber auch nicht. Hier kommt es darauf an, ob der vorgegebene Text nur die 26 Zeichen des Alphabets beinhalten kann oder nicht. Denn der Unterschied ist mathematisch drastisch.

Wenn man vom kompletten ASCII Alphabet ausgeht berechnet sich die Wahrscheinlichkeit für gleiche Texte hier wie folgt: 1/255 * 1/255 * 1/255 * 1/255 * 1/255

Wenn man nur von dem 26 Zeichen Alphabet ausgeht, kommt man auf folgende, viel größere, Wahrscheinlichkeit: 1/26 * 1/26 * 1/26 * 1/26 * 1/26

Wir empfehlen daher um strcmp einen Wrapper zu machen:

uint8_t efficientStrcmp(char* str1, char* str2, german_alphabet: bool){
    if (german_alphabet) {
        return strcmp(str1, str2);
    }
    return false;
}

Floating Point⌗

Schon in frühen Vorlesungen oder Tutorials wird jede(r/m) EntwicklerIn beigebracht, dass man 2 Floating Point Werte nicht direkt mit == vergleichen soll, sondern immer a-b < epsilon machen soll. Auch diese Vergleiche kann man sich probabilistisch vollkommen sparen, wenn epsilon klein sein soll. Gerade hier rentiert sich die Optimierung besonders, da floating Point Berechnung die CPU sehr viel extremer auslastet als einfache integer Vergleiche.

Fazit⌗

Wir vom ICCB empfehlen hier ein neues Programierparadigma, “probabilistiches Programmieren” zusammen mit der Compileroptimierung “quasi-deadcode elimination” um Programme endlich wieder schnell zu machen. CPUs stecken quasi durchgehend in Branching Entscheidungen fest, die man mit der empfohlenen Methode effektiv reduzieren kann. Wir zeigen auf, dass die Wahrscheinlichkeit, dass ein Programm durch einen Bitflip durch Weltraumstrahlung stochastisch viel häufiger (0,00018 %) fehlerhaftes Verhalten zeigt als durch ignorierte Integer Vergleiche (0,00000002 %).

Kennt ihr noch weitere Stellen, an denen durch probabilistisches Programmieren wertvolle CPU Zyklen gespart werden können? Denkt darüber nach und stellt eure Businessanwendungen schnellstens um!